updated: 23 maggio 2012
University of Verona
| Data | Argomenti |
| 5-3-2012 (2 ore) | Induzione: il problema di enumerare tutte le piastrellature possibili di un array 1xn
con piastrelle 1x1 e 1x2. Numero di chiamate ricorsive e struttura
dell'albero di ricorsione.
Ricorsione con memoizzazione: nel calcolare il numero delle piastrellature avvalendosi della ricorrenza di Fibonacci è importante memorizzarsi i valori già calcolati per non ricalcolarli. Programmazione dinamica: computare iterativamente i valori uno dopo l'altro. Esercizi proposti: 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 positivi, con i problemi di enumerare le permutazioni oppure i sottoinsiemi di dimensione k di un insieme di dimensione n. Il nostro problema del campo minato (robot su griglia, quante strade lo portano a casa). I problemi triangolo e massima sottosequenza crescente. |
| 7-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). |
| 12-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). |
| 14-3-2012 (2 ore) | 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).
Introduzione ai grafi come strumeto per modellare problemi: Percorsi cavallo su scacchiera e cicli Hamiltoniami in grafi. (Gioco di Hamilton). Problema di ciclo Hamiltoniano e riduzioni tra vari problemi di quel tipo. Definizione di P, NP e coNP. Problemi NP-completi. L'importanza dell'arte di ridurre un problema ad un altro. |
| 19-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.
Ancora riduzioni tra problemi: da SAT a 3-SAT. La PLI è NP-completa anche senza funzioni obiettivo e in senso forte. Introduzione ai grafi: Problema dei ponti di Konighsberg. Tecniche base del matematico ed il primo grafo della storia. Cammini e cicli Euleriani. NP e coNP. Congettura di Eulero è una buona congettura. Teorema di Eulero. Teorema di Eulero è un buon teorema. Lemma delle strette di mano. Altri esempi di buoni teoremi: la caratterizzazione del GCD di Euclide. Esercizi proposti: Trovare la minima stringa che abbia come sottostringhe tutte le stringhe di lunghezza k su un certo alfabeto. |
| 21-3-2012 (2 ore) | Programmazione dinamica: arcobaleno.
Esercizi proposti: longest 321-free subsequence. Grafi: grafi (diretti e non) come relazioni binarie, componenti connesse, certificati di connessione, alberi, foreste, alberi dei cammini minimi, BFS. |
| 26-3-2012 (2 ore) | Ridurre un problema ad un altro:
superstringa minima con Eulero.
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: - Ho lavori con precedenze e durate, capire se ci sono incongruenze ed in caso negativo valutare la durata del progetto. - Problema di partizionare un set di 3n numeri in triplette di costo lo scarto quadratico tra i due numeri grandi. |
| 28-3-2012 (2 ore) (mattina) | 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 poi ci siamo divertiti a proporre
stime via via più strette sulla sua cardinalità introducendo nel percorso
alcune metodologie base del calcolo combinatorio.
Come conseguenza del fatto che lo spazio era esponenziale si è 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 la pancia al problema delle triplette. - problema di costruire la più alta torre di trolls da un dato insieme di trolls, ciascuno caratterizzato da una forza e da un peso. - problema della proiezione del cinema con arrivi asincroni volendo minimizzare i tempi di attesa totale. |
| 28-3-2012 (2 ore) (pomeriggio) | Algoritmo di Dijkstra per il computo dell'albero dei cammini minimi nel caso pesato (con pesi non-negativi).
buone congetture: caratterizzazione di grafi bipartiti ed algoritmo per il riconoscimento di grafi bipartiti. (Enfasi sul lavorare per certificati). |
| 16-4-2012 (2 ore) | Esercizi proposti: - problema delle scatole cinesi. Magari provate prima in 2 e solo poi in 3 dimensioni.
Alberi ricoprenti di peso minimo: argomento dei cicli ed argomento dei tagli, algoritmi di Prim e Kruskal. Algoritmo di ricerca locale. |
| 18-4-2012 (2 ore) (mattina) | Grafi planari: partiti dal problema dei 4 colori, modelizzandolo tramite un grafo da colorare sui vertici. Definizione della classe dei grafi planari (quelli che ammettono un planar embedding). Formula di Eulero. Non planarità di K_5 e K_{3,3}. Grafo duale. Esplorazione della relazione di dualità. |
| 18-4-2012 (2 ore) (pomeriggio) | Enunciato del teorema di Kuratowski. Dimostrazione della formulazione di Wagner del teorema di Kuratowski. Enunciato del graph minor theorem. |
| 23-4-2012 (2 ore) | Massimo flusso e minimo taglio: buona caratterizzazione ed algoritmo. |
| 30-4-2012 (3 ore) | Introduzione alla PL: formulazione di un problema di gestione (contadino) che
diventa un problema di PL in 2 variabili. Definizione di problema di PL.
Risoluzione del particolare problema ottenuto per via geometrica,
con discussione di vari aspetti (dualità e degeneratività)
formulazione di un secondo problema di gestione (fiat) che diventa un problema di PL in 3 variabili. Illustrazione del metodo del simplesso su questo problema. Forma standard, riduzioni a forma standard. Forma canonica. |
| 2-5-2012 (2 ore) (mattina) | Metodo del simplesso: Illustrazione del metodo del simplesso su un problema (del tipo fiat) a 3 variabili. Dizionari, soluzioni di base, variabili in base e fuori base. Il tableau. Regola di pivot sul tableau e regola di controllo. Terminazione all'ottimo. Problemi illimitati. Hint sul problema dei troll. |
| 2-5-2012 (2 ore) (pomeriggio) | Metodo del simplesso: Interpretazione geometrica del metodo del simplesso. Come avviare il metodo del simplesso su problemi a origine non-ammissibile. Problema ausiliario e metodo del simplesso a due fasi. |
| 7-5-2012 (2 ore) | Metodo del simplesso. Il cycling: Degeneratività e cycling. Metodo delle perturbazioni e metodo lessicografico. Regola di Bland. Il teorema fondamentale della programmazione lineare. Efficienza del metodo del simplesso (cenni): numero medio di pivot di O(m log n), implementazione O(m+n) del pivot nel simplesso rivisto, cubi di Klee e Minty (1972), il metodo dell'elissoide di Khachian (1979) e sue implicazioni teoriche, metodo di Karmarkar. |
| 9-5-2012 (2 ore) (mattino) | teoria della dualità: Motivazione: fornire bounds, dimostrare ottimalità Duale di un problema in forma standard. E se il primale non è in forma standars. Duale del duale. Dimostrazione del teorema della dualità debole. Enunciato del teorema della dualità forte. |
| 9-5-2012 (2 ore) (pomeriggio) | Teorema della dualità forte: Dimostrazione del teorema della dualità forte. Metodo del simplesso duale. Metodi del simplesso duale-primale e primale-duale. |
| 14-5-2012 (2 ore) | Scarti Complementari: Motivazione: ricostruire la soluzione duale ottima a partire dalla soluzione primale ottima al fine di certificare l'ottimalità Cosa sono le condizioni degli scarti complementari. Ad ogni soluzione primale di base è associata almeno una soluzione duale di base ad essa "ortogonale", tale soluzione è unica nel caso non-degenere. Un paio di formulazioni equivalenti del teorema degli scarti complementari e loro dimostrazione. Un esercizio di scarti complementari risolto. |
| 16-5-2012 (2 ore) (mattino) | interpretazione economica variabili duali. |
| 16-5-2012 (2 ore) (pomeriggio) | analisi di sensitività. |
| 23-5-2012 (2 ore) (mattino) | esercizi in preparazione all'esame. |
| 23-5-2012 (2 ore) (pomeriggio) | esercizi in preparazione all'esame. |
|
| created: 12 aprile 2012 updated: 23 maggio 2012 |
©
Department of Computer Science University of Verona |