DidaWiki

Strumenti Utente

Strumenti Sito

Ti trovi qui: DidaWiki » Corso di Laurea Magistrale in Informatica » Algoritmica 2
magistraleinformatica:alg2: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
magistraleinformatica:alg2:start [01/10/2010 alle 15:32 (14 anni fa)]
Linda Pagli 		magistraleinformatica:alg2:start [19/09/2016 alle 09:53 (8 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. +
- +
-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. +
- +
-=== Programma === +
- +
-== Accesso ai dati e loro compressione == +
-     * Compressione di testi e di interi +
-     * 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}} +
- +
-Quarto Appello del 22/6/2010 {{:magistraleinformatica:alg2:alg2-22-06-10.pdf|Testo}} Per risultati e registrazione presentarsi il 29/6/2010 in N1 dalle 10.30 alle 12. +
- +
-Quinto Appello del 13/7/2010 {{:magistraleinformatica:alg2:ris13-07-10.pdf|Risultati}}{{:magistraleinformatica:alg2:alg2-13-07-10.pdf|Testo}} +
- +
-Sesto Appello del 7/9/2010 {{:magistraleinformatica:alg2:ris-07-09-10.pdf|Risultati}}+
  
 +===== Anni accademici precedenti =====
 +   * [[.algo2_15:|A.A. 2015/2016]]
 +   * [[.algo2_14:|A.A. 2014/2015]]
 +   * [[.algo2_13:|A.A. 2013/2014]]
 +   * [[.algo2_12:|A.A. 2012/2013]]
 +   * [[.algo2_11:|A.A. 2011/2012]]
 +   * [[.algo2_10:|A.A. 2010/2011]]
 +   * [[.algo2_09:|A.A. 2009/2010]]
magistraleinformatica/alg2/start.1285947162.txt.gz · Ultima modifica: 01/10/2010 alle 15:32 (14 anni fa) da Linda Pagli

Strumenti Pagina

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki