Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
Entrambe le parti precedenti la revisione Revisione precedente Prossima revisione | Revisione precedente | ||
matematica:asd:asd_18:start [12/04/2019 alle 13:42 (5 anni fa)] Linda Pagli [Programma] |
matematica:asd:asd_18:start [22/07/2019 alle 15:13 (5 anni fa)] Linda Pagli [Date esame orale di teoria luglio 19] |
||
---|---|---|---|
Linea 2: | Linea 2: | ||
Prof. Linda Pagli (teoria)\\ | Prof. Linda Pagli (teoria)\\ | ||
- | Prof. Roberto Grossi (lab) | + | Prof. Roberto Grossi (lab)\\ |
+ | Dott. Giulia Punzi (supporto) | ||
{{: | {{: | ||
Linea 8: | Linea 9: | ||
==== Avvisi ==== | ==== Avvisi ==== | ||
+ | * Sono disponibili il [[progetto_18|[progetto]]] e il [[mini_progetto_18|[mini-progetto]]] del corso. | ||
* Per chi intende sostenere l' | * Per chi intende sostenere l' | ||
* Orario lezioni: mar 14: | * Orario lezioni: mar 14: | ||
* Per il ricevimento, | * Per il ricevimento, | ||
* Nota: il contenuto di questa pagina è preliminare | * Nota: il contenuto di questa pagina è preliminare | ||
- | * **OGGI la lezione é soppressa**. La lezione si terrà | ||
==== Motivazioni ==== | ==== Motivazioni ==== | ||
Linea 47: | Linea 48: | ||
+ | ==== Date esame orale di teoria luglio 2019 ==== | ||
+ | |||
+ | * lunedì 15 ore 11.30 ufficio Pagli (studio 277 Dipartimento di informatica) | ||
+ | * martedì 23 ore 10 ufficio Pagli | ||
+ | * lunedì 29 ore 11 ufficio Pagli | ||
==== Testi e materiale didattico ==== | ==== Testi e materiale didattico ==== | ||
Linea 66: | Linea 72: | ||
|26.02.2019| Presentazione del corso. Complessità di un algoritmo e di un problema nel modello di calcolo RAM (random access machine): esempio della moltiplicazione egizia. | [CGGR, cap.0, par.1.2] | | |26.02.2019| Presentazione del corso. Complessità di un algoritmo e di un problema nel modello di calcolo RAM (random access machine): esempio della moltiplicazione egizia. | [CGGR, cap.0, par.1.2] | | ||
|28.02.2019| Le notazioni asintotiche, | |28.02.2019| Le notazioni asintotiche, | ||
- | |28.02.2019|Il problema del Sorting: SelectionSort, | + | |29.02.2019|Il problema del Sorting: SelectionSort, |
|05.03.2019| Algoritmi randomizzati e variabili indicatrici: | |05.03.2019| Algoritmi randomizzati e variabili indicatrici: | ||
|07.03.2019| Laboratorio: | |07.03.2019| Laboratorio: | ||
Linea 76: | Linea 82: | ||
|21.03.2019| Laboratorio: | |21.03.2019| Laboratorio: | ||
|22.03.2019|Alberi definizioni e proprietà. Alberi binari: rappresentazione in memoria, algoritmi ricorsivi di tipo Divide et Impera, Visite e applicazioni. Trasformazione da alberi ordinati a alberi binari.| [ CGGR da 3.8 a fine capitolo]. | | |22.03.2019|Alberi definizioni e proprietà. Alberi binari: rappresentazione in memoria, algoritmi ricorsivi di tipo Divide et Impera, Visite e applicazioni. Trasformazione da alberi ordinati a alberi binari.| [ CGGR da 3.8 a fine capitolo]. | | ||
- | |22.03.2019|Alberi binari di ricerca, operazioni di ricerca, inserzione, predecessore e successore, cancellazione e ordinamento. Alberi AVL, altezza nel caso pessimo, rotazioni.| [ CGGR par. 4.4]. | | + | |25.03.2019|Alberi binari di ricerca, operazioni di ricerca, inserzione, predecessore e successore, cancellazione e ordinamento. Alberi AVL, altezza nel caso pessimo, rotazioni.| [ CGGR par. 4.4]. | |
|28.03.2019| Laboratorio: | |28.03.2019| Laboratorio: | ||
|29.03.2019|Tabelle Hash per implementare dizionari. Funzioni hash metodi di gestione delle collisioni. Liste di trabocco. Scansione lineare. Tempo medio di ricerca.| [ CGGR par. 4.1-4.3 fino al teorema 4.2.]. | | |29.03.2019|Tabelle Hash per implementare dizionari. Funzioni hash metodi di gestione delle collisioni. Liste di trabocco. Scansione lineare. Tempo medio di ricerca.| [ CGGR par. 4.1-4.3 fino al teorema 4.2.]. | | ||
Linea 83: | Linea 89: | ||
|08.04.2019| Grafi, terminologia, | |08.04.2019| Grafi, terminologia, | ||
|09.04.2019| Cammini minimi su albero BSF, BSF-Explore, | |09.04.2019| Cammini minimi su albero BSF, BSF-Explore, | ||
+ | |11.04.2019| Laboratorio: | ||
|12.04.2019| Algoritmo di Dijkstra, introduzione al problema del Minimal Spanning Tree| [ CGGR par. 7.4.1 e 7.4.2, 7.5 e 7.5.1] | | |12.04.2019| Algoritmo di Dijkstra, introduzione al problema del Minimal Spanning Tree| [ CGGR par. 7.4.1 e 7.4.2, 7.5 e 7.5.1] | | ||
+ | |30.04.2019| Hash universale e hash perfetto | {{ : | ||
+ | |02.05.2019| Laboratorio: | ||
+ | |03.05.2019| Cuckoo hashing.| {{: | ||
+ | |07.05.2019| Problema del Minimal Spanning Tree: algoritmo di Kruskal e algoritmo di Jarnik-Prim| [ CGGR par. 7.5] | | ||
+ | |09.05.2019| Laboratorio: | ||
+ | |10.05.2019| Paradigma della programmazione dinamica, numeri di Fibonacci, problema della Longest Common Subsequence, | ||
+ | |14.05.2019| Paradigma della programmazione dinamica: ottimalità della sotto-struttura per LCS, Edit Distance e Zaino. Pseudopo-polinomialità| [ CGGR par.6.5, 6.8, CLRS pag.325 , [[http:// | ||
+ | | ||
+ | |16.05.2019| Laboratorio: | ||
+ | |17.05.2019|GeneraBinarie e GeneraPermutazioni. Algoritmi Greedy per lo Zaino frazionato. Algoritmi enumerativi per lo Zaino0-1 e per il ciclo Hamiltoniano di un grafo. Verifica polinomiale. Classi P e NP | [ CGGR par.8.1, 8.2, CLRS pag.885] | | ||
+ | |21.05.2019| Laboratorio: | ||
+ | |23.05.2019| Laboratorio: | ||
+ | |24.05.2019| Riduzione polinomiale. Problemi NP-completi. Teorema di Cook-Levin, enunciato. Problemi aperti. Problemi NP-hard. Tecnica di restrizione.| [ CGGR par.8.3, 8.4, 8.5, 8.6, 8.7] | | ||
+ | |28.05.2019| Esempi di dimostrazioni di NP-completezza. Tecnica di similitudine , tecnica del gadget. Algoritmi di approssimazione. Algoritmi 2-approssimati per Vertex Cover e TSP, dimostrazioni.| [ CGGR par.8.8, 8.10, 8.11. CLRS pag.926-927] | | ||
+ | |30.05.2019| Question time sul progetto. | {{ : |