Ottimizzazione Combinatoria – A.A. 2019/20
Avvisi
Didattica on-line: Si invitano tutti gli studenti ad accedere alla pagina Moodle del corso e a seguire le istruzioni contenute nella sezione Avvisi di Moodle per potersi registrare alla didattica on-line (Microsoft Teams).
Pagina Microsoft Stream del corso
In accordo con le direttive governative e di Ateneo, la didattica frontale in presenza è attualmente sospesa.
Nello stesso periodo, il ricevimento (telematico) può essere concordato via email.
Orari ed aule
Quando: Lunedì 9.00-11.00, Mercoledì 14.00-16.00 e Venerdì 9.00-11.00
Dove: Aula M4 (Lunedì), Lab (Mercoledì), M5 (Venerdì)
Ricevimento studenti
Durante le settimane di lezione: Mercoledì, 11.00-12.00, Largo San Leonardo Murialdo, Pal. C - Stanza 201
Al di fuori dei periodi di lezione è necessario prenotare il ricevimento per email.
Libro di testo
Il libro di testo adottato è
Per le altre informazioni ufficiali sul corso (programma, modalità d'esame) si rimanda al GOMP.
Diario delle lezioni
I riferimenti [KT] indicano le sezioni o gli esercizi del libro di testo.
24 Febbraio: Presentazione del corso. Problemi di ottimizzazione combinatoria. Problema dell'abbinamento stabile. Algoritmo Gale-Shapley e sua analisi (demo).
[KT 1.0, 1.1, 1.2.]
26 Febbraio: Introduzione a Python. Esercitazione su enumerazione di sottoinsiemi.
28 Febbraio: Altre proprietà di Gale-Shapley. Altri esempi di problemi di ottimizzazione combinatoria. Trattabilità computazionale. Ordine asintotico di crescita (O, Ω, Θ).
[KT 2.0, 2.1, 2.2]
2 Marzo: Implementazione di Gale-Shapley. Tempi di esecuzione più comuni: costante, lineare, logaritmico. Ricerca binaria (demo).
[KT 2.3, 2.4]
4 Marzo: Python: liste e tipi sequenza. Esercitazione su costruzione di permutazioni inverse e su Gale-Shapley.
13 Marzo (online): Tempi di esecuzione comuni. Grafi: definizione, rappresentazione, connettività.
[KT 2.4, 3.0, 3.1]
16 Marzo (online): Connettività e visite di grafi. Grafi bipartiti. Digrafi e loro connettività. Digrafi aciclici.
[KT 3.2, 3.3, 3.4, 3.5]
18 Marzo (online): Python: tipi mutabili e immutabili, array bidimensionali, idiomi di input/output. Esercitazione su rappresentazione di grafi e problema della raggiungibilità.
20 Marzo (online): DAG e ordinamento topologico. Algoritmi avidi. Problema del resto in monete e algoritmo del cassiere. Schedulazione di intervalli e algoritmo Earliest-Finish-Time-First (demo).
[KT 3.6, 4.0, 4.1]
23 Marzo (online): Code di priorità. Partizionamento di intervalli e algoritmo Earliest-Start-Time-First (demo). Schedulazione per minimizzare il ritardo e algoritmo Earliest-Deadline-First. Il problema del caching ottimo .
[KT 4.2, 4.3]
25 Marzo (online): Python: ordinamento e coda di priorità. Esercitazione su algoritmi avidi per problemi di schedulazione.
[KT 2.5]
27 Marzo (online): Algoritmo Farthest-in-Future per il problema del caching. Problema dei cammini minimi e algoritmo di Dijkstra (demo).
[KT 4.3, 4.4]
30 Marzo (online): Tagli e cutset. Problema dell'albero ricoprente minimo. Regola rossa e regola blu. Algoritmo di Prim (demo).
[KT 4.5]
1 Aprile (online): Python: oggetti e classi. Esercitazione su algoritmi di Dijkstra e di Prim.
3 Aprile (online): Algoritmo di Kruskal e di cancellazione a rovescio (demo). Algoritmi divide et impera. Fusione ordinata (demo) e mergesort. Soluzione di ricorrenze. Limitazione inferiore per algoritmi di ordinamento basati su confronti.
[KT 4.5, 5.0, 5.1]
6 Aprile (online): Algoritmo divide et impera per il conteggio delle inversioni (demo). Algoritmo divide et impera per il problema della coppia di punti più vicina.
[KT 5.2, 5.3, 5.4]
8 Aprile (online): Python: insiemi e dizionari. Esercitazione sul Merge Sort e sull'algoritmo divide et impera per il conteggio delle inversioni.
15 Aprile (online): Esercitazione su algoritmo divide et impera per il problema della coppia di punti più vicina. Esercizi sul progetto di algoritmi [KT es. 4.5]. Lavagna
17 Aprile (online): Programmazione dinamica. Equazione di Bellman. Schedulazione di intervalli pesati. Algoritmo top-down e bottom-up.
[KT 6.0, 6.1, 6.2]
20 Aprile (online): Problema dei minimi quadrati a segmenti e algoritmo bottom-up. Problema della bisaccia e algoritmo bottom-up.
[KT 6.3, 6.4]
22 Aprile (online): Python: variabili globali e regole di visibilità. Esercitazione su algoritmi di programmazione dinamica per i numeri di Fibonacci e per la schedulazione di intervalli pesati. Esercizi sul progetto di algoritmi [KT es. svolto 5.1]. Lavagna
24 Aprile (online): Cammini minimi con pesi negativi. Algoritmo di Bellman-Ford. Flussi di rete.
[KT 6.8, 6.9, 7.0]
27 Aprile (online): Teorema del massimo flusso - minimo taglio. Algoritmo di Ford-Fulkerson (demo).
[KT 7.1, 7.2]
29 Aprile (online): Esercitazione su algoritmi di programmazione dinamica per il problema della bisaccia. Esercizi sul progetto di algoritmi [KT es. 5.3; es. svolto 6.1]. Lavagna
4 Maggio (online): Tempo di esecuzione di Ford-Fulkerson. Algoritmo capacity-scaling.
[KT 7.2, 7.3]
6 Maggio (online): Esercizi sul progetto di algoritmi [KT es. 4.13, 6.1; es. svolto 4.3]. Lavagna
8 Maggio (online): Applicazioni del massimo flusso: abbinamento bipartito, cammini arco-disgiunti. Teoremi di Hall e di Menger.
[KT 7.5, 7.6]
11 Maggio (online): Intrattabilità computazionale. Riduzioni tempo-polinomiali. Riduzioni da 3-SAT a problemi di copertura e impaccamento.
[KT 8.1, 8.2]
13 Maggio (online): Estensioni al massimo flusso. Esercizi sul progetto di algoritmi [KT es. 5.6]
15 Maggio (online): Problemi di decisione, ricerca, ottimizzazione. Riduzioni da 3-SAT a problemi di sequenziamento.
[KT 8.5]
18 Maggio (online): Riduzioni da 3-SAT a problemi di partizionamento e a problemi numerici.
[KT 8.6, 8.7, 8.8]
20 Maggio (online): Esercitazione su algoritmo di Ford-Fulkerson. Esercizi sul progetto di algoritmi [KT es. svolto 5.2; es. 6.7, 7.1, 7.2]. Lavagna
22 Maggio (online): Le classi P ed NP. Il problema P vs NP.
[KT 8.3]
25 Maggio (online): I problemi NP-completi. Co-NP e l'asimmetria di NP.
[KT 8.4, 8.9]
27 Maggio (online): Esercizi sulla NP-completezza [KT es. svolto 5.1]. Lavagna
29 Maggio (online): Problemi NP-ardui. Oltre la NP-completezza. Lavagna
[KT 8.10, 9.1, 10.0]
Diapositive per il testo Kleinberg & Tardos tradotte in italiano
Le seguenti diapositive sono tradotte da quelle ufficiali del libro di testo, messe a punto da Kevin Wayne (Università di Princeton).
