Automi Calcolabilita' e Complessita' – prof. Daniele Gorla

Informatica – erogato in modalità prevalentemente a distanza · Sapienza Università di Roma · 3º anno · 1º semestre · 6 CFU · canale unico

Testi d'esame di Automi Calcolabilita' e Complessita' del prof. Daniele Gorla, canale unico, corso di laurea in Informatica – erogato in modalità prevalentemente a distanza (Laurea triennale (L-31)), Sapienza Università di Roma, 3º anno · 1º semestre · 6 CFU, a.a. 2026/2027. Libri adottati: Sipser – Introduction to the Theory of Computation; Hopcroft – Introduction to Automata Theory.

Automi Calcolabilita' e Complessita' – Prof. Daniele Gorla Canale unico

Il docente consiglia di frequentare

Corso di laurea: Informatica – erogato in modalità prevalentemente a distanza · Laurea triennale (L-31) · 3º anno · 1º semestre · 6 CFU

Sapienza · Ingegneria dell'informazione, informatica e statistica · 6 CFU · apri nel catalogo

Il docente indica 2 testi · da studiare tutti

Sipser – Introduction to the Theory of Computation Vai su Amazon ›Verificato sulla scheda ufficiale il 18/09/2026

Alcuni argomenti saranno tratti dal capitolo 9 di

Hopcroft – Introduction to Automata Theory Vai su Amazon ›Verificato sulla scheda ufficiale il 18/09/2026

Bacheca del docente: cosa indica di studiare

Argomenti del programma: Automi e Linguaggi: Linguaggi regolari, automi a stati finiti e grammatiche regolari. Linguaggi context-free, grammatiche context-free e automi a pila; gerarchia di Chomsky. Teoria della Calcolabità: Macchine di Turing. Tesi di Church-Turing. Problemi indecidibili: il problema della fermata. La riduzione tra problemi: uno strumento per dimostrarne l'indecibilità o la decidibilità.

Apri la scheda ufficiale ›

Aiutaci a tenerci aggiornati

Il prof ha indicato altri libri, pagine o modifiche? Scrivicelo.

Altre materie del prof. Gorla

Foundations Of Computer Science · Applied Computer Science and Artificial Intelligence – Informatica Applicata e Intelligenza Artificiale · 3º anno · 1º semestre · 6 CFU
Concurrent Systems · Computer Science - Informatica · 1º anno · 2º semestre · 6 CFU · a scelta (Gruppo B - Caratterizzanti)

Altri esami del 3º anno – Informatica – erogato in modalità prevalentemente a distanza

Gamification e Game Design · 2º semestre · Damiano Distante
Sicurezza · 2º semestre · Emiliano Casalicchio

Vedi anche: Prof. Daniele Gorla · Automi Calcolabilita' e Complessita' a Sapienza (tutti i canali)