Il corso

Introduzione

Il corso di Informatica 2 (IN410 - Modelli di Calcolo) è dedicato all'approfondimento degli aspetti matematici del concetto di computazione, e allo studio della relazioni tra diversi modelli di calcolo, e tra diversi stili di programmazione. La competenza di base sull'informatica e sulla programmazione dei calcolatori elettronici che è stata acquisita nei corsi di TIB e IN1 verrà qui ampliata con nuovi concetti e punti di vista. E' richiesto come prerequisito di tipo informatico la conoscenza del sistema operativo Unix (Linux) e della programmazione in C.

Più in dettaglio, il corso Modelli di Calcolo 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à.

La seconda parte del corso si concentrerà sul modello funzionale della computabilità e più in generale sulla programmazione funzionale.

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'halt.

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

Programmazione object-oriented

Cenni di programmazione in java.

Programmazione funzionale.

Programmazione in ML (ocaml).

Programma finale del corso A.A. 2010-2011

Il programma effettivo sarà disponobile al termine del corso.