Differenze

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

--- matematica:asd:asd_17:start [04/05/2018 alle 15:02 (7 anni fa)] – [Programma] Roberto Grossi
+++ matematica:asd:asd_17:start [01/05/2019 alle 06:59 (6 anni fa)] (versione attuale) – [Algoritmi e Strutture dei Dati: A.A. 2017-2018] Roberto Grossi
@@ Linea 2: / Linea 2: @@
 Prof. Roberto Grossi\\
-Luca Versari
+Dott. Luca Versari (supporto)
 {{:matematica:asd:asd_14:asd_logo.jpg?200|}}
@@ Linea 8: / Linea 8: @@
 ==== Avvisi ====
-  * Lezioni del 9 e 16 maggio cancellate per consentire agli studenti di seguire un altro corso.
+  * Sono disponibili il [[progetto_17|[progetto]]] e il [[mini_progetto_17|[mini-progetto]]] del corso.
+  * Importante per consegnare il progetto e completare l'orale: sarò in missione nel periodo 19.09.18-15.10.18 e in congedo per motivi di studio nel periodo 01.11.2018-28.02.19 (ma sarò a Pisa fino al 16 novembre).
+  * Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento
   * Orario lezioni: mar 11-13, mer 14-16, ven 14-16.
-  * Per il ricevimento, consultare la [[http://www.di.unipi.it/~grossi|homepage del docente]].
-  * Per chi intende sostenere l'esame scritto, le date sono da concordare su appuntamento
-  * Mesi consigliati per consegnare il progetto e completare l'orale: gennaio, febbraio, marzo, giugno, luglio, settembre, ottobre.
   * [[https://www.dropbox.com/sh/o7hyigl7ffbbbxa/Awg3RMaGgR|Immagini usate]] durante la lezione.
   * [[http://www.di.unipi.it/~grossi/html5/|Visualizzazioni in HTML5]] mostrate a lezione.
@@ Linea 45: / Linea 44: @@
   * Parte prima, a scelta una delle seguenti possibilità:
     * [[progetto_17|[progetto]]] con sviluppo di nuovi algoritmi e relativa implementazione, avente una votazione in trentesimi (non richiede la presentazione del mini-progetto).
-    * scritto con esercizi da svolgere, avente una votazione in trentesimi, più un [[mini_progetto16|[mini-progetto]]] con votazione booleana (prova superata o meno per valutare le capacità programmative);
+    * scritto con esercizi da svolgere, avente una votazione in trentesimi, più un [[mini_progetto_17|[mini-progetto]]] con votazione booleana (prova superata o meno per valutare le capacità programmative);
-    * seminario basato su un argomento di ricerca nel campo dell'algoritmica, avente una votazione in trentesimi, più un [[mini_progetto16|[mini-progetto]]] con votazione booleana (vedi sopra);
+    * seminario basato su un argomento di ricerca nel campo dell'algoritmica, avente una votazione in trentesimi, più un [[mini_progetto_17|[mini-progetto]]] con votazione booleana (vedi sopra);
   * Parte seconda, comune per tutti: verifica tramite l'orale basato sul programma dettagliato (vedi sotto).
@@ Linea 73: / Linea 72: @@
 |09.03.2018| Heap binario implicito. Heapsort. | [CGGR par. 2.4, 3.6, 3.7] |
 |13.03.2018| Divide et impera, relazioni di ricorrenza e teorema principale: ricerca binaria, moltiplicazione veloce tra matrici; coppia di punti più vicini.  | [CGGR, par.3.6, 3.7] |
-|14.03.2018| Laboratorio |ordinamento e problemi collegati (parte II). | [[http://carp.di.unipi.it/asd1718/#/task/kmin/statement]]  [[http://carp.di.unipi.it/asd1718/#/task/sort_dup/statement]] [[http://carp.di.unipi.it/asd1718/#/task/inversions/statement]]|
+|14.03.2018| Laboratorio: ordinamento e problemi collegati (parte II). | [[http://carp.di.unipi.it/asd1718/#/task/kmin/statement]]  [[http://carp.di.unipi.it/asd1718/#/task/sort_dup/statement]] [[http://carp.di.unipi.it/asd1718/#/task/inversions/statement]]|
 |16.03.2018| Divide et impera su alberi: problemi decomponibili. Visita di alberi. Ricerca binaria e albero binario di ricerca corrispondente.  Alberi binari di ricerca: ricerca, inserimento, cancellazione. | [CGGR par. 4.4.1] |
 |20.03.2018| Il problema del dizionario: realizzazione mediante array, liste e alberi binari di ricerca. Alberi binari di ricerca AVL: ricerca, inserimento, cancellazione. | [CGGR, par. 4.1, 4.4.2] |
-|21.03.2018| Laboratorio | [[http://carp.di.unipi.it/asd1718/#/task/bst_dup/statement]] |
+|21.03.2018| Laboratorio: alberi binari di ricerca | [[http://carp.di.unipi.it/asd1718/#/task/bst_dup/statement]] |
 |23.03.2018| Discussione dettagliata del codice per gli alberi binari di ricerca AVL. | [CGGR, par. 4.1, 4.4.2] |
 |27.03.2018| Funzioni hash e tabelle hash con liste concatenate e indirizzamento aperto | [CGGR, par. 4.3] |
@@ Linea 82: / Linea 81: @@
 |06.04.2018| Cuckoo hashing.| {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Notes}} {{:magistraleinformatica:alg2:algo2_16:cuckoohashinsertion.pdf|Note in inglese}} |
 |10.04.2018| Skip list. Karp-Rabin fingerprint e string matching. |[CGGR, par. 5.2] [CLRS par.32.2] |
-|11.04.2018| Laboratorio | - |
+|11.04.2018| Laboratorio: hashing (parte I) | [[http://carp.di.unipi.it/asd1718/#/task/hash_dup/statement]] |
 |13.04.2018| Grafi: alcune proprietà combinatorie; esempi di problemi; rappresentazione in memoria. Visita in profondità (DFS) di un grafo, cicli, e ordinamento topologico.  | [CGGR, par. 7.1, 7.2.1] |
 |17.04.2018| Visita in ampiezza (BFS) con coda implementata mediante liste. Diametro. Grafi pesati e cammini minimi. Algoritmo di Dijkstra.  | CGGR, par. 7.3.1, 7.4] |
-|18.04.2018| Laboratorio | - |
+|18.04.2018| Laboratorio: hashing (parte II) | [[http://carp.di.unipi.it/asd1718/#/task/hash_dup/statement]] |
 |20.04.2018| Algoritmo di Floyd-Warshall. Albero di ricoprimento minimo (MST): regola del ciclo e del taglio. Algoritmo di Jarnik-Prim mediante heap. | [CGGR, par. 7.5.1-7.5.2] |
 |24.04.2018| Programmazione dinamica. Fibonacci e sottosequenza comune più lunga. Zaino (knapsack). Problemi pseudo-polinomiali. | [CGGR, par. 6.1, 6.3-6.5] |
-|27.04.2018| Algoritmo di Kursaal per MST con struttura di dati per union-find e analisi ammortizzata. | [CGGR, par. 5.3, 7.5.3] |
+|27.04.2018| Algoritmo di Kruskal per MST con struttura di dati per union-find e analisi ammortizzata. | [CGGR, par. 5.3, 7.5.3] |
+|02.05.2018| Laboratorio: grafi | [[http://carp.di.unipi.it/asd1718/#/task/graph_dup/statement]] [[http://carp.di.unipi.it/asd1718/#/task/diameter_dup/statement]] |
+|04.05.2018| Classi di complessità P e NP: esempio dei cicli euleriani e hamiltoniani (HAM) nei grafi, colorazione di mappe (grafi) planari. Nozione di certificato polinomiale. Definizione della classe NP. Riduzione polinomiale. Esempio da HAM a commesso viaggiatore (TSP). | [CGGR, par. 8.1-8.3] [[http://9gag.com/tv/p/ayzL0v/p-vs-np-and-the-computational-complexity-zoo|video]] |
+|08.05.2018| Relazione tra certificato polinomiale e non-determinismo polinomiale. Proprietà della riduzione polinomiale e definizione della classe NPC (problemi NP-completi). Problema della soddisfacibilità (SAT) e Teorema di Cook-Levin. Riduzione da 3-colorazione di mappe (3-COL) a SAT. | [CGGR, par. 8.4-8.6]|
+|11.05.2018| Riduzioni a la Karp: da SAT a soddisfacibilità con clausole a 3 letterali (3-SAT), da vertex cover (VC) a 3-SAT, da independent set (IS) a VC, da hitting set (HS) a VC. Algoritmi di r-approssimazione.| [CGGR, par. 8.8-8.9] |
+|15.05.2018| 2-approssimazione per min VC e max SAT. Inapprossimabilità di TSP nel caso generale e sua 2-approssimazione per istanze metriche. | [CGGR, par. 8.10-8.11] [TBA] |
+|18.05.2018| Algoritmi esatti parametrizzati: esempio con min VC | [[https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf|sect. 2.2.1, 3.1]] |
+|23.05.2018| Esercitazione: grafi e discussione progetto | [[http://carp.di.unipi.it/asd1718/#/task/dijkstra/statement]] |