Analisi e Progetto di Algoritmi

  Analisi e Progetto di Algoritmi
  Gennaio/Febbraio 2007

  Docente: Dr Damiano Macedonio
  Dipartimento di Informatica
  Università Ca' Foscari di Venezia

Contenuti

Comunicazioni

Programma dettagliato

Prove di esame

Comunicazioni

Ricevimento: previo appuntamento via e-mail.

Ufficio: stanza n.7 (Assegnisti/Ospiti).

Appello autunnale:

scritto: mercoledì 12 Settembre ore 10:00, aula D.
orale: venerdì 14 Settembre.

Programma dettagliato

10 gen 2007. Teoria dei grafi: introduzione ai grafi, componenti connesse, cliques.

13 gen 2007. Rappresentazione dei grafi. Grafi bipartiti. Isomorfismi tra grafi. Grafo complento. Lemma della stretta di mano. Esercizi

17 gen 2007. Applicazioni del lemma della stretta di mano. Isomorfismo e clique massima nel grafo associazione. Colorazione di grafi.

20 gen 2007. Proprietà dei grafi connessi e dei grafi aciclici. Caratterizzazione alberi liberi. Esercizi.

24 gen 2007. Grafi pesati. Alberi di copertura minini e loro teorema fondamentale.

27 gen 2007. Algoritmi greedy. Algoritmi di Kruskal e Prim: correttezza, complessità ed esempi. Algoritmo greedy_clique.

31 gen 2007. Algoritmo greedy_selection. Cammini minimi e loro principali proprietà.

03 feb 2007. Algoritmo di Dijkstra: sottoprocedure, correttezza, complessità ed esempi.

07 feb 2007. Algoritmo di Bellman-Ford: correttezza e complessità. Esercizi.

10 feb 2007. Cammini minimi tra tutte le coppie di vertici. Metodo della moltiplicazione di matrici: correttezza e complessità. Esercizi.

14 feb 2007. Algoritmo di Floyd-Warshall: formula ricorsiva, correttezza, complessità temporale e spaziale. Esempi.

17 feb 2007. Reti di flusso: definizioni e principali proprietà. Reti residue: flussi e cammini aumentanti.

21 feb 2007. Flusso associato al cammino aumentante. Taglio in una rete di flusso. Teorema del flusso massimo e del taglio minimo.

24 feb 2007. Algoritmo di Ford-Fulkerson e ottimizzazione di Edmonds-Karp: correttezza, complessità ed esempi di esecuzione.

28 feb 2007. Classi di complessità di problemi. Problemi P, NP ed NP-Completi: definizioni ed esempi.

03 mar 2007. Problemi NP-Completi e riduzioni: da CIRCUIT_SAT a CLIQUE, passando attraverso SAT (formule booleane) e 3_SAT_FNC.