Informatica teorica

Numero di crediti ECTS: 10 (96 ore frontali)

SSD di riferimento: INF/01

Docente: N. Leone

Prerequisiti:

Nessuno.

Obiettivi

• La prima parte del corso si propone di fornire le conoscenze di base dell'Informatica Teorica, con particolare attenzione alla teoria della calcolabilità. Al termine, gli studenti saranno in grado di distinguere tra problemi decidibili ed indecidibili, e dimostrane tali proprietà mediante l'applicazione di teoremi studiati durante il corso o mediante l'uso di tecniche di riduzione tra problemi.
• Nella seconda parte del corso, l'accento è posto sulla teoria della complessità. Gli studenti saranno in grado di distinguere tra problemi trattabili, intrattabili e presumibilmente intrattabili. Saranno inoltre in grado di determinare formalmente la complessità computazionale di svariati problemi noti in letteratura.

Programma

• Parte 1: Macchine di Turing e calcolabilità
  • Introduzione.
  • Richiami di matematica (insiemi, relazioni, funzioni, cardinalità di insiemi, grafi).
  • Linguaggi formali (alfabeti, linguaggi, rappresentazioni finite di linguaggi, automi a stati finiti e linguaggi regolari).
  • Macchine di Turing (TM a nastro singolo, TM deterministiche, calcolabilità secondo Turing, TM multi nastro).
  • Calcolabilità e decidibilità (tesi di Church-Turing, descrizione linearizzata delle TM, TM universale, il problema della terminazione, linguaggi indecidibili, enumerazione di proprietà ricorsive, proprietà di enumerazioni di funzioni ricorsive, funzioni non calcolabili, teoremi di Kleene e di Rice, insiemi decidibili e semidecidibili).
  • Indecidibilità ed incompletezza nella logica del primo ordine (richiami alla logica proposizionale e del I ordine, Teoremi di Gödel, assiomi della teoria dei numeri, indecidibilità ed incompletezza).
• Parte 2: Complessità computazionale
  • Introduzione (problemi e algoritmi: raggiungibilità, MST, TSP).
  • Classi di complessità deterministiche (PTIME, problemi PTIME-completi).
  • Macchine di Turing non deterministiche. La classe NP. Certificati e verificatori polinomiali. NP-completezza. Teorema di Cook-Levin.
  • Complessità spaziale e teoremi di gerarchia (LOGSPACE, problemi LOGSPACE-completi, NL, problemi NL-completi, PH, PSPACE).

Bibliografia

• Libro di testo

  • Elaine A. Rich. Automata, Computability, and Complexity: Theory and Applications. Prentice Hall, 2008.

• Molto utile

  • Christos H. Papadimitriou. Computational Complexity. Addison Wesley, 1994.

• Potenzialmente utili

  • Carlo Ghezzi, and Dino Mandrioli. Informatica teorica. Città-Studi Edizioni, 1989.

  • Jon Kleinberg, and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.

  • Giorgio Ausiello, Fabrizio D'Amore, and Giorgio Gambosi. Linguaggi, Modelli, Complessità. Franco Angeli Editore, 2003.

  • Sanjeev Arora, and Boaz Barak. Complexity Theory: A Modern Approach. Cambridge University Press, 2009.

• Rudimenti

  • Harry R. Lewis, and Christos H. Papadimitriou. Elements of the Theory of Computation (2nd Edition). Prentice-Hall, 1997.

  • J. Glenn Brookshear. Informatica - Una panoramica generale, 11/ed. Pearson Italia, 2010.

Metodi di valutazione

Prova scritta + prova orale, entrambe obbligatorie.