Anno 2010-2011
Docenti: Roberto Grossi, Linda Pagli, Nadia Pisanti
Avviso
Correzione compiti e verbalizzazione venerdì 18 febbraio ore 11:00 e lunedì 28 febbraio ore 11:00 presso lo studio della prof.ssa Pagli.
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
ALGORITMI ON LINE
-
-
Web Caching: algoritmi Greedy Dual e Greedy Dual Size
gds.pdf
HASHING DISTRIBUITO
-
Dalla tesi di master di Daniel M. Lewin
prima parteseconda 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.2, sezione 5.6, sezione 11.1)
Risultati e Soluzioni
OMISSIS
N.B.: per incrementare il voto finale, l'unica possibilità è quella di ripetere la prova nei prossimi appelli
Compitino del 15.12.2010
testo
Compitino del 26.01.2011
testo
OMISSIS
OMISSIS
OMISSIS