IN410 - Informatica 2 - Modelli di Calcolo - AA 2016-2017

Corso

Descrizione, Programma


Introduzione

Il corso Informatica 2 - Modelli di Calcolo (IN410) è 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 nel corso IN110 verrà qui ampliata con nuovi concetti e punti di vista. È richiesto come prerequisito di tipo informatico la conoscenza del sistema operativo Unix (Linux) e della programmazione in C.

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).

Programma finale del corso A.A. 2016-2017

Il programma effettivo sarà disponobile al termine del corso.