Differenze

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

--- matematica:asd:asd_18:start [01/05/2019 alle 07:03 (6 anni fa)] – [Avvisi] 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 9: / 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
 ==== Motivazioni ====
@@ Linea 48: / 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 89: / Linea 94: @@
 |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}} |