Automi, Calcolabilità e Complessità (Autunno 2025)

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.
• Grammatiche acontestuali, automi a pila.

Teoria della calcolabilità:

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

Teoria della complessità

• Complessità di tempo e di spazio.
• Le classi P ed NP.
• NP completezza.

Logistica

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

Orario: Mercoledì (08:00 - 11:00) e Venerdì (08:00 - 10:00). Aula: Aula 4 (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.

Esami

Le date degli esami per l’anno accademico 2025/2026 saranno mostrate di seguito. Esame 8. Riservato agli studenti part-time e fuori corso a.a. 2024/2025 (compilare il modulo di richiesta in segreteria; ricordarsi di registrarsi comunque su INFOSTUD). Data: 05/11/2025. Aula: 4 (RM158). Orario: 08:00-11:00. Voti [pdf].

Avvisi

20/09/2025: Il corso inizierà il 23 settembre 2025.
02/10/2025: A causa dello sciopero nazionale proclamato per la giornata di domani, la lezione del 3 ottobre sarà eccezionalmente da remoto a questo link.

Diario delle lezioni