TCI - Teoria della Computazione e dell'Interazione - AA 2014-2015
Corso
Descrizione, Programma
Introduzione
Il corso Teoria della Computazione e dell'Interazione (TCI) è dedicato all'approfondimento degli aspetti teorici legati al concetto di computazione e allo studio della relazioni tra diversi modelli di calcolo. La competenza di base sull'informatica acquisita nel corso Architettura dell'Informazione e della Computazione verrà qui ampliata con nuovi concetti e punti di vista teorici.
Il corso è suddiviso in due moduli da 6 CFU in modo da permettere che l'esame venga sostenuto solo sul primo modulo (6 CFU) o su entrambi (12 CFU).Più in dettaglio, il corso fornisce una presentazione dei concetti formali di algoritmo e di computabilità. Dopo l'introduzione classica del concetto di computabilità mediante la formalizzazione data da Alan M. Turing verranno affrontati i concetti di base della complessità algoritmica ed alcune questioni riguardanti la decidibilità. I modelli funzionali e più in generale sulla programmazione funzionale.
Il secondo modulo del corso si concentrerà sulla questione dei paradigmi interattivi nella teoria della computazione, utilizzati nella descrizione di classi di complessità ma anche nella semantica delle prove logiche. Il corso è mutuato dal corso di Laurea in Matematica e sostituisce l'insegnamento IN410 del corso di Laurea in Matematica.
Programma indicativo del corso
1. Computabilità, complessità e rappresentabilità
Algoritmi e Macchine di Turing: problemi di decisione (esempio intuitivo di funzione non calcolabile e insiemi non decidibili), sistemi di transizione, automi finiti, macchine di Turing, equivalenze tra i diversi tipi di macchine di Turing (nastro, seminastro, multinastro, deterministiche e non deterministiche), macchina di Turing universale, problema dell'arresto.
Complessità algoritmica, Teorema di speedup, Tesi di Church. Modello RAM: macchina ad accesso casuale (RAM) definizione, esempi; risorse in spazio e tempo; criteri di costo uniforme e logaritmico; equivalenza tra modello RAM e macchina di Turing. Funzioni Ricorsive: definizione ed esempi, esempi di funzioni totali non primitive ricorsive, funzioni ricorsive parziali.
Classi di complessità, notazioni asintotiche, le classi P ed NP, problemi NP completi. - (opt. funzioni generatrici)
2. Lambda calcolo e programmazione funzionale
Introduzione, definizione dei lambda termini. Congruenze, equivalenze, riduzioni, Teorema di Church-Rosser. Teorema di lambda-definibilità per le funzioni ricorsive. Risolubilità di lambda-termini, Teorema di Boehm. Sistemi di tipo, Teorema di standardizzazione e Teorema di forte normalizzazione. Immersione del lambda calcolo puro nel lambda calcolo tipato. Polimorfismo, sistema F, tipi di dato astratto (ADT).
3. Modelli del lambda calcolo
Insiemi e Relazioni, insiemi parzialmente ordinati, reticoli, costruzione dei domini. Continuità, calcolabilità, stabilità, sequenzialità.
4. Paradigmi di programmazione: linguaggi funzionali ed object-oriented (solo per gli studenti di IN410)
Programmazione object-oriented Cenni di programmazione in java. Programmazione funzionale. Programmazione in ML (ocaml).