Home page di Marco Liverani

Corso di Ottimizzazione Combinatoria - IN440

“[...] da allora assunsi la mia "filosofia": mi occuperò soprattutto
degli studenti più deboli e parlerò sempre, a voce alta, a quelli dell'ultimo banco.”
−− Mario Fiorentini

Il corso di Ottimizzazione Combinatoria (IN440) ha l'obiettivo di dotare gli studenti di strumenti teorici ed operativi per l'ottimizzazione di problemi nel discreto. 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. Le competenze acquisite dagli studenti consistono nella capacità di "problem solving" per problemi su grafi, alberi ed altre strutture combinatorie 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 e 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, prerequisiti essenziali per il corso di Ottimizzazione Combinatoria.

Sito web del corso

All'indirizzo http://www.mat.uniroma3.it/users/liverani/IN440 è disponibile il sito web dedicato alla didattica del corso di Ottimizzazione Combinatoria. Sul sito è possibile trovare:

• una descrizione del corso e dei suoi contenuti generali;
• il diario delle lezioni tenute durante l'anno accademico in corso, con numerosi link ad appunti e alle soluzioni degli esercizi proposti durante le esercitazioni;
• una raccolta di esercizi svolti in linguaggio C;
• i riferimenti bibliografici utili per la preparazione dell'esame e i link per l'accesso alle dispense del corso;
• la bacheca delle comunicazioni agli studenti.

Programma indicativo del corso

Il corso si articola su tre temi principali:

Teoria dei grafi

Grafi, grafi orientati, alberi, alberi liberi e con radice, connessione, connessione forte, aciclicità; isomorfismo 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. Codici di Huffman.

È disponibile il programma ufficiale del corso per l'anno accademico 2020/2021.