Dettagli sull'Insegnamento per l'A.A. 2016/2017

Prerequisiti

Conoscenze di base di: Matematica discreta, Programmazione Lineare, Algoritmi e Strutture dati, Complessità Computazionale.

Obiettivi

Capacità di individuare e formulare problemi di ottimizzazione su reti di flusso. Conoscenza di algoritmi di base e avanzati per problemi di ottimizzazione su reti di flusso. Capacità di progettare metodologie di risoluzione per problemi di ottimizzazione non standard su reti di flusso.

Sillabo

• Problemi di flusso su reti: introduzione e definizioni
• Problemi di Massimo Flusso: il problema di impaccamento di cammini. Teorema Max-Flow/Min-Cut. Algoritmi basati su cammini aumentanti: algoritmo di Ford e Fulkerson e algoritmo di Edmonds e Karp. Algoritmo preflow push. Problemi di flusso con richiesta minima.
• Applicazioni dei problemi di Massimo Flusso. Flusso su reti con capacità unitaria. Flusso su reti bipartite. Problemi di connettività.
• Problemi di taglio minimo su grafi non orientati; Algoritmo Node Identification; Algoritmo Random Contraction. Applicazioni
• Problemi di Flusso a Costo Minimo: definizioni e applicazioni.Condizioni di ottimalità. Problemi di cammino minimo con pesi qualsiasi. Algoritmi primali: algoritmo del circuito aumentante.
• Simplesso su reti. Applicazioni dei problemi di flusso a costo minimo

Descrittori di Dublino

Alla fine del corso, lo studente dovrebbe

Testi di riferimento

• Cunningham, Pulleyblank, Schrijver , Combinatorial Optimization    
• Ahuja, Magnanti, Orlin, Network Flows    

Modalità d'esame

Prova scritta (eventuale prova orale)

Risorse Internet

Aggiornamenti alla pagina del corso

• A.A. 2015/2016
• A.A. 2016/2017
• A.A. 2017/2018
• A.A. 2018/2019
• A.A. 2019/2020