Diario delle lezioni
Il corso si svolge nel secondo semestre (febbraio-maggio) dell'anno accademico 2022/2023. Le lezioni e le esercitazioni si tengono secondo il seguente calendario: il lunedì e il martedì dalle ore 8:30 alle ore 10:30 in Aula A (edificio di Fisica), il mercoledì dalle ore 8:30 alle ore 10:30 (esercitazioni) nel laboratorio informatico dell'edificio aule di Matematica. Durante le ore di esercitazione 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 2022/2023 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
In questa pagina sarà riportata una breve sintesi degli argomenti trattati durante le lezioni e le esercitazioni.
- Lezione n. 1 - lunedì 20 febbraio 2023
- Presentazione del corso, bibliografia, orario di riferimento, orario delle lezioni e delle esercitazioni, modalità d'esame (Presentazione del corso
). - Ottimizzazione e Ottimizzazione Combinatoria, insieme delle soluzioni ammissibili e funzione obiettivo, fenomeni di esplosione combinatoria, esempi. Algoritmi, dimostrazione di correttezza, richiami sulle regole della programmazione strutturata.
- Lezione n. 2 - martedì 21 febbraio 2023
- 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.
- 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.
- Lezione n. 3 - lunedì 27 febbraio 2023
- 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-SUM ≤p PARTITION e PARTITION ≤p SUBSET-SUM; il problema “P=NP” (dispensa n.1 , Slide su algoritmi e complessità computazionale ).
- 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. 4 - martedì 28 febbraio 2023
- 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; coefficiente binomiale, triangolo di Tartaglia. Cenni sui Quadrati Latini e sul gioco del Sudoku; alcuni problemi di combinatoria legati ai Quadrati Latini.
- 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 , Slide su insiemi e calcolo combinatorio su insiemi finiti ).
- 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; diametro, raggio e centro di un grafo, esempi.
- 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.
- 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.
- Lezione n. 5 - lunedì 6 marzo 2023
- Supergrafi, espansioni, Teorema di Kuratowski; esempi. Cenni sulla colorazione dei grafi, sulla colorazione di grafi planari e sul Teorema dei Quattro Colori (dispensa n.4 , slide sulla Teoria dei grafi ).
- 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.
- Applicazioni dell'algoritmo per la visita in profondità di un grafo: calcolo delle componenti fortemente connesse di un grafo orientato, calcolo dell'ordinamento topologico dei vertici su un grafo orientato aciclico, pseudo codice, complessità, esempi.
- Lezione n. 6 - martedì 7 marzo 2023
- Applicazioni dell'algoritmo per la visita in profondità di un grafo: verifica dei punti di articolazione e dei ponti su un grafo, pseudo codice, esempi. Confronto tra algoritmo di visita in ampiezza BFS e algoritmo di visita in profondità in forma iterativa: utilizzo delle strutture dati di coda e di pila.
- 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. Operazioni di inserimento, ricerca, ordinamento, minimo e massimo; pseudo codifica degli algoritmi e stima della complessità computazionale (slide sugli algoritmi elementari su grafi ).
- Problemi di ottimizzazione, programmazione lineare, programmazione lineare intera; formulazione standard di un problema di programmazione lineare; cenni sul metodo del simplesso; formulazione di alcuni problemi di ottimizzazione combinatoria come problemi di programmazione lineare intera (dispensa n.5 , Slide sui problemi di programmazione matematica ).
- Lezione n. 7 - mercoledì 8 marzo 2023
- Introduzione al linguaggio di programmazione Python, ambienti di sviluppo on-line repl.it e Jupyter e interprete dei comandi Python. Tipi di dato elementari, strutture dati di base, le liste; le strutture algoritmiche “if-else”, “while” e “for” (Introduzione al linguaggio Python , Dispense introduttive al linguaggio Python ).
- Lezione n. 8 - lunedì 13 marzo 2023
-
- 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.
- 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. 9 - martedì 14 marzo 2023
- Struttura dati di heap per la gestione di code di priorità gli algoritmi per l'inserimento di un elemento, l'estrazione dell'elemento di priorità massima e l'innalzamento della priorità di un elemento.
- Algoritmo di Sollin-Boruvka per il problema MST, presentazione della strategia risolutiva, pseudo-codice dell'algoritmo, esempi (slide sugli alberi ricoprenti di costo minimo ).
- 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.
- 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.
- Lezione n. 10 - mercoledì 15 marzo 2023
- Esercizi elementari in Python, esercizi su liste/array, codifica del programma per la generazione delle stringhe binarie con n elementi, la visualizzazione di tutte le permutazioni degli elementi di un insieme e la visualizzazione di tutte le combinazioni in classi di k elementi (testo e soluzione degli esercizi ).
- Lezione n. 11 - lunedì 20 marzo 2023
- 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.
- Algoritmo di programmazione dinamica per il calcolo dei cammini di costo minimo tra tutte le coppie di vertici di un grafo pesato; 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. 12 - martedì 21 marzo 2023
- 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 , slide sui problemi e gli algoritmi per il calcolo dei cammini di costo minimo ).
- Cenni sui principi fondamentali della programmazione a oggetti (OOP - object oriented programming): classi di oggetti, oggetti, metodi costruttori, metodi setter/getter, incapsulamento, ereditarietà e polimorfismo; esempi.
- Lezione n. 13 - mercoledì 22 marzo 2023
- Librerie per la grafica in Python: MatPlotLib e Graphix, presentazione delle principali funzioni ed esempi (slide sulle librerie grafiche in Python ).
- Lezione n. 14 - lunedì 27 marzo 2023
- 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. 15 - martedì 28 marzo 2023
- Preflusso, eccesso di flusso e vertici traboccanti, algoritmo Push-Relabel per il problema del flusso massimo su una rete, pseudo-codifica dell'algoritmo, esempi (slide sul problema del massimo flusso su una rete ).
- 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 Vedi anche gli appunti sulla codifica di Algoritmi su grafi in linguaggio Python .
- Lezione n. 16 - mercoledì 29 marzo 2023
- Codifica di una funzione per la costruzione del grafo ciclico Cn, del grafo random, del grafo bipartito completo, visualizzazione di un grafo random con la libreria graphics. Vedi anche gli appunti sulla codifica di Algoritmi su grafi in linguaggio Python e le slide con le soluzioni degli esercizi.
- Lezione n. 17 - lunedì 3 aprile 2023
- Esercizi di programmazione in Python su grafi: visita in un grafo in ampiezza e in profondità; calcolo dei cammini di costo minimo fra tutte le coppie di vertici di un grafo random con pesi non negativi assegnati agli spigoli (slide con le soluzioni degli esercizi).
- Lezione n. 18 - martedì 4 aprile 2023
- 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.
- 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. 19 - mercoledì 5 aprile 2023
- Panoramica ed esempi sull'uso del software Mathematica per la rappresentazione di grafi e l'esecuzione di operazioni su grafi (dispensa n.3 ; vedi anche il notebook di Mathematica utilizzato per illustrare l'uso delle funzioni sui grafi e le slide su Mathematica per l'utilizzo di alcune funzioni sui grafi).
- Costruzione di una libreria di funzioni in Python; caricamento ed esportazione di matrici di adiacenza con Mathematica, export su file della matrice di adiacenza di un grafo in Python.
- Lezione n. 20 - venerdì 12 aprile 2023
- Esercizi di programmazione in Python per la costruzione della matrice di adiacenza di un grafo e la lettura e scrittura delle matrici su file di testo sequenziali (vedi slide con gli esercizi )
- Lezione n. 21 - mercoledì 26 aprile 2023
- Introduzione al linguaggio Latex per la composizione di testi: linguaggi di mark-up del testo, 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 (slide introduttive al linguaggio Latex ).
- Lezione n. 22 - martedì 2 maggio 2023
- Partizionamento di un cammino con funzione obiettivo “Norma L∞”, formalizzazione del problema, esempi, pseudo-codifica dell'algoritmo PathShifting.
- Dimostrazione della correttezza e della complessità computazionale dell'algoritmo PathShifting per il partizionamento di cammini pesati con funzione obiettivo “Norma L∞” (dispensa n.10 , slide sul partizionamento di grafi ).
- Lezione n. 23 - mercoledì 3 maggio 2023
- Esercizi di programmazione in Python per la generazione di alberi casuali e la visualizzazione di alberi con radice (slide con gli esercizi )
- Lezione n. 24 - lunedì 8 maggio 2023
- Esercizi di programmazione in Python per la costruzione di tutte le partizioni in p componenti connesse (sotto-alberi) di un albero T generato in modo casuale, con pesi non negativi assegnati agli spigoli. Tra tutte le partizioni generate, identificare quella che ottimizza la funzione obiettivo calcolata come max(W) − min(W) (slide con gli esercizi )
- Lezione n. 25 - martedì 9 maggio 2023
- 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;
- 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
, slide sul problema del matrimonio stabile ). - Lezione n. 26 - mercoledì 10 maggio 2023
- Esercizi di programmazione in Python: codifica dell'algoritmo di Floyd-Warshall per il calcolo dei cammini di costo minimo tra tutte le coppie di vertici del grafo (slide con gli esercizi ).
- Lezione n. 27 - lunedì 15 maggio 2023
- Algoritmi su grafi in Python: codifica in linguaggio Python dell'algoritmo per il calcolo delle componenti fortemente connesse di un grafo orientato casuale (i sorgenti del programma sono su Teams, nei file del gruppo IN440 - slide con gli esercizi ).
- Lezione n. 28 - martedì 16 maggio 2023
- 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 (slide sugli algoritmi approssimanti ).
- Lezione n. 29 - mercoledì 17 maggio 2023
- Codifica in linguaggio Python degli algoritmi per il calcolo esatto e approssimato della soluzione del problema Vertex Cover su grafi random (il sorgente dei programmi è su Teams, tra i file del gruppo IN440 - slide con gli esercizi ).
- Lezione n. 30 - lunedì 22 maggio 2023
- 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 (slide sui codici di Huffman ).
- Riepilogo degli argomenti del corso e riferimenti per la preparazione dell'esame (vedi anche Riepilogo degli argomenti del corso IN440 ).