Analisi e Progetto di Algoritmi   Anno Accademico 2008/2009   Corso per Studenti Part Time   Docente Dr. Damiano Macedonio   Dipartimento di Informatica   Università Ca’ Foscari di Venezia

Contenuti   (ultimo aggiornamento: 13 maggio 2009)

• Comunicazioni
• Programma del Corso
• Lezioni in Dettaglio
• Prove di Esame

Comunicazioni

• Ricevimento: previo appuntamento via e-mail.
• Ufficio: stanza n.7 (Assegnisti/Ospiti).
• Ricevimento generale
  • mercoledì 13 maggio 2009, ore 18:00 aula 2.
  • sabato 16 maggio 2009, ore 10:00 - Da confermare -
• Appello straordinario
  • scritto: martedì 19 maggio 2009
  • orale: venerdì 22 maggio 2009

Programma del Corso

• Grafi e loro proprietà.
• Tecniche fondamentali per il progetto e l'analisi di algoritmi (greedy, programmazione dinamica).
• Cammini minimi (Dijkstra, Bellman-Ford, Floyd-Warshall).
• Flusso massimo (Ford-Fulkerson, Edmonds-Karp) e abbinamento massimo bipartito.
• Problemi NP-completi e approssimazioni. Classi di complessità P e NP. Riducibilità e NP-completezza.
• Testo di Riferimento:
  T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein.
  Introduction to Algorithms (Second Edition), MIT Press, 2001.
  Traduzione italiana a cura di Livio Colussi edita da McGraw-Hill, Milano, 2005.

Lezioni in Dettaglio

Top

• 19 feb 2009. Teoria dei grafi: introduzione, sottografi, cammini, componenti connesse.
• 21 feb 2009. Grafi completi, cliques. Grafi bipartiti. Rappresentazione di grafi: liste e matrici di adiacenza.
• 24 feb 2009. Isomorfismo tra grafi. Grafo complemento. Riduzione del problema dell'isomorfismo al problema della clique massima nel grafo di associazione.
• 26 feb 2009. Lemma della stretta di mano e sue applicazioni. Esercizi.
• 02 mar 2009. Proprietà dei grafi connessi e dei grafi aciclici.
• 05 mar 2009. Caratterizzazione degli alberi liberi. Esercizi.
• 07 mar 2009. Grafi pesati. Alberi di copertura minini e loro teorema fondamentale. Algoritmo di Kruskal: correttezza e complessità.
• 12 mar 2009. Algoritmo di Prim: correttezza, complessità ed esempi.
• 14 mar 2009. Algoritmi greedy. Algoritmo greedy_clique. Algoritmo greedy_selection. Esericizi.
• 17 mar 2009. Cammini minimi su grafi orientati. Principali proprietà.
• 19 mar 2009. Algoritmo di Dijkstra: proprietà delle sottoprocedure, complessità.
• 23 mar 2009. Algoritmo di Dijkstra: correttezza e simulazione su esempi.
• 25 mar 2009. Algoritmo di Bellman-Ford: correttezza e complessità.
• 30 mar 2009. Cammini minimi tra tutte le coppie di vertici. Formula ricorsiva per il metodo della moltiplicazione di matrici.
• 02 apr 2009. Metodo della moltiplicazione di matrici: correttezza e complessità. Simulazione.
• 06 apr 2009. Algoritmo di Floyd-Warshall: formula ricorsiva, correttezza, complessità temporale e spaziale. Esempi.
• 08 apr 2009. Reti di flusso: definizioni e principali proprietà.
• 17 apr 2009. Reti residue: flussi e cammini aumentanti.
• 20 apr 2009. Flusso associato al cammino aumentante. Taglio in una rete di flusso.
• 23 apr 2009. Teorema del flusso massimo e del taglio minimo.
• 27 apr 2009. Algoritmo di Ford-Fulkerson e ottimizzazione di Edmonds-Karp: correttezza, complessità.
• 30 apr 2009. Esempi di esecuzione degli algoritmi presentati ed esercizi.

Prove di Esame

Top

• Appello straordinario
  • scritto: martedì 19 maggio 2009
  • orale: venerdì 22 maggio 2009

mace@dsi.unive.it