|
Docente
|
PEDICINI MARCO
(programma)
(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)
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).
|
Università Roma Tre