Automi, Calcolabilità e Complessità (Autunno 2024)

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ì (15:00 - 17:00). Aula: La lezione del Mercoledì è in Aula 3L – Via del Castro Laurenziano 7a. La lezione del Venerdì è in Aula 4 De Lollis.

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 2024/2025 appariranno qui non appena disponibili.

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.
09/11/2024: A causa dei lavori in corso nelle aule in Via De Lollis, la lezione del 15 novembre avrà luogo in Aula 201 - Palazzina D - Viale Regina Elena 295.
16/11/2024: A causa dei lavori in corso nelle aule in Via De Lollis, la lezione del 22 novembre avrà luogo in Aula 201 - Palazzina D - Viale Regina Elena 295.
18/10/2024: Gli studenti sono invitati al prossimo appuntamento della serie di seminari Distinguished Lectures, sponsorizzata dal Dipartimento di Informatica. Il seminario avrà luogo il 25/11/24 alle ore 12pm in Viale Regina Elena 295, Palazzina D, Aula 101.
23/11/2024: A partire dalla prossima settimana, le lezioni del venerdì avranno luogo in Aula 4 De Lollis (Via Tiburtina 205).
12/12/2024: A causa dello sciopero nazionale proclamato per la giornata di domani, la lezione del 13 dicembre sarà eccezionalmente da remoto a questo link.

Diario delle lezioni