Il Corso

Descrizione, contenuti, obiettivi

Il corso di Ottimizzazione Combinatoria (IN440) ha l'obiettivo di dotare gli studenti di strumenti teorici ed operativi per lo studio e la risoluzione di problemi di ottimizzazione su grafi. Vengono inizialmente costruite le basi teoriche necessarie per la formulazione di modelli e strategie risolutive (teoria dei grafi, generalità sulla teoria dell'ottimizzazione, richiami di teoria degli algoritmi e della complessità computazionale). Successivamente, partendo da una serie di problemi reali e complessi, si sviluppa la teoria per la loro analisi, si costruiscono gli algoritmi relativi e si verifica la loro efficienza ed efficacia, sia dal punto di vista teorico sia da quello operativo, attraverso applicazioni al computer. Le competenze acquisite dagli studenti consistono nella capacità di "problem solving" per problemi con variabili discrete e nel miglioramento e consolidamento delle capacità di progettazione di algoritmi e di programmazione.

Il corso è attivo presso il Corso di Laurea in Matematica del Dipartimento di Matematica e Fisica dell'Università degli Studi Roma Tre ed è destinato agli studenti iscritti al terzo anno della laurea triennale o agli studenti della laurea Magistrale; il corso di Informatica Generale 1 (IN110) fornisce le necessarie competenze sulla programmazione in linguaggio C e sull'uso del calcolatore e del sistema operativo Linux, prerequisito indispensabile per poter seguire proficuamente il corso di Ottimizzazione Combinatoria.

Programma del corso

Di seguito si riporta un elenco degli argomenti trattati nel corso; tale programma potrà subire delle variazioni sulla base dell'effettivo svolgimento delle lezioni e delle esercitazioni.

Teoria dei grafi
Grafo, grafo orientato, albero, albero libero e con radice, connessione, connessione forte, aciclicità; isomorfismi tra grafi, planarità, Teorema di Kuratowski, formula di Eulero; colorazione di grafi, numero cromatico, polinomio cromatico; cammini euleriani, circuiti hamiltoniani.
Teoria degli algoritmi e dell'ottimizzazione
Algoritmi, programmazione strutturata, complessità computazionale di un algoritmo, classi di complessità per problemi, le classi P, NP, NP-completo, NP-hard; problemi di decizione, di ricerca, di enumerazione e di ottimizzazione; problemi di programmazione non lineare, di programmazione convessa, di programmazione lineare e di programmazione lineare intera; problemi di ottimizzazione combinatoria.
Problemi di ottimizzazione su grafi e reti di flusso
Visita di grafi, verifica di proprietà fondamentali (connessione, connessione forte, presenza di cicli, ecc.); albero ricoprente di peso minimo, algoritmo di Kruskal e di Prim; ricerca di cammini minimi, algoritmi di Dijkstra, Bellman-Ford, Floyd-Warshall; calcolo del flusso massimo su una rete, algoritmi di Ford-Fulkerson e di Edmonds-Karp, teorema del Flusso Massimo-Taglio Minimo. Partizionamento di grafi in componenti connesse. Problemi di matching, il Problema del Matrimonio Stabile.

È disponibile il programma del corso IN440Documento in formato PDF per l'a.a. 2017/2018.

Organizzazione delle lezioni

Il corso si svolge nel primo semestre (settembre-dicembre 2017) dell'anno accademico 2017/2018. Si tengono due lezioni in aula a settimana, il mercoledì in aula 211 dalle ore 9:00 alle ore 11:00 e il giovedì in Aula 311 dalle ore 14:00 alle ore 16:00. Sono parte integrante del corso le esercitazioni nel laboratorio informatico, che si tengono a settimane alterne il venerdì dalle ore 9:00 alle ore 11:00. Durante le ore di laboratorio saranno sviluppati dei programmi in linguaggio C in ambiente Linux e si approfondirà l'utilizzo dell'ambiente di calcolo Mathematica per lo studio di problemi di ottimizzazione combinatoria.

Si segnala che tutti gli studenti iscritti all'Università Roma Tre possono ottenere gratuitamente una licenza del software Mathematica, grazie alla convenzione stipulata tra l'Ateneo e la Wolfram Research (azienda produttrice del software Mathematica). Maggiori informazioni per il download del software per le diverse versioni di sistema operativo (Microsoft Windows, Apple OS X, Linux) sono disponibili sul sito dell'Università Roma Tre all'indirizzo http://asi.uniroma3.it/page.php?page=convenzio4.

Esami

La valutazione finale è costituita da un esame orale sugli argomenti trattati nell'ambito del corso; è parte integrante della prova orale la discussione di una tesina realizzata da ciascuno studente durante la seconda parte del corso. La tesina prevede l'implementazione di algoritmi per la soluzione di uno specifico problema di ottimizzazione assegnato dal docente.