updated: 23 giugno 2014
University of Verona
| Data | Argomenti |
| 3-3-2013 (2 ore) | Introduzione al corso.
Problemi, modelli di computazione, e algoritmi: Trovare il massimo in un vettore. Invarianti e monovarianti. Invarianti di ciclo. |
| 6-3-2013 (2 ore) | Progetto ed analisi di algoritmi: Induzione=ricorsione come tecnica per risolvere i problemi ed arrivare all'elaborazione di un algoritmo. SelectionSort, InsertSort e MergeSort e loro analisi. Tecnica divide et impera. Efficacia della ricera binaria. |
| 10-3-2013 (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. Abbiamo anche listato le piastrellature. 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. |
| 13-3-2013 (2 ore) | Induzione/Ricorsione con memoizzazione/Programmazione dinamica: Svolto campo minato. Svolto il problema triangolo: 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. Esercizi proposti: il problema borse per affinare l'induzione. I problemi Poldo, massima sottosequenza comune, shaffle, e collage (arcobaleno). |
| 17-3-2013 (2 ore) | Induzione/Ricorsione: Svolto borse = problema di enumerare in quanti modi sostanzialmente diversi sia possibile scomporre un numero naturale n come somma di naturali positivi. Lavorato con piastrelle 1xk, poi con bagni 2xn e piastrelle 1x2 dove sia anche possibile ruotare la piastrella 1x2. Induzione/Ricorsione/Programmazione Dinamica: Svolto Poldo (prima matrice e poi array di problemi). Esercizi proposti: - il problema della massima sottosequenza crescente con un ripensamento, o di una massima Z-sequenza. - il problema dello zaino con solo i pesi, zaino anche coi valori. |
| 20-3-2013 (2 ore) | Induzione Matematica come tecnica di problem solving e stile dichiarativo nella stesura di codice ricorsivo: - torre di Hanoi. |
| 24-3-2013 (2 ore) | Ridurre un problema ad un altro: - partition < knapsack - knapsack < partition - 3SAT è NP-completo - knapsack è NP-completo Esercizi proposti: - massima sottosequenza crescente < longest common subsequence - longest common subsequence < massima sottosequenza crescente |
| 27-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. |
| 31-3-2013 (2 ore) | zaino:
algoritmi di PD per formulazioni base dello zaino.
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. |
| 3-4-2013 (2 ore) | programmazione dinamica:
- come gestire con la PD giochi a due giocatori:
esempio della tavoletta di cioccolato.
- come capire se una stringa è shuffle di due stringhe date.
svolgimento di un esercizio in un compito anno precedente: svolgimento di un esercizio di programmazione dinamica (omino in griglia con mine). |
| 7-4-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.
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. |
| 10-4-2013 (2 ore) | binary heaps: un'implementazione efficiente per la coda di priorità |
| 14-4-2013 (2 ore) | grafi bipartiti: caratterizzazione ed algoritmo |
| 24-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.
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. |
| 28-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. - correzione dell'esercizio sui grafi in un compito. |
| 5-5-2013 (2 ore) | 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. - formula 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. |
| 8-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. - la rete dei ripensamenti. - descrizione competa dell'algoritmo di Ford-Fulkerson. - cammino BFS ed algoritmo fortemente polinomiale. |
| 12-5-2013 (2 ore) |
-introduzione alla programmazione lineare: - formulazione di un problema di programmazione lineare. - soluzione di un problema di programmazione lineare per via geometrica. - programmazione lineare (PL) e programmazione lineare intera (PLI). |
| 15-5-2013 (2 ore) |
programmazione lineare:
- ogni problema di programmazione lineare può essere portato in forma standard. - prima descrizione del metodo del simplesso. |
| 19-5-2013 (2 ore) |
programmazione lineare:
- comportamento geometrico del metodo del simplesso. - il tableau. |
| 22-5-2013 (2 ore) |
programmazione lineare:
- descrizione generale del metodo del simplesso. |
| 26-5-2013 (2 ore) |
programmazione lineare:
- come produrre una soluzione ammissibile di partenza nel caso di problemi ad origine non-ammissibile. Metodo del simplesso a 2 fasi. |
| 29-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. |
| 5-6-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. |
| 9-6-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.
Scarti Complementari: Motivazione: ricostruire la soluzione duale ottima a partire dalla soluzione primale ottima al fine di certificare l'ottimalità |
| 12-6-2013 (2 ore) (mattino) | Scarti Complementari:
- Precisazioni: Ad ogni soluzione primale di base è associata almeno una soluzione duale di base ad essa "ortogonale", - Tale soluzione è unica nel caso non-degenere. - Un esercizio di scarti complementari risolto. interpretazione economica variabili duali. analisi di sensitività tramite prova del 9 della PL. |
|
| created: 1 marzo 2014 updated: 23 giugno 2014 |
©
Department of Computer Science University of Verona |