Strumenti Utente

Strumenti Sito


matematica:asd:asd_16:start

Differenze

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

Link a questa pagina di confronto

Entrambe le parti precedenti la revisione Revisione precedente
Prossima revisione
Revisione precedente
matematica:asd:asd_16:start [22/05/2017 alle 15:58 (7 anni fa)]
Roberto Grossi
matematica:asd:asd_16:start [01/05/2019 alle 06:59 (5 anni fa)] (versione attuale)
Roberto Grossi [Algoritmi e Strutture dei Dati: A.A. 2016-2017]
Linea 2: Linea 2:
  
 Prof. Roberto Grossi\\ Prof. Roberto Grossi\\
-Luca Versari+Dott. Luca Versari (supporto)
  
 {{:matematica:asd:asd_14:asd_logo.jpg?200|}} {{:matematica:asd:asd_14:asd_logo.jpg?200|}}
- 
 ==== Avvisi ==== ==== Avvisi ====
  
Linea 62: Linea 61:
  
  
-[[http://unimap.unipi.it/registri/printregistriNEW.php?re= 190090::::&ri=9172|Registro delle lezioni]]+[[http://unimap.unipi.it/registri/printregistriNEW.php?re=190783::::&ri=9172|Registro delle lezioni]]
  
 ^ Data ^ Argomento ^ Riferimenti e note ^ ^ Data ^ Argomento ^ Riferimenti e note ^
Linea 88: Linea 87:
 |24.04.2017| Grafi: alcune proprietà combinatorie; esempi di problemi; rappresentazione in memoria. Chiusura transitiva. | [CGGR, par. 7.1] |  |24.04.2017| Grafi: alcune proprietà combinatorie; esempi di problemi; rappresentazione in memoria. Chiusura transitiva. | [CGGR, par. 7.1] | 
 |26.04.2017| Laboratorio. Lettura e creazione di un grafo. |[[http://carp.di.unipi.it/asd1617/#/task/graph/statement|lab8]] |  |26.04.2017| Laboratorio. Lettura e creazione di un grafo. |[[http://carp.di.unipi.it/asd1617/#/task/graph/statement|lab8]] | 
-|28.04.2017| ccc | [CGGR, par. 7.1] | +|28.04.2017| Visita in profondità (DFS) di un grafo e ordinamento topologico.  Visita in ampiezza (BFS) con coda implementata mediante liste. Diametro. | [CGGR, par. 7.2.1, 7.3.1] | 
 |03.05.2017| Laboratorio. | ... |  |03.05.2017| Laboratorio. | ... | 
-|05.05.2017| ccc | [CGGR, par. 7.1] |  +|05.05.2017| 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]  |  
-|08.05.2017| ccc | [CGGR, par. 7.1] | +|08.05.2017| 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] | 
 |10.05.2017| Laboratorio. | ... |  |10.05.2017| Laboratorio. | ... | 
-|12.05.2017| ccc | ... | +|12.05.2017| 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] 
 |15.05.2017| 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]] |  |15.05.2017| 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]] | 
 |17.05.2017| Laboratorio: Discussione del progetto (I). | [[progetto_16|[progetto]]] |  |17.05.2017| Laboratorio: Discussione del progetto (I). | [[progetto_16|[progetto]]] | 
-|19.05.2017| 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]| +|19.05.2017| 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. 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]| 
 |22.05.2017| 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]  |22.05.2017| 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] 
 |24.05.2017| Laboratorio: Discussione del progetto (II). | [[progetto_16|[progetto]]] |  |24.05.2017| Laboratorio: Discussione del progetto (II). | [[progetto_16|[progetto]]] | 
matematica/asd/asd_16/start.1495468736.txt.gz · Ultima modifica: 22/05/2017 alle 15:58 (7 anni fa) da Roberto Grossi