Differenze

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

--- matematica:asd:asd_14:start [05/06/2015 alle 06:00 (9 anni fa)] – [Programma] Roberto Grossi
+++ matematica:asd:asd_14:start [01/05/2019 alle 07:00 (5 anni fa)] (versione attuale) – [Algoritmi e Strutture dei Dati: A.A. 2014-2015] Roberto Grossi
@@ Linea 2: / Linea 2: @@
 Prof. Roberto Grossi\\
-Dott. Alessio Conte (conte@di.unipi.it)
+Dott. Alessio Conte (supporto)
 {{:matematica:asd:asd_14:asd_logo.jpg?200|}}
@@ Linea 8: / Linea 8: @@
 ==== Avvisi ====
+  * La mattina di venerdì 24 luglio sarà dedicata a chi vuole sostenere orali e/o consegnare il progetto a partire dalle ore 8:30. L'occasione successiva sarà fissata a fine agosto o inizio settembre (data da concordare con gli eventuali interessati).
   * IMPORTANTE: compilare il [[http://www.questionario.unipi.it|questionario in rete]]
   * Sono disponibili i testi del [[progetto_14|[progetto]]] e del [[mini_progetto_14|[mini-progetto]]]
@@ Linea 83: / Linea 84: @@
 |01.04.2015| Cuckoo hashing. | {{: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]]|
 |10.04.2015| Grafi: rappresentazione e alcune proprieta'. Grafi bipartiti e bicolorazione.  | [CGGR, 7.1] |
-|14.04.2015| Laboratorio: dizionari di stringhe | [[https://www.dropbox.com/sh/uz2briuk0ept1ju/AABNknFKnBBK8KCtxR7TgUGTa?dl=0|[laboratorio, lez. 6]]]|
+|14.04.2015| Laboratorio: dizionari di stringhe e ricerca binaria | [[https://www.dropbox.com/sh/uz2briuk0ept1ju/AABNknFKnBBK8KCtxR7TgUGTa?dl=0|[laboratorio, lez. 6]]]|
 |15.04.2015| Visita in ampiezza (BFS) con coda implementata mediante liste. Diametro. | [CGGR, codice 8.1, 7.2.1] |
 |17.04.2015| Visita in profondità (DFS) mediante ricorsione. Alberi BFS e DFS. DAG e ordinamento topologico.| [CGGR, 7.2.2, 7.3.1] |
-|21.04.2015| Laboratorio: discussione degli elaborati con gli studenti | [[https://www.dropbox.com/sh/uz2briuk0ept1ju/AABNknFKnBBK8KCtxR7TgUGTa?dl=0|[laboratorio]]]|
+|21.04.2015| Laboratorio: word-graph in liste di adiacenza relativo al testo indicizzato nel dizionario | [[https://www.dropbox.com/sh/uz2briuk0ept1ju/AABNknFKnBBK8KCtxR7TgUGTa?dl=0|[laboratorio, lez.7]]]|
 |22.04.2015| Grafi pesati e cammini minimi. Algoritmi di Dijstra e Floyd-Warshall | [CGGR, 7.4 ] |
 |24.04.2015| Albero di ricoprimento minimo (MST): regola del ciclo e del taglio. Algoritmo di Jarnik-Prim mediante heap. | [CGGR, 7.5.1, 7.5.3] |
-|28.04.2015| Laboratorio:  discussione degli elaborati con gli studenti | [[https://www.dropbox.com/sh/uz2briuk0ept1ju/AABNknFKnBBK8KCtxR7TgUGTa?dl=0|[laboratorio]]]|
+|28.04.2015| Laboratorio: DFS e ricerca di cicli nei grafi | [[https://www.dropbox.com/sh/uz2briuk0ept1ju/AABNknFKnBBK8KCtxR7TgUGTa?dl=0|[laboratorio, lez.8]]]|
 |29.04.2015| MST: algoritmo di Kruskal con struttura di dati per union-find e analisi ammortizzata. | [CGGR, 5.3, 7.5.2] |
 |05.05.2015| Laboratorio: progetto d'esame | [[progetto_14|[progetto]]]|
-|06.05.2015| Programmazione dinamica: Fibonacci e sottosequenza comune più lunga. | [CGGR, ] |
+|06.05.2015| Programmazione dinamica: Fibonacci e sottosequenza comune più lunga. | [CGGR, 6.1, 6.3] |
-|08.05.2015| Programmazione dinamica: Partizione (subset sum) e zaino (knapsack). Problemi pseudo-polinomiali. | [CGGR, ]|
+|08.05.2015| Programmazione dinamica: Partizione (subset sum) e zaino (knapsack). Problemi pseudo-polinomiali. | [CGGR, 6.4, 6.5]|
 |12.05.2015| Laboratorio: edit distance | [[https://www.dropbox.com/sh/uz2briuk0ept1ju/AABNknFKnBBK8KCtxR7TgUGTa?dl=0|[laboratorio, lez.9]]] |
 |13.05.2015| Laboratorio: progetto d'esame | [[progetto_14|[progetto]]] |
-|15.05.2015| Classi di complessità P e NP: esempio dei cicli euleriani e hamiltoniani (HAM) nei grafi. Nozione di certificato polinomiale. | [CGGR, ] |
+|15.05.2015| Classi di complessità P e NP: esempio dei cicli euleriani e hamiltoniani (HAM) nei grafi. Nozione di certificato polinomiale. | [CGGR, 8.1, 8.2] |
-|19.05.2015| Definizione della classe NP. Relazione tra certificato polinomiale e non-determinismo polinomiale. Riduzione polinomiale. Esempio da HAM a commesso viaggiatore (TSP). | [CGGR, ] |
+|19.05.2015| Definizione della classe NP. Relazione tra certificato polinomiale e non-determinismo polinomiale. Riduzione polinomiale. Esempio da HAM a commesso viaggiatore (TSP). | [CGGR, 8.3] |
-|20.05.2015| 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). | [CGGR, ] |
+|20.05.2015| 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). | [CGGR, 8.4, 8.5] |
-|22.05.2015| Riduzioni a la Karp: da soddisfacibilità con clausole a 3 letterali (3-SAT) a SAT, e da 3-SAT a vertex cover (VC). Algoritmi di r-approssimazione: min VC. | [CGGR, ] |
+|22.05.2015| Riduzioni a la Karp: da soddisfacibilità con clausole a 3 letterali (3-SAT) a SAT, e da 3-SAT a vertex cover (VC). Algoritmi di r-approssimazione: min VC. | [CGGR, 8.6, 8.8, 8.9, 8.10] |
-|29.05.2015| 2-approssimazione per min VC. Inapprossimabilità di TSP nel caso generale e sua 2-approssimazione per istanze metriche. | [CGGR, ] |
+|29.05.2015| 2-approssimazione per min VC. Inapprossimabilità di TSP nel caso generale e sua 2-approssimazione per istanze metriche. | [CGGR, 8.10, 8.11] |