Ottimizzazione su grafo
A.A. 2025/2026
Obiettivi formativi
Gli obiettivi del corso sono: 1) apprendere alcuni algoritmi di complessita' polinomiale per problemi di ottimizzazione su grafo e i fondamenti teorici sui quali tali algoritmi si basano; 2) implementare alcuni degli algoritmi presentati (una parte del corso si svolge in laboratorio informatizzato); 3) capire quando la ricerca di algoritmi polinomiali, per un nuovo problema di ottimizzazione combinatoria, e'
probabilmente destinata a fallire (mediante la teoria della complessita'
computazionale).
probabilmente destinata a fallire (mediante la teoria della complessita'
computazionale).
Risultati apprendimento attesi
Capacità di progettazione di algoritmi per risolvere in modo efficiente problemi di ottimizzazione combinatoria polinomiali su grafo
Periodo: Primo quadrimestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento può essere seguito come corso singolo.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo quadrimestre
Programma
· Richiami di programmazione lineare e teoria della dualità.
· Grafi, definizioni, proprietà. Componenti connesse, algoritmi di visita di grafi.
· Alberi e arborescenze. Minimum cost spanning tree: Kruskal, Prim, Boruvka algorithms. Minimum cost spanning arborescence: Edmonds algorithm.
· Cammini minimi. Grafi non pesatti: algoritmo BFS. Digrafi aciclici: Critical Path Method. Grafi senza cicli negativi: algoritmo di Bellman-Ford. Grafi senza archi negativi: algoritmo di Dijkstra, A*. Algoritmo di Floyd-Warshall per il calcolo degli all-pairs shortest paths.
· Flussi ottimi. Algoritmo di Ford-Fulkerson per il problema di massimo flusso. Algoritmi per Il problema di massimo flusso a minimo costo. Dualità: max flow - min cut. Algoritmo di Gomory e Hu per trovare il minimo taglio in un grafo pesato.
· Matching bipartito. Algoritmo ungherese.
· Trasporto a costo minimo. Algoritmo di Dantzig.
· Grafi, definizioni, proprietà. Componenti connesse, algoritmi di visita di grafi.
· Alberi e arborescenze. Minimum cost spanning tree: Kruskal, Prim, Boruvka algorithms. Minimum cost spanning arborescence: Edmonds algorithm.
· Cammini minimi. Grafi non pesatti: algoritmo BFS. Digrafi aciclici: Critical Path Method. Grafi senza cicli negativi: algoritmo di Bellman-Ford. Grafi senza archi negativi: algoritmo di Dijkstra, A*. Algoritmo di Floyd-Warshall per il calcolo degli all-pairs shortest paths.
· Flussi ottimi. Algoritmo di Ford-Fulkerson per il problema di massimo flusso. Algoritmi per Il problema di massimo flusso a minimo costo. Dualità: max flow - min cut. Algoritmo di Gomory e Hu per trovare il minimo taglio in un grafo pesato.
· Matching bipartito. Algoritmo ungherese.
· Trasporto a costo minimo. Algoritmo di Dantzig.
Prerequisiti
Sono prerequisiti i concetti fondamentali di Algoritmi e strutture-dati, Programmazione dei calcolatori e Ricerca operativa. E' utile una buona comprensione dell'inglese tecnico-scientifico.
Metodi didattici
Lezioni frontali.
Materiale di riferimento
R.K. Ahuja, T.L. Magnanti, J.B. Orlin "Network flows", Prentice Hall, 1993
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste in tre prove.
1. Una breve prova scritta per accertare che lo studente abbia maturato le conoscenze necessarie per affrontare le prove successive.
2a. La realizzazione di un progetto nel quale è richiesto allo studente di progettare un algoritmo di ottimizzazione per un problema di ottimizzazione combinatoria concordato col docente, scrivere il codice in un linguaggio di programmazione a scelta dello studente e valutare sperimentalmente le prestazioni del programma.
2b. In alternativa al progetto, la seconda prova può consistere nella preparazione di un seminario di circa 20-30 minuti su un articolo concordato col docente.
3. In ogni caso, l'esame è concluso da una prova orale riguardante gli argomenti del corso che non sono stati oggetto del progetto o del seminario.
1. Una breve prova scritta per accertare che lo studente abbia maturato le conoscenze necessarie per affrontare le prove successive.
2a. La realizzazione di un progetto nel quale è richiesto allo studente di progettare un algoritmo di ottimizzazione per un problema di ottimizzazione combinatoria concordato col docente, scrivere il codice in un linguaggio di programmazione a scelta dello studente e valutare sperimentalmente le prestazioni del programma.
2b. In alternativa al progetto, la seconda prova può consistere nella preparazione di un seminario di circa 20-30 minuti su un articolo concordato col docente.
3. In ogni caso, l'esame è concluso da una prova orale riguardante gli argomenti del corso che non sono stati oggetto del progetto o del seminario.
Docente/i