updated: 22 maggio 2012
University of Verona
| Data | Argomenti |
| 1-3-2012 (3 ore) | visto: query somma intervallo con somme prefisse,
ricerca numeri in database (ordina),
torre di Hanoi,
piastrellature.
proposto: query somma rettangolo, ordinamento su confronto di triple che ritorna mediano, problemi di tiling di scacchiere, cantina con n lampadine ed n interruttori. |
| 5-3-2012 (laboratorio, 2 ore) | visto: codifica torre di Hanoi, stampare piastrellature.
proposto: flippare albero. |
| 5-3-2012 (aula, 1 ora) | visto: query rettangolo.
proposto: stampare n come somme sostanzialmente diverse stampare permutazioni stampare parentesizzazioni query somme intervallo con updates, gioco del 15. |
| 6-3-2012 (2 ore) | visto: buone caratterizzazioni: cammini e cicli Euleriani.
proposto: deBrujin sequences, matrice 0/1 con flip di riga e colonna. |
| 12-3-2012 (laboratorio, 2 ore) | visto: ricorsione con memoizzazione e programmazione dinamica, percorso con numeri di Fibonacci, soluzione ricorsiva del problema triangolo. |
| 12-3-2012 (aula, 1 ora) | visto: triangolo dall'alto e dal basso, con memoria lineare.
proposto: compiere lo stesso percorso con: bagni 2xn dove sia anche possibile ruotare la piastrella 1x2, con il problema di enumerare le formule ben formate di parentesi con n "(" ed n ")", con il problema di enumerare in quanti modi sostanzialmente diversi sia possibile scomporre un numero naturale n come somma di naturali |
| 13-3-2012 (2 ore) | da Induzione a Programmazione dinamica: - il problema del triangolo di numeri in cui reperire un cammino discendente dal vertice a somma massima dei numeri nel cammino (ricorrenza a salire e ricorrenza a scendere). - il problema della massima sottosequenza crescente. - il problema dello zaino con solo i pesi (PARTITION), zaino anche coi valori (KNAPSACK). |
| 19-3-2012 (2 ore) | da Induzione a Programmazione dinamica:
- robot in Campo Minato.
- coniglio su linea con erba che invecchia.
- longest common subsequence.
ridurre un problema ad un altro: LongestIncr < lcs Esercizi proposti: shuffling di stringhe, riduzione inversa: lcs < LongestIncr, zaino bidimensionale (peso e ingombro in litri). |
| 19-3-2012 (1 ora) | Esercizi proposti di programmazione dinamica:
collage di un arcobaleno,
contare le sottosequenze crescenti di data lunghezza,
sottosequenza crescente a somma massima,
quante sono le soluzioni ottime per un problema dello zaino.
(Giochi e programmazione dinamica:
Uova da condominio,
qualche gioco posizionale a due giocatori).
|
| 20-3-2012 (2 ore) |
Giochi e programmazione dinamica:
Come sfruttare un'approccio di programmazione dinamica
per esplorare il problema di uova da condominio.
Gioco della rana con passi da 1 o da 2.
Caratterizzazione delle posizioni "chi tocca perde".
Proposta del gioco con barra di cioccolato a quadretti,
con la rgola che quando uno spezza resta in gioco la parte piccola.
|
| 26-3-2012 (2 ore) | visto: arcobaleno.
proposto: longest 321-free subsequence. |
| 26-3-2012 (1 ora) | progressively finite games e DAGs:
gioco salta 1 o 2,
DAGs: caratterizzazione e riconoscimento di DAGs, kernel in DAGs, cammino piu' lungo in DAG. Esercizi proposti: Problema di partizionare un set di 3n numeri in triplette di costo lo scarto quadratico tra i due numeri grandi. |
| 27-3-2012 (2 ore) | Lavorando su esercizio 3n numeri in triplette:
Abbiamo fatto un percorso di analisi dello spazio delle possibili soluzioni ammissibili.
Ci siamo convinti che tale spazio era esponenziale e ne abbiamo concluso che è
necessario leggere qualcosa della struttura matematica del problema volendo risolverlo
e che dovremmo aspettarci una soluzione di tipo programmazione dinamica.
Probabilmente conviene ragionare sui numeri ordinati.
Per leggere della struttura potremmo concentrarci su un sottospazio di soluzioni "ragionevoli"
che contenga almeno una soluzione ottima. Abbiamo fatto dei passi assieme per restringere lo spazio di soluzioni ragionevoli.
Esercizi proposti: - Chiudere il problema delle triplette. - problema della proiezione del cinema con arrivi asincroni volendo minimizzare i tempi di attesa totale. |
| 16-4-2012 (2 ore) | Certificati di connessione ed alberi.
buone congetture: caratterizzazione di grafi bipartiti ed algoritmo per il riconoscimento di grafi bipartiti. (Enfasi sul lavorare per certificati). |
| 16-4-2012 (1 ora) | Esercizi proposti: - problema delle scatole cinesi. Magari provate prima in 2 e solo poi in 3 dimensioni.
algoritmi di branch and bound. |
| 17-4-2012 (2 ore) | Riduzioni tra problemi: Independent set, node cover, clique, riduzioni tra problemi. |
| 23-4-2012 (2 ore) | Relazione esistente tra i due problemi di massima sottosequenza crescente e di massima sottosequenza comune. Accenno all'importanza ed ai ruoli del mestiere di ridurre da un problema all'altro e proposta del problema dello zaino. Problemi di decisione, di ottimizzazione, di costruzione. |
| 23-4-2012 (1 ora) | Progetto di un branch and bound per il problema sorting by reversals. |
| 24-4-2012 (2 ore) | Progetto di un branch and bound per il problema sorting by reversals. |
| 30-4-2012 (2 ore) | Progetto di un branch and bound per il problema sorting by reversals. |
| 30-4-2012 (1 ora) | Idee di progetto di un branch and bound per il problema node cover. |
| 7-5-2012 (2 ore) | Produrre buoni bounds, algoritmi approssimanti, FPT ed iterative compression. |
| 7-5-2012 (1 ora) | Problema del min bipartizer. |
| 8-5-2012 (2 ore) | Algoritmo FPT per min bipartizer. |
| 14-5-2012 (2 ore) | Algoritmi di approssimazione per node cover. |
| 14-5-2012 (1 ora) | Approssimando set cover. |
| 15-5-2012 (2 ore) | Analisi dell'approssimazione dell'algoritmo greedy per set cover. |
| 22-5-2012 (2 ore) | Algoritmo FPT per ricerca di alberi in grande grafo database. |
| 28-5-2012 (2 ore) | 2-approssimazione e 3/2-approssimazione per il TSP. |
| 28-5-2012 (1 ora) | Dimostrazione NP-completezza problema dello zaino. |
| 29-5-2012 (2 ore) | Algoritmo FPTAS per il problema dello zaino. |
|
| created: 1 marzo 2012 updated: 22 maggio 2012 |
©
Department of Computer Science University of Verona |