Docente

• Prof. Carla Piazza
  

Indirizzo e-mail
carla.piazza@uniud.it

Indirizzo Pagina Web Personale
https://users.dimi.uniud.it/~carla.piazza/index.html

Crediti

6 CFU

Prerequisiti e propedeuticità

Propedeuticità:
Informatica I e II e Logica dal corso di laurea triennale

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

Conoscenze e abilità da acquisire

Lo/la studente/essa dovrà:
-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;
-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.).

Capacità relative alle discipline:
-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.)

Capacità trasversali /soft skills
- 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 apprendimento e metodi didattici previsti

L’insegnamento prevede:
- lezioni frontali alla lavagna
- ricevimento su appuntamento

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

Strumenti a supporto della didattica:
Pagina del corso predisposta dal docente.
Link agli articoli che fanno parte della bibliografia disponibili nella pagina del corso.
Su richiesta fotocopie degli articoli che fanno parte della bibliografia e fotocopie di altri articoli consigliati.

Modalità d'esame

L’esame consiste in prova orale con possibilità di scelta di un approfondimento da presentare all'orale.