Obiettivi formativi

Scopo del corso è quello di fornire gli strumenti formali e le nozioni fondamentali che stanno alla base dell'informatica vista come scienza. Il corso, fondamentale per la Laurea in Informatica e Tecnologie dell'informazione, sviluppa la teoria della cacolabilità arricchendo semplici macchine a stati (automi a stati finiti) con strutture dati via via piu' complesse, fino ad ottenere la potenza espressiva dei moderni linguaggi di programmazione. Partendo dalla teoria degli automi e dei linguaggi formali, teoria a fondamento della descrizione e dell'implementazione dei linguaggi di programmazione, si arriva a delineare i concetti e la natura dei problemi che ammettono soluzione effettiva, ovvero dei problemi risolvibili mediante strumenti automatici di calcolo quali i computers, e dei problemi che non sono risolvibili mediante gli stessi strumenti, defininendo i limiti di cio' che è calcolabile. Il corso è propedeutico per tutti i corsi di informatica teorica ed applicata, in particolar modo per i corsi di Complessità, Metodi formali, Sicurezza e crittografia, i corsi di linguaggi (III, compilatori etc.), deduzione automatica, e Semantica.

Attività formative

Il corso ha carattere prevalentemente teorico. Sono previste esercitazioni orientate allo studio di semplici problemi ed alla loro classificazione all'interno della teoria classica della calcolabilità.

Programma del corso

Automi e linguaggi formali (25h):

Linguaggi e grammatiche
Automi a stati finiti e linguaggi regolari
Linguaggi liberi da contesto
Forme normali di Chomsky e Greibach
Automi a pila non deterministici
Classificazione di Chomsky

Calcolabilità (30h):

Nozione intuitiva di algoritmo
Modelli formali per il calcolo: Macchine di Turing/funzioni ricorsive/programmi while
Espressività di un linguaggio di programmazione
Tesi di Church
Goedelizzazione, Universalità e Teorema s-m-n
Metaprogrammazione: compliazione, interpretazione e specializzazione
Problemi risolvibili e non: il problema della terminazione
Insiemi ricorsivi e r.e.
Teoremi di Ricorsione e Teorema di Rice
Riducibilità funzionale e completezza in r.e.
Insiemi creativi, produttivi e semplici
Risultati di incompletezza (cenni)

TESTI

Dispense distribuite a lezione a integrazione dei seguenti testi:

Hopcroft and Ullman, "Introduction to Automata Theory, languages and computation", Addison Wesley, 1979
Jones, "Computability and Complexity", MIT Press, 1997
Rogers, "Theory of recursive functions and effective computability", MIT Press, 1988
Odifreddi, "Classical recursion theory", Elsevier North-Holland, 1989