IN440 Ottimizzazione Combinatoria – A.A. 2025/26
La pagina web inerente la precedente erogazione dell’insegnamento da parte del docente è reperibile qui.
Avvisi
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. Una copia digitale può essere presa in prestito a questo link, previa registrazione.
-
[KV] 🇮🇹 Ottimizzazione combinatoria, di B. Korte, J. Vygen (Springer, 2011). Reperibile anche in biblioteca di area scientifica, sede centrale. Una copia digitale in lingua inglese può essere presa in prestito a questo link, previa registrazione.
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). |
