Automi, Calcolabilità e Complessità (Autunno 2026)

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

• Michael Sipser, Introduzione alla Teoria della Computazione, Maggioli Editore, 2016.

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

• Simone Bianco, Appunti del Corso di Automi, Calcolabilità e Complessità, Sapienza Università di Roma, A. A. 2024/2025.

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