Diario delle lezioni
Il corso si svolge nel secondo semestre (febbraio-maggio) dell'anno accademico 2024/2025. Le lezioni e le esercitazioni si tengono secondo il seguente calendario: il martedì e il giovedì dalle ore 9:00 alle ore 11:00 in Aula L, il mercoledì dalle ore 11:00 alle ore 13:00 (esercitazioni) nel laboratorio informatico. 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 lezioni del corso di Ottimizzazione Combinatoria (IN440) per l'a.a. 2024/2025 sono iniziate martedì 25 febbraio 2025.
Sintesi degli argomenti trattati durante le lezioni
- Lezione n. 1 - martedì 25 febbraio 2025
- 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 - giovedì 27 febbraio 2025
- Cenni sulla teoria della calcolabilità, Macchina di Turing, esempi, codifica di una Macchina di Turing, Macchina di Turing Universale; 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.
- Lezione n. 3 - martedì 4 marzo 2025
- 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.
- Laboratorio n. 1 - mercoledì 5 marzo 2025
- 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. 4 - giovedì 6 marzo 2025
- 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
- Lezione n. 5 - martedì 11 marzo 2025
- 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.
- 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 ).
- Laboratorio n. 2 - mercoledì 12 marzo 2025
- 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. 6 - giovedì 13 marzo 2023
- 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.
- Lezione n. 7 - martedì 18 marzo 2025
- Clique di un grafo, cenni sul comportamento di un grafo G sottoposto all'azione dell'operatore clique iterato Kp(G); dimostrazione della K-divergenza dell'ottaedro n-dimensionale.
- 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.
- Colorazione di grafi, numero cromatico e polinomio cromatico di un grafo; cenni sul Teorema dei quattro colori e sulla colorazione di grafi planari (dispensa n.4 , slide sulla Teoria dei grafi ).
- Laboratorio n. 3 - mercoledì 19 marzo 2025
- Algoritmi per la generazione di numeri pseudo-casuali: algoritmo di von Neumann, algoritmo dei quadrati e algoritmo delle congruenze; moduli Python per la generazione di numeri pseudo-casuali (testo e soluzione degli esercizi ).
- Librerie per la grafica in Python: MatPlotLib e Graphix, presentazione delle principali funzioni ed esempi (slide sulle librerie grafiche in Python ).
- Lezione n. 8 - giovedì 20 marzo 2025
- Algoritmo generico per la visita di un grafo; specializzazione dell'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. 9 - martedì 25 marzo 2025
- 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, predecessore e successore, cancellazione; 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 ).
- Laboratorio n. 4 - giovedì 26 marzo 2025
- La libreria Python NetworkX per la rappresentazione di grafi: classi, metodi e funzioni principali della libreria, visualizzazione di grafi, codifica di algoritmi per la visita di grafi.
- Lezione n. 10 - giovedì 27 marzo 2025
- Grafi random e algoritmi per la loro generazione: modello di Erdös-Réni, modello di Barabasi-Albert, modello di Watts-Strogatz. Utilizzo di Jupyter notebook, esempi con l'utilizzo di NetworkX, visualizzazione di grafi.
- 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).
- Lezione n. 11 - martedì 1 aprile 2025
-
- 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.
- 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.
- Laboratorio n. 5 - mercoledì 2 aprile 2025
- 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 ).
- Codifica in Python dell'algoritmo di Kruskal per il calcolo dell'albero ricoprente di costo minimo (MST - minimum spanning tree).
- Lezione n. 12 - giovedì 3 aprile 2025
- 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. 13 - martedì 8 aprile 2025
- 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.