Introduzione, analisi, divide et impera.
Ordinamento e code con priorità.
Dizionari: tabelle hash, alberi binari di ricerca.
Programmazione dinamica.
Algoritmi elementari sui grafi.
Alberi di copertura minimi.
Cammini minimi.
Esempi di implementazione ed applicazioni degli algoritmi trattati nel corso.
Libro di testo ufficiale:
[CLRS09] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (2009). Introduzione agli algoritmi, 3rd ed,
Può essere utile la consultazione di:
[MR05] B. N. Miller and D. L. Ranum (2005). Problem Solving with Algorithms and Data Structures Using
Python, Franklin, Beedle & Associates Inc. Amazon link.
Obiettivi Formativi
Al termine del corso sarete in grado di comprendere ed applicare metodi per analizzare il tempo di
esecuzione degli algoritmi, mostrare la loro correttezza, utilizzare soluzioni algoritmiche adeguate per
risolvere problemi concreti.
Prerequisiti
I prerequisiti necessari includono una buona comprensione della programmazione procedurale e orientata
agli oggetti, le idee fondamentali della matematica discreta (calcolo combinatorio, serie, sommatorie,
induzione matematica) e della teoria della probabilità (variabili aleatorie, distribuzioni, valori attesi).
Normalmente dovete aver frequentato i corsi B003262 - (Fondamenti di informatica), B003271 -
(Geometria, algebra lineare e calcolo numerico), e B003426 (Laboratorio di tecnologie dell'informazione) e
superato i corrispondenti esami.
Metodi Didattici
lezioni, esercitazioni
Altre Informazioni
Nessuna
Modalità di verifica apprendimento
L'esame consiste di una prova scritta e di una prova orale sull'intero programma del corso.
Durante il corso sono assegnati con cadenza approssimativamente settimanale alcuni
esercizi teorici e pratici che devono essere consegnati individualmente attraverso la piattaforma di
e-learning dell'ateneo (e-l.unifi.it)
Programma del corso
Presentazione del corso. Algoritmi: introduzione all'analisi e pseudocodice. Esempi: Insertion-Sort e
Merge-Sort. Correttezza. Applicazione del principio di induzione matematica. Ricorsione. Invarianti di
ciclo. Analisi degli algoritmi. Notazione asintotica e crescita delle funzioni. Significato pratico e
definizioni matematiche delle classi O, Theta e Omega.
Divide et Impera. Idee generali. Ricorrenze e tecniche risolutive: metodo della sostituzione. Esempi.
Teorema fondamentale e schema della sua dimostrazione. Esempi. Calcolo di potenze intere. Numeri di
Fibonacci. Moltiplicazione di matrici e algoritmo di Strassen. Quicksort. Analisi del caso peggiore e
migliore. Analisi di quicksort randomizzato. Code con priorità loro e realizzazione con max-heaps.
Ordinamento in tempo lineare: confine asintotico inferiore per gli algoritmi basati su confronto.
Ordinamento per conteggio. Radix-Sort. Calcolo di statistiche. Selezione randomizzata. Analisi del caso
medio. Applicazioni.
Dizionari. Tabelle ad indirizzamento diretto. Tabelle hash. Collisioni. Chaining e relativa analisi. Metodo
della divisione e della moltiplicazione. Indirizzamento aperto. Sondaggio lineare e doppio hash. Analisi.
Tabelle dinamiche e analisi ammortizzata degli algoritmi. Alberi binari di ricerca. Definizioni. Visite.
Ricerca. Analisi. Massimo, minimo, successore e predecessore. Inserimento. Cancellazione. BST-sort e
relazione con QuickSort. Altezza attesa degli alberi binari construiti da una sequenza casuale di chiavi.
Alberi bilanciati. Alberi red-black. Definizione. Relazione tra altezza e numero di nodi. Inserimento.
Correttezza. Cenni su alberi AVL. Treaps. Statistiche d'ordine dinamiche. Selezione e rango con alberi
RB. Generalità su strutture dati aumentate. Applicazioni.
Programmazione dinamica. Il problema della sottosequenza comune più lunga. Definizione. Algoritmo
per bruta forza. Sottostruttura ottimale di una sottosequenza comune più lunga. Algoritmo ricorsivo e
versione tabellare. Esempi. Distanza di Levenshtein. Allineamento di sequenze ed algoritmo di
Needleman-Wunsch. Implementazione C++. Applicazioni.
Grafi. Definizioni fondamentali. Esempi. Matrici e liste di adiacenza. Visita in ampiezza. Analisi e
proprietà. Visita in profondità. Teorema delle parentesi e classificazione degli archi. Relazione tra BFS e
DFS. Iterative deepening. Ordinamento topologico nei DAG. Calcolo delle componenti fortemente
connesse nei grafi orientati. Alberi di copertura minimi. Definizioi. Ottimalità dei sottoproblemi.
Proprietà del taglio e scelta golosa. Algoritmi di Prim. Analisi. Cenni sull'analisi ammortizzata. Strutture
per insiemi disgiunti. Realizzazione con foreste ed euristiche del rango e della compressione dei
cammini. Analisi. Algoritmo di Kruskal. Analisi. Cammini minimi da singola sorgente. Definizione del
problema e proprietà. Algoritmo di Dijkstra. Correttezza. Analisi. Algoritmo di Bellman-Ford.
Correttezza. Caso dei DAGs. Applicazioni.