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 Python e si approfondirà l'utilizzo dell'ambiente di calcolo Mathematica per lo studio di problemi di ottimizzazione combinatoria.

Le attività didattiche del corso di Ottimizzazione Combinatoria (IN440) per l'anno accademico 2018/2019 sono terminate. Rimane attivo il ricevimento degli studenti, ogni venerdì dalle ore 8:00 alle ore 9:00 nella stanza 301, su appuntamento via e-mail.

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 (Appunti sul linguaggio Python Formato PDF): 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.
Lezione n. 9 - venerdì 22 marzo 2019
Applicazioni dell'algoritmo per la visita in profondità di un grafo: verifica dei punti di articolazione su un grafo, calcolo delle componenti fortemente connesse di un grafo orientato, calcolo dell'ordinamento topologico dei vertici su un grafo orientato aciclico, pseudo codice, 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.
Lezione n. 10 - lunedì 25 marzo 2019
Alberi binari di ricerca: operazioni di inserimento, ricerca, ordinamento, minimo e massimo; pseudo codifica degli algoritmi e stima della complessità computazionale.
Il problema dell'albero ricoprente di peso minimo (MST - Minimum Spanning Tree), esempi; algoritmo generico per la soluzione del problema MST; la tecnica greedy, la sottostruttura ottima della soluzione del problema, 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 - mercoledì 27 marzo 2019
[LAB] Utilizzo di librerie grafiche per produrre grafici di funzione, diagrammi ed altri output di tipo grafico in Python; la libreria MatPlotLib e i moduli pylab e pyplot; la libreria matematica NumPy; la libreria GraphicsDocumento in formato PDF; esempiDocumento in formato PDF, codifica di un programma per la visualizzazione di una spirale, codifica di un programma per la visualizzazione dell'insieme di Mandelbrot.
Lezione n. 12 - venerdì 29 marzo 2019
Ancora sull'algoritmo di Kruskal per il problema del minimum spanning tree, strutture dati per rappresentare in modo efficiente una collezione di insiemi disgiunti, complessità dell'algoritmo.
Algoritmo di Prim per il problema del minimum spanning tree, presentazione della strategia risolutiva, pseudo-codice dell'algoritmo, analisi della complessità computazionale, esempi.
Lezione n. 13 - lunedì 1 aprile 2019
Algoritmo di Prim per il problema del minimum spanning tree: un esempio completo.
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. 14 - mercoledì 3 aprile 2019
[LAB] Utilizzo della libreria pythonds per la codifica di algoritmi su grafi in Python. Presentazione delle classi e i metodi della libreria, codifica di una funzione per la costruzione del grafo completo, del grafo ciclico Cn, del grafo random, del grafo bipartito completo; codifica del programma per la visita in ampiezza di un grafo. Vedi anche gli appunti sulla codifica di Algoritmi su grafi in linguaggio Python Documento in formato PDF.
Lezione n. 15 - venerdì 5 aprile 2019
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. 16 - lunedì 15 aprile 2019
Ancora sull'algoritmo di Bellman-Ford, pseudo-coifica ed esempi; 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'uso di una coda di priorità (heap), esempi.
Lezione n. 17 - mercoledì 17 aprile 2019
[LAB] 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 illustrare l'uso delle funzioni sui grafi e gli appunti sintetici Formato PDF su alcuni funzioni per i grafi di Mathematica 11).
Lezione n. 18 - lunedì 29 aprile 2019
Il problema del calcolo del cammino di costo minimo tra tutte le coppie di vertici di un grafo pesato. La programmazione dinamica, proprietà del problema, descrizione generale di un algoritmo di programmazione dinamica.
Algoritmo di programmazione dinamica per il calcolo dei cammini di costo minimo tra tutte le coppie di vertici di un grafo pesato (“AllPairsShortestPath”); pseudo-codifica dell'algoritmo, analisi della complessità computazionale, esempi.
Miglioramento della complessità dell'algoritmo “AllPairsShortestPath”, pseudo-codifica dell'algoritmo “FastAllPairsShortestPath”, analisi della complessità, esempi.
Lezione n. 19 - venerdì 3 maggio 2019
Algoritmo di Floyd-Warshall per il calcolo dei cammini di costo minimo su un grafo pesato; pseudo-codifica dell'algoritmo, analisi della complessità computazionale, esempi; estensione dell'algoritmo per il calcolo dei cammini (e non solo del costo), pseudo-codifica di un algoritmo ricorsivo per la stampa di un cammino; utilizzo dell'algoritmo di Floyd-Warshall per il calcolo della chiusura transitiva di un grafo. Esempi.
Riepilogo sugli algoritmi di cammino minimo, confronto della complessità computazionale dei diversi algoritmi presentati nelle lezioni precedenti (dispensa n.7 Formato PDF).
Lezione n. 20 - lunedì 6 maggio 2019
Reti di flusso, capacità, definizione e proprietà della funzione flusso, rete residua, cammino aumentante, taglio di una rete di flusso, capacità del taglio di una rete, Teorema del flusso massimo e del taglio minimo, algoritmo di Ford-Fulkerson, esempi.
Valutazione della complessità computazionale dell'algoritmo di Ford-Fulkerson, ottimizzazione dell'algoritmo attraverso l'uso della visita in ampiezza per l'identificazione dei cammini aumentanti; algoritmo di Edmonds-Karp.
Problemi di matching massimo su grafi; il problema del matching massimale su un grafo bipartito e la soluzione mediante un algoritmo di calcolo del massimo flusso su una rete.
Lezione n. 21 - mercoledì 8 maggio 2019
[LAB] Esercizi di programmazione in Python: costruzione del triangolo di Tartaglia; generazione di un grafo random, esportazione della matrice di adiacenza su file e importazione/visualizzazione del grafo con Mathematica; generazione di un grafo random con Mathematica, esportazione della matrice di adiacenza su file, caricamento del file in un programma Python e visualizzazione del grafo (vedi anche le slide con la traccia degli esercizi Documento in formato PDF).
Lezione n. 22 - venerdì 10 maggio 2019
Preflusso, eccesso di flusso e vertici traboccanti, algoritmo Push-Relabel per il problema del flusso massimo su una rete, pseudo-codifica dell'algoritmo, esempi.
Lezione n. 23 - lunedì 13 maggio 2019
Il problema del partizionamento di un grafo in p componenti connesse, problemi di ottimizzazione combinatoria legati al partizionamento di un grafo, problemi di equipartizione, di clustering, di taglio della partizione e di partizionamento continuo.
Funzioni obiettivo per problemi di equipartizione: norma L1, norma L2, norma L, max-min, min-max, MUP (most uniform partition), esempi. Funzioni obiettivo per problemi di clustering: massimo diametro, somma delle distanze, minimo split, somma delle distanze tra cluster, esempi.
Lezione n. 24 - mercoledì 15 maggio 2019
[LAB] Esercizi di programmazione in Python: visualizzazione di grafi random.
Lezione n. 25 - venerdì 17 maggio 2019
Complessità computazionale dei principali problemi di ottimizzazione combinatoria per equipartizione e clustering di cammini, alberi e grafi generici; tecniche algoritmiche per la soluzione dei problemi (ottimizzazione su reti, migrazione di gruppi, simulated annealing, semi, programmazione dinamica, shifting dei tagli, programmazione lineare).
Il problema del p-partizionamento di un albero con funzione obiettivo “Max-Min”, formalizzazione del problema, pseudo-codifica di un algoritmo risolutore, esempi.
Lezione n. 26 - lunedì 20 maggio 2019
Partizionamento di un cammino con funzione obiettivo “Norma L”, formalizzazione del problema, esempi, pseudo-codifica dell'algoritmo PathShifting.
Lezione n. 27 - mercoledì 22 maggio 2019
[LAB] Esercizi di programmazione in Python: letti in input quattro interi n, m, p, q > 0, genera un albero random con n vertici e al più m figli per ogni vertice; assegna ad ogni vertice dell'albero un peso random minore di q. Calcola tutte le partizioni dell'albero in p componenti connesse (sotto-alberi) e determina la partizione con il minimo valore per il peso massimo di una componente.
Lezione n. 28 - venerdì 24 maggio 2019
Dimostrazione della correttezza e della complessità computazionale dell'algoritmo PathShifting per il partizionamento di cammini pesati con funzione obiettivo “Norma L” (dispensa n.10 Formato PDF).
Il problema del “matrimonio stabile” (stable marriage problem), formalizzazione del problema, condizione di instabilità, matching, matching massimale, three dimensional matching, generalizzazione del problema ad insiemi di cardinalità diversa e con liste di preferenza incomplete, applicazioni, esempi;
Lezione n. 29 - lunedì 27 dicembre 2019
Ancora sul problema del “matrimonio stabile”, approccio dei “divorzi successivi”, pseudo-codifica dell'algoritmo, esempi.
Algoritmo di Gale e Shapley per la soluzione del problema del matrimonio stabile, pseudo-codice, analisi della complessità, esempi, dimostrazione della correttezza dall'algoritmo (dispensa n.11 Formato PDF).
Lezione n. 30 - mercoledì 29 maggio 2019
[LAB] Esercizi di programmazione in Python: letti in input quattro interi n, m, p, q > 0, genera un albero random con n vertici e al più m figli per ogni vertice; assegna ad ogni vertice dell'albero un peso random minore di q. Calcola tutte le partizioni dell'albero in p componenti connesse (sotto-alberi) e determina la partizione con il minimo valore per il peso massimo di una componente.
Lezione n. 31 - venerdì 31 maggio 2019
Codici di Huffman: codifica dell'informazione per ridurre la dimensione del dato; codifica prefissa; il Codice di Huffman, presentazione dell'algoritmo per la costruzione del codice, esempi.
Algoritmi approssimanti: calcolo di una soluzione approssimata per la risoluzione di problemi di ottimizzazione combinatoria NP-completi o NP-hard; il rapporto di approssimazione e la stima dell'errore dell'algoritmo; esempio sul problema VertexCover: l'algoritmo VertexCoverApprossimato, pseudo-codice, esempi, calcolo della stima dell'errore; algoritmo GreedyVertexCoverApprossimato; il problema SetCover (copertura di insiemi), l'algoritmo approssimato GreedySetCover.
Riepilogo degli argomenti del corso e riferimenti per la preparazione dell'esame (vedi anche Riepilogo degli argomenti del corso IN440 Documento in formato PDF).