Differenze

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

--- matematica:asd:asd_13:start [09/06/2014 alle 17:13 (11 anni fa)] – [Programma] Roberto Grossi
+++ matematica:asd:asd_13:start [25/07/2014 alle 14:32 (11 anni fa)] (versione attuale) – [Modalità d'esame] Roberto Grossi
@@ Linea 44: / Linea 44: @@
     * [[progetto_13|[progetto]]] con sviluppo di nuovi algoritmi e relativa implementazione, avente una votazione in trentesimi (non richiede la presentazione del mini-progetto).
   * Parte seconda, comune per tutti:
-    * verifica tramite l'orale basato sul programma dettagliato: Capitolo 0 ([[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|versione elettronica]]), Capitolo 1 (tranne par.1.3), Capitolo 2 (tranne par.2.2), Capitolo 3 (tranne par. 3.5), Capitolo 4 (par.4.5 facoltativo, [[http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf|cuckoo hashing]]), Capitolo 5 (solo par.5.1 e 5.2), Capitolo 6 (saltare), Capitolo 7 (par. 7.1, 7.2, 7.3.1), Capitolo 8 (tutto tranne par. 8.7 e 8.11). Guardare [[http://tinyurl.com/d9ajvky|errata-corrige]], integrazioni ed esempi utilizzando ALVIE sul [[http://wps.pearsoned.it/crescenzi_strutture-dati-algoritmi2/|sito Web]].
+    * verifica tramite l'orale basato sul programma dettagliato: Capitolo 0 ([[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|versione elettronica]]), Capitolo 1 (tranne par.1.3), Capitolo 2 (tranne par.2.2), Capitolo 3 (tranne par. 3.5), Capitolo 4 (più [[http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf|cuckoo hashing]]), Capitolo 5 (solo par.5.1), Capitolo 6 (par. 6.1, 6.3, 6.4, 6.5), Capitolo 7 (par. da 7.1 a 7.4), Capitolo 8 (par. da 8.1 a 8.5 più par. 8.8). Guardare [[http://tinyurl.com/d9ajvky|errata-corrige]], integrazioni ed esempi utilizzando ALVIE sul [[http://wps.pearsoned.it/crescenzi_strutture-dati-algoritmi2/|sito Web]].
@@ Linea 57: / Linea 57: @@
 ==== Programma ====
-[[http://unimap.unipi.it/registri/printregistriNEW.php|Registro delle lezioni]]
+[[http://unimap.unipi.it/registri/printregistriNEW.php?re=130300::::&ri=9172|Registro delle lezioni]]
 ^ Data ^ Argomento ^ Riferimenti e note ^
@@ Linea 63: / Linea 63: @@
 | 07.03.2014| Scheduling di lavori e ordinamento (insertion sort, selection sort), con analisi asintotica della complessità. Complessità di un algoritmo e di un problema, limiti superiori e inferiori. "Fooling argument" per limiti inferiori lineari. | [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|CGGR, par. 0.7, par.1.2]] |
 | 07.03.2014| Segmento di somma massima | [[laboratorio_13|lab]] |
-| 10.03.2014| Strutture di dati per rappresentare le istanze dei problemi: elementari e sequenze (array e liste). Memorizzazione di array e liste e impatto sul costo di accesso. Array di dimensione variabile. | [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|CGGR, par.  0.1, 0.2, 0.4, par. 1.1]] |
+| 11.03.2014| Strutture di dati per rappresentare le istanze dei problemi: elementari e sequenze (array e liste). Memorizzazione di array e liste e impatto sul costo di accesso. Array di dimensione variabile. | [[http://wps.pearsoned.it/wps/media/objects/14141/14480998/calcolabilita_ecomplessita_.pdf|CGGR, par.  0.1, 0.2, 0.4, par. 1.1]] |
 | 14.03.2014| Limiti superiori e inferiori per il problema dell'ordinamento mediante confronti. Semplici esempi di algoritmi lineari (ordinare zeri e uni mediante scambi). | [CGGR, teorema 2.4] |
 | 14.03.2014| Array di dimensione variabile | [[laboratorio_13|lab]] |
@@ Linea 86: / Linea 86: @@
 | 09.05.2014| Esempi di programmazione dinamica | [[laboratorio_13|lab]] |
 | 13.05.2014| Cammini minimi e algoritmo di Dijkstra. Pesi negativi: algoritmi di Bellman-Ford e Floyd-Warshall.| [CGGR, par.7.4] |
-| 16.05.2014| Cammini euleriani e hamiltoniani. Classi di complessità P e NP. Colorazioni di grafi. Problema della soddisfacibilità. Riduzioni polinomiali e teorema di Cook-Levin (senza dimostrazione). | [CGGR, par. 8.1-8.5] |
+| 16.05.2014| Cammini euleriani e hamiltoniani. Classi di complessità P e NP. Colorazioni di grafi. Problema della soddisfacibilità (SAT). Riduzioni polinomiali e teorema di Cook-Levin (senza dimostrazione). | [CGGR, par. 8.1-8.5] |
 | 16.05.2014| Generazione di grafi e visita in ampiezza | [[laboratorio_13|lab]] |
-| 20.05.2014| Lezione | [CGGR, par.] |
+| 20.05.2014| Riduzione da 3-colorazione di mappe a SAT. Karp: riduzione da SAT a 3-SAT, e da 3-SAT a vertex cover (VC). | [CGGR, par. 8.1-8.5, 8.8]  |
 | 23.05.2014| sospensione della didattica | elezioni |
 | 23.05.2014| sospensione della didattica | elezioni |