Indice
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
- 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
Materiale didattico
- PROBLEMI DIFFICILI E APPROSSIMAZIONE 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 alg-random.pdf
- DATA COMPRESSION: 07_mg-partchap2.pdf
- HASH UNIVERSALE E HASH PERFETTO clr-hash.pdf
- STRINGOLOGIA
- EXACT MATCHING (patternmatching1.pdf, patternmatching2.pdf)
- AHO-CORASICKuno.pdf
- KARP-RABIN due.pdf
- SUFFIX TREE tre.pdf
- SUFFIX ARRAY quattro.pdf
- ALGORITMI ON LINE
- MOVE TO FRONT mtf.pdf
- Algoritmi per il problema del paging 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 gds.pdf
- HASHING DISTRIBUITO
- Consisitent Hashing
- Dalla tesi di master di Daniel M. Lewinprima parte
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
- Dizionari: lucidi di L. Arge VERSIONE ELETTRONICA (prime 21 pagine) e G. S. Brodal 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 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 VERSIONE ELETTRONICA (sezioni 38.1 e 38.2/38.2.1)