Ottimizzazione combinatoria
A.A. 2024/2025
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 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
Algoritmi e strutture-dati. Programmazione. Ricerca operativa. Inglese.
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.
MAT/09 - RICERCA OPERATIVA - CFU: 6
Lezioni: 48 ore
Docente:
Righini Giovanni
Turni:
Turno
Docente:
Righini GiovanniDocente/i