Docente

• Prof. Carla Piazza

Indirizzo e-mail

carla.piazza@uniud.it

Indirizzo Pagina Web Personale

http://users.dimi.uniud.it/~carla.piazza/

Crediti

6 CFU

Finalità e obbiettivi formativi

Lo scopo di questo corso è quello di presentare i principali risultati noti nel campo della complessità computazionale degli algoritmi. In particolare, verranno descritte la gerarchia classica delle classi di complessità e le principali tecniche di analisi computazionale. Saranno anche presentate alcune idee e nozioni alla base di modelli computazioni innovativi proposti in letteratura. Alla fine del corso lo studente dovrebbe essere in grado di analizzare la complessità in termini di TEMPO/SPAZIO di semplici problemi e di studiare in maniera autonoma altri modelli computazionali (e.g., modelli randomizzati o paralleli).

Programma

1. Classi di Complessità e risultati ad esse relativi tra cui: Teorema della Gerarchia; Teorema del Gap; Teorema di Savitch; Teorema di Immermann-Szelepscenyi e conseguenze; Riduzioni e Completezza; Classi esterne ad NP.

2. Algoritmi su grafi tra cui: algoritmi per la minimizzazione di automi e il calcolo della massima bisimulazione (algoritmo di Hopcroft, algoritmo di Paige-Tarjan e algoritmo di Paige-Tarjan-Bonic); algoritmi per il calcolo della massima simulazione; algoritmi per la manipolazione di strutture dati simboliche.

3. DNA Computing. Il modello di Adleman e Lipton. Risoluzione di SAT e altri problemi NP-completi. Turing completezza del modello.

4. Da concordare (e.g., algoritmi approssimati, computazioni parallele, automi ibridi, Quantum Computing).

Attività di Laboratorio

Sono previste almeno 10 ore di attività pratiche al calcolatore, in cui lo studente avrà modo di sperimentare le tecniche di analisi e ottimizzazione delle interrogazioni, l'uso di interfacce di programmazione per le basi di dati, nonché implementare semplici basi di dati spaziali, temporali e distribuite.

Prerequisiti

E’ utile che lo studente conosca già seguenti nozioni:

1. modello computazionale (e.g., Macchine di Turing);
2. nozione di calcolabilità, Tesi di Church, Teorema dell’arresto;
3. notazione asintotica;
4. strutture dati di base (e.g., vettori, liste, alberi, grafi).
   
   

Queste nozioni vengono sicuramente studiate in alcuni dei corsi della Laurea Triennale in Informatica (e.g., Fondamenti dell’Informatica, Algoritmi e Strutture Dati).

Bibliografia

C. H. Papadimitriou. Computational Complexity. Addison Wesley. 1995

PSPACE-completeness

-Word Problems Requiring Exponential Time di L. J. Stockmeyer e A. R. Meyer

Bisimulation and Automata Minimization

-An NlogN Algorithm for Minimizing States in a Finite Automaton di J. Hopcroft

-CCS Expressions, Finite State Processes, and Three Problems of Equivalence di P.C. Kanellakis e S.A. Smolka

-Three Partition Refinement Algorithms di R. Paige e R. E. Tarjan

OBDD

-Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams di R. E. Bryant

-Symbolic Model Checking di K. McMillan

DNA Computing

-Molecular Computation of Solutions of Combinatorial Problems di L. Adleman

-Speeding up Computations via Molecular Biology di R. Lipton

-On the Computational Power of DNA di D. Boneh, C. DunWorth e R. Lipton

-A DNA and restriction enzyme implementation of Turing Machines di P. Rothemund

-A Survey on DNA Computing di N. Pisanti

Modalità d'esame

L’esame è orale su appuntamento con il docente durante le sessioni d’esame. E’ possibile presentare all’orale un approfondimento su un argomento concordato con il docente. In ogni caso la discussione dell’approfondimento sarà seguita da domande sugli argomenti trattati durante il corso.

Orario di ricevimento

Su appuntamento da concordare via mail con il docente.