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

Conoscenze e abilità da acquisire

-      Conoscenza e comprensione
Conoscere le principali classi di complessità deterministiche e non deterministiche, le relazioni tra classi, i più noti problemi completi per le diverse classi. Conoscere le strutture dati per la rappresentazione simbolica di grafi e gli algoritmi per il calcolo del quoziente per bisimulazione. Conoscere i principi alla base di modelli di calcolo alternativi quali DNA-computing e Quantum-computing

-      Capacità di applicare conoscenza e comprensione
Essere in grado di classificare un problema nuovo, stabilendo in quali classi ricade e valutandone l'eventuale completezza per una classe. Essere in grado di definire algoritmi per la riduzione di grafi. Essere in grado di analizzare autonomamente altre classi di complessità e modelli di calcolo (e.g., classi randomizzate, modelli paralleli, etc.)

-      Autonomia di giudizio
Essere in grado di valutare la correttezza di risultati di complessità. Essere in grado di valutare l'eventuale impatto di un risultato di complessità sulla gerarchia di classi di complessità. Essere in grado di valutare modelli di calcolo alternativi

-      Abilità comunicative
Essere in grado di trasmettere quanto appreso nel corso e quanto approfondito autonomamente.

-      Capacità di apprendimento
Essere in grado di comprendere risultati algoritmici e di complessità descritti in letteratura.
Essere in grado di analizzare nuovi problemi dal punto di vista della complessità computazionale.  Essere in grado di proporre soluzioni algoritmiche efficienti per problemi su grafi.

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.

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

- Programmazione e Algoritmi

- Algoritmi su grafi

- Complessità degli Algoritmi con notazione asintotica

- Modelli di Calcolo (Macchine di Turing, URM)

- Tesi di Church, Calcolabilità, Macchine Universali, Teorema dell'arresto

- Automi deterministici e non deterministici

Bibliografia

Costituiscono fonti di studio per l’esame:

Testo:

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

Alcuni articoli scientifici:

- A Short History of Computational Complexity di L. Fortnow e S. Homer

- The History and Status of the P versus NP Question di M. Sipser

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

- 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

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

- Graph Algorithms for Massive Data-Sets di R. Gentilini

- Symbolic Model Checking di K. McMillan

- 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

- Machines, Logic and Quantum Physiscs di D. Deutsch, A. Ekert, e R. Lupacchini

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.

******************************************************************************

Aims 

During this course we intend to present the main results in the field of computational complexity of algorithms.
In particular, we intend to discuss the classical hierarchy of complexity classes and the main techniques for the analysis of related problems. We will also present basic ideas and notions of some interesting innovative computational models recently proposed in the scientific community.

Program 

1. Computational classes. Hierarchy theorem. Gap theorem. Savitch theorem. Immermann-Szelepscenyi theorem and consequences. Computational reductions and completeness. Classes outside NP.
2. Algorithms. The problem of automata minimization and the notion of bisimulation. Hopcroft algorithm. Paige-Tarjan algorithm. Paige-Tarjan-Bonic algorithm. The notion of simulation. Symbolic data structures.
3. Quantum Computing. Computational classes in quantum computing.Quantum algorithms.
4. DNA Computing. Adleman and Lipton model. Solutions for SAT and other NP-complete problems. Universal Turing machine in DNA computing.

References 

- C.H. Papadimitriou, Computational Complexity, Addison Wesley, 1995.
- other research papers.

Exams 

The exam is oral.