Elementi di informatica teorica

Introdurre lo studente a nozioni e risultati teorici di base soggiacenti all’informatica. Lo studente potrà impadronirsi di concetti fondamentali dell'Informatica teorica e dei relativi modelli astratti di calcolo, apprezzandone l’utilità sia per un inquadramento generale del curriculum in Informatica sia per lo sviluppo delle sue capacità professionali.

Automi finiti e macchine sequenziali. Automi non deterministici. Linguaggi regolari. Espressioni regolari. Pumping lemma per i linguaggi regolari. Grammatiche e linguaggi indipendenti dal contesto. Forme normali di Chomski. Automi a pilae non determinismo. Corrispondenza tra automi e grammatiche. Pumping lemma per i linguaggi indipendenti dal contesto. La gerarchia di Chomsky. I concetti di algoritmo, funzione calcolabile e parzialmente calcolabile. Funzioni primitive ricorsive. La minimalizzazione. Funzioni parziali ricorsive. Numerazioni di Goedel. Macchina universale. Tesi di Church - Turing. Problemi di decisione e di enumerazione. Indecidibilità. Insiemi ricorsivi e ricorsivamente numerabili. Macchina di Turing e indecidibilità, Complessità computazionale: nozioni di base