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 7 Marzo si terrà nell'Aula L del blocco aule anziché in laboratorio.
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 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).
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] |