Combinatorial optimization
A.A. 2021/2022
Obiettivi formativi
L'obiettivo dell'insegnamento è di approfondire la conoscenza degli algoritmi di complessità polinomiale per calcolare la soluzione ottima di classici problemi di ottimizzazione combinatoria su grafo.
Risultati apprendimento attesi
Capacità di progettazione di algoritmi per risolvere in modo efficiente problemi di ottimizzazione combinatoria polinomiali su grafo
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo semestre
In relazione alle modalità di erogazione delle attività formative per l'a.a. 2021/22, verranno date indicazioni più specifiche nei prossimi mesi, in base all'evoluzione della situazione sanitaria.
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. Unweighted graphs: BFS algorithm. Weighted acyclic graphs: Critical Path Method. Grafi senza cicli negativi: Bellman-Ford algorithm. Grafi senza archi negativi: Dijkstra algorithm. 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. Unweighted graphs: BFS algorithm. Weighted acyclic graphs: Critical Path Method. Grafi senza cicli negativi: Bellman-Ford algorithm. Grafi senza archi negativi: Dijkstra algorithm. 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
Ricerca operativa
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
Prova scritta preliminare di circa mezz'ora, senza testi. Quindi (a) progetto e prova orale, oppure (b) presentazione di articolo scientifico e prova orale.
Siti didattici
Docente/i