Algoritmica 2
Docenti: Paolo Ferragina, Roberto Grossi, Fabrizio Luccio, Linda Pagli, Nadia Pisanti
News
ATTENZIONE: Corona e Lima hanno un risultato diverso dalla prima pubblicazione dei risultati del compito del 1/2/2010
Obiettivi di apprendimento
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.
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
Stringologia
Strutture di dati evolute
Problemi "difficili" e loro soluzione
Registro delle lezioni
Materiale didattico
-
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.
-
HASHING DISTRIBUITO
Consisitent Hashing
-
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
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
VERSIONE ELETTRONICA
-
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
VERSIONE ELETTRONICA (sezione 5)
-
Risultati e Soluzioni
Compitino del 17/12/2009 Soluzione
Primo Appello (11/1/2010) Soluzione
Secondo Appello dell'1/2/2010 Testo
Terzo Appello del 2/6/2010 Testo
Quarto Appello del 22/6/2010 Testo
Quinto Appello del 13/7/2010 Testo
Sesto Appello del 7/9/2010