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
Vedi sopra per le diapositive principali

[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.

Diapositive Python
Esercitazione
Soluzione

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.

Esercitazione
Soluzione

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à.

Esercitazione
Soluzione

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).

Esercitazione
Soluzione

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).

Esercitazione
Soluzione

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).

Esercitazione
Soluzione

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.

Esercitazione
Soluzione

[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).

Esercitazione
Soluzione

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).

Esercitazione
Soluzione

9 Maggio

Estensioni del massimo flusso.

[KT 7.7]

11 Maggio

Esercitazione su algoritmo di Ford-Fulkerson.

Esercitazione
Soluzione

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]