Automi, Calcolabilità e Complessità (Autunno 2025)

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.
  • 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

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 2025/2026 sono elencate di seguito. La registrazione su Infostud è obbligatoria.
Esame 1. Data: 12/01/26. Aula: 3L (RM018). Orario: 10:00-13:00. Voti [pdf].
Esame 2. Data: 09/02/26. Aula: 3L (RM018). Orario: 10:00-13:00. Voti [pdf].
Esame 3. Riservato agli studenti part-time e fuori corso (compilare il modulo di richiesta in segreteria; ricordarsi di registrarsi comunque su Infostud). Data: TBA. Aula: TBA. Orario: TBA. Voti [pdf].
Esame 4. Data: 08/06/26. Aula: 3L (RM018). Orario: 10:00-13:00. Voti [pdf].
Esame 5. Data: 13/07/26. Aula: 3L (RM018). Orario: 10:00-13:00. Voti [pdf].
Esame 6. Data: 07/09/26. Aula: 3L (RM018). Orario: 10:00-13:00. Voti [pdf].
Esame 7. Riservato agli studenti part-time e fuori corso (compilare il modulo di richiesta in segreteria; ricordarsi di registrarsi comunque su Infostud). Data: TBA. Aula: TBA. Orario: TBA. 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.
30/10/2025: La lezione del 31 ottobre sarà un’esercitazione e avrà luogo in Aula Magna - Viale Regina Elena 295. La lezione del 5 novembre non avrà luogo.
13/11/2025: A causa dello sciopero dei trasporti proclamato per la giornata di domani, la lezione del 14 novembre sarà in presenza ma verrà anche trasmessa da remoto a questo link.
27/11/2025: La lezione del 28 novembre non avrà luogo.

Diario delle lezioni

Date Topics References
Lezione 1 24/09/25 Introduzione al corso. Automi a stati finiti: prime definizioni ed esempi. [PDF]
Lezione 2 26/09/25 Esempi di progettazione di DFA. Linguaggi regolari. Operazioni sui linguaggi. [PDF]
Lezione 3 01/10/25 Chiusura dei linguaggi regolari rispetto ad unione ed intersezione. Automi a stati finiti non deterministici: definizioni ed esempi. Equivalenza tra automi a stati finiti deterministici e non-deterministici. [PDF]
Lezione 4 03/10/25 Chiusura dei linguaggi regolari rispetto alla concatenzazione e all'operazione star. Espressioni regolari: definizioni ed esempi. [PDF]
Lezione 5 08/10/25 Equivalenza tra espressioni regolari e linguaggi regolari. [PDF]
Lezione 6 10/10/25 Linguaggi non regolari: pumping lemma. Esercizi sui linguaggi regolari. [PDF]
Lezione 7 15/10/25 Esercizi sui linguaggi regolari. Grammatiche acontestuali: prime definizioni ed esempi. [PDF]
Lezione 8 17/10/25 Progettazione di grammatiche. Forma normale di Chomsky. Esempi. [PDF]
Lezione 9 22/10/25 Automi a pila: definizioni ed esempi. Equivalenza tra automi a pila non-deterministici e grammatiche acontestuali. [PDF]
Lezione 10 24/10/25 Equivalenza tra automi a pila non-deterministici e grammatiche acontestuali. Pumping lemma per linguaggi acontestuali. [PDF]
Lezione 11 29/10/25 Pumping lemma per linguaggi acontestuali. Calcolabilità. Macchine di Turing: prime definizioni ed esempi. Linguaggi Turing-riconoscibili e linguaggi decidibili. [PDF]
Lezione 12 31/10/25 Esercitazione. [PDF]
Lezione 13 07/11/25 Varianti di macchine di Turing: La macchina di Turing multi-nastro e macchine di Turing non-deterministiche. Equivalenza con la macchina di Turing deterministica a singolo nastro. [PDF]
Lezione 14 12/11/25 Esempi di linguaggi decidibili basati su automi e grammatiche acontestuali. Esistenza di linguaggi non decidibili tramite diagonalizzazione. [PDF]
Lezione 15 14/11/25 Esistenza di linguaggi non riconoscibili. Riducibilità mediante funzione. [PDF]
Lezione 16 19/11/25 Teoremi di incompletezza di Goedel. [PDF]
Lezione 17 21/11/25 Esercizi di calcolabilità. Complessità di tempo. [PDF]
Lezione 18 26/11/25 Le classi P ed EXP. Esempi di problemi in P. Soddisfacibilità. 2-SAT in P. [PDF]
Lezione 19 03/12/25 Le classi NP e NEXP. Definizione di NP tramite verificatori. Definizione di NP tramite non-determinismo. Esempi di linguaggi in NP. Equivalenza delle due definizioni di NP. [PDF]
Lezione 20 05/12/25 NP-completezza. Teorema di Cook-Levin. [PDF]