II periodo (III anno)

• Docenti: A. Dovier e 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 e Semantica.
• Programma:
• Automi e linguaggi formali (20h):
Linguaggi formali e grammatiche generative
Classificazione di Chomsky e ambiguità
Linguaggi regolari e ASF
Linguaggi liberi da contesto (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
Teorema di Ricorsione e programmazione: Funzionali ricorsivi
Riducibilità funzionale: Insiemi creativi e produttivi
• Testi: Dispense distribuite a lezione (dispensa.ps.gz) a integrazione dei seguenti testi:

 
• Hopcroft and Ullman, "Introduction to Automata Theory, languages and computation" (Addison Wesley)
• Jones, "Computability and Complexity" (MIT Press)
• Rogers, "Theory of recursive functions and effective computability",  (MIT Press)
• Odifreddi, "Classical recursion theory" (Elsevier North-Holland)
• The Alan Turing Home Page (...for fun!)