Docenti

Prof. Carla Piazza carla.piazza@uniud.it http://www.dimi.uniud.it/piazzaProf. Alberto Policriti alberto.policriti@uniud.it http://www.dimi.uniud.it/policriti

Crediti

12 CFU

Finalità

Modulo 1

Il corso si propone di presentare i principali risultati nel campo della complessità computazionale degli algoritmi con particolare attenzione alle classiche gerarchie di classi di complessità astratte ed alle tecniche di studio dei problemi nel campo. Ci si propone inoltre di presentare agli studenti le idee e le nozioni fondamentali relative ai più promettenti ed innovativi modelli computazionali proposti dalla comunità scientifica.

Modulo 2

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à, soprattuto 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.

Programma

Modulo 1

1. Classi di complessità. Il teorema di gerarchia sulle classi di complessità. Il Gap theorem. Teorema di Savitch. Il teorema di Immermann-Szelepscenyi e conseguenze. Riduzioni e completezza. Classi esterne ad NP.
2. Algoritmi. Il problema della riduzione di automi e la bisimulazione. Algoritmo di Hopcroft. Algoritmo di Paige-Tarjan. Il problema della simulazione (cenni). Strutture dati simboliche.
3. Quantum Computing. Classi di complessità quantistica. Algoritmi quantistici.
4. DNA Computing. Il modello di Adleman e Lipton. Soluzione di SAT ed altri problemi NP-completi. Simulazione di macchine di Turing.

Modulo 2

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

Modulo 1

- C.H. Papadimitriou, Computational Complexity, Addison Wesley, 1995.
- articoli e dispense.

Modulo 2

• 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.

Modalità d'esame

L'esame consiste in una prova orale.