Sapienza Università di Roma · Ingegneria dell'informazione, informatica e statistica · tutti i canali con docenti, libri e orari, a.a. 2026/2027
Ingegneria dell'informazione, informatica e statistica · 3º anno · 1º semestre · 6 CFU · apri nel catalogo
Il docente non ha ancora pubblicato i testi per questo canale.
Cosa indica di studiare il docente
Argomenti del programma: 1) Automi e Linguaggi: Linguaggi regolari e automi a stati finiti. Linguaggi acontestuali e automi a pila. 2) 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à. Esempi di problemi decidibili e indecidibili.
Ingegneria dell'informazione, informatica e statistica · 3º anno · 1º semestre · 6 CFU · apri nel catalogo
Alcuni argomenti saranno tratti dal capitolo 9 di
Cosa indica di studiare il docente
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à.