Il corso di Algoritmi 2 affronta le principali tecniche per la progettazione e l'analisi degli algoritmi, con particolare attenzione agli algoritmi su grafi e alle tecniche per la soluzione di problemi complessi.
Il programma comprende i seguenti argomenti.
Grafi e loro rappresentazione
Visita in profondità (DFS)
Visita in ampiezza (BFS)
Distanze nei grafi non pesati
Diametro di un grafo
Riconoscimento dei cicli nei grafi diretti
Grafi aciclici diretti (DAG)
Ordinamenti topologici
Componenti fortemente connesse
Algoritmo di Kosaraju
Grafi pesati
Problema dei cammini minimi
Cammini minimi da una sorgente
Algoritmo di Dijkstra
Alberi di copertura
Minimo albero di copertura
Algoritmo di Kruskal
Principio della scelta greedy
Strategie greedy
Costruzione delle soluzioni
Dimostrazione della correttezza delle strategie greedy
Applicazioni della tecnica greedy
Problemi difficili
Necessità dell'approssimazione
Algoritmi di approssimazione
Qualità delle soluzioni
Rapporto di approssimazione
Esempi di algoritmi di approssimazione
Principio Divide et Impera
Suddivisione in sottoproblemi
Ricombinazione delle soluzioni
Problema della selezione
Problema della coppia di punti più vicini
Sottoproblemi sovrapposti
Memoizzazione
Approccio top-down
Approccio bottom-up
Tabelle di Programmazione Dinamica
Tabelle bidimensioni
Applicazioni ai problemi di ottimizzazione
Cammini minimi in presenza di pesi negativi
Algoritmo di Bellman-Ford
Cammini minimi tra tutte le coppie di vertici
Algoritmo di Floyd-Warshall
Principio del backtracking
Costruzione incrementale delle soluzioni
Ricerca con vincoli
Generazione di insiemi, matrici e permutazioni con vincoli
Problemi decisionali
Problemi di ottimizzazione
Tecniche di riduzione dello spazio di ricerca
Gli argomenti del corso sono sviluppati attraverso le presentazioni disponibili nella sezione Lezioni e slide.
Una singola presentazione può essere utilizzata durante più lezioni. Per questo motivo la successione delle presentazioni non corrisponde necessariamente alla successione delle singole lezioni svolte in aula.
Per conoscere le date e gli argomenti trattati nelle singole lezioni, consultare il Diario delle lezioni.
Gli argomenti oggetto d'esame sono quelli indicati nel programma e trattati durante le lezioni. Oltre alle presentazioni disponibili nella sezione Lezioni e slide, gli argomenti possono essere approfonditi attraverso materiale didattico e risorse disponibili in rete e mediante i seguenti testi.
S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani, Algorithms, McGraw-Hill, 2006.
Il testo è disponibile anche online qui.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, L. Colussi, A. Frigeri, Introduzione agli algoritmi e strutture dati, 4ª edizione, McGraw-Hill Education, 2023.
C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, 3ª edizione, McGraw-Hill Education, 2025.
P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi, Strutture di dati e algoritmi. Progettazione, analisi e visualizzazione, 2ª edizione, Pearson, 2012.