Progettazione di Algoritmi a.a. 2025-2026

Il programma dettagliato del corso lezione per lezione lo trovate qui: Syllabus.pdf

Gli appunti saranno pubblicati durante lo svolgimento del corso alla fine di ogni lezione.

Qui i seguito trovate un programma di massima con le indicazioni di testi su cui gli argomenti sono trattati.

Grafi

Rappresentazione tramite matrici di adiacenza e liste di adiacenza. Visite in ampiezza (BFS) e in profondità (DFS). Alberi di visita e classificazione degli archi di una visita. Componenti connesse e fortemente connesse, Ordinamento topologico. Distanze in un grafo.

[Appunti del corso. Testo 1: Cap. 3, 4. Testo 3: Cap. 18. Testo 5: Cap. 11. Testo 6: Cap.7]

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: algoritmo di di Kruskal, strutture dati per insiemi disgiunti. Algoritmi di approssimazione e quantificazione dell'errore. Il problema del ricoprimento tramite nodi (Vertex Cover).

[Appunti del corso. Testo 1: Cap. 4, 5. Testo 3: Cap. 15, 17, 19, 20, 33. Testo 4: Cap. 4, 11]

Divide et Impera

Descrizione della tecnica. Algoritmo per la ricerca della coppia di punti più vicini. Il problema della selezione.

[Appunti del corso. Testo 1: Cap. 2. Testo 4: Cap. 5. Testo 5: Cap. 5, 10. Testo 6: Cap. 3]

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). Algoritmi di Bellman-Ford e di Floyd-Warshall.

[Appunti del corso. Testo 1: Cap. 6. Testo 2: Cap. 5. Testo 3: Cap. 14. Testo 4: Cap. 6. Testo 5: Cap. 10. Testo 6: Cap. 6]

Backtracking

Descrizione della tecnica. Enumerazione di strutture semplici: sottoinsiemi, sequenze, permutazioni. Esplorazione dello spazio di ricerca, ovvero generazione delle possibili soluzioni di un problema: 3-colorazione, ciclo Hamiltoniano. Euristiche di taglio per problemi di ottimizzazione: Zaino.

[Appunti del corso. Test 1: Cap. 9. Testo 2: Cap. 7]