Data Argomenti
4-3-2013
(2 ore)
Introduzione al corso.
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: il nostro problema del campo minato (robot su griglia, quante strade lo portano a casa). I problemi triangolo e massima sottosequenza crescente.
Ulteriori esercizi: 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.
7-3-2013
(2 ore)
da Induzione a Programmazione dinamica: computare iterativamente i numeri di piastrellature uno dopo l'altro.
Esercizi proposti: - 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).
11-3-2013
(2 ore)
da Induzione a Programmazione dinamica: Il nostro problema del campo minato (robot su griglia, quante strade lo portano a casa). Siamo partiti da una ricorsiva scritta da voi in MatLab, che abbiamo pulito. Poi abbiamo aggiunto la memoizzazione e poi l'abbiamo vista alla programmazione dinamica.
Esercizi proposti: - 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).
14-3-2013
(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. Uno studente ha proposto un approccio di programmazione dinamica. Abbiamo cercato di vederlo sia direttamente come una programmazione dinamica ma anche come un'idea ricorsiva con eventuale memoizzazione. Abbiamo visto sia una ricorrenza a salire che una ricorrenza a scendere, dove una delle due consentiva una risposta in streaming. - Il problema PARTITION. Il problema dello ZAINO e riduzione di PARTITION a ZAINO. Accenno alla complessità computazionale. Ruolo dell'arte di ridurre un problema all'altro. Soluzione di programmazione dinamica.
Esercizi proposti: - enumerare in quanti modi sostanzialmente diversi sia possibile scomporre un numero naturale n come somma di naturali positivi.
18-3-2013
(2 ore)
da Induzione a Programmazione dinamica: - ricorrenza per contare in quanti modi sostanzialmente diversi sia possibile scomporre un numero naturale n come somma di naturali positivi.
Induzione Matematica come tecnica di problem solving e stile dichiarativo nella stesura di codice ricorsivo: - torre di Hanoi.
Esercizi proposti: - il problema della massima sottosequenza crescente.
21-3-2013
(2 ore)
da Induzione a Programmazione dinamica: - massima sottosequenza crescente. - 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).
25-3-2013
(2 ore)
grafi come modelli: - il problema dei ponti di Eulero. - il lemma delle strette di mano. - il teorema di Eulero. - buone congetture, caratterizzazioni, NP e coNP.
ridurre un problema ad un altro: palindrome < lcs
Esercizi proposti: - caratterizzare esistenza di ciclo Euleriano in grafi diretti; - disegnare la casetta senza staccare matita da foglio; - costruire minima superstringa per parole di lunghezza k su alfabeti finiti.
28-3-2013
(2 ore)
algoritmo BFS (visita in ampiezza): - la relazione "essere connessi" e le sue proprietà. - certificati di connessione. - fuoco che si propaga. - l'algoritmo BFS. - code FIFO. - albero dei cammini minimi.
svolgimento di un esercizio in un compito anno precedente: svolgimento di un esercizio di programmazione dinamica (omino in griglia con mine).
8-4-2013
(2 ore)
algoritmo di Dijkstra: - invariante sulla coda FIFO nella BFS. - l'algoritmo di Dijkstra come variazione della BFS. - code con priorità: un'esempio di strutture dati astratte. - l'algoritmo di Dijkstra come event-driven simulation.
ridurre un problema ad un altro: riduzione pseudopolinomiale: distanze pesate < distanze non pesate
Esercizi proposti: fornire implementazioni della coda con priorità.
lcs < LongestIncr.
dimostrare correttezza della riduzione: palindrome < lcs.
lcs < palindrome.
11-4-2013
(2 ore)
binary heaps: un'implementazione efficiente per la coda di priorità
15-4-2013
(2 ore)
network design: alberi ricoprenti di peso minimo. Un connettore di costo minimo è un albero ricoprente. Tagli e cicli. Lemma dei tagli e lemma dei cicli. NP, coNP, ed NP-completezza. La programmazione lineare intera è NP-completa.
18-4-2013
(2 ore)
grafi bipartiti: caratterizzazione ed algoritmo
alberi ricoprenti di peso minimo: dimostrazioni del lemma dei tagli e del lemma dei cicli. Algoritmo di Kruskal. Ruolo dei due lemmi nelle scelte che avvengono lungo l'algoritmo di Kruskal.
22-4-2013
(2 ore)
algoritmo di Prim: - descrizione algoritmo, ruolo dei lemmi nel supportare la scelta locale. Verifica dell'ottimalità di un albero ricoprente minimo. Algoritmo per ricerca locale.
grafi planari:
- problema dei 4 colori come vertex-coloring di grafi planari
- grafi planari e planar embedding
- triangolazioni di grafi planari
- il duale di un grafo planare (approccio di Tait: edge-coloring di grafi planari cubici)
- duale del duale
- legami combinatorici da primale e duale
- politopi, poliedri, scheletro di un politopo, dualità di politopi.
- teorema di Eulero e sua dimostrazione nel setting dei grafi tramite deletion e contraction.
- non planarità di K_5 e K_{3,3}.
- enunciato del teorema di Kuratowski.
29-4-2013
(2 ore)
grafi planari:
- enunciato di Wagner del teorema di Kuratowski.
- equivalenza dell'enunciato di Wagner e di quello di Kuratowski.
- enunciato del graph minor theorem e sue conseguenze algoritmiche.
6-5-2013
(2 ore)
flusso in reti:
- flusso come assegnamento di valori agli archi.
- flusso come famiglia di cammini.
- il max-flow min cut theorem.
6-5-2013
(2 ore)
flusso in reti:
- la rete dei ripensamenti.
- descrizione competa dell'algoritmo di Ford-Fulkerson.
- cammino BFS ed algoritmo fortemente polinomiale.
-introduzione alla programmazione lineare:
- formulazione di un problema di programmazione lineare.
- soluzione di un problema di programmazione lineare per via geometrica.
- ogni problema di programmazione lineare può essere portato in forma standard.
9-5-2013
(2 ore)
un esercizio di programmazione dinamica:
- abbiamo visto assieme, per richiesta di un compagno, un esercizio di programmazione dinamica da un vecchio tema.
-introduzione alla programmazione lineare:
- soluzione di un problema di programmazione lineare col metodo del simplesso. B
13-5-2013
(2 ore)
un esercizio di flussi:
- abbiamo visto assieme, per richiesta di un compagno, un esercizio di massimo flusso/minimo taglio da un vecchio tema.
-programmazione lineare:
- come produrre una soluzione ammissibile di partenza nel caso di problemi ad origine non-ammissibile. Metodo del simplesso a 2 fasi.
16-5-2013
(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.

20-5-2013
(2 ore)
(pomeriggio)
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.
23-5-2013
(2 ore)
(mattino)
Teorema della dualità forte: Dimostrazione del teorema della dualità forte. Metodo del simplesso duale. Metodi del simplesso duale-primale e primale-duale.
27-5-2013
(2 ore)
(mattino)
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.
27-5-2013
(2 ore)
(pomeriggio)
interpretazione economica variabili duali.
30-5-2013
(2 ore)
(mattino)
analisi di sensitività.


created:   12 aprile 2012
updated:   23 maggio 2012
© Department of Computer Science
University of Verona