Docente

Prof. Carla Piazza carla.piazza@uniud.it sito web

Crediti

6 CFU

Finalità

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.

Programma

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.

Bibliografia

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

Modalità d'esame

L'esame consiste in una prova orale.