CODICE 65896 ANNO ACCADEMICO 2020/2021 CFU 9 cfu anno 3 INGEGNERIA INFORMATICA 8719 (L-8) - GENOVA SETTORE SCIENTIFICO DISCIPLINARE ING-INF/05 LINGUA Italiano SEDE GENOVA PERIODO 1° Semestre MATERIALE DIDATTICO AULAWEB PRESENTAZIONE Il corso si propone di introdurre lo studente alla progettazione e all'analisi degli algoritmi. Mediante la presentazione delle principali strutture dati e degli algoritmi ad essi relative lo studente maturerà la comprensione del funzionamento degli algoritmi e delle principali tecniche ad essi collegate. OBIETTIVI E CONTENUTI OBIETTIVI FORMATIVI Il corso introduce le principali strategie di progettazione di algoritmi e gli strumenti per valutarne la correttezza e le prestazioni. L'obiettivo è lo sviluppo della capacità di formalizzare e risolvere problemi per via algoritmica, e della capacità di analisi e valutazione delle soluzioni. OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO Il corso introduce le principali strategie di progettazione di algoritmi: Forza Bruta: soluzione del problema a partire dalla sua definizione formale Dividi e Conquista: approccio che prevede il frazionamento in sottoproblemi (solitamente di eguale diimensione) e la ricombinazione delle soluzionie parziali Diminuisci e Conquista: soluzione del problema mediante riduzione iterativa delle dimensioni (di una costante, di un fattore costante o di un fattore variabile) Trasforma e Conquista: approccio che prevede la riformulazione del problema in modo da semplificarne la soluzione Compremesso Spazio-Tempo: incremento delle prestazioni per lo svolgimento di operazioni mediante utilizzo di overhead in termini di memoria Algoritmi Golosi: strumenti di ottimizzazione combinatoria che prevedono l'utilizzo di strategia "greedy" (scelte localmente ottime si rivelano anche globalmente tali) Complessivamente, l'obiettivo è quello di realizzare una buona conoscenza dei principali algoritmi facenti parte di ogni famiglia, avente come risultato la capacità di impostare la soluzione a problemi computazionali per via algoritmica e analizzarne la correttezza e la complessità per via analitica o empirica. PREREQUISITI E' richiesta una buona conoscenza di almeno un linguaggio di programmazione, preferibilmente della famiglia C/C++/Java. Conoscenze preliminari di calcolo combinatorico, algebra e informatica teorica sono utili per una migliore comprensione del materiale del corso. MODALITA' DIDATTICHE Lezioni frontali ed esercitazioni, eventualmente erogate in modalità online. PROGRAMMA/CONTENUTO Progettazione ed analisi di algoritmi Introduzione: definizione di algoritmo; aspetti fondamentali nella soluzione di problemi mediante algoritmi; tipologie di problemi e strategie di soluzione; specifica degli algoritmi mediante diagrammi di flusso e pseudocodifica; sintassi e semantica relative alle convenzioni di pseudocodifica. Strutture dati fondamentali: strutture lineari (array, stringhe, pile, code e liste); grafi (definizioni fondamentali e strutture dati); alberi (definizioni fondamentali e strutture dati); insiemi, dizionari e mappe (definizioni fondamentali). Elementi di base: efficienza degli algoritmi, risorse computazionali e modello RAM; notazione asintotica (proprietà e classi fondamentali); tipologie di analisi di algoritmi (caso pessimo, ottimo e medio); limiti inferiori nell'analisi di algoritmi e ottimalità; efficienza ammortizzata. Strategia "Forza Bruta": metodologia ed esempi di analisi di algoritmi non ricorsivi (ricerca del massimo, unicità degli elementi e moltiplicazione fra matrici). Algoritmi di ordinamento elementare su vettori (Selection Sort); ricerca sequenzale su vettori; insiemi, dizionari e mappe con array dinamici e liste linkate; ricerca all'interno di stringhe (string matching). Strategia "Dividi e conquista": metodologia di analisi di algoritmi ricorsivi; teorema dell'esperto (Master Theorem). Algoritmi di ordinamento su vettori (Merge Sort e Quick Sort); limiti inferiori per gli algoritmi di ordinamento basati su confronti; alberi binari (definizione, calcolo dell'altezza, visite); analisi sintattica di linguaggi formali (definizione di linguaggio, grammatiche context-free, automi a pila); parsing ricorsivo top-down. Strategia "Diminuisci e conquista": algoritmo di Euclide; algoritmi di ordinamento su vettori (Insertion Sort e Shell Sort); visita di grafi non diretti in profondità e in ampiezza; componenti connesse su grafi non diretti; visita in profondità e in ampiezza su grafi diretti; ordinamento topologico; componenti fortemente connesse; ricerca binaria nei vettori, potenze di interi e matrici; alberi binari di ricerca (BST - Binary Search Tree). Strategia "Trasforma e conquista": struttura dati heap; utilizzo degli heap per l'ordinamento di vettori (Heap Sort); utilizzo degli heap per la gestione di code di priorità; confronto sperimentale fra ordinamenti asintoticamente ottimi; metodo di Horner per il calcolo di polinomi; insiemi disgiunti e problemi "Union-Find"; BST bilanciati: 2-3 alberi e alberi LLRB; tries. Strategia "Compromesso spazio-tempo": ordinamento di vettori in tempo lineare (Counting Sort); tabelle ad indirizzamento diretto, tabelle hash (separate chaining); funzioni hash; Strategia "Greedy" (golosa): algoritmi di Prim e Kruskal per il minimo albero ricoprente (MST - Minimum Spanning Tree), algoritmo di Dijkstra per la ricerca di cammini minimi; codici di Huffman per la compressione dei dati. Programmazione orientata agli oggetti (riferimenti al libro di testo Core Java I e II) Introduzione e ripasso su oggetti e classi (Core Java I - Cap. 4) ed ereditarietà (Core Java I - Cap. 5), libreria "legacy" per la lettura e la scrittura di file di testo Interfacce, espressioni lambda e classi interne (Core Java I - Cap. 6); gestione delle stringhe, gestione della memoria, misurazione delle prestazioni. Progettazione orientata agli oggetti: UML (class diagram, sequence diagram, state diagram); Eccezioni e logging (Core Java I - Cap. 7), rilascio di applicazioni Java (Core Java I - Cap. 13) Programmazione generica (Core Java I - Cap. 8), Java collection framework (Core Java I - Cap. 9) Introduzione ai Design Pattern (creazionali, strutturali e comportamentali); definizione dei pattern (Factory Method, Iterator, Composite, Decorator, Interpreter, Visitor, Observer) Utilizzo degli stream (Core Java II - Cap. 1) e gestione I/O (Core Java II - Cap. 2) TESTI/BIBLIOGRAFIA T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein ‐ Introduzione agli algoritmi e strutture dati ‐ 3a Edizione ‐ McGraw ‐ Hill; R. Sedgewick ‐ Algorithms ‐ 4th edition ‐ Addison Wesley A. Levitin ‐ Introduction to The Design and Analysis of Algorithms ‐ 2nd edition ‐ Addison ‐ Wesley; S. Skiena ‐ The Algorithm Design Manual ‐ 2nd edition – Springer; Cay Horstmann - Core Java (Vol. 1 e 2) - Prentice Hall DOCENTI E COMMISSIONI ARMANDO TACCHELLA Ricevimento: Su appuntamento a richiesta degli studenti. Commissione d'esame ARMANDO TACCHELLA (Presidente) MARCO MARATEA MASSIMO NARIZZANO ENRICO GIUNCHIGLIA (Presidente Supplente) LEZIONI INIZIO LEZIONI 21 Settembre 2020 Orari delle lezioni PROGETTAZIONE E ANALISI DI ALGORITMI ESAMI MODALITA' D'ESAME Progetti durante il corso (2 progetti, massimo 3 punti ciascuno), Prova pratica a calcolatore (massimo 12 punti) ed esame orale (massimo 12 punti). Qualora le lezioni si svolgessero online, i progetti vengono comunque assegnati; la prova pratica e l'esame orale vengono svolti in modalità telematica. MODALITA' DI ACCERTAMENTO Capacità di impostare la soluzione a problemi computazionali per via algoritmica implementando la soluzione con il linguaggio di programmazione Java; capacità di analizzarne la correttezza e la complessità delle soluzioni trovate per via analitica.Capacità di impostare la soluzione a problemi computazionali per via algoritmica e, analizzarne la correttezza e la complessità per via analitica. Calendario appelli Data appello Orario Luogo Tipologia Note 08/01/2021 10:00 GENOVA Prova pratica 02/02/2021 10:00 GENOVA Prova pratica 14/06/2021 10:00 GENOVA Prova pratica 06/07/2021 10:00 GENOVA Prova pratica 03/09/2021 10:00 GENOVA Prova pratica