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.
Lezione n. 6 (laboratorio) - venerdì 13 ottobre 2017
Richiami sulla modalità con cui può essere costruita e compilata nel programma una libreria di funzioni di utilità generale; cenni sull'ottimizzazione del codice di un programma e sull'opzione di ottimizzazione del codice binario eseguibile; cenni sull'uso del debugger gdb; esempi.
Richiami sulle strutture in linguaggio C, le istruzioni struct e typedef. Strutture dati per la definizione di liste e grafi. Implementazione in linguaggio C di alcune funzioni di libreria di utilità per l'elaborazione di grafi: impila (aggiunta di un elemento ad una pila), leggiLista, stampaLista, leggiGrafo, stampaGrafo, esempi (slide di sintesi sulle funzioni di libreria Formato PDF).
Lezione n. 7 - mercoledì 18 ottobre 2017
Elementi di Teoria dei Grafi: sottografi, sottografi indotti da un insieme di vertici, clique di un grafo, insiemi indipendenti, cenni sul comportamento di un grafo G sottoposto all'azione dell'operatore clique iterato Kp(G); diametro, raggio e centro di un grafo, esempi. Grafi bipartiti e multipartiti, grafi multipartiti completi. Isomorfismi tra grafi, grafi planari.
Lezione n. 8 - venerdì 20 ottobre 2017
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 di un grafo.
Lezione n. 9 - mercoledì 25 ottobre 2017
Algoritmo generale per la visita di un grafo, varianti dell'algoritmo generale per la visita in ampiezza (Breadth First Search) e in profondità (Depth First Search) di un grafo; complessità degli algoritmi di visita.
Applicazioni della visita di un grafo: verifica della connessione, componenti connesse di un grafo non orientato; aciclicità di un grafo non orientato; ordinamento topologico; distanze tra vertici del grafo e cammino minimo tra due vertici. Esempi. Calcolo delle componenti fortemente connesse di un grafo orientato, pseudo-codifica dell'algoritmo, complessità computazionale dell'algoritmo, esempi.
Lezione n. 10 - giovedì 26 ottobre 2017
Applicazioni dell'algoritmo di visita in profondità di un grafo: individuazione dei punti di articolazione, esempi.
Il concetto di indice di un archivio, alberi binari di ricerca come struttura dati elementare per la rappresentazione di un indice; proprità degli alberi binari di ricerca.
Il problema dell'albero ricoprente di peso minimo (MST - Minimum Spanning Tree), esempi; algoritmo generico per la soluzione del problema MST; la tecnica greedy, esempi.
Algoritmo di Kruskal per il problema dell'albero ricoprente di peso minimo, pseudo-codice dell'algoritmo, analisi della complessità computazionale, modalità di rappresentazione della collezione di insiemi disgiunti per l'implementazione ottimale delle operazioni “makeSet”, “findSet” e “unionSet”; esempi.
Lezione n. 11 (laboratorio) - venerdì 27 ottobre 2017
Ancora sull'uso della libreria di funzioni per la codifica di algoritmi su alberi, grafi e liste.
Panoramica ed esempi sull'uso del software Mathematica per la rappresentazione di grafi e l'esecuzione di operazioni su grafi (dispensa n.3 Formato PDF; vedi anche il notebook di Mathematica utilizzato in laboratorio per dimostrare l'uso delle funzioni sui grafi e gli appunti sintetici Formato PDF su alcuni funzioni per i grafi di Mathematica 11).
Lezione n. 12 - giovedì 2 novembre 2017
Algoritmo di Prim per il problema del minimum spanning tree, presentazione della strategia risolutiva, pseudo-codice dell'algoritmo, analisi della complessità computazionale, esempi.
Algoritmo di Sollin-Boruvka per il problema MST, presentazione della strategia risolutiva, pseudo-codice dell'algoritmo, esempi.
Problemi di ottimizzazione, programmazione lineare, programmazione lineare intera; formulazione standard di un problema di programmazione lineare; cenni sul metodo del simplesso; formulazione del problema del minimum spanning tree come problema di programmazione lineare intera (dispensa n.5 Formato PDF).
Lezione n. 13 (laboratorio) - venerdì 3 novembre 2017
Introduzione al linguaggio Latex per la composizione di testi: definizione del tipo di documento, struttura del documento, caratterizzazione degli stili del testo, formule matematiche, figure, pseudo-codice di algoritmi, riferimenti incrociati, riferimenti bibliografici, esempi.
Lezione n. 14 - mercoledì 15 novembre 2017
Il problema del cammino minimo su un grafo orientato con pesi assegnati agli spigoli, varianti del problema (sorgente singola, destinazione singola, cammini minimi tra tutte le coppie di vertici, cammino minimo tra una coppia di vertici), proprietà della distanza tra due vertici, proprietà di “sottostruttura ottima” del problema e delle sue soluzioni; algoritmo di Dijkstra, pseudo-codifica dell'algoritmo, analisi della complessità computazionale, esempi.
Algoritmo di Bellman-Ford per la soluzione del problema del cammino di costo minimo da una sorgente singola su un grafo pesato, pseudo-codifica dell'algoritmo, analisi della complessità computazionale, esempi.
Lezione n. 15 - giovedì 16 novembre 2017
Una variante dell'algoritmo di Bellman-Ford nel caso di grafi orientati aciclici (DAG) con l'ordinamento topologico dei vertici, pseudo-codifica dell'algoritmo, analisi della complessità computazionale, esempi. Un algoritmo per l'ordinamento topologico di un grafo orientato aciclico, studio della complessità computazionale e miglioramento dell'efficienza con l'introduzione di alcune strutture dati, esempi.