IN440 Ottimizzazione Combinatoria – A.A. 2021/22
La pagina web inerente la precedente erogazione dell’insegnamento da parte del docente è reperibile qui.
Avvisi
Non ci sarà lezione/esercitazione nei giorni 13, 18, 19 e 20 aprile, né il 25 aprile (festivo).
Orari ed aule
Quando: Lunedì 12.00-14.00 (aula A), Martedì 12.00-14.00 (aula A) e Mercoledì 10.00-12.00 (Lab)
Dove: aula A e 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 in biblioteca.
Altri riferimenti bibliografici utili sono:
-
[GJ] Computers and Intractability, di M.R. Garey, D.S. Johnson (Freeman, 1979). Alcune copie del testo sono reperibili in biblioteca.
-
[KV] Ottimizzazione combinatoria, di B. Korte, J. Vygen (Springer, 2011).
Per ulteriori riferimenti bibliografici si rimanda alla scheda GOMP dell’insegnamento.
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 | Allegati | Riferimenti al testo |
|---|---|---|---|
21 Febbraio |
Presentazione del corso. Problemi di ottimizzazione combinatoria. Problema dell’abbinamento stabile. Algoritmo di Gale-Shapley. |
Presentazione corso |
[KT 1.1, 1.2] |
22 Febbraio |
Altre proprietà di Gale-Shapley. Altri esempi di problemi di ottimizzazione combinatoria. |
[KT 1.2] |
|
23 Febbraio |
Introduzione a Python. Esercitazione su enumerazione combinatoria. |
||
28 Febbraio |
Trattabilità computazionale. Ordine asintotico di crescita (O, Ω, Θ). |
[KT 2.0—2.2] |
|
1 Marzo |
Implementazione di Gale-Shapley. Tempi di esecuzione più comuni. Esempi. |
[KT 2.3, 2.4] |
|
2 Marzo |
Python: liste e tipi sequenza. Esercitazione su abbinamenti stabili. |
||
7 Marzo |
Grafi: definizione, rappresentazione, connettività. Grafi bipartiti. |
[KT 3.0—3.4] |
|
8 Marzo |
Digrafi e loro connettività. Digrafici aciclici, ordinamento topologico. Algoritmi avidi, problema del resto in monete. |
[KT 3.5—3.6, 4.0] |
|
9 Marzo |
Python: tipi mutabili e immutabili, array bidimensionali, idiomi di input/output. Esercitazione su rappresentazione di grafi e problema della raggiungibilità. |
||
14 Marzo |
Schedulazione di intervalli. Code di priorità. Partizionamento di intervalli. |
[KT 2.5, 4.0—4.1] |
|
15 Marzo |
Minimizzazione del ritardo. Caching offline ottimo. |
[KT 4.2—4.3] |
|
16 Marzo |
Python: ordinamento e coda di priorità. Esercitazione su algoritmi avidi (I). |
||
21 Marzo |
Problema dei cammini minimi e algoritmo di Dijkstra. |
[KT 4.4] |
|
22 Marzo |
Albero ricoprente minimo e algoritmo di colorazione rosso-blu. |
[KT 4.5] |
|
23 Marzo |
Python: oggetti e classi. Esercitazione su algoritmi avidi (II). |
||
28 Marzo |
Algoritmi divide et impera. Ordinamento e ricorrenze. Conteggio delle inversioni. |
[KT 5.0—5.3] |
|
29 Marzo |
Problema della coppia di punti più vicina. |
[KT 5.4] |
|
30 Marzo |
Python: insiemi e dizionari. Esercitazione su algoritmi divide et impera (I). |
||
5 Aprile |
Programmazione dinamica. Equazione di Bellman. Schedulazione di intervalli pesati. |
[KT 6.0—6.2] |
|
6 Aprile |
Esercitazione su algoritmi divide et impera (II). Esercizi sul progetto di algoritmi. |
[KT es. 4.5] |
|
11 Aprile |
Minimi quadrati a segmenti. Problema della bisaccia. |
[KT 6.3—6.4] |
|
12 Aprile |
Cammini minimi con pesi negativi. |
[KT 6.8—6.9] |
|
26 Aprile |
Flussi di rete. Teorema del massimo flusso e minimo taglio. |
[KT 7.0—7.2] |
|
27 Aprile |
Python: variabili globali e regole di visibilità. Esercitazione su algoritmi di programmazione dinamica (I). |
||
2 Maggio |
Tempo di esecuzione di Ford-Fulkerson. Algoritmo capacity-scaling. |
[KT 7.2—7.3] |
|
3 Maggio |
Applicazioni del massimo flusso. Teoremi di Hall e di Menger. |
[KT 7.5—7.6] |
|
4 Maggio |
Esercitazione su algoritmi di programmazione dinamica (II). |
||
9 Maggio |
Estensioni del massimo flusso. |
[KT 7.7] |
|
11 Maggio |
Esercitazione su algoritmo di Ford-Fulkerson. |
||
16 Maggio |
Intrattabilità. Riduzioni tempo-polinomiali. Riduzioni da 3-SAT a problemi di copertura e impaccamento. |
[KT 8.1—8.2] |
|
17 Maggio |
Decisione, ricerca, ottimizzazione. Riduzioni da 3-SAT a problemi di sequenziamento. |
[KT 8.5] |
|
18 Maggio |
Esercizi sul progetto di algoritmi. |
[KT es. svolti 5.1, 6.1; es. 5.3, 6.1] |
|
23 Maggio |
Riduzioni da 3-SAT a problemi di partizionamento e numerici. |
[KT 8.6—8.8] |
|
24 Maggio |
Il problema P versus NP. Problemi NP-completi. |
[KT 8.3—8.4] |
|
25 Maggio |
Esercizi su problemi NP-completi. |
[KT es. svolti 8.1, 8.2] |
|
30 Maggio |
Oltre la NP-completezza. |
[KT 10.0, 10.2] |