Università Roma Tre

COMPLESSITÀ, COMPUTABILITÀ, RAPPRESENTABILITÀ: PROBLEMI DI DECISIONE, AUTOMI FINITI E ALGORITMI. TURING-CALCOLABILITÀ. COMPLESSITÀ SPAZIALE E TEMPORALE DEGLI ALGORITMI. MACCHINE RAM. 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 BÖHM. 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. ‪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).

TESTI DI APPROFONDIMENTO:

[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).