Automi, Calcolabilità e Complessità (Autunno 2026)

Laurea Triennale in Informatica

Contenuto del Corso

Durante il corso saranno introdotti i più importanti risultati dell’Informatica teorica: a partire dai fondamentali risultati in teoria della calcolabilità degli anni trenta, passando per quelli in teoria degli automi degli anni cinquanta per arrivare al problema aperto P contenuto o uguale a NP, esplicitamente sollevato negli anni settanta.

Teoria degli automi:

  • Linguaggi regolari e non regolari, automi finiti e non determinismo.
  • Espressioni regolari.
  • Grammatiche acontestuali, automi a pila.

Teoria della calcolabilità:

  • La tesi di Church-Turing e la macchina di Turing.
  • Linguaggi decidibili e non decidibili.
  • Riducibilità.
  • Teoremi di incompletezza di Goedel.

Teoria della complessità

  • Complessità di tempo e di spazio.
  • Le classi P, NP, EXP, NEXP, PSPACE, L, NL, coNP, coNL.
  • Teoremi di gerarchia di tempo e di spazio.

Logistica

Importante: Le lezioni avvengono esclusivamente in presenza (senza registrazioni).

Orario: Mercoledì (08:00 - 10:00) e Venerdì (08:00 - 11:00). Aula: Aula 4 De Lollis (RM158).

Modalità di Esame

Prova scritta. La prova consiste nella risoluzione di tre esercizi e nella risposta a tre domande di teoria.

Bibliografia

Gli appunti che seguono, relativi a un’edizione passata del corso, possono anche essere un riferimento utile:

Esami

Le date degli esami per l’anno accademico 2026/2027 appariranno di seguito non appena disponibili.
Esame 0. Riservato agli studenti part-time e fuori corso dello scorso anno accademico (compilare il modulo di richiesta in segreteria; ricordarsi di registrarsi comunque su Infostud). Data: 30/10/2026. Aula: 4 De Lollis (RM158). Orario: 08:30-11:30. Voti [pdf].

Avvisi

20/09/2026: Il corso inizierà il 23 settembre 2026.
05/10/2026: Le lezioni del 28/10/2026 e 30/10/2026 non avranno luogo.

Diario delle lezioni

Date Topics References
Lezione 1 23/09/26 Introduzione al corso. Automi a stati finiti: prime definizioni ed esempi. [PDF]
Lezione 2 25/09/26 Esempi di progettazione di DFA. Linguaggi regolari. Operazioni sui linguaggi. Chiusura dei linguaggi regolari rispetto ad unione ed intersezione. [PDF]
Lezione 3 29/09/26 Automi a stati finiti non deterministici: definizioni ed esempi. Equivalenza tra automi a stati finiti deterministici e non-deterministici. [PDF]
Lezione 4 02/10/26 Chiusura dei linguaggi regolari rispetto alla concatenzazione e all'operazione star. Espressioni regolari: definizioni ed esempi. [PDF]
Lezione 5 07/10/26 Equivalenza tra espressioni regolari e linguaggi regolari. [PDF]
Lezione 6 09/10/26 Linguaggi non regolari: pumping lemma. Esercizi sui linguaggi regolari. [PDF]
Lezione 7 14/10/26 Grammatiche acontestuali: definizioni ed esempi. Progettazione di grammatiche. [PDF]
Lezione 8 16/10/26 Forma normale di Chomsky. Esempi. Automi a pila: definizioni ed esempi. [PDF]
Lezione 9 21/10/26 Equivalenza tra automi a pila non-deterministici e grammatiche acontestuali. [PDF]
Lezione 10 23/10/26 Equivalenza tra automi a pila non-deterministici e grammatiche acontestuali. Pumping lemma per linguaggi acontestuali. Esercizi sulle grammatiche. [PDF]