updated: 6 febbraio 2014
University of Verona
| Data (aula 7) | Argomenti Insieme | Lavoro Autonomo o collegiale |
| 22 gen -2014 (2 ore) | Introduzione al corso ed alla PL. - presentazione del corso, dei materiali di riferimento, di possibili obiettivi, percorsi, lavoro, e partecipazione. introduzione alla programmazione lineare: - modellazione di un semplice problema come problema di PL; (Per approfondire sulle competenze di modellazione si rimanda alla dispensa apposita). - soluzione per via grafica di un problema di programmazione lineare in 2 dimensioni. - soluzioni ammissibili, politopi e poliedri, vertici, combinazioni convesse e coniche, soluzioni ottime. - anticipazione, sull'esempio grafico, dei teoremi principali che incontreremo. Con appello all'intuizione fisico-geometrica. - definizione di problema di PL e di PLI, con accenno alla dicotomia in termini di trattabilità. - accenni alla rilevanza storica e scientifica della PL. | - Valutare colleggialmente se lavorare anche in autonomia su programmazione dinamica (studio dispense, soluzione problemi, produzione codice). - anticipare autonomamente lo studio di argomenti prossimi avvalendosi dei materiali e risorse presentati. - riflettere su proprio percorso individuale nel corso. |
| 23 gen -2014 (2 ore) | Introduzione al metodo del simplesso. - portare un problema di PL in forma standard. - considerazioni sull'arte di introdurre un problema ad un altro e la dovuta pubblicit\'a alla teoria della complessit&agreve;. - descrizione del metodo del simplesso su un esempio. - approccio diretto, come sorgono le difficoltà. - le variabili di slack e la forma canonica. - come aggirare la difficoltà, il pivot. - soluzioni di base. - terminazione. - un orgia di informazioni nascoste nei numeri computati. | Vedere in autonomia la generalizzazione a metodo dell'approccio esemplificato su un'istanza specifica di problema di PL. Trovate questo ed altro sul testo adottato, ma, se vi capita, suggerisco eventualmente di rifarsi anche a più di una fonte per abituarsi ad accedere indifferentemente a testi che utilizzino notazioni all'apparenza molto diverse ma che in definitiva trovano il loro minimo coumn denominatore ruotando attorno al metodo del simplesso illustrato. |
| 23 gen -2014 (1 ora) | 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. |
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.
ridurre un problema ad un altro: palindrome < lcs |
| 24 gen -2014 (2 ore) | Metodo del simplesso. - utilizzo di una scrittura tabellare compatta per i dizionari: il tableau. (Per approfondire sull'uso del tableau si rimanda alla dispensa apposita). - la prova del 9 e considerazioni correlate. - il metodo del simplesso a due fasi. - degeneratività e cycling. | Approfondimento autonomo concordato: - Regola di Bland. - Metodo delle perturbazioni e metodo lessicografico. - 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. |
| 3 feb -2014 (3 ore) | 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. Teorema della dualità debole. Enunciato del teorema della dualità forte. Dimostrazione del teorema della dualità forte. Metodo del simplesso duale. Metodi del simplesso duale-primale e primale-duale. Metodo del simplesso duale per la fase 1 del metodo del simplesso. | |
| 4 feb -2014 (3 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. | un esercizio di programmazione dinamica:
- abbiamo visto assieme, per richiesta di un compagno, un esercizio di programmazione dinamica. |
|
| created: 24 gennaio 2014 updated: 6 febbraio 2014 |
©
Department of Computer Science University of Verona |