Differenze

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

--- matematica:asd:asd_15:start [07/12/2016 alle 12:03 (8 anni fa)] – 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 96: / Linea 96: @@
 |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) | [[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. Inapprossimabilità di TSP nel caso generale e sua 2-approssimazione per istanze metriche. | [CGGR, par. 8.10-8.11] |
 |18.05.2016| Discussione del progetto su PDB. | [[https://www.dropbox.com/sh/xs7ai44i82q2hm8/AACCdbuqtV67hoK933ZevkWMa/Lezione10?dl=0|[laboratorio, lez.10]]] |