matematica:asd:asd_15:start
Differenze
Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente | ||
| matematica:asd:asd_15:start [16/05/2016 alle 14:40 (8 anni fa)] – [Programma] Roberto Grossi | matematica:asd:asd_15:start [01/05/2019 alle 06:59 (5 anni fa)] (versione attuale) – [Algoritmi e Strutture dei Dati: A.A. 2015-2016] Roberto Grossi | ||
|---|---|---|---|
| Linea 2: | Linea 2: | ||
| Prof. Roberto Grossi\\ | Prof. Roberto Grossi\\ | ||
| - | Dott. Alessio Conte (conte@di.unipi.it) | + | Dott. Alessio Conte (supporto) |
| {{: | {{: | ||
| Linea 81: | Linea 81: | ||
| |01.04.2016| Sospensione della didattica disposta dal presidente di corso. | Elezioni studentesche | | |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] {{: | |04.04.2016| Hashing e tabelle hash. Liste trabocco, indirizzamento aperto, cuckoo hash (prima parte) | [CGGR, par. 4.3] {{: | ||
| - | |06.04.2016| Semplice implementazione del cuckoo hashing | [[http:// | + | |06.04.2016| Semplice implementazione del cuckoo hashing | [[http:// |
| |08.04.2016| Cuckoo hash (seconda parte) | {{: | |08.04.2016| Cuckoo hash (seconda parte) | {{: | ||
| |11.04.2016| Grafi: alcune proprietà combinatorie; | |11.04.2016| Grafi: alcune proprietà combinatorie; | ||
| - | |13.04.2016| Lettura da file di un grafo e creazione della sua rappresentazione in memoria mediante liste compatte di adiacenza | [[http:// | + | |13.04.2016| Lettura da file di un grafo e creazione della sua rappresentazione in memoria mediante liste compatte di adiacenza | [[http:// |
| |15.04.2016| Visita in profondità (DFS) di un grafo e ordinamento topologico. | [CGGR, par. 7.2.1, 7.3.1] | | |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] | | |18.04.2016| Visita in ampiezza (BFS) con coda implementata mediante liste. Diametro. | [CGGR, par. codice 8.1, 7.2.1] | | ||
| - | |20.04.2016| | + | |20.04.2016| |
| |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] | | |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| | + | |27.04.2016| |
| - | |29.04.2016| | + | |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] | | |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:// |
| - | |06.05.2016| cancellata | aule chiuse a causa sciopero | | + | |06.05.2016| |
| - | |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:// |
| - | |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:// |
| - | |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) | + | |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:// |
matematica/asd/asd_15/start.1463409601.txt.gz · Ultima modifica: 16/05/2016 alle 14:40 (8 anni fa) da Roberto Grossi