Fondamenti dell Informatica: Calcolabilità

Scopo del corso è quello di fornire gli strumenti formali e le nozioni fondamentali per studiare problemi trattabili e non mediante algoritmi. Il corso è strutturato in 2 parti. Nella prima parte viene presentata la teoria degli automi e dei linguaggi formali, teoria a fondamento della descrizione e dell'implementazione dei linguaggi di programmazione. Nella seconda parte si delineano i limiti di ciò che è effettivamente calcolabile mediante calcolatore, e si studia la natura e la struttura dei problemi che ammettono soluzione algoritmica.

Programma del corso:

Automi e linguaggi formali

Linguaggi formali e grammatiche generative
Classificazione di Chomsky e ambiguità
Linguaggi regolari e ASF
Linguaggi liberi da contesto, forme normali
Linguaggi dipendenti da contesto

Calcolabilità

Nozione intuitiva di algoritmo
Modelli formali per il calcolo: Macchine di Turing/funzioni ricorsive/programmi for-while
Tesi di Church
Goedelizzazione, Universalità e Teorema s-m-n
Problemi solubili e non: problema della terminazione
Metaprogrammazione: compliazione, interpretazione e specializzazione
Insiemi ricorsivi e r.e.
Teoremi di Ricorsione e Teorema di Rice
Riducibilità funzionale: Insiemi creativi e produttivi

Titolare del Corso: Prof. Roberto Giacobazzi.