Corso di:
Fondamenti dell'Informatica:
Calcolabilitā
I periodo (III e IV
anno)
- Docenti: R.
Giacobazzi
- Descrizione del corso: (1UD =
60h ca.)
Scopo del corso č quello di fornire gli strumenti
formali e le nozioni fondamentali per studiare
problemi trattabili e non mediante calcolatore. 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. La seconda parte
delinea i concetti e la natura dei problemi che
ammettono soluzione effettiva, ovvero dei problemi risolvibili mediante
calcolatore. Il corso č propedeutico per tutti corsi di informatica
teorica, in particolar modo per i corsi di Complessitā, Metodi formali,
Sicurezza e crittografia, i corsi di linguaggi (III, compilatori etc.),
deduzione automatica, e Semantica.
- Programma:
- Automi e linguaggi formali (25h):
Linguaggi e grammatiche
Automi a stati finiti e linguaggi regolari
Linguaggi liberi da contesto, forme normali e automi a pila
Classificazione di Chomsky (cenni)
- Calcolabilitā (30h):
Nozione intuitiva di algoritmo
Modelli formali per il calcolo:
Macchine di Turing/funz. 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
- 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