Differenze

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

--- matematica:asd:asd_17:start [08/05/2018 alle 12:29 (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 88: / Linea 87: @@
 |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| | |
+|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| | |
+|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| | |
+|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| | |
+|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| | |
+|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| Laboratorio: grafi e progetto | [[http://carp.di.unipi.it/asd1718/#/task/dijkstra/statement]] |
+|23.05.2018| Esercitazione: grafi e discussione progetto | [[http://carp.di.unipi.it/asd1718/#/task/dijkstra/statement]] |