| Data | Argomenti |
| 3-3-2015 (laboratorio, 3 ore) |
organizzazione generale del corso.
Alcuni obiettivi del corso.
Presentazione sito CMS.
Problema di piastrellare corridoio: soluzione ricorsiva di piastrellature. Esaminiamo l'albero di ricorsione di tale soluzione. Proponiamo e studiamo la memoizzazione. Primo accenno alla programmazione dinamica. Dire no: invarianti e monovarianti. Tessere di domino su griglie mxn. Buone caratterizzazioni. |
| 5-3-2015 (aula, 3 ore) |
piastrellature di bagni 2xn. Computare = enumerare. Enumerare = procedere in ordine. Eserciti di fatine ricorsine. |
| 10-3-2015 (laboratorio, 3 ore) |
codifica dei problemi di piastrellature |
| 12-3-2015 (aula, 3 ore) |
monovarianti/invarianti: quali celle posso bruciare nella mxn (tessere di domino). ricorsione/induzione: scacchiera 2^k per 2^k problema proposto: ricerca sottointervallo di somma massima in array. E modello con query. |
| 17-3-2015 (laboratorio, 3 ore) |
ricerca sottointervallo di somma massima: lavoro in gruppi sul problema. Soluzione n^3. Soluzione ricorsiva esponenziale. Dalla esponenziale, con memoizzazione, otteniamo soluzione n^2. Somme prefisse. Problema di query. Alla riscoperta del divide et impera come tecnica algoritmica. |
| 24-3-2015 (laboratorio, 3 ore) |
campo minato: proposta e soluzione di primo problema di programmazione dinamica. E se chiedevamo cammino più lungo? un invariante mostra che hanno tutti la stessa lunghezza. Diventa un problema di reachability. La DFS, il fuoco che propaga, la coda FIFO che basta a mantenere sincrono il processo, il book-keeping delle cause di ogni evento rilevante e l'albero dei cammini minimi. I grafi come modello concettuale, la DFS come archetipo. |
| 26-3-2015 (3 ore) |
Somme prefisse, alberi di Fenweek, e un'applicazione: abbiamo lavorato sulla presentazione di Gabriele Farina sulle strutture dati per informazioni facilmente unibili. |
| 31-3-2015 (3 ore, laboratorio) |
Primo problema dell'ultimo COCI |
| 14-4-2015 (3 ore, laboratorio) |
Abbiamo esplorato il problema "taglialegna". Abbiamo messo a punto un approccio ricorsivo. Abbiamo osservato che esso si prestava a memoizzazione e poteva essere formulato come una prograggazione dinamica a spazio lineare e tempo quadratico. Abbiamo indicato i vari elementi da comporre per giungere ad una semplice (ma per nulla facile) soluzione lineare. |
| 21-4-2015 (3 ore, laboratorio) |
Presentazione del primo progetto. Varie proposte al collaborare ed esprimersi. Strutture dati: le code e gli heaps binary. Rimando alle slides di Farina per le sparse tables ed i range trees, ai problemi COCI per esercizi. |
| 23-4-2015 (3 ore) |
Abbiamo dimostrato varie buone caratterizzazioni per il problema pirellone, e contemporaneamente ottenuto un algoritmo basato sul portare il pirellone a forma canonica.
Ho richiamato alcuni problemi assegnati su invarianti e monovarianti, e ne ho assegnati di nuovi. Ho richiesto di camminare anche in autonomia su versante programmazione dinamica, avvalendosi delle dispense al sito del corso (in particolare il capitolo di Papadimitriou e Vazirani) e proponendo i seguenti problemi sul CMS: minato, triangolo, somme, poldo. Abbiamo iniziato la nostra teoria dei grafi. Siamo partiti dal buon teorema di Eulero sui ponti di Konigsberg, evidenziando: i grafi offrono un ottimo linguaggio per la modellizzazione di problemi; la buona congettura di Eulero; il lemma delle strette di mano; dimostrando la congettura otteniamo un algoritmo. Come esercizi: estendere al caso di grafi diretti. Ricerca della supersequenza universale di lunghezza minima per stringhe di lunghezza k. Il problema matita sul CMS. |
| 28-4-2015 (3 ore, laboratorio) |
Il problema triangolo: un'altra famiglia di problemi chiusa rispetto a ricorsione ed un algoritmo di streaming.
problema proposto: determinare il valore del gioco di due giocatori che a turno possano prendere da una a tre monete da una pila. |
| 20-4-2015 (3 ore) |
La programmazione dinamica come strumento per affrontare giochi a 2 giocatori (running example: una pila di monete con 2 giocatori che si alternano potendo prendere 1,2,3 monete dalla cima).
Un problema di scheduling con precedenze: possiamo collocare i nodi di un grafo diretto su una linea in modo che tutti gli archi puntino in una stessa direzione della linea? L'ostacolo dei cicli diretti ed una buona congettura. Definizione di DAG, concetto di pozzo e sorgente, dimostrazione della congettura ed algoritmo. Implementazione lineare dell'algoritmo. Implementazione self-certifying dell'algoritmo. Progressively finite games a DAGs. Il gioco del nim e le Grundy functions. esercizio proposto: cioccolata mxn (Polonia) |
| 5-5-2015 (1 ora, laboratorio) |
un esempio di programmazione dinamica su alberi.
matching bipartito: il modello, esempi di applicabilita` anche in seno ad uno schema di programmazione dinamica per combinare le soluzioni dei sottoproblemi. |
| 6-5-2015 (1 ora, aula I (sostituzione di Ferdinando)) |
matching bipartito: la buona caratterizzazione nel linguaggio di Koenig, la buona caratterizzazione nel linguaggio di Hall e loro equivalenza sostanziale. Lo schema generale di un algoritmo ad approccio incrementale ma non greedy, e definizione dell'interfaccia della procedura principe. |
| 7-5-2015 (3 ore) |
matching bipartito: il lemma di Berge. L'algoritmo ungherese. Rimapparsi i problemi e rimapparsi i certificati. L'algoritmo di Hopcroft e Karp. Contare i cammini minimi tra due nodi in un grafo non diretto. programmazione dinamica: lancio uova da palazzo. |
| 12-5-2015 (3 ore, laboratorio) |
presentazione progetto: i portali della Galassia. programmazione dinamica su albero: quando nella composizione dei sottoproblemi diviene necessario adottare i figli uno alla volta. Calcolo dei valori di Grundy function per il problema della cioccolata. |
| 14-5-2015 (3 ore) |
convivere con l'NP-completezza: euristiche generative (greedy e GRASP) e di affinamento (local search, simulated annealing, tabu search, algoritmi genetici, algoritmi memetici, exponential neighborhoods), algoritmi approssimati. |
| 19-5-2015 (3 ore, laboratorio) |
algoritmi approssimati: $\log n$-approssimazione ed $f$-approssimazione per il Set Cover pesato.
Tecnica del layering per la $2$-approssimazione del vertex cover pesato. exponential local search: 3 poly-checkable exponential neighbours per il TSP: uno basato sul bipartite matching, uno sulla programmazione dinamica, ed uno su cammino minimo in un DAG. algoritmi esatti: enumerazione esplicita, enumerazione implicita, backtracking, constraint programming, branch-and-bound ed un ruolo per gli algoritmi approssimati. |
| 26-5-2015 (3 ore, laboratorio) |
informazioni sul progetto Portali Si è dovuto lavorare su questo progetto che era rimasto indietro. |