Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- matematica:asd:asd_18:start [01/05/2019 alle 06:41 (7 anni fa)] – [Programma] Roberto Grossi
+++ matematica:asd:asd_18:start [22/07/2019 alle 15:13 (6 anni fa)] (versione attuale) – [Date esame orale di teoria luglio 19] Linda Pagli
@@ Linea 2: / Linea 2: @@
 Prof. Linda Pagli (teoria)\\
-Prof. Roberto Grossi (lab)
+Prof. Roberto Grossi (lab)\\
+Dott. Giulia Punzi (supporto)
 {{:matematica:asd:asd_14:asd_logo.jpg?200|}}
@@ Linea 8: / Linea 9: @@
 ==== Avvisi ====
+  * Sono disponibili il [[progetto_18|[progetto]]] e il [[mini_progetto_18|[mini-progetto]]] del corso.
   * Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento
   * Orario lezioni: mar 14:00‑16:00 (Fib E1), gio 9:00‑11:00 (Fib M-Lab), ven 14:00‑16:00 (Fib E1)
   * Per il ricevimento, consultare la homepage dei docenti
   * Nota: il contenuto di questa pagina è preliminare
-  * **OGGI la lezione é soppressa**. La lezione si terrà  lun 8, 16:00-18.00 (Fib E1)
 ==== 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 ====
@@ Linea 83: / Linea 89: @@
 |08.04.2019| Grafi, terminologia, definizioni, rappresentazione in memoria, visita in ampiezza| [ CGGR par. 7.1,7.2.1 escluso codice 71. fino a pagina 222] |
 |09.04.2019| Cammini minimi su albero BSF, BSF-Explore, DFS ricorsiva e Ordinamento Topologico| [ CGGR par. 7.2.2 e 7.3] |
+|11.04.2019| Laboratorio: operazioni di range query (con priorità) in un albero binario di ricerca. | [[http://carp.di.unipi.it/asd1819/#/task/pbst/statement|lab]]  |
 |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 | {{ :matematica:asd:asd_17:clrsuniversalhash.pdf | CLRS par. 11.3.3}} {{ :matematica:asd:asd_17:clrsperfecthash.pdf | CLRS par. 11.5}} |
-|02.05.2019| Laboratorio: visita di grafi e diametro | [[http://carp.di.unipi.it/asd1819/#/task/diameter_dup_dup/statement|lab]]  |
+|02.05.2019| Laboratorio: visita di grafi e diametro (parte I)| [[http://carp.di.unipi.it/asd1819/#/task/diameter_dup_dup/statement|lab]]  |
 |03.05.2019| Cuckoo hashing.| {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Notes}} {{:magistraleinformatica:alg2:algo2_16:cuckoohashinsertion.pdf|Note in inglese}} |
+|07.05.2019| Problema del Minimal Spanning Tree: algoritmo di Kruskal e algoritmo di Jarnik-Prim| [ CGGR par. 7.5] |
+|09.05.2019| Laboratorio: visita di grafi e diametro (parte II)| [[http://carp.di.unipi.it/asd1819/#/task/diameter_dup_dup/statement|lab]]  |
+|10.05.2019| Paradigma della programmazione dinamica, numeri di Fibonacci, problema della Longest Common Subsequence, ricostruzione della sequenza| [ CGGR cap 6, fino a 6.3] |
+|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://didawiki.di.unipi.it/lib/exe/fetch.php/informatica/all-b/pd.pdf|Note di F.
+ Luccio]] ] |
+|16.05.2019| Laboratorio: rappresentazione dei grafi in memoria in C++ e presentazione progetto di esame| {{ :matematica:asd:asd_18:grafi.zip |codice }} {{ :matematica:asd:asd_18:progettoasd1819.pdf | lucidi}} |
+|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: discussione del progetto in aula. | {{ :matematica:asd:asd_18:progettoasd1819.pdf | lucidi}} |
+|23.05.2019| Laboratorio: creazione grafo di de Bruijn. | {{ :matematica:asd:asd_18:progettoasd1819.pdf | lucidi}} |
+|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. | {{ :matematica:asd:asd_18:progettoasd1819.pdf | lucidi}} |