Diario delle lezioni

Il corso si svolge nel primo semestre (settembre-dicembre) dell'anno accademico 2017/2018. Si tengono due lezioni in aula a settimana, il mercoledì in aula 211 dalle 9:00 alle 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 vengono 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.

Le lezioni del corso di Ottimizzazione Combinatoria (IN440) per l'a.a. 2017/2018 sono iniziate giovedì 28 settembre 2017 alle ore 14:00 in aula 311.

Sintesi degli argomenti trattati durante le lezioni

Lezione n. 1 - giovedì 28 settembre 2017
Presentazione del corso, bibliografia, orario di riferimento, orario delle lezioni e delle esercitazioni, modalità d'esame.
Ottimizzazione e Ottimizzazione Combinatoria, insieme delle soluzioni ammissibili e funzione obiettivo, limiti dei metodi di ricerca esaustiva, fenomeni di esplosione combinatoria, esempi. Algoritmi, dimostrazione di correttezza, richiami sulle regole della programmazione strutturata.
Lezione n. 2 - mercoledì 4 ottobre 2017
Cenni sulla teoria della calcolabilità, Tesi di Church-Turing, problemi indecidibili e il “problema della fermata” di Turing. Complessità computazionale di un algoritmo, caratteristiche delle funzioni di complessità; gli insiemi O(f(n)), Ω(f(n)) e Θ(f(n)), proprietà che legano tra loro i tre insiemi. Complessità computazionale di un problema; esempio della complessità computazionale del problema dell'ordinamento; algoritmi ottimi.
Problemi trattabili e intrattabili, la classe P dei problemi polinomiali; problemi con complessità super-polinomiale. Algoritmi “non deterministici”, l'istruzione “choice”, esempi per la soluzione del problema dell'ordinamento di una sequenza e del cammino di lunghezza minima su un grafo; la classe dei problemi NP.
Lezione n. 3 - giovedì 5 ottobre 2017
Riducibilità in tempo polinomiale di un problema ad un altro, transitività della riducibilità in tempo polinomiale, la classe dei problemi NP-Completi, problemi decisionali associati a problemi di ottimizzazione.
Schema generale della dimostrazione di NP-completezza di un problema. Cenni sul Teorema di Cook (SAT è NP-Completo). Esempi di problemi NP-Completi: SUBSET-SUM, PARTITION, 3DM. Dimostrazione che SUBSET-SUMp PARTITION e PARTITIONp SUBSET-SUM (dispensa n.1 Formato PDF).
Lezione n. 4 - mercoledì 11 ottobre 2017
Insiemi, cardinalità di un insieme, insieme delle parti, algoritmo per la generazione delle stringhe binarie di lunghezza n.
Permutazioni degli elementi di un insieme, algoritmo per la generazione delle permutazioni degli elementi di un insieme di cardinalità n, pseudo-codifica, esempi; disposizioni semplici di k elementi di un insieme di cardinalità n, numero delle disposizioni semplici, disposizioni con ripetizioni; combinazioni semplici di k elementi su un insieme di cardinalità n, numero delle combinazioni semplici, algoritmo per la generazione di tutti i sottoinsiemi di cardinalità k di un insieme A di cardinalità n.
Lezione n. 5 - giovedì 12 ottobre 2017
Il “rompicapo” del Sudoku, come caso particolare del concetto di quadrato latino; problemi combinatori legati al gioco del Sudoku, configurazioni equivalenti per rotazione o per isomorfismi, un algoritmo ricorsivo per la soluzione del gioco del Sudoku, pseudo-codifica dell'algoritmo (dispensa n.2 Formato PDF).
Richiami di Teoria dei Grafi: definizione di grafo orientato e non orientato, cammino, ciclo, lunghezza di un cammino, grafi k-regolari, grafi completi, grafi nulli, vertici universali, insiemi di vertici dominanti, cammino, ciclo, distanza tra due vertici.
Cicli hamiltoniani, Teorema di Dirac, esempi; il problema dei ponti di Königsberg, cammini euleriani, cicli euleriani, Teorema di Eulero, esempi.