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