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.
[1] Dehornoy, P., Complexite' et Decidabilite'. Springer-Verlag, (1993).[2] Krivine, J.-L., Lambda Calculus: Types and Models. Masson,[3] Sethi, R., Programming Languages: concepts and constructs. Addison-Wesley (ed. italiana Zanichelli),[4] Aho, Hopcroft, Ullman, Design and Analysis of Computer Programming.[5] Ausiello, G., Gambosi, G., d’Amore F., Linguaggi, Modelli, Complessita'. (draft scaricabile in rete: http://www.dis.uniroma1.it/~ausiello/InfoTeoRM/main.pdf)[6] Hermes, H., Enumerability, Decidability, Computability. Die Grundlehren der MathematichenWissenshaften in Einzeldarstellungen, n. 127, Springer-Verlag, ().[7] Darnell, P. A. and Margolis, P. E., C A Software Enginereeing Approach. Springer-Verlag, (1996).