Docente

Prof. Alberto Policriti alberto.policriti@uniud.it

Crediti

6 CFU

Finalità

Il principale obiettivo del corso è quello di approfondire alcuni degli argomenti studiati nel corso di Algoritmi e Strutture Dati, introducendo problematiche e strumenti relativi ad alcuni settori in cui la teoria degli algoritmi gioca oggi un ruolo fondamentale. I temi scelti a questo scopo sono gli algoritmi su stringhe ed alberi e le relative strutture dati, gli algoritmi paralleli e gli algoritmi randomizzati. Si accennerà infine alla algoritmica basata su una rappresentazione simbolica dei dati. La vastità dei campi permetterà, soprattutto per i temi studiati nella seconda e terza parte, solo una introduzione ma la centralità, la pervasività e l’eleganza delle idee presentate ne giustifica e motiva il trattamento.
Il corso si dividerà quindi in tre parti: nella prima parte si studieranno problematiche relative al disegno ed utilizzo di algoritmi di string matching e alla analisi della complessità degli algoritmi. Nella seconda parte si studieranno i principali modelli e architetture parallele, insieme alle tecniche fondamentali per l'analisi ed il disegno di algoritmi paralleli. Nella terza parte si studieranno i fondamenti della teoria degli algoritmi randomizzati rivisitando algoritmi noti nella loro versione randomizzata.
Si prevede, durante la parte finale del corso, un'attività seminariale e di approfondimento e introduzione alla ricerca.

Argomenti

1. Prima parte: Introduzione. Il problema dello string matching esatto: algoritmi di Knuth-Morris e Pratt, Rabin e Karp, Boyer e Moore. Suffix trees e applicazioni, algoritmo di Ukkonen e McCreight, algoritmo di Harel e Tarjan per il calcolo del lowest common ancestor. Algoritmo di Aho e Coarsik. Il problema dello string matching approssimato: algoritmo di Sellers, algoritmo di Landau e Vishkin, algoritmo di Chang e Lawler.
2. Seconda parte: Sorting networks: introduzione, running time, bitonic e merging algorithms. Modelli e algoritmi per computers paralleli: il modello PRAM, pointer jumping, teorema di Brent, esempi. Fixed-connection networks: arrays e alberi, sorting e counting, aritmetica intera.
3. Terza parte: Introduzione agli algoritmi randomizzati. Il metodo probabilistico. Strutture dati: hashing. Algoritmi probabilistici su grafi: all pairs shortest paths e minimum spanning trees.

Bibliografia

• Appunti delle lezioni.
• Cormen T.H., Leiserson C.E., Rivest R.L Introduction to Algorithms, and C.Stein MIT Press.
• Gusfield D., Algorithms on Strings, Trees and Sequences, Cambridge University Press, 1997.
• Motwani R. and Raghavan P. Randomized Algorithms Cambridge University Press, 1995.
• Quinn M.J.: Parallel computing - Theory and Practice, 2nd Ed. McGraw-Hill, 1994.