Università Roma Tre

(I MODULO)

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.

(II MODULO)

NON-DETERMINISMO: IL TEOREMA PCP; INTRODUZIONE AI MODELLI DI COMPUTAZIONE QUANTISTICI.

TESTI DI RIFERIMENTO:

[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:

[5] AHO, HOPCROFT, ULLMAN, DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS. ADDISON-WESLEY PUB. CO., (1974).

[6] AUSIELLO, G., GAMBOSI, G., D'AMORE F., LINGUAGGI, MODELLI, COMPLESSITA'. FRANCO ANGELI (2003).

[7] A. BERNASCONI, B. CODENOTTI, INTRODUZIONE ALLA COMPLESSITA' COMPUTAZIONALE. SPRINGER-VERLAG, (1998).

[8] SETHI, R., PROGRAMMING LANGUAGES: CONCEPTS AND CONSTRUCTS. ADDISON-WESLEY (ED. ITALIANA ZANICHELLI), (1996).

[9] HERMES, H., ENUMERABILITY, DECIDABILITY, COMPUTABILITY. DIE GRUNDLEHREN DER MATHEMATICHENWISSENSHAFTEN IN EINZELDARSTELLUNGEN, N. 127, SPRINGER-VERLAG, (1969).

[10] DARNELL, P. A. AND MARGOLIS, P. E., C A SOFTWARE ENGINEREEING APPROACH. SPRINGER-VERLAG, (1996).