UNIVERSITÀ di UDINE

Corso di Laurea in Matematica

Programma del corso di

Ottimizzazione 2

a.a. 2003-04

docente: Franca Rinaldi

TEORIA DELLE RETI DI FLUSSO (14 ore)

Definizioni fondamentali. Il problema di flusso a costo minimo. Il metodo del simplesso adattato alle reti di flusso. Il problema del massimo flusso e l'algoritmo di Dinic-Karzanov. Il problema del cammino minimo e l'algoritmo di Dijkstra. L'algoritmo "out-of-kilter".

PROGRAMMAZIONE DINAMICA (12)

Il principio di ottimalità e l'equazione di Bellman. L'algoritmo di Bellman-Ford. L'algoritmo per reti acicliche. L'algoritmo di Floyd-Warshall. Applicazioni della PD a: il problema del knapsack, il problema dell'allineamento di due stringhe, un problema di schedulazione.

OTTIMIZZAZIONE COMBINATORIA (22)

Problemi di accoppiamento e assegnamento. Algoritmi per l'accoppiamento di cardinalità massima. Ottimizzazione su matroidi. Algoritmo di Kruskal per il problema dell'albero di supporto di costo minimo. Combinatorica poliedrale. Analisi poliedrale del problema dell'accoppiamento di costo minimo, del problema del commesso viaggiatore e del problema dell'insieme stabile.

Modalità d'esame

Sono previste una prova scritta ed una prova orale.

Libro di testo: Paolo Serafini, Ottimizzazione , Zanichelli, Bologna 2000.