Combinatorial optimization
A.A. 2023/2024
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
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, Algoritmi e strutture-dati.
Metodi didattici
Lezioni frontali
Materiale di riferimento
Ahuja, Magnanti, Orlin, "Network Flows: Theory, Algorithms, and Applications", Pearson
Modalità di verifica dell’apprendimento e criteri di valutazione
Progetto o seminario.
Docente/i