Progettazione di Algoritmi

Professore:

Paul Wollan

Giacomo Paesani: sito per l'esercitazione

giovedì 10:30 - 12:00
Viale Regina Elena 295,
ufficio G28

martedì 17:00 - 19:00 - 16:00 in Aula 2, Edificio Caglioti
mercoledì 14:00 - 16:00 in Aula 3 Fisica, Edificio Fermi
giovedì 16:00 - 19:00 in Aula 2, Edificio Caglioti

Annunci

• Si avvisa gli studenti che le lezioni della settimana 18 - 22 marzo sono cancellati.
• Risultati dell'esame del 19 febbraio 2024.
• L'esame della sessione straordinaria si terrá il 11 aprile dalle 11 - 13 in Aula Riunione Via Regina Elena Palazzo E (stanza 305).

Programma

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).

• 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

Lezione 1:

Definizioni: Grafo, nodi e vertici, archi e lati, grado di un nodo, grafi diretti, vertice incidente ad un arco, vertici adiacenti, passeggiata in un grafo, passeggiata Euleriano, matrice di adiacenze, lista di adiacenze.

Problema: algoritmo per trovare un ciclo in un grafo con grado minimo 2.

Lezione 2:

Proposizione: se esiste una passeggiata collegando due vertici, allora esista un cammino collegando i vertici.

Definizioni: Grafi connessi, ricerca in profondità (DFS).

Algoritmo per il DFS con la dimostrazione di correttezza.

Lezione 3:

Definizioni: albero di visita, arborescenza di visita, ordine topologiche di un grafo diretto aciclico.

Proposizione: Ogni grafo diretto aciclico ha un vertice senza archi entranti.

Algoritmo O(n³) per trovare un ordine topologiche di un grafo aciclico.

Definizioni: Tempo di visita e tempo di chiusura di un vertice in un DFS. Archi in avanti, archi al indietro, e archi di attraversamenti.

Lezione 4:

Definizioni: Tempo di visita e tempo di chiusura di un vertice in un DFS. Archi in avanti, archi al indietro, e archi di attraversamenti.

Proposizione: Un grafo connesso/fortemente connesso ha cicli se e solo se esiste un arco al indietro per un DFS.

Lezione 5:

Esercitazioni. Problemi.

Lezione 6:

Algoritmo O(n+m) per trovare un ordine topologiche con dimostrazione di correttezza.

Definizioni: ponti in un grafo.

Algoritmo O(n(n+m)) per trovare tutti i ponti in un grafo non-diretto.

Proposizione: Un arco xy nel albero di visita T di un grafo non-diretto e un ponte se e solo se non esiste un arco collegando i due componenti di T-xy.

Algoritmo O(n+m) per trovare tutti i ponti in un grafo non-diretto.

Lezione 7:

Definizioni: componente fortemente connesso, c-radice, contrazione di un sotto insieme di vertici, G/X.

Proposizione: G un grafo diretto, u un vertice. G è fortemente connesso se e solo se for all vertici x esiste un cammino diretto da u ad x e da x ad u.

Proposizione: G un grafo diretto, H un sottografo di G fortemente connesso. Allora G/V(H) é fortemente connesso.

Algoritmo O(n(n+m)) per trovare i componenti fortemente connessi in un grafo diretto.

Proposizione: Un arco xy nel albero di visita T di un grafo non-diretto e un ponte se e solo se non esiste un arco collegando i due componenti di T-xy.

Lezione 8:

Algoritmo O(n+m) per trovare i componenti fortemente connessi in un grafo diretto, dato un subroutine per riconoscere le c-radice.

Proposizione: Un nodo u non é un c-radice se e solo se nella chiamata ricorsiva del DFS_SCC con radice u viene attraversato un arco (v,w) tale che w é stato già visitata ma il componente di w non é stato ancora determinato.

Algoritmo O(n+m) per trovare i componenti fortemente connessi in un grafo diretto.

Lezione 9:

Esercitazioni. Problemi.

Lezione 10:

Definizioni: distanza in un grafo.

Definizioni: Breadth-first search.

Algoritmo O(n+m) per effettuare un BFS con la dimostrazione che DIST contiene le distanze dei vertici dalla radice.

Algoritmo O(n+m) contare i numeri ci cammini di lunghezza minima tra due vertici dato in input.

Lezione 11:

Esercitazioni. Problemi.

Lezione 12:

Algoritmo O(n+m) per trovare la distanza tra due insieme di vertici.

Lezione 13:

Definizioni: grafi pesati, distanza in un grafo pesato.

Proposizione: Per ogni grafo G con pesi w(e) sugli archi del grafo,

• dist_w (x,x) = 0 per ogni vertice x,
• dist_w (x, y) ≥ 0 e per x, y distinti, dist_w (x, y)>0,
• dist_w (x, y) ≤ dist_w (x, u) + dist_w (u, y) for all vertices u.

Algoritmo di Dijkstra per trovare la distanza tra due vertices in un grafo con pesi sugli archi.

Lezione 14:

Esercitazioni.

Lezione 15:

Implementazione di Dijkstra con un heap per realizzare la complessitá di O(log n (n + m))

Algoritmo greedy per trovare un sottoinsieme di intervali disgiunti di cardinalitá massima con la dimostrazione di correttezza.

Lezione 16:

Esercitazioni.

Lezione 17:

Definizioni: albero di copertura di peso minimo (MST).

Algoritmo di Kruskal per trovare il MST con la dimostrazione di correttezza.

Lezione 18:

Algoritmo di Prim per trovare il MST con la dimostrazione di correttezza.

Lezione 19:

Esercitazioni.

Lezione 20:

Discussione del Master Theorem per trovare la formula per la complessità dato una relazione di ricorrenza.

Algoritmo divide et impera per trovare il massimo sottovettore di un array.

Lezione 21:

Esercitazioni.

Lezione 22:

Algoritmo divide et impera per trovare la coppia di punti più vicini nel plano.