Differenze

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

--- matematica:asd:asd_15:start [16/05/2016 alle 14:35 (9 anni fa)] – [Programma] Roberto Grossi
+++ matematica:asd:asd_15:start [01/05/2019 alle 06:59 (6 anni fa)] (versione attuale) – [Algoritmi e Strutture dei Dati: A.A. 2015-2016] Roberto Grossi
@@ Linea 2: / Linea 2: @@
 Prof. Roberto Grossi\\
-Dott. Alessio Conte ([email protected])
+Dott. Alessio Conte (supporto)
 {{:matematica:asd:asd_14:asd_logo.jpg?200|}}
@@ Linea 81: / Linea 81: @@
 |01.04.2016| Sospensione della didattica disposta dal presidente di corso. | Elezioni studentesche |
 |04.04.2016| Hashing e tabelle hash. Liste trabocco, indirizzamento aperto, cuckoo hash (prima parte) | [CGGR, par. 4.3] {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Note in inglese}} |
-|06.04.2016| Semplice implementazione del cuckoo hashing | [[http://pages.di.unipi.it/grossi/ASD_LAB/06aprile2016/cuckoo_simple.c |simple cuckoo hash code]] |
+|06.04.2016| Semplice implementazione del cuckoo hashing | [[http://pages.di.unipi.it/grossi/ASD_LAB/06aprile2016/cuckoo_simple.c |[laboratorio, lez.5]]] |
 |08.04.2016| Cuckoo hash (seconda parte) | {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|Note in inglese}}  [[http://www.cs.toronto.edu/~wgeorge/csc265/2013/10/17/tutorial-5-cuckoo-hashing.html|analisi insert]] |
 |11.04.2016| Grafi: alcune proprietà combinatorie; esempi di problemi; rappresentazione in memoria. | [CGGR, par. 7.1] |
-|13.04.2016| Lettura da file di un grafo e creazione della sua rappresentazione in memoria mediante liste compatte di adiacenza | [[http://pages.di.unipi.it/grossi/ASD_LAB/lettura_grafo.c|codice]] |
+|13.04.2016| Lettura da file di un grafo e creazione della sua rappresentazione in memoria mediante liste compatte di adiacenza | [[http://pages.di.unipi.it/grossi/ASD_LAB/lettura_grafo.c|[laboratorio, lez.6]]] |
 |15.04.2016| Visita in profondità (DFS) di un grafo e ordinamento topologico. | [CGGR, par. 7.2.1, 7.3.1] |
 |18.04.2016| Visita in ampiezza (BFS) con coda implementata mediante liste. Diametro. | [CGGR, par. codice 8.1, 7.2.1] |
-|20.04.2016|  | [lab] |
+|20.04.2016| Scrittura di uno header in C/C++ per la lettura di un grafo da file | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AABWUoaJBbbMg4UtwQwvcbOaa/lezione7?dl=0|[laboratorio, lez.7a]]] |
-|22.04.2016|  | [CGGR, par. ] |
+|22.04.2016| Grafi pesati e cammini minimi. Algoritmi di Dijstra e Floyd-Warshall. Albero di ricoprimento minimo (MST): regola del ciclo e del taglio. | [CGGR, par. 7.4, 7.5.1] |
-|27.04.2016|  | [lab] |
+|27.04.2016| DFS, BFS e calcolo eccentricità di un grafo. | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AABWUoaJBbbMg4UtwQwvcbOaa/lezione7?dl=0|[laboratorio, lez.7b]]] |
-|29.04.2016|  | [CGGR, par. ] |
+|29.04.2016| Algoritmo di Jarnik-Prim mediante heap. Algoritmo di Kruskal con struttura di dati per union-find e analisi ammortizzata. | [CGGR, par. 5.3, 7.5.2-7.5.3] |
 |02.05.2016| Programmazione dinamica. Fibonacci e sottosequenza comune più lunga. Partizione (subset sum) e zaino (knapsack). Problemi pseudo-polinomiali. | [CGGR, par. 6.1, 6.3-6.5] |
-|04.05.2016| Programmazione dinamica per edit distance | [lab] |
+|04.05.2016| Programmazione dinamica per edit distance. | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AABzfJW6WqQGc1mKKGMx0fVia/lezione8?dl=0|[laboratorio, lez.8]]] |
-|06.05.2016| cancellata | aule chiuse a causa sciopero |
+|06.05.2016| Lezione cancellata. | Aule chiuse a causa sciopero. |
-|09.05.2016| Classi di complessità P e NP: esempio dei cicli euleriani e hamiltoniani (HAM) nei grafi. Nozione di certificato polinomiale. Definizione della classe NP. Relazione tra certificato polinomiale e non-determinismo polinomiale. Riduzione polinomiale. Esempio da HAM a commesso viaggiatore (TSP). | [CGGR, par. 8.1-8.3] |
+|09.05.2016| Classi di complessità P e NP: esempio dei cicli euleriani e hamiltoniani (HAM) nei grafi. Nozione di certificato polinomiale. Definizione della classe NP. Relazione tra certificato polinomiale e non-determinismo polinomiale. 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]] |
-|11.05.2016| Introduzione alla struttura delle proteine per il progetto (a cura del dott. Lorenzo Tattini). Parsing dei file PDB (Protein Data Bank) | [lab] |
+|11.05.2016| Introduzione alla struttura delle proteine per il progetto (a cura del dott. Lorenzo Tattini). Parsing dei file PDB (Protein Data Bank) | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AACaAA8CRSdsQBBx1IhhgltLa/Lezione9?dl=0|[laboratorio, lez.9]]] |
-|13.05.2016| Proprietà della riduzione polinomiale e definizione della classe NPC (problemi NP-completi). Problema della soddisfacibilità (SAT) e Teorema di Cook-Levin. Riduzione da SAT a 3-colorazione di mappe (3-COL). Riduzioni a la Karp: da soddisfacibilità con clausole a 3 letterali (3-SAT) a SAT, e da 3-SAT a vertex cover (VC). | [CGGR, par. 8.4-8.6, 8.8-8.10] |
+|13.05.2016| Proprietà della riduzione polinomiale e definizione della classe NPC (problemi NP-completi). Problema della soddisfacibilità (SAT) e Teorema di Cook-Levin. Riduzione da SAT a 3-colorazione di mappe (3-COL). Riduzioni a la Karp: da SAT a soddisfacibilità con clausole a 3 letterali (3-SAT), e da 3-SAT a vertex cover (VC). | [CGGR, par. 8.4-8.6, 8.8-8.10] |
-|16.05.2016| Algoritmi di r-approssimazione. 2-approssimazione per min VC e per MAX CUT. Inapprossimabilità di TSP nel caso generale e sua 2-approssimazione per istanze metriche. | [CGGR, par. 8.10-8.11] |
+|16.05.2016| Algoritmi di r-approssimazione. 2-approssimazione per min VC. Inapprossimabilità di TSP nel caso generale e sua 2-approssimazione per istanze metriche. | [CGGR, par. 8.10-8.11] |
-|17.05.2016| Discussione del progetto su PDB. | [lab] |
+|18.05.2016| Discussione del progetto su PDB. | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AACCdbuqtV67hoK933ZevkWMa/Lezione10?dl=0|[laboratorio, lez.10]]] |