IN440 Ottimizzazione Combinatoria – A.A. 2023/24
La pagina web inerente la precedente erogazione dell’insegnamento da parte del docente è reperibile qui.
Avvisi
La lezione del 14 Maggio si terrà in modalità remota su Teams in Aula 80 anziché in Aula A.
Il 23 Maggio non vi sarà lezione (verrà recuperata la settimana successiva).
Orari ed aule
-
Mar 9-11 aula A
-
Mer 11-13 laboratorio informatico
-
Gio 9-11 laboratorio informatico
Libro di testo
Il libro di testo adottato è
-
[KT] Algorithm Design di J. Kleinberg, E. Tardos (Pearson, 2006). Una copia del testo è reperibile nella biblioteca di area scientifica, sede centrale.
Altri riferimenti bibliografici utili sono:
-
[GJ] Computers and Intractability, di M.R. Garey, D.S. Johnson (Freeman, 1979). Alcune copie del testo sono reperibili nella biblioteca di area scientifica, sede centrale. Una copia digitale può essere presa in prestito a questo link, previa registrazione.
-
[KV] Ottimizzazione combinatoria, di B. Korte, J. Vygen (Springer, 2011). Una copia del testo è reperibile nella biblioteca di area scientifica, sede centrale. Una copia digitale in lingua inglese può essere presa in prestito a questo link, previa registrazione.
Diapositive per il testo Kleinberg & Tardos tradotte in italiano
Le seguenti diapositive sono tradotte da quelle ufficiali del libro di testo, messe a punto dagli autori e da Kevin Wayne (Università di Princeton).
Diario delle lezioni
I riferimenti [KT] indicano le sezioni del libro di testo.
| Data | Argomenti | Riferimenti al testo | Allegati |
|---|---|---|---|
20 Febbraio |
Presentazione del corso. Problemi di ottimizzazione combinatoria. Problema dell’abbinamento stabile. Algoritmo di Gale-Shapley. |
[KT 1.1, 1.2] |
|
21 Febbraio |
Introduzione a Python. Esercitazione su enumerazione combinatoria. |
||
22 Febbraio |
Altre proprietà di Gale-Shapley. Altri esempi di problemi di ottimizzazione combinatoria. |
[KT 1.2] |
|
27 Febbraio |
Trattabilità computazionale. Ordine asintotico di crescita (O, Ω, Θ). Implementazione di Gale-Shapley. |
[KT 2.0—2.2] |
|
28 Febbraio |
Python: liste e tipi sequenza. Esercitazione su abbinamenti stabili. |
||
29 Febbraio |
Tempi di esecuzione più comuni. Esempi. |
[KT 2.3, 2.4] |
|
5 Marzo |
Grafi: definizione, rappresentazione, connettività. Grafi bipartiti. Digrafi e loro connettività. |
[KT 3.0—3.4] |
|
6 Marzo |
Python: tipi mutabili e immutabili, array bidimensionali, idiomi di input/output. Esercitazione su rappresentazione di grafi e problema della raggiungibilità. |
||
7 Marzo |
Digrafici aciclici, ordinamento topologico. Algoritmi avidi, problema del resto in monete. |
[KT 3.5—3.6, 4.0] |
|
12 Marzo |
Schedulazione di intervalli. Code di priorità. Partizionamento di intervalli. |
[KT 2.5, 4.0—4.1] |
|
13 Marzo |
Python: ordinamento e coda di priorità. Esercitazione su algoritmi avidi (I). |
||
14 Marzo |
Minimizzazione del ritardo. Caching offline ottimo. |
[KT 4.2—4.3] |
|
19 Marzo |
Problema dei cammini minimi e algoritmo di Dijkstra. |
[KT 4.4] |
|
20 Marzo |
Python: insiemi e dizionari. Esercitazione su algoritmi avidi (II). |
||
21 Marzo |
Albero ricoprente minimo e algoritmo di colorazione rosso-blu. |
[KT 4.5] |
|
26 Marzo |
Algoritmi divide et impera. Ordinamento e ricorrenze. Conteggio delle inversioni. |
[KT 5.0—5.3] |
|
27 Marzo |
Python: oggetti e classi. Esercitazione su algoritmi divide et impera (I). |
||
28 Marzo |
Problema della coppia di punti più vicina. |
[KT 5.4] |
|
3 Aprile |
Esercitazione su algoritmi divide et impera (II). Esercizi sul progetto di algoritmi. |
[KT es. 3.4, 3.10] |
|
4 Aprile |
Programmazione dinamica. Equazione di Bellman. Schedulazione di intervalli pesati. |
[KT 6.0—6.2] |
|
9 Aprile |
Minimi quadrati a segmenti. Problema della bisaccia. |
[KT 6.3—6.4] |
|
10 Aprile |
Esercitazione su algoritmi di programmazione dinamica (I). Esercizi sul progetto di algoritmi. |
[KT es. 4.5, 4.13] |
|
11 Aprile |
Cammini minimi con pesi negativi. |
[KT 6.8—6.9] |
|
23 Aprile |
Flussi di rete. Teorema del massimo flusso e minimo taglio. |
[KT 7.0—7.2] |
|
24 Aprile |
Esercitazione su algoritmi di programmazione dinamica (II). Esercizi sul progetto di algoritmi. |
[KT es. svolti 5.2] |
|
30 Aprile |
Tempo di esecuzione di Ford-Fulkerson. Algoritmo capacity-scaling. |
[KT 7.2—7.3] |
|
2 Maggio |
Applicazioni del massimo flusso. Teoremi di Hall e di Menger. |
[KT 7.5—7.6] |
|
7 Maggio |
Estensioni del massimo flusso. |
[KT 7.7] |
|
8 Maggio |
Esercitazione su algoritmo di Ford-Fulkerson. Esercizi sul progetto di algoritmi. |
[KT es. 5.3, 6.1] |
|
9 Maggio |
Intrattabilità. Riduzioni tempo-polinomiali. Riduzioni da 3-SAT a problemi di copertura e impaccamento. |
[KT 8.1—8.2] |
|
14 Maggio |
Riduzioni da 3-SAT a problemi di sequenziamento. |
[KT 8.5] |
|
15 Maggio |
Esercizi sul progetto di algoritmi. |
[KT es. svolti 6.1; es. 6.3, 7.7, 7.14] |
|
16 Maggio |
Riduzioni da 3-SAT a problemi di partizionamento e numerici. |
[KT 8.6—8.8] |
|
21 Maggio |
Il problema P versus NP. Problemi NP-completi. |
[KT 8.3—8.4] |
|
22 Maggio |
Esercizi su problemi NP-completi. |
[KT es. 6.7; es. svolti 8.1, 8.2] |
|
28 Maggio |
Oltre la NP-completezza. Ottimizzazione lineare (LP) e ottimizzazione lineare intera (ILP). |
[KT 10.0, 10.2] |