Differenze

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

--- magistraleinformatica:alg2:algo2_11:start [19/12/2011 alle 10:58 (13 anni fa)] – Roberto Grossi
+++ magistraleinformatica:alg2:algo2_11:start [04/10/2015 alle 10:07 (10 anni fa)] (versione attuale) – Roberto Grossi
@@ Linea 4: / Linea 4: @@
 === Avviso ===
-Le lezioni terminano il 7 dicembre 2011 e sono previste due lezioni extra, il 24.11 e l'1.12 ore 9-11 in aula N1.
+** Maltempo ** La prova di esame di "Algoritmica e Laboratorio" e di "Algoritmica 2" dell'1.2.2012 si svolgerà regolarmente. Tuttavia, per gli studenti iscritti a tale prova (nel calendario degli appelli della sezione didattica del sito www.di.unipi.it) ma impossibilitati a partecipare a causa del maltempo, sarà fissata una prova di recupero in data da concordare direttamente con il prof. Grossi via email.
+Com'è consuetudine, il voto finale dipende dal voto dell'esame scritto e da quello dell'esame orale. Per iscriversi all'esame orale, presentarsi nello studio del docente all'ora indicata, per redigere un calendario insieme agli altri studenti interessati all'esame orale. In caso di impegni, scrivere il proprio nome nel foglio/calendario che verrà successivamente appeso sulla porta del docente.
 === Date d'esame ===
@@ Linea 11: / Linea 14: @@
 | 21/12/2011 | 15:00 | Aula C1 | Compitino | Iscriversi all'esame |
 | 11/01/2012 | 09:00 | Aula A | Primo appello | Iscriversi all'esame |
+| 16/01/2012 | 09:00 | studio | Orali | Partecipare per fissare il calendario |
 | 01/02/2012 | 09:00 | Aula A | Secondo appello | Iscriversi all'esame |
+| 06/02/2012 | 09:00 | studio | Orali | Partecipare per fissare il calendario |
 === Obiettivi di apprendimento ===
@@ Linea 61: / Linea 66: @@
 === Materiale didattico ===
-  * ESERCITAZIONI
+  * ESERCITAZIONI - PROBLEM SOLVING
-    * Elenco dei problemi discussi {{:magistraleinformatica:alg2:algo2_11:esercitazioni2011.pdf|Elenco}}
+    * Problemi discussi (non è detto che abbiano un'unica soluzione) {{:magistraleinformatica:alg2:algo2_11:esercitazioni2011.pdf|[Elenco]}}
   * STRINGOLOGIA e COMPRESSIONE DI DATI
     * Stringologia {{:magistraleinformatica:alg2:algo2_11:dispensestringmatching.pdf|[dispensa: tutta, escluse sez.2.4,2.5,4.4,5.3]}}
-    * Compressione d di ati {{:magistraleinformatica:alg2:algo2_11:07_mg-partchap2.pdf|[cap.2:inizio-pag.36,sez.2.4,sez.2.5(solo BWT), sez.2.6])}} {{:magistraleinformatica:alg2:algo2_11:07_mg-partchap3.pdf|[cap 3: fino pag.119]}}
+    * Compressione di dati {{:magistraleinformatica:alg2:algo2_11:07_mg-partchap2.pdf|[cap.2:inizio-pag.36,sez.2.4,sez.2.5(solo BWT), sez.2.6]}} {{:magistraleinformatica:alg2:algo2_11:07_mg-partchap3.pdf|[cap 3: fino pag.119]}}
     * Suffix tree {{:magistraleinformatica:alg2:tre.pdf|[Cap.5; fino pag.93]}}
-    * Suffix array {{:magistraleinformatica:alg2:quattro.pdf|[Cap.7: fino pag.154]}} [[http://www.cs.helsinki.fi/u/tpkarkka/publications/jacm05-revised.pdf|DC3: solo Sezione 3]]
+    * Suffix array {{:magistraleinformatica:alg2:quattro.pdf|[Cap.7: fino pag.154]}} [[http://www.cs.helsinki.fi/u/tpkarkka/publications/jacm05-revised.pdf|[DC3: solo Sezione 3]]]
@@ Linea 76: / Linea 81: @@
     * MapReduce: [[http://code.google.com/edu/parallel/mapreduce-tutorial.html|[Mini tutorial]]]
     * van Emde Boas (vEB) layout [[http://erikdemaine.org/papers/BRICS2002/paper.pdf|[sez.4.1]]]
-    * paginazione alberi {{:magistraleinformatica:alg2:algo2_11:paginazione.pdf|[sez.3.1]}} [[http://www.cs.sunysb.edu/~bender/pub/treelayout-full.ps|[sez.5.1]]]
+    * paginazione alberi {{:magistraleinformatica:alg2:algo2_11:paginazione.pdf|[sez.3.1]}} [[http://www.cs.sunysb.edu/~bender/pub/treelayout-full.ps|[sez.5.1]]] {{:magistraleinformatica:alg2:algo2_11:cotrees_grossi.pdf|[esempio]}}
-  * ALGORITMI ON LINE
+  * ALGORITMI ON LINE E RANDOMIZZATI
-    * Move to front {{:magistraleinformatica:alg2:mtf.pdf|}}
+    * Algoritmi per il problema del paging {{:magistraleinformatica:alg2:paging.pdf|[sez.3]}} [[http://www.cs.cmu.edu/~sleator/papers/competitive-paging.pdf|[sez.2 e 3]]]
-    * Algoritmi per il problema del paging {{:magistraleinformatica:alg2:paging.pdf|}}
+    * QUICKSORT randomizzato {{:magistraleinformatica:alg2:algo2_10:randqs.pdf|[sez.2.5.4]}}
+    * CUCU Hashing {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|[dispensa]}}
-  * ALGORITMI RANDOMIZZATI
+    * Skip list {{:magistraleinformatica:alg2:algo2_11:skip.pdf|[sez.3.3]}}
-    * QUICKSORT randomizzato {{:magistraleinformatica:alg2:algo2_10:randqs.pdf|}}
-    * CUCU Hashing {{:magistraleinformatica:alg2:algo2_10:cuckoo-undergrad.pdf|}}
-    * Skip lists
   * PROBLEMI DIFFICILI E APPROSSIMAZIONE
-    * {{:magistraleinformatica:alg2:algo2_10:dispensa_0.pdf|dispensa_1.0.pdf: capitolo 9 del testo Crescenzi, Gambosi, Grossi}}
+    * NP-completezza e approssimazione I {{:magistraleinformatica:alg2:algo2_10:dispensa_0.pdf|[cap.9]}} {{:magistraleinformatica:alg2:algo2_10:alg2_21-12.pdf|[appunti Dinelli]}}
-      * {{:magistraleinformatica:alg2:algo2_10:dispensa.pdf|dispensa_1.1.pdf (a cura di P. Crescenzi)}}
+    * Approssimazione II [[http://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/libro.html|[cap.2:pp.39-47, paragrafo 2.2.2]]]
-      * {{:magistraleinformatica:alg2:algo2_10:alg2_21-12.pdf|appunti_1.2 (a cura di E. Dinelli)}}
-      * [[http://www.csc.kth.se/~viggo/wwwcompendium/|Sito dedicato a problemi di ottimizzazione NP-hard]]
-      * [[http://www.tsp.gatech.edu|Sito dedicato al problema del commesso viaggiatore (TSP)]]
-    * {{:magistraleinformatica:alg2:dispensa_1.pdf|dispensa_2.0.pdf: non-determinismo (a cura di Horowitz-Sahni)}}
-      * L'esempio 12.2 contiene degli errori: individuarli.
-      * Teoremi 12.5 e 12.7 senza dimostrazione.
-      * Nel Teorema 12.8, k>=(1+e)n deve essere: k>=1+en.
-    * [[http://www.dis.uniroma1.it/~ausiello/InfoTeoIIRM/libro.html|dispensa_3.0: capitolo 2 del testo Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, Protasi]]
-      * studiare soltanto: pp.39-47, paragrafo 2.2.2
-      * {{:magistraleinformatica:alg2:algo2_10:maxclique.pdf|dispensa_3.1}}
-      * {{:magistraleinformatica:alg2:algo2_10:maxsat.pdf|dispensa_3.2: varianti di max-sat (da consultare)}}
 === Risultati e Soluzioni ===
+  * Non più disponibili
   * TESTI DI ALCUNI ESAMI: {{:magistraleinformatica:alg2:algo2_10:algo2_110621.pdf|}},{{:magistraleinformatica:alg2:algo2_10:algo2_110606.pdf|}}, {{:magistraleinformatica:alg2:algo2_10:algo2-01-02-11.pdf|}}, {{:magistraleinformatica:alg2:algo2_10:algo2-16-02-11.pdf|}}, {{:magistraleinformatica:alg2:algo2_10:algo2-26-01-11.pdf|}}, {{:magistraleinformatica:alg2:algo2_10:algo2-30-11-10.pdf|}}