Fondamenti di Informatica

Martedì 6 Marzo si terrà la prima lezione del corso per l'anno accademico 2017/18
Cari studenti, mi scuso ma la lezione di domani è cancellata confermo la lezione di mercoledì 21 Marzo.

Docente:

Link ESSE3

Orario delle Lezioni:

Ricevimento studenti:

La computabilità da Leibniz ai giorni nostri. Il concetto di Algoritmo.
Alfabeti, stringhe e linguaggi. Il ruolo che stringhe e linguaggi hanno per rappresentare l’informazione.
Linguaggi. Strumenti per definire un linguaggio. Espressioni Regolari, Approccio Generativo, Approccio Riconoscitivo.
Calcolabilità e Grammatiche. Grammatiche e automi. La gerarchia di Chomsky. Linguaggi regolari, liberi da contesto, dipendenti dal contesto.
Automi di riconoscimento. Deterministici e Non Deterministici. Trasformazioni.
Macchine di Turing. Funzioni calcolabili e linguaggi decidibili secondo Turing. La tesi di Church. Macchine di Turing non deterministiche.
Problemi senza soluzione. La macchina Universale. Il problema dell'arresto. Il decimo problema di Hilbert. I teoremi di Rice e di Kleene.
Funzioni Ricorsive. Calcolabilità secondo Church. Funzioni parziali ricorsive.
Calcolabilità e Linguaggi di Programmazione. Il linguaggio WHILE: sintassi e semantica.

Slide del Corso (saranno pubblicate durante lo svolgimento delle lezioni)

Slide anno accademico precedente [zip file].

Testi di Riferimento

F. Corradini, S. Leonesi, S. Mancini, C. Toffalori: Teoria della computabilità e della complessità. McGraw-Hill Italia, 2005. (Capitolo 1 – 6)

Le date di esame sono già disponibili al Seguente Link - https://didattica.unicam.it/Home.do

Regole di esame:

Risultati Esame

News