Progettazione di Algoritmi
Professore:
Paul Wollan
Esercitatore:
Giacomo Paesani
Ricevimento:
giovedì 10:30 - 12:00
Viale Regina Elena 295,
ufficio G28
Orario delle lezioni:
martedì 17:00 - 19:00 in Aula 4 De Lollis
mercoledì 14:00 - 16:00 in Aula 4 De Lollis
giovedì 16:00 - 19:00 in Aula 4 De Lollis
Annunci
- Si avvisa gli studenti che le lezioni della settimana 24 - 28 febbraio sono cancellati. Il corso inizia il 4 marzo.
- Risultati dell'esame del 20 febbraio. Per verbalizzare si può confermare l'accettazione del voto via email.
Programma
Per ogni algoritmo nel programma è data una dimostrazione di correttezza e valutata la complessità di possibili implementazioni. Alla fine di ogni argomento sono elencati i testi consigliati in ordine di rilevanza. Gli appunti saranno pubblicati durante lo svolgimento del corso.
Grafi
Rappresentazione tramite matrici di adiacenza e liste di adiacenza. Visite in ampiezza (BFS) e in profondità (DFS). Albero di visita e classificazione degli archi di una visita. Componenti connesse e fortemente connesse, algoritmo di Tarjan. Ordinamento topologico. Distanze in un grafo.
Greedy
Descrizione della tecnica e schema generale per dimostrare la correttezza di un algoritmo Greedy. Algoritmi per Selezione Attività. Cammini minimi in grafi pesati: algoritmo di Dijkstra. Minimo albero di copertura: algoritmi di Prim e di Kruskal, strutture dati per insiemi disgiunti. Algoritmi di approssimazione e quantificazione dell'errore. Il problema del ricoprimento tramite nodi (Vertex Cover). Codici di Huffman.
Divide et Impera
Descrizione della tecnica. Il problema del massimo sottovettore. Algoritmo per la ricerca della coppia di punti più vicini (Closest Pair). Il problema della mediana.
Programmazione Dinamica
Descrizione della tecnica e confronto con Divide et Impera. Ricerca esaustiva e memoizzazione. Dal calcolo del valore ottimo al trovare una soluzione ottima. Il problema dello Zaino (Knapsack). Cammino più lungo in grafi aciclici (Longest Path in DAG). Pianificazione Attività (CPM). Sistemi con vincoli di differenza e cammini minimi in grafi con pesi anche negativi. Algoritmi di Bellman-Ford e di Floyd-Warshall. Il problema della massima sottosequenza comune (LCS). Distanza tra stringhe (Edit Distance). Prodotto di una sequenza di matrici (Matrix Chaining).
Testi consigliati
- S. Dasgupta, C. Papadimitriou, U. Vazirani Algorithms . Disponibile anche online.
- E. Horowitz, S. Sahni Fundamentals of Computer Algorithms Computer Science Press.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein Introduzione agli algoritmi e strutture dati MacGraw -Hill 2010
- J. Kleimberg, E. Tardos Algorithm Design Addison Wesley, 2005
- C. Demetrescu, I. Finocchi, G.F. Italiano Algoritmi e Strutture di Dati. MacGraw-Hill 2010
- P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi Strutture di dati e algoritmi. Pearson 2012
Appunti
Gli appunti per le lezioni si trovano qui.
Diario delle lezioni