IN2 - Informatica 2, modelli di calcolo

Prof. Marco Pedicini

DM, Stanza 202 tel. 06 5488 8231

e-mail: pedicini@mat.uniroma3.it

Complessità, computabilità, rappresentabilità: problemi di decisione, automi finiti e algoritmi. Turing-calcolabilità. Complessità spaziale e temporale degli algoritmi. Funzioni di complessità. Funzioni ricorsive. Il problema dell'arresto per le macchine di Turing. Programmazione funzionale: Lambda calcolo. Teorema di Church-Rosser. Strategie di normalizzazione. Risolubilità. Teorema di Bohm. Teorema di lambda-definibilità per le funzioni ricorsive. Modelli beta-funzionali del lambda-calcolo. Programmazione object-oriented: dichiarazioni di classi funzionali. Ereditarietà tra classi. Dichiarazione di classi virtuali. Definizione di metodi privati. Late-binding di metodi.

I Semestre Crediti: 7,5 c Prerequisiti: IN1

Insegnamento valido per la PFA

Programma esteso:   [Versioni disponibili:  PDF]