73093 - INFORMATICA TEORICA (1) (LM)

Scheda insegnamento

Anno Accademico 2020/2021

Conoscenze e abilità da conseguire

Al termine del corso lo studente conosce i principi della calcolabilità e le teorie alla base dell'informatica. E' in grado di verificare l'esistenza o l'inesistenza di programmi che calcolano una determinata funzione.

Contenuti

Il programma e' diviso in due moduli incentrati rispettivamente sulla teoria della Calcolabilita' e sulla Teoria della Complessita'.

Calcolabilita':
Linguaggi subricorsivi: ricorsione primitiva, sistema T;incompletezza dei formalismi totali;
Macchine di Turing e altri formalismi equivalenti; la tesi di Church.
Il problema della terminazione, altri problemi indecidibili; il teorema di Rice.
Insiemi ricorsivi e ricorsivamente enumerabili; il teorema di Rice-Shapiro.
Il teorema del punto fisso di Kleene.
Riducibilita'; insiemi produttivi, creativi, immuni, semplici.
Calcolabilita' e (in)completezza.

Complessita'
:
Problemi computazionali;
Modelli di Computazione e misure di Complessita';
Classi e gerarchie di complessita'; classi notevoli; riduzione
P vs NP e altri problemi aperti
Macchine ad oracolo e gerarchia polinomiale





Testi/Bibliografia

Note del docente.
Testi addizionali consigliati:

N.J.Cutland. Computability. Cambridge University Press.

S.Arora, B.Barak. Computational Complexity: a modern approach. Cambridge University Press, 2009
Complessita': C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1994.

Metodi didattici

Lezioni frontali. Uso slides, ma lavoro anche spesso alla lavagna.

Modalità di verifica dell'apprendimento

Esame scritto e orale.

Orario di ricevimento

Consulta il sito web di Andrea Asperti