matematica:asd:asd_14: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_14:start [05/06/2015 alle 06:10 (10 anni fa)] – Roberto Grossi | matematica:asd:asd_14:start [01/05/2019 alle 07:00 (6 anni fa)] (versione attuale) – [Algoritmi e Strutture dei Dati: A.A. 2014-2015] Roberto Grossi | ||
---|---|---|---|
Linea 2: | Linea 2: | ||
Prof. Roberto Grossi\\ | Prof. Roberto Grossi\\ | ||
- | Dott. Alessio Conte (conte@di.unipi.it) | + | Dott. Alessio Conte (supporto) |
{{: | {{: | ||
Linea 8: | Linea 8: | ||
==== Avvisi ==== | ==== 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' | ||
* IMPORTANTE: compilare il [[http:// | * IMPORTANTE: compilare il [[http:// | ||
* Sono disponibili i testi del [[progetto_14|[progetto]]] e del [[mini_progetto_14|[mini-progetto]]] | * Sono disponibili i testi del [[progetto_14|[progetto]]] e del [[mini_progetto_14|[mini-progetto]]] | ||
Linea 83: | Linea 84: | ||
|01.04.2015| Cuckoo hashing. | {{: | |01.04.2015| Cuckoo hashing. | {{: | ||
|10.04.2015| Grafi: rappresentazione e alcune proprieta' | |10.04.2015| Grafi: rappresentazione e alcune proprieta' | ||
- | |14.04.2015| Laboratorio: | + | |14.04.2015| Laboratorio: |
|15.04.2015| Visita in ampiezza (BFS) con coda implementata mediante liste. Diametro. | [CGGR, codice 8.1, 7.2.1] | | |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] | | |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: | + | |21.04.2015| Laboratorio: |
|22.04.2015| Grafi pesati e cammini minimi. Algoritmi di Dijstra e Floyd-Warshall | [CGGR, 7.4 ] | | |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] | | |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: | + | |28.04.2015| Laboratorio: |
|29.04.2015| MST: algoritmo di Kruskal con struttura di dati per union-find e analisi ammortizzata. | [CGGR, 5.3, 7.5.2] | | |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: | |05.05.2015| Laboratorio: | ||
- | |06.05.2015| Programmazione dinamica: Fibonacci e sottosequenza comune più lunga. | [CGGR, ] | | + | |06.05.2015| Programmazione dinamica: Fibonacci e sottosequenza comune più lunga. | [CGGR, |
- | |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, |
|12.05.2015| Laboratorio: | |12.05.2015| Laboratorio: | ||
|13.05.2015| Laboratorio: | |13.05.2015| Laboratorio: | ||
- | |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, |
- | |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, |
- | |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, |
- | |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: | + | |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: |
- | |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, |
matematica/asd/asd_14/start.1433484649.txt.gz · Ultima modifica: 05/06/2015 alle 06:10 (10 anni fa) da Roberto Grossi