Informazioni di Fondamenti Dell'informatica

Dipartimento: Scienze Matematiche, Fisiche E Naturali
Settore Ministeriale: INF/01
Codice di verbalizzazione: 8060883
Metodi di insegnamento: Frontale E Altro
Metodi di valutazione: Scritto E Orale
Prerequisiti: Matematica Discreta
Obiettivi: Introduzione alla teoria della computazione. Linguaggi regolari. Definizione di linguaggio formale e notazioni. Automa a stati finiti deterministico. Automa a stati finiti non deterministico. Teorema di equivalenza di automa non deterministico con automa deterministico. Espressioni regolari. PumpingLemma. Proprieta' di chiusura. Algoritmi per automi a stati finiti. Minimizzazione di automi. Linguaggi context-free. Grammatiche contextfree. Derivazioni. Automi a pila. Teorema di equivalenza grammatiche context-free / automi a pila. Proprieta' di chiusura. Linguaggi non context-free. Determinismo. Definizione macchina di Turing. Computazioni di macchine diTuring. Estensioni di macchine di Turing. Linguaggi ricorsivamente enumerabili e linguaggi ricorsivi. La tesi di Turing-Church. Il linguaggio diagonale. Macchine di Turing Universali. Il problema della fermata. Problemi indecidibili.
Ricevimento: Martedi' 11:00-13:00

Navigazione Utente: