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 Algoritmi e Strutture Dati (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 decisione, 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 IN440
per l'a.a. 2022/2023.
Organizzazione delle lezioni
Il corso si svolge nel secondo semestre (febbraio-maggio 2023) dell'anno accademico 2022/2023. Si tengono due lezioni e un'esercitazione a settimana, il lunedì e il martedì dalle ore 8:30 alle ore 10:30 in aula A presso l'edificio di Fisica, il mercoledì dalle ore 8:30 alle ore 10:30 presso il laboratorio informatico nell'edificio aule di Matematica. Durante le ore di esercitazione saranno sviluppati dei programmi in linguaggio Python 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 https://www.uniroma3.it/servizi/software-in-convenzione/wolfram-mathematica/.
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.
Per l'a.a. 2022/2023 gli esami orali si terranno nelle seguenti date:
- Appello A: venerdì 23 giugno 2023, ore 14:00 - 18:00, Aula M4
- Appello B: venerdì 28 luglio 2023, ore 9:00 - 12:00, Aula M4
- Appello X: venerdì 15 settembre 2023, ore 9:00 - 12:00, Aula M4
- Appello C: venerdì 26 gennaio 2024, ore 9:00 - 12:00, Aula M4
Gli studenti interessati a sostenere l'esame di IN440 sono pregati di contattare il docente per richiedere l'assegnazione di una tesina da presentare almeno una settimana prima della prova d'esame. Per la redazione della tesina scritta si suggerisce di utilizzare il seguente modello in Latex.
Per sostenere l'esame e verbalizzare l'esito della prova è necessario registrarsi sul sistema GOMP - Portale dello Studente. In mancanza della prenotazione l'esame non potrà essere materialmente registrato sul verbale.