Diario delle lezioni

Il corso si svolge nel secondo semestre (febbraio-maggio) dell'anno accademico 2018/2019. Si tengono due lezioni in aula a settimana, il lunedì e il venerdì in aula M5 dalle ore 9:00 alle ore 11:00. Sono parte integrante del corso le esercitazioni nel laboratorio informatico, che si tengono a settimane alterne il mercoledì dalle ore 14:00 alle ore 16: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. 2018/2019 sono iniziate lunedì 25 febbraio 2019 alle ore 9:00 in aula M5.

Sintesi degli argomenti trattati durante le lezioni

Lezione n. 1 - lunedì 25 febbraio 2019
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 - venerdì 1 marzo 2019
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 - lunedì 4 marzo 2019
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 - venerdì 8 marzo 2019
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. Cenni sui Quadrati Latini e sul gioco del Sudoku; alcuni problemi di combinatoria legati ai Quadrati Latini.
Lezione n. 5 - lunedì 11 marzo 2019
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.
Sottografi, sottografi indotti da un insieme di vertici, clique di un grafo, cenni sul comportamento di un grafo G sottoposto all'azione dell'operatore clique iterato Kp(G); diametro, raggio e centro di un grafo, esempi.
Lezione n. 6 - mercoledì 13 marzo 2019
[LAB] Introduzione al linguaggio di programmazione Python: regole sintattiche generali, variabili, tipi, oggetti, le strutture dati di lista, insieme, dizionario; istruzioni per l'implementazione delle strutture algoritmiche condizionale e iterativa; funzioni di input e di output; esempi ed esercizi (programma per la visualizzazione delle stringhe binarie di lunghezza n; programma per la visualizzazione delle permutazioni di un insieme di n elementi).
Lezione n. 7 - venerdì 15 marzo 2019
Elementi di Teoria dei Grafi: insiemi indipendenti, grafi multipartiti, grafi multipartiti completi, comportamento del grafo Kn, n, ..., n sottoposto all'azione dell'operatore K. Isomorfismi tra grafi.
Grafi planari, cenni sul Teorema della curva di Jordan, K5 e K3,3 non sono planari, supergrafi, espansioni, Teorema di Kuratowski; esempi (dispensa n.4 Formato PDF).
Algoritmi su grafi: algoritmo generico per la visita in ampiezza e in profondità di un grafo.
Lezione n. 8 - lunedì 18 marzo 2019
Algoritmo per la visita in ampiezza (Breadth First Search) e in profondità (Depth First Search) di un grafo; complessità degli algoritmi di visita, pseudo-codifica, esempi.
Applicazioni della visita di un grafo: verifica della connessione, componenti connesse di un grafo non orientato; aciclicità di un grafo non orientato; distanze tra vertici del grafo e cammino minimo tra due vertici. Esempi.