Università Roma Tre

COMPLEXITY, COMPUTABILITY, REPRESENTABILITY: DECISION PROBLEMS, FINITE AUTOMATA AND ALGORITHMS. TURING-COMPUTABILITY. SPACE AND TIME COMPLEXITY OF ALGORITHMS. RAM MACHINES. COMPLEXITY FUNCTIONS. RECURSIVE FUNCTIONS. THE HALT PROBLEM FOR TURING MACHINES. FUNCTIONAL PROGRAMMING: LAMBDA CALCULUS. CHURCH-ROSSER THEOREM. STRATEGIES OF REDUCTION. SOLVABLE TERMS. BÖHM'S THEOREM. THEOREM FOR LAMBDA-DEFINABLE RECURSIVE FUNCTIONS. BETA-FUNCTIONAL MODELS OF LAMBDA-CALCULUS. OBJECT-ORIENTED PROGRAMMING: CLASSES, FUNCTIONAL CLASSES. CLASS INHERITANCE. ABSTRACT CLASS DECLARATION. PUBLIC AND PRIVATE METHODS. METHOD LATE-BINDING.

[1] DEHORNOY, P., COMPLEXITE' ET DECIDABILITE'. SPRINGER-VERLAG, (1993).
[2] KRIVINE, J.-L., LAMBDA CALCULUS: TYPES AND MODELS. ‪ELLIS HORWOOD, (1993).
[3] SIPSER,M., INTRODUCTION TO THE THEORY OF COMPUTATION.THOMSON COURSE TECHNOLOGY, (2006).
[4] GABBRIELLI, M., MARTINI, S., LINGUAGGI DI PROGRAMMAZIONE: PRINCIPI E PARADIGMI. MCGRAW-HILL, (2011).

FURTHER TEXTBOOKS:

[4] AHO, HOPCROFT, ULLMAN, DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS. ADDISON-WESLEY PUB. CO., (1974).
[5] AUSIELLO, G., GAMBOSI, G., D'AMORE F., LINGUAGGI, MODELLI, COMPLESSITA'. FRANCO ANGELI (2003).
[6] A. BERNASCONI, B. CODENOTTI, INTRODUZIONE ALLA COMPLESSITA' COMPUTAZIONALE. SPRINGER-VERLAG, (1998).
[7] SETHI, R., PROGRAMMING LANGUAGES: CONCEPTS AND CONSTRUCTS. ADDISON-WESLEY (ED. ITALIANA ZANICHELLI), (1996).
[8] HERMES, H., ENUMERABILITY, DECIDABILITY, COMPUTABILITY. DIE GRUNDLEHREN DER MATHEMATICHENWISSENSHAFTEN IN EINZELDARSTELLUNGEN, N. 127, SPRINGER-VERLAG, (1969).
[9] DARNELL, P. A. AND MARGOLIS, P. E., C A SOFTWARE ENGINEREEING APPROACH. SPRINGER-VERLAG, (1996).