11933 - INFORMATICA TEORICA

Anno Accademico 2018/2019

  • Docente: Andrea Asperti
  • Crediti formativi: 12
  • SSD: INF/01
  • Lingua di insegnamento: Italiano
  • Modalità didattica: Convenzionale - Lezioni in presenza
  • Campus: Bologna
  • Corso: Laurea in Informatica (cod. 8009)

    Valido anche per Laurea Magistrale in Scienze filosofiche (cod. 8773)

Conoscenze e abilità da conseguire

"Il corso fornisce una introduzione alla teoria della calcolabilita' e alla teoria della complessita' computazionale. Al termine del corso lo studente avra' acquisito consapevolezza dei limiti teorici e pratici dei metodi effettivi di calcolo e sara' in grado di utilizzare ed applicare metodologie e tecniche proprie dei metodi formali nello studio della trattabilita' computazionale di problemi algoritmici di svariata natura."

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:
S.Arora, B.Barak. Computational Complexity: a modern approach. Cambridge University Press, 2009
Complessita': C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1994.

Modalità di verifica e valutazione dell'apprendimento

Esame scritto e orale.

Orario di ricevimento

Consulta il sito web di Andrea Asperti