Appunti

1. Appunti (pdf) Grafi: diretti e non diretti, adiacenza, grado, cammino, ciclo. Rappresentazione di grafi: matrice di adiacenza e liste di adiacenza. I concetti di Connessione, forte connessione e componenti connesse. Esempio [9-puzzle]. Esercizio [acqua].
2. Appunti (pdf) Discussione esercizio [acqua]: modellare un problema tramite un grafo. Visita di un grafo: DFS. Albero di visita. Determinazione delle componenti connesse. Esempio [2-colorazione, bipartizione]. Esercizio [ordine].
3. Appunti (pdf) Discussione esercizio [ordine]: grafi aciclici o DAG e ordinamento topologico. Proprietà DFS: tempi di inizio e fine visita. Classificazione degli archi di una DFS: attraversamento, indietro e avanti. Algoritmo per trovare cicli, vettore dei padri. Algoritmo per ordine topologico basato su DFS. Esercizio [gradi].
4. Appunti (pdf) Discussione esercizio [gradi]: implementazione efficiente dell'algoritmo non basato sulla DFS per l'ordine topologico. Esercizi discussi: [archi] (conta gli archi per tipo di una DFS), [trasposto] (calcolo grafo trasposto), [grado due] (sui cicli), [ponte] (archi ponte), [pozzo] (pozzi universali). Esercizio [strade critiche].
5. Appunti (pdf) Discussione esercizio [strade critiche]: algoritmo per trovare archi ponte. Esempio [snodi critici]: punti di articolazione. Algoritmo per trovare i punti di articolazione. Biconnessione. Esercizio [sensi unici].
6. Appunti (pdf) Discussione esercizio [sensi unici]: modellazione tramite grafo e introduzione alla forte connessione. Componenti fortemente connesse: algoritmo di Tarjan. DAG delle componenti fortemente connesse. Esercizio [broadcast].
7. Appunti (pdf) Discussione esercizio [broadcast]: applicazione dell'algoritmo di Tarjan. Distanze in un grafo. Visita BFS: cammini minimi e calcolo delle distanze da un nodo. Esempio[reve's puzzle]. Esercizio [labirinto].
8. Appunti (pdf) Discussione esercizio [labirinto]: conteggio numero cammini minimi, variazione BFS. Esercizi discussi: [DFS vs BFS] (confronto tra le visite DFS e BFS), [dall'albero alle distanze] (calcolare le distanze dall'albero di visita di un BFS), [stessa distanza] (i nodi a uguale distanza da due nodi dati), [distanza tra insiemi] (distanza tra due insiemi di nodi), [Roma] (cammini minimi che passano per un nodo dato). Esercizio [acqua 2].
9. Appunti (pdf) Discussione esercizio [acqua 2]: applicazione BFS. Cammini minimi in grafi pesati. Algoritmo di Dijkstra e un'implementazione efficiente. Introduzione agli algoritmi Greedy. Esercizio [pesi].
10. Appunti (pdf) Discussione esercizio [pesi] modi diversi di pesare un cammino. Problema Selezione Attività: discussione di tre algoritmi. Schema generale per dimostrare la correttezza di algoritmi Greedy, correttezza di un algoritmo per Selezione Attività e un'implementazione efficiente. Correttezza dell'algoritmo di Dijkstra. Esercizio [rifornimenti].
11. Appunti (pdf) Discussione esercizio [rifornimenti]: applicazione dello schema generale per dimostrare la correttezza. Minimo Albero di Copertura (MST). Algoritmo di Prim: correttezza e implementazione efficiente. Esercizi [MST].
12. Appunti (pdf) Discussione esercizio [MST]: proprietà di MST. Algoritmo di Kruskal: correttezza e implementazione efficiente. Ricoprimento tramite nodi (VC). Algoritmi di approssimazione. Un algoritmo di approssimazione per VC. Esercizio [file].
13. Appunti (pdf) Discussione esercizio [file]: un algoritmo di approssimazione. Esercizi di preparazione alla prova intermedia discussi: [sempre connesso] (visite, DFS), [super-minimo] (modellazione e Dijkstra), [arco massimo] (proprietà di MST), [Universa] (sull'algoritmo di Prim), [sicurezza] (modellazione e Prim), [univoco] (Greedy e correttezza). Altri esercizi [cicli diretti], [resto], [k-MST], [teatro].
14. Appunti (pdf) Breve Discussione degli esercizi della prova intermedia. Divide et Impera. Master Theorem. Il problema del Massimo Sottovettore. Esercizio [salto].
15. Appunti (pdf) Discussione esercizio [salto]: applicazione Divide et Impera. Il problema della Coppia di punti più vicini (Closest Pair). Calcolo della mediana e del k-esimo elemento. Esercizio [mediana].
16. Appunti (pdf) Discussione esercizio [mediana]: applicazione Divide et Impera. Ricerca esaustiva (ricorsiva) e Memoizzazione: esempio problema File. Programmazione Dinamica. Dal valore ottimo alla soluzione ottima. Eserczio [resto].
17. Appunti (pdf) Discussione esercizio [resto]: dalla Memoizzazione alla Programmazione Dinamica. Problema Zaino. Riduzione a problemi su grafi per i problemi Zaino e resto. Esercizio [resto 2].
18. Appunti (pdf) Discussione esercizio [resto 2]: applicazione Programmazione Dinamica. Longest Path in DAG. Pianificazione di Attività (CPM). Sistemi con Vincoli di Differenza. Esercizio [viaggio].
19. Appunti (pdf) Discussione esercizio [viaggio]: dalla rappresentazione tramite DAG alla Programmazione Dinamica. Cammini minimi con pesi anche negativi. Algoritmo di Bellman-Ford. Esercizio [cammini].
20. Appunti (pdf) Discussione esercizio [cammini]: applicazione di Bellman-Ford. Cammini minimi tra tutte le coppie di nodi. Algoritmo di Floyd-Warshall. Massimo sottovettore. Esercizio [prezzi].
21. Appunti (pdf) Discussione esercizio [prezzi]: applicazione Programmazione Dinamica. Massima Sottosequenza Comune (LCS). Edit Distance. Esercizio [senza spazi].
22. Appunti (pdf) Discussione esercizio [senza spazi]: applicazione Programmazione Dinamica. Prodotto di Matrici. Esercizi sulla Programmazione Dinamica: [massima sottosequenza crescente] e [gettoni]. Esercizio [palindroma].
23. Appunti (pdf) Discussione esercizio [palindroma]: applicazione Programmazione Dinamica. Backtracking: Generare sottoinsiemi, colorazioni, permutazioni e combinazioni. Esercizio [cassaforte].
24. Appunti (pdf) Discussione esercizio [cassaforte]: applicazione Backtracking. Sfrondare lo spazio di ricerca: 3-Colorazione, Cicli Hamiltoniani, Zaino. Esercizi Backtracking: [cricca], [regine], [parità]. Esercizi Programmazione Dinamica: [numero sottosequenze crescenti], [cammino], [somma].