IN410 - Calcolabilità e Complessità - AA 2019-2020

Corso

Descrizione, Programma


Introduzione

Il corso Calcolabilità e Complessità (IN410) è dedicato all'approfondimento degli aspetti matematici del concetto di computazione, allo studio delle relazioni tra diversi modelli di calcolo e alla complessità computazionale. La competenza di base sull'informatica e sulla programmazione dei calcolatori elettronici che è stata acquisita nel percorso precedente verrà qui ampliata con nuovi concetti e punti di vista.

Programma indicativo del corso

1. Computabilità, complessità e rappresentabilità

Automia stati finiti e decidibilità. 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, le classi di complessità probabilistica. - (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à.

Programma finale del corso A.A. 2019-2020

Il programma effettivo sarà disponobile al termine del corso.