Primo Semestre (III e IV anno)

• Docenti: A. Dovier e R. Giacobazzi
• Descrizione del corso: (2UD = 120h)
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 3 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, mentre nella terza parte vengono caratterizzati i problemi risolvibili con risorse limitate e la complessità astratta dei problemi.
• Programma:
• Automi e linguaggi formali (30h):
Linguaggi formali e grammatiche generative
Classificazione di Chomsky e ambiguità
Linguaggi regolari e ASF
Linguaggi liberi da contesto, forme normali e Automi a Pila
Linguaggi dipendenti da contesto
 
• Calcolabilità (60h):
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
     
• Complessità (30h):
Misure della complessità di problemi
Classi di complessità: P e NP
Robustezza delle classi
Complessità in spazio e altre classi di complessità
Gerarchia delle Classi
 
• 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)
• Garey and Johnson, "Computers and Intractability" (Freeman & co.)
• Papadimitriou, "Computation and Complexity" (Addison Wesley)
• The Alan Turing Home Page (...for fun!)