updated: 3 giugno 2016
University of Verona
| Lezione num(part) | year-month-day | content |
|---|---|---|
| Lez 1 | 2017-03-02 | induzione, ricorrenza di fibonacci, ma da dove nascono le ricorrenze? |
| Lez 2 | 2017-03-07 | campo minato, monovarianti ed invarianti, problemi di tiling, dire di no, buone caratterizzazioni, certificati da fornire ed algoritmi che li producono, induzione e decomposizione ricorsiva dei problemi, piastrellature, ricostruire con le mani lo spartito ricorsivo di un problema, decidibilita`ed enumerabilita` ricorsiva dei linguaggi, ricorsione e tesi di Turing |
| Lez 3 | 2017-03-14 | presentazione del sito del corso e dei materiali da esso disponibili, presentazione del CMS per le esercitazioni autonome, il problema pirellone, lavorare tramite buone congetture, il ruolo guida della teoria della complessita` nell'analisi dei problemi |
| Lez 4(1) | 2017-03-16 | pirellone, buone congetture e caratterizzazioni |
| Lez 4(2) | 2017-03-16 | porre delle questioni su un piano operativo, le categorie NP e coNP supportano nell'impostare certe dimostrazioni, ruolo delle buone caratterizzazzioni, spartito delle dimostrazioni, buone congetture, buoni teoremi e dimostrazioni algoritmiche, algoritmi come opportunita` di esplorazione, leggere la struttura per individuare gli algoritmi, pirellone |
| Lez 5 | 2017-03-21 | campo minato, presentazione di vari possibili problemi sul CMS, massima sottosequenza crescente |
| Lez 6 | 2017-03-23 | massima sottosequenza crescente, ricorsione e programmazione dinamica, rappresentazioni binarie e posizionali, efficienza degli algoritmi, binary search, leggenda degli scacchi, equipotenza tra insiemi: numerabilita` fino ai razionali, diagonalizzazione: non numerabilita` dei reali, da Kantor ai risultati di incompletezza ed indecidibilita`, ricostruzione di una soluzione ottima: la promessa ad Abramo |
| Lez 7 | 2017-03-28 | registrazione non riuscita: non abbiamo centrato la telecamera! programmazione dinamica: problema triangolo, il ruolo dell'induzione: decomposizione ricorsiva dei problemi, ricostruzione di una soluzione ottima: fatine ed angeli custodi, algoritmi e dimostrazioni, dimostrazioni ed algoritmi, lower bound sul numero di confronti per ordinare |
| Lez 8 | 2017-03-30 | lower bound sul numero di confronti per trovare il massimo, rassegna di alcuni algoritmi di ordinamento, ricorsione come astrazione, analisi del costo computazionale, il divide et impera, mergesort, algoritmi come tecnologia, le code, strutture di dati astratti, binary heaps |
| Lez 9 | 2017-04-04 | esercizio sull'induzione matematica: problema borse di studio, quando il progetto dell'interfaccia della ricorsione richiede di introdurre parametri non scontati |
| Lez 10 | 2017-04-06 | programmazione dinamica, massima sottosequenza comune (MCS), sull'arte di ridurre un problema ad un altro, equivalenza tra massima sottosequenza crescente e MCS, dimostrazioni di NP-completezza: ridurre SAT a 3SAT, riduzioni nella direzione sbagliata: abbiamo ridotto Set Cover a SAT mentre invece volevamo dimostrare che Set Cover era NP-completo |
| Lez 11(1) | 2017-04-11 | introduzione alla PLI: la sua espressivita`, la sua NP-hardness |
| Lez 11(2) | 2017-04-11 | introduzione alla PL: geometria (politopi, poliedri, convessita`), forma standard, introduzione al metodo del simplesso |
| Lez 12(1) | 2017-04-13 | metodo del simplesso, variabili di slack, forma canonica, pivot, terminazione, la prova del nove, la prova a terminazione |
| Lez 12(2) | 2017-04-13 | geometria del metodo del simplesso |
| Lez 13 | 2017-04-18 | non registrato per problemi con nuovo sistema, problema dello zaino, riduzioni tra problemi |
| Lez 14 | 2017-04-20 | non registrato per problemi con nuovo sistema, problemi ad origine non ammissibile, problema ausiliario e metodo del simplesso a due fasi |
| Lez 15 | 2017-04-27 | degenerativita`, cycling, metodi per evitare il cycling (regola di Bland, perturbare il problema), il teorema fondamentale della programmazione lineare |
| Lez 16 | 2017-05-02 | il pivot come operazioni di riga su un tableau esteso, il metodo lessicografico, rudimenti della notazione matriciale, accenni storici alla complessita` della PL: cubo di Klee-Minty, metoso dell'elissoide, metodi di punto interno, smooth analysis |
| Lez 17 | 2017-05-04 | il problema duale, teorema della dualita' forte, simplesso duale, prezzi ombra, analisi di sensitivita` |
| Lez 18(1) | 2017-05-16 | gli scarti complementari |
| Lez 18(2) | 2017-05-16 | introduzione ai grafi: il problema dei ponti di Eulero |
| Lez 19(1) | 2017-05-18 | Registrazione che prende solo parte della lavagna. Problemi come modelli. Il problema dei ponti di Eulero su grafi diretti. Buone congetture. Dimostrazioni ed algoritmi. |
| Lez 19(2) | 2017-05-18 | Decidere se un grafo e` connesso. Componenti connesse di un grafo. |
| Lez 20(1) | 2017-05-23 | L'abero dei cammini minimi. Algoritmo BFS. |
| Lez 20(2) | 2017-05-23 | Algoritmo Dijstra. Il problema dell'albero ricoprente di peso minimo. |
| Lez 21 | 2017-05-25 | Problema dell'albero ricoprente di peso minimo. Lemma del taglio e lemma del ciclo. Algoritmo di Kruskal. La Union-Find data structure. Algoritmo di Prim. |
| Lez 22(1) | 2017-05-30 | Riconoscimento di grafi bipartiti. Dall'analisi dei linguaggi di SI e di NO all'algoritmo. Leggere la struttura delle dimostrazioni. Definizione di s,t-flusso e di s,t-taglio. Buona congettura che lega s,t-flussi ed s,t-tagli. |
| Lez 22(2) | 2017-05-30 | Cammini come flussi elementari. Struttura di un algoritmo per il massimo flusso e ruolo delle buone congetture nella sua architettura. Dimostrazione del max-flow/min-cut theorem. |
| Lez 23 | 2017-06-01 | Bellman-Ford: esempio di comportamento pseudo-polinomiale ed algoritmo fortemente polinomiale. Problema del matching bipartito: alcune formulazioni. Teorema di Berge e buon teorema di Konig. Algoritmo per il massimo matching in grafo bipartito. |
| Lez 24(1) | 2017-06-06 | problema dei 4 colori, grafi planari, dualita`, deletion e contraction, formula di Eulero, teorema di Kuratowski, congettura di Wagner, graph minor theorem. |
| Lez 24(2) | 2017-06-06 | esercizio sui grafi: cicli dispari e bipartizioni, alberi ricoprenti di peso minimo. |
| Lez 25 | 2017-06-06 | esercizio sui grafi: planarita`, bipartizioni, alberi ricoprenti di peso minimo, alberi dei cammini minimi, flussi e tagli. |
| Lezione num(part) | year-month-day | content |
|---|---|---|
| Lez 1(1) | 2016-03-01 | Presentazione del Corso. -il sito del corso: come raggiungerlo, cosa contiene, temi svolti, CMS, video lezioni. -contenuti del corso: problem solving, ricorsione, programmazione dinamica, grafi ed ottimizzazione combinatorica, programmazione lineare, invito alla teoria della complessita'. - storia a ruolo della ricerca operativa. - obiettivi e taglio del corso: fuoco sul piano metodologico, cura delle competenze di dettaglio. - organizzazione e concezione dell'esame. |
| Lez 1(2) | 2016-03-01 | Problemi, istanze, algoritmi, risorse. Ricerca del massimo. SelectionSort - analisi caso peggiore. InsertSort - analisi caso medio. MergeSort - divide et impera. |
| Lez 2 | 2016-03-03 | problema pirellone. Buone caratterizzazioni. Tiling. Invarianti per dire di NO. Ricorsione per dire di SI. Ricorsione: numero piastrellature bagno monodimensionale con piastrelle da 1 e 2. Ricorsione con memoizzazione. |
|
Lez 3(1) parte al calcolatore |
2016-03-08 | Codifichiamo al calcolatore e sperimentiamo le soluzioni ricorsiva e ricorsiva con memoizzazione viste per il calcolo del numero di piastrellature bagno monodimensionale. |
| Lez 3(2) | 2016-03-08 | Proposta del problema triangolo. Problema del problema borse di studio. Approfondimento sulla ricorsione. Affrontiamo le piastrellature del bagno 2xn. Quando la ricorsione richiede di introdurre un parametro in piu'. |
| Lez 4 | 2016-03-10 | Ricorsione, ricorsione con memoizzazione, e programmazione dinamica. Problema triangolo. Tiling di scacchiere 2^k x 2^k.|
| Lez 5(1) | 2016-03-15 | Problema borse di studio. Soluzione ricorsiva. Ricorsione con memoizzazione. Programmazione dinamica. Problema Pirellone: la buona caratterizzazione. |
| Lez 5(2) | 2016-03-15 | Un percorso piu' completo: problema funghi nel bosco. Esercizio di programmazione dinamica: massima sottosequenza comune. Massima sottosequenza crescente. Semplificare i problemi e portarli alla loro forma fondamentale. Ridurre un problema ad un altro: Massima sottosequenza crescente e' riducibile a massima sottosequenza comune. |
| Lez 6 | 2016-03-17 | Buone congetture crescono (e diventano teoremi): dei ragazzi hanno chiuso Pirellone. Problema cammini del robot in griglia rettangolare. Ricostruzione delle soluzioni in problemi trattati con la programmazione dinamica. Listare tutte le sottosequenze comuni di massima lunghezza. Ridurre massima sottosequenza comune a cammino minimo in un grafo. Ridurre massima sottosequenza comune a massima sequenza crescente. Algoritmo n log n per massima sottosequenza crescente. |
| Lez 7 | 2016-03-22 | Problema (modello) dello zaino. Dimostrazione che knapsack e' NP-completo. Riduzione di SAT a 3-SAT. Dimostrazione che la PLI e' NP-completa. Soluzione di programmazione dinamica. |
| Lez 8(1) | 2016-03-31 | Grafi come modelli. Problema dei ponti di Eulero. Cammini e cicli Euleriani. |
| Lez 8(2) | 2016-03-31 | Lemma delle strette di mano. Buona caratterizzazione dei grafi Euleriani e sua dimostrazione. Grafi diretti Euleriani. Problema della superstringa ottima. Problema del ciclo Hamiltoniano. Problema del capire se un grafo e' connesso. Buone congetture, linguaggio del SI e linguaggio del NO. |
| Lez 9(1) | 2016-04-05 | Connessione. Dai linguaggi del SI e del NO all'algoritmo. Algoritmo del fuoco. La BFS e la coda FIFO. Prefisso di cammino minimo e' cammino minimo. Grafi pesati, algoritmo di Dijkstra e priority queue. |
| Lez 9(2) | 2016-04-05 | La coda di priorita` come struttura di dati astratta. Implementazione della coda di priorita` tramite i binary heaps. Proposta dei problemi: capire ss e un grafo e' bipartito, capire se un grafo e' planare. |
| Lez 10 | 2016-04-07 | Sottografi e sottografi indotti. Caratterizzazione dei grafi bipartiti. Algoritmo e dimostrazione della caratterizzazione buon congetturata. Analisi della struttura dei certificati di SI ed altri indizi per trasformare una buona congettura in un algoritmo che la dimostri. Buone caratterizzazioni come strumento operativo e punto di riferimento. Problema del massimo matching in grafi bipartiti. Le buone caratterizzazioni di Konig ed Hall. Il teorema di Berge. Algoritmo ungherese e dimostrazioni. Grafi non bipartiti: Tutte ed Edmonds. |
| Lez 11(1) | 2016-04-12 | Modello del massimo flusso minimo taglio. Definizione di flusso e sua scomposizione in cammini. Flussi ammissibili. Buona congettura. Rete ausiliaria. Dimostrazione della buona congettura ed algoritmo. |
| Lez 11(2) | 2016-04-12 | Esercizio sul massimo flusso preso da tema d'esame. |
| Lez 12 | 2016-04-14 | L'algoritmo del massimo flusso visto era solo pseudopolinomiale. Il problema dei 4 colori e sua modellazione in termini di grafi. Il grafo duale. Deletion e contraction. Formula di Eulero. Comprendere cosa sia la planarita'. Il teorema di Kuratowski. La metacongettura di Wagner. Il graph minor theorem. |
| Lez 13(1) | 2016-04-19 | Analisi della relazione di dualita' per grafi planari. L'approccio di Tait. Congetture celebri e loro controesempi. La dimostrazione di NP-completezza di Holyer. Problema del minimum spanning tree. Lemma del ciclo e lemma del taglio. |
| Lez 13(2) | 2016-04-19 | Problema del minimum spanning tree. Algoritmo di Prim e algoritmo di Kruskal. Esercizi su grafi da tema esame. |
| Lez 14 | 2016-04-21 | Esercizi su grafi da tema esame. |
| Lez 15 | 2016-04-26 | La programmazione lineare. Problema con due variabili, metodo geometrico. Certificati di ottimalita', prezzi ombra. Il metodo del simplesso su quel problema. |
| Lez 16 | 2016-04-28 | Purtroppo non abbiamo il video. Il metodo del simplesso. Il tableau. |
| Lez 17(1) | 2016-05-03 | Problemi ad origine non ammissibile. Il metodo della variabile ausiliaria. Il metodo del simplesso a due fasi. |
| Lez 17(2) | 2016-05-03 | La degenerativita'. Il cicling. La regola di Bland. Il metodo delle perturbazioni. Il metodo lessicografico. |
| Lez 18 | 2016-05-05 | Teorema fondamentale della programmazione lineare. La teoria della dualita'. Formulazione e ruolo del problema duale. Il duale del duale e' il primale. |
| Lez 19(1) | 2016-05-10 | Scrittura del duale per problemi non in forma standard. Teorema della dualita' debole. Il teorema degli scarti complementari. |
| Lez 19(2) | 2016-05-10 | Sintesi sul teorema degli scarti complementari. Teorema della dualita' forte. Il simplesso duale. Il simplesso primale duale. |
| Lez 20(1) | 2016-05-17 | Quando gli scarti complementari consentono di ricostruire il certificato di ottimalita'. |
| Lez 20(2) | 2016-05-17 | Problema di cammini minimi trattato come problema di programmazione lineare. |
| Lez 21 | 2016-05-19 | Interpretazione economica delle variabili duali e del metodo del simplesso. Analisi dimensionale e ricostruzione di semantica. Prezzi ombra. Significato dei prezzi ombra per ottimi non degeneri ed entro un'intorno. Accenni all'analisi di sensitivia`. |
| Lez 22(1) | 2016-05-24 | Un esercizio di formulazione come problema di PL. Correzione di un tema di esame. |
|
Lez 22(2) ultima lezione |
2016-05-24 | Un esercizio di programmazione lineare ed analisi di sensitivita' sullo stesso. |
|
| created: 3 marzo 2016 updated: 3 giugno 2016 |
©
Department of Computer Science University of Verona |