Differenze

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

--- magistraleinformatica:alg2:start [07/06/2010 alle 10:36 (15 anni fa)] – Linda Pagli
+++ magistraleinformatica:alg2:start [19/09/2016 alle 09:53 (9 anni fa)] (versione attuale) – Roberto Grossi
@@ Linea 1: / Linea 1: @@
-====== Algoritmica 2 ======
+===== Algoritmica 2 =====
-Docenti: **Paolo Ferragina**, **Roberto Grossi**, **Fabrizio Luccio**, **Linda Pagli**, **Nadia Pisanti**
+===== Informazioni Generali =====
-=== News ===
+**Codice:** 316AA
-ATTENZIONE: Corona e Lima hanno un risultato diverso dalla prima pubblicazione dei risultati del compito del 1/2/2010
+**Impegno:** 9 CFU.
-=== Obiettivi di apprendimento ===
+**Semestre:** primo.
-In questo corso studieremo, progetteremo e analizzeremo soluzioni algoritmiche e strutture di dati avanzate per la risoluzione efficiente di problemi combinatori che coinvolgono vari tipi di dato, quali interi, stringhe, punti (geometrici), alberi, grafi.
+===== Anno accademico corrente =====
+   * [[.algo2_16:|A.A. 2016/2017]]
-Questo corso costituisce un naturale approfondimento e ampliamento delle conoscenze di base apprese nel percorso della laurea triennale.
+===== Anni accademici precedenti =====
+   * [[.algo2_15:|A.A. 2015/2016]]
-Il suo syllabus è organizzato per ambiti applicativi, al fine di contestualizzare le tecniche studiate nella realizzazione di software efficiente per essi, e così da consentire adattamenti e specializzazioni di anno in anno che si renderanno necessari e/o opportuni.
+   * [[.algo2_14:|A.A. 2014/2015]]
+   * [[.algo2_13:|A.A. 2013/2014]]
-=== Programma ===
+   * [[.algo2_12:|A.A. 2012/2013]]
+   * [[.algo2_11:|A.A. 2011/2012]]
-== Accesso ai dati e loro compressione ==
+   * [[.algo2_10:|A.A. 2010/2011]]
-     * Compressione di testi e di interi
+   * [[.algo2_09:|A.A. 2009/2010]]
-     * Strutture di dati randomizzate
-     * Motori di ricerca: liste invertite
-== Memorie gerarchiche ==
-     * Modelli di computazione
-     * Permutazioni e ordinamenti
-     * Dizionari
-== Stringologia ==
-     * Matrice dei suffissi
-     * Albero dei suffissi
-     * Algoritmi di pattern matching
-== Strutture di dati evolute ==
-     * Strutture di dati distribuite
-     * Analisi competitiva
-     * Algoritmi on-line
-== Problemi "difficili" e loro soluzione ==
-     * I problemi NP-hard
-     * Algoritmi di approssimazione
-     * Algoritmi randomizzati
-== Registro delle lezioni ==
-     * [[http://unimap.unipi.it/registri/printregistriNEW.php?re=29405:::&ri=5777|REGISTRO DELLE LEZIONI]]
-=== Materiale didattico ===
-     * PROBLEMI DIFFICILI E APPROSSIMAZIONE {{:magistraleinformatica:alg2:dispensa_1.pdf|}}
-        * 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.
-     * ALGORITMI RANDOMIZZATI {{:magistraleinformatica:alg2:alg-random.pdf|}}
-     * DATA COMPRESSION: {{:magistraleinformatica:alg2:07_mg-partchap2.pdf|}}
-        * Non studiare "Computing Huffman code lengths" e "Maintaining cumulative counts"
-        * Studiare anche "Huffman canonico"
-        * Esempio per {{:magistraleinformatica:alg2:bwt1.ppt|BWT}}
-        * Dimostrazione performance di {{:magistraleinformatica:alg2:mtf-analysis.pdf|MTF}} (Teo 1 e Cor 1)
-     * BLOOM FILTER {{:magistraleinformatica:alg2:bloomfiltersurvey.pdf|survey}} e {{:magistraleinformatica:alg2:bf_slides.pdf|slides}}
-     * HASH UNIVERSALE E HASH PERFETTO {{:magistraleinformatica:alg2:clr-hash.pdf|}}
-     * MOTORI DI RICERCA ({{:magistraleinformatica:alg2:searchengines_cenni_.ppt|cenni}}, {{:magistraleinformatica:alg2:chapferrluccio.pdf|note}})
-     * STRINGOLOGIA
-        * EXACT MATCHING ({{:magistraleinformatica:alg2:patternmatching1.pdf|}}, {{:magistraleinformatica:alg2:patternmatching2.pdf|}})
-        * AHO-CORASICK{{:magistraleinformatica:alg2:uno.pdf|}}
-        * KARP-RABIN {{:magistraleinformatica:alg2:due.pdf|}}
-        * SUFFIX TREE {{:magistraleinformatica:alg2:tre.pdf|}}
-        * SUFFIX ARRAY {{:magistraleinformatica:alg2:quattro.pdf|}}
-     * ALGORITMI ON LINE
-        * MOVE TO FRONT {{:magistraleinformatica:alg2:mtf.pdf|}}
-        * Algoritmi per il problema del paging {{:magistraleinformatica:alg2:paging.pdf|}}
-        * La dimostrazione dell'analisi competitiva dell'algoritmo DG è dubbia anche nell'articolo originale, non è da studiare.
-        * WEB-Caching,  studiare paragrafo 3 e 4 {{:magistraleinformatica:alg2:gds.pdf|}}
-     * HASHING DISTRIBUITO
-        * Consisitent Hashing
-        * Dalla tesi di master di Daniel M. Lewin{{:magistraleinformatica:alg2:ch1.pdf|prima parte}}
-         {{:magistraleinformatica:alg2:ch2.pdf|seconda parte}}. Studiare fino all'enunciato del teorema 2.2.3. Poi i lemmi 2.2.5 e 2.2.6.
-     * MEMORIE GERARCHICHE
-        * Modelli di computazione, permutazioni e ordinamenti: J. S. Vitter. Algorithms and Data Structures for External Memory, Series on Foundations and Trends in Theoretical Computer Science, now Publishers, Hanover, MA, 2008. Also published as Volume 2, Issue 4 of Foundations and Trends in Theoretical Computer Science [[http://faculty.cse.tamu.edu/jsv/Papers/Vit.IO_book.pdf|VERSIONE ELETTRONICA (introduzione, sezione 2.1, capitolo 3, sezione 5.1/5.1.1, sezione 5.2, sezione 5.6, sezione 6)]]; L. Arge, M.G. Lagoudakis. External partition element finding [[http://www.daimi.au.dk/~large/ioS06/AL.pdf|VERSIONE ELETTRONICA]]
-        * Dizionari: lucidi di L. Arge [[http://www.daimi.au.dk/~large/ioS08/Lecture2.pdf|VERSIONE ELETTRONICA (prime 21 pagine)]] e G. S. Brodal [[http://www.daimi.au.dk/~gerth/emF03/slides/b-trees.pdf|VERSIONE ELETTRONICA]] (guardare anche la bibliografia menzionata in tali lucidi).
-        * List ranking: Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-Memory Graph Algorithms, ACM-SIAM SODA 1995 [[http://www.cs.duke.edu/~jsv/Papers/CGG95.external_graph.pdf|VERSIONE ELETTRONICA (sezione 5)]]
-        * Modello Cache-Oblivious (CO): L. Arge, G. S. Brodal and R. Fagerberg. Cache-Oblivious Data Structures. Chapter 38 in Handbook of Data Structures and Applications, CRC Press, 2004 [[http://www.daimi.au.dk/~large/ioS05/ABF.pdf|VERSIONE ELETTRONICA (sezioni 38.1 e 38.2/38.2.1)]]
-=== Risultati e Soluzioni ===
-Compitino del 17/12/2009 {{:magistraleinformatica:alg2:ris17-12-09.pdf|Risultati}} {{:magistraleinformatica:alg2:sol17-12-09.pdf|Soluzione}}
-Primo Appello (11/1/2010){{:magistraleinformatica:alg2:ris11-01-10.pdf|Risultati}}{{:magistraleinformatica:alg2:alg2-11-01-10sol.pdf|Soluzione}}
-Secondo Appello dell'1/2/2010{{:magistraleinformatica:alg2:ris1-02-10.pdf|Risultati}}{{:magistraleinformatica:alg2:alg2-02-02-10.pdf|Testo}}
-Terzo Appello del 2/6/2010{{:magistraleinformatica:alg2:ris02-06-10.pdf|Risultati}} {{:magistraleinformatica:alg2:alg2-02-06-10.pdf|Testo}}