Complessità, computabilità, rappresentabilità: problemi di decisione, automi finiti e algoritmi. Turing-calcolabilità. Complessità spaziale e temporale degli algoritmi. Funzioni di complessità. Macchine RAM. 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 Boehm. 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. Latebinding di metodi.
[1] Dehornoy, P., Complexite' et Decidabilite'. Springer-Verlag, (1993). [2] Krivine, J.-L., Lambda Calculus: Types and Models. Masson, [3] M. Gabbrielli, S. Martini, Linguaggi di programmazione: principi e paradigmi, McGraw-Hill. [4] Ausiello, G., Gambosi, G., D'Amore F., Linguaggi, Modelli, Complessita', Franco Angeli (2003).