Automi, Calcolabilità e Complessità (Autunno 2024)

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

Importante: La lezione del 08/11/24 sarà eccezionalmente da remoto a questo link.

Orario: Mercoledì (08:00 - 11:00) e Venerdì (15:00 - 17:00). Aula: La lezione del Mercoledì è in Aula 3L – Via del Castro Laurenziano 7a. La lezione del Venerdì è in Aula 3 De Lollis.

Modalità di Esame

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

Bibliografia

Esami

Le date degli esami per l’anno accademico 2024/2025 appariranno qui non appena disponibili.

Esame (Ottobre 2024). Riservato agli studenti lavoratori e part-time (è necessario aver fatto la richiesta in segreteria; la registrazione su INFOSTUD è comunque richiesta). Data: 21/10/24. Aula: G50 (Viale Regina Elena 295). Orario: 11:00-14:00. Risultati [pdf].

Avvisi

11/09/2024: Il corso inizierà il 25 settembre 2024. A causa dei lavori in corso nelle aule in Via De Lollis, la lezione del 27 settembre avrà luogo in Aula A - Pietro Benedetti (Via dei Sabelli 108).
30/09/2024: A causa dei lavori in corso nelle aule in Via De Lollis, la lezione del 4 ottobre sarà da remoto a questo link.
02/10/2024: A causa dei lavori in corso nelle aule in Via De Lollis, la lezione del 11 ottobre avrà luogo in Aula A - Scienze Biochimiche (Città Universitaria).
12/10/2024: A causa dei lavori in corso nelle aule in Via De Lollis, la lezione del 18 ottobre avrà luogo in Aula 101 - Palazzina D - Viale Regina Elena 295.
22/10/2024: A causa dei lavori in corso nelle aule in Via De Lollis, la lezione del 25 ottobre avrà luogo in Aula 301 - Palazzina D - Viale Regina Elena 295.
02/11/2024: A causa dei lavori in corso nelle aule in Via De Lollis, la lezione del 08 novembre avrà luogo in Aula 301 - Palazzina D - Viale Regina Elena 295.
07/11/2024: A causa dello sciopero nazionale proclamato per la giornata di domani, la lezione del 8 novembre sarà eccezionalmente da remoto a questo link.

Diario delle lezioni

Date Topics References
Lezione 1 25/09/24 Introduzione al corso. Automi a stati finiti: definizioni ed esempi. Linguaggi regolari. Operazioni sui linguaggi. [PDF]
Lezione 2 27/09/24 Chiusura dei linguaggi regolari rispetto ad unione ed intersezione. Automi a stati finiti non deterministici: definizioni ed esempi. [PDF]
Lezione 3 02/10/24 Equivalenza tra automi a stati finiti deterministici e non-deterministici. Chiusura dei linguaggi regolari rispetto alla concatenzazione e all'operazione star. Espressioni regolari: definizioni ed esempi. Equivalenza tra espressioni regolari e linguaggi regolari. [PDF]
Lezione 4 04/10/24 Equivalenza tra espressioni regolari e linguaggi regolari. Esempi. Linguaggi non regolari: pumping lemma. [PDF]
Lezione 5 09/10/24 Esercizi sui linguaggi regolari. Grammatiche acontestuali: prime definizioni ed esempi. [PDF]
Lezione 6 11/10/24 Ambiguità nelle grammatiche acontestuali. Forma normale di Chomsky. Esempi. [PDF]
Lezione 7 16/10/24 Automi a pila: definizioni ed esempi. Equivalenza tra automi a pila non-deterministici e grammatiche acontestuali. [PDF]
Lezione 8 18/10/24 Equivalenza tra automi a pila non-deterministici e grammatiche acontestuali. Pumping lemma per linguaggi acontestuali. [PDF]
Lezione 9 23/10/24 Esercizi sulle grammatiche acontestuali. Calcolabilità. Macchine di Turing: prime definizioni ed esempi. [PDF]
Lezione 10 25/10/24 Esempi di macchine di Turing e trucchi di programmazione. Linguaggi Turing-riconoscibili e linguaggi decidibili. [PDF]
Lezione 11 30/10/24 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. Macchine di Turing enumeratori. [PDF]
Lezione 12 06/11/24 Esempi di linguaggi Turing-decidibili. Esistenza di linguaggi non decidibili e non Turing-riconoscibili. [PDF]
Lezione 13 08/11/24 La diagonalizzazione ed esempi di linguaggi indecidibili. Primi esempi di riducibilità. [PDF]