IN440 Ottimizzazione Combinatoria – A.A. 2025/26
La pagina web inerente la precedente erogazione dell’insegnamento da parte del docente è reperibile qui.
Avvisi
-
L’esercitazione del 14 Maggio è rinviata
-
Dal 21 al 23 Aprile le lezioni saranno sospese per la pausa esoneri
Orari ed aule
-
Mar 9-11 aula M4
-
Mer 14-16 aula M4
-
Gio 11-13 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). Reperibile anche in biblioteca di area scientifica, sede centrale.
-
[KV] 🇮🇹 Ottimizzazione combinatoria, di B. Korte, J. Vygen (Springer, 2011). Reperibile anche in biblioteca di area scientifica, sede centrale. Disponibile per il download in lingua inglese.
Legenda: = scaricabile, = disponibile in biblioteca, 🇮🇹 = traduzione italiana disponibile
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 |
|---|---|---|---|
24 Febbraio |
Presentazione del corso. Problemi di ottimizzazione combinatoria. Problema dell’abbinamento stabile. Algoritmo di Gale-Shapley. |
[KT 1.1, 1.2] |
|
25 Febbraio |
Altre proprietà di Gale-Shapley. Altri esempi di problemi di ottimizzazione combinatoria. |
[KT 1.2] |
|
26 Febbraio |
Esercizi su abbinamenti stabili. Esercitazione su enumerazione combinatoria. |
[KT es. s1.1, 1.1] |
|
3 Marzo |
Trattabilità computazionale. Ordine asintotico di crescita (O, Ω, Θ). Implementazione di Gale-Shapley. |
[KT 2.0—2.2] |
|
4 Marzo |
Tempi di esecuzione più comuni. Esempi. |
[KT 2.3, 2.4] |
|
5 Marzo |
Esercizi su notazione asintotica. Esercitazione su abbinamenti stabili. |
[KT es. s2.1, 2.6] |
|
10 Marzo |
Grafi: definizione, rappresentazione, connettività. Grafi bipartiti. Digrafi e loro connettività. |
[KT 3.0—3.4] |
|
11 Marzo |
Digrafici aciclici, ordinamento topologico. Algoritmi avidi, problema del resto in monete. Schedulazione di intervalli. |
[KT 3.5—3.6, 4.0—4.1] |
|
12 Marzo |
Esercitazione su rappresentazione di grafi e problemi di raggiungibilità. |
||
17 Marzo |
Richiami di strutture dati. Code di priorità. Partizionamento di intervalli. |
[KT 2.5, 4.1] |
|
18 Marzo |
Minimizzazione del ritardo. Caching offline ottimo. |
[KT 4.2—4.3] |
|
19 Marzo |
Esercitazione su algoritmi avidi (I). |
||
24 Marzo |
Problema dei cammini minimi e algoritmo di Dijkstra. |
[KT 4.4] |
|
25 Marzo |
Albero ricoprente minimo e algoritmo di colorazione rosso-blu. |
[KT 4.5] |
|
26 Marzo |
Esercitazione su algoritmi avidi (II). |
||
31 Marzo |
Algoritmi divide et impera. Ordinamento e ricorrenze. Conteggio delle inversioni. |
[KT 5.0—5.3] |
|
1 Aprile |
Problema della coppia di punti più vicina. Moltiplicazione di interi. |
[KT 5.4—5.5] |
|
2 Aprile |
Esercitazione su algoritmi divide et impera (I). |
||
8 Aprile |
Programmazione dinamica. Equazione di Bellman. Schedulazione di intervalli pesati. |
[KT 6.0—6.2] |
|
9 Aprile |
Esercitazione su algoritmi divide et impera (II). Esercizi sul progetto di algoritmi. |
[KT es. s3.1, 3.4] |
|
14 Aprile |
Minimi quadrati a segmenti. Problema della bisaccia. |
[KT 6.3—6.4] |
|
15 Aprile |
Cammini minimi con pesi negativi. |
[KT 6.8—6.9] |
|
16 Aprile |
Esercitazione su algoritmi di programmazione dinamica (I). Esercizi sul progetto di algoritmi. |
[KT es. 4.5] |
|
28 Aprile |
Flussi di rete. Teorema del massimo flusso e minimo taglio. |
[KT 7.0—7.2] |
|
29 Aprile |
Tempo di esecuzione di Ford-Fulkerson. Algoritmo capacity-scaling. Esercizi sul progetto di algoritmi. |
[KT 7.2—7.3, es. 4.13] |
|
30 Aprile |
Esercitazione su algoritmi di programmazione dinamica (II). |
||
5 Maggio |
Applicazioni del massimo flusso. Teoremi di Hall e di Menger. |
[KT 7.5—7.6] |
|
6 Maggio |
Estensioni del massimo flusso. |
[KT 7.7] |
|
7 Maggio |
Esercitazione su reti di flusso. |
||
12 Maggio |
Intrattabilità. Riduzioni tempo-polinomiali. Riduzioni da 3-SAT a problemi di copertura e impaccamento. |
[KT 8.1—8.2] |
|
13 Maggio |
Riduzioni da 3-SAT a problemi di sequenziamento. |
[KT 8.5] |
