Automi, Calcolabilità e Complessità (Autunno 2023)
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.
- La tesi di Church-Turing e la macchina di Turing.
- Linguaggi decidibili e non decidibili.
- Riducibilità.
- 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ì (14:00 - 17:00) e Venerdì (14:00 - 16:00).Aula: Aula IV - Città Universitaria - Edificio Castelnuovo.
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
Appello 1. Data: 10/01/24. Aula: 3 (Edificio RM018). Orario: 09:00-12:00. Risultati [pdf].Appello 2. Data: 08/02/24. Aula: 3 (Edificio RM018). Orario: 09:00-12:00. Risultati [pdf].
Appello 3. Riservato agli studenti fuori corso e agli studenti lavoratori (è necessario fare la richiesta in segreteria; la registrazione su infostud è comunque obbligatoria). Data: 09/04/24. Aula: 2L (Via del Castro Laurenziano 7a). Orario: 09:30-12:30. Risultati [pdf].
Appello 4. Data: 06/06/24. Aula: TBA. Orario: TBA. Risultati [pdf].
Appello 5. Data: 03/07/24. Aula: TBA. Orario: TBA. Risultati [pdf].
Appello 6. Data: 11/09/23. Aula: TBA. Orario: TBA. Risultati [pdf].
Notizie
24/09/2023: Il corso inizierà il 27 Settembre 2023.25/09/2023: La lezione del 29/09/2023 è cancellata.
06/10/2023: La lezione del 11/10/2023 è cancellata.
19/10/2023: Gli studenti sono invitati a partecipare al prossimo seminario della serie Distinguished Lectures, sponsorizzato dal Dipartimento di Informatica. Il seminario è il 23/10/23 con inizio alle ore 12pm, in Viale Regina Elena 295, Palazzina D, Aula 101.
30/11/2023: La lezione del 06/12/2023 è cancellata per consentire agli studenti di partecipare all'IT Meeting organizzato dal Dipartimento di Informatica. Sto organizzando 3 lezioni di recupero (circa 9 ore) che avranno luogo durante le ultime due settimane di lezioni. I dettagli saranno pubblicati appena possibile su questa pagina.
12/12/2023: Per concludere il programma, ci saranno tre lezioni di recupero:
- 14/12/23, Aula RE 1 Regina Elena Edificio A, orario 9-13;
- 18/12/23, Aula 101, Regina Elena Edificio D, orario 9-11;
- 21/12/23, Aula RE 1, Regina Elena Edificio A, orario 9-13.
Diario delle Lezioni
| Lezione/Data | Argomenti | Letture |
|---|---|---|
| Lezione 1, 27/09/23 | Introduzione al corso. Definizione di automa a stati finiti (DFA) e linguaggi regolari. Esempi di progettazione di DFA. | 0.1, 1.1 |
| Lezione 2, 04/10/23 | Operazioni sui linguaggi: unione, intersezione, complemento, concatenazione, star. Chiusura dei linguaggi regolari rispetto all'unione. Non determinismo. | 1.1, 1,2 |
| Lezione 3, 06/10/23 | Equivalenza tra NFA e DFA. Chiusura dei linguaggi regolari rispetto alla concatenzazione e star. | 1.2 |
| Lezione 4, 13/10/23 | Espressioni regolari. Equivalenza tra linguaggi regolari e linguaggi generati da espressioni regolari. | 1.3 |
| Lezione 5, 18/10/23 | Equivalenza tra linguaggi regolari e linguaggi generati da espressioni regolari. | 1.3 |
| Lezione 6, 20/10/23 | Linguaggi non regolari. Il pumping lemma. Esercizi. | 1.4 |
| Lezione 7, 27/10/23 | Esercizi. Grammatiche acontestuali: prime definizioni. | 2.1 |
| Lezione 8, 03/11/23 | Ambiguità ed esercizi sulle grammatiche. | 2.1 |
| Lezione 9, 08/11/23 | Forma normale di Chomsky. Automi a pila. Equivalenza tra automi a pila e grammatiche acontestuali. | 2.2 |
| Lezione 10, 10/11/23 | Equivalenza tra automi a pila e grammatiche acontestuali. | 2.2 |
| Lezione 11, 15/11/23 | Pumping lemma per linguaggi acontestuali. | 2.3 |
| Lezione 12, 17/11/23 | Esercizi e applicazioni del pumping lemma per linguaggi acontestuali. | -- |
| Lezione 13, 22/11/23 | Definizione di macchina di Turing e la tesi di Church-Turing. Primi esempi di macchine di Turing e trucchi di programmazione. Decidibilità e Turing-riconoscibilità. | 3.1 |
| Lezione 14, 24/11/23 | Robustezza del modello: Macchine di Turing multinastro, non-deterministiche, ed enumeratori. Il X problema di Hilbert. | 3.2, 3.3 |
| Lezione 15, 29/11/23 | Linguaggi decidibili. Macchina di Turing universale. Diagonalizzazione. | 4.1 |
| Lezione 16, 01/12/23 | Linguaggi non decidibili: accettazione, fermata, test del vuoto. Linguaggi non Turing-riconoscibili. | 4.2 |
| Lezione 17, 13/12/23 | Riducibilità mediante funzione. Esempi di riduzioni. | 5.3 |
| Lezione 18, 14/12/22 | Esercizi di calcolabilità. Complessità di tempo ed esempi. Le classi P ed EXP. Esempi di problemi in P. | 7.1, 7.2 |
| Lezione 19, 15/12/23 | Le classi NP e NEXP. Verificatori polinomiali e definizioni equivalenti di NP. Esempi di problemi in NP. | 7.3 |
| Lezione 20, 18/12/23 | NP completezza. Il teorema di Cook-Levin. | 7.4,7.5 |
| Lezione 21, 20/12/23 | La classe coNP. Complessità di spazio. Le classi L e PSPACE. Teorema di Savitch. | 8.1, 8.2 |
| Lezione 22, 21/12/22 | PSPACE completezza. Le classi L ed NL. Teoremi di gerarchia | 8.3, 8.4, 9.1, 9.2 |
| Lezione 23, 22/12/22 | Esercizi di complessità. | -- |