Università Roma Tre

IL CORSO TEORIA DELLA COMPUTAZIONE E DELL'INTERAZIONE (TCI) È DEDICATO ALL'APPROFONDIMENTO DEGLI ASPETTI TEORICI LEGATI AL CONCETTO DI COMPUTAZIONE E ALLO STUDIO DELLA RELAZIONI TRA DIVERSI MODELLI DI CALCOLO. LA COMPETENZA DI BASE SULL'INFORMATICA ACQUISITA NEL CORSO ARCHITETTURA DELL'INFORMAZIONE E DELLA COMPUTAZIONE VERRÀ QUI AMPLIATA CON NUOVI CONCETTI E PUNTI DI VISTA TEORICI.
IL CORSO È SUDDIVISO IN DUE MODULI DA 6 CFU IN MODO DA PERMETTERE CHE L'ESAME VENGA SOSTENUTO SOLO SUL PRIMO MODULO (6 CFU) O SU ENTRAMBI (12 CFU).

PIÙ IN DETTAGLIO, IL CORSO FORNISCE UNA PRESENTAZIONE DEI CONCETTI FORMALI DI ALGORITMO E DI COMPUTABILITÀ. DOPO L'INTRODUZIONE CLASSICA DEL CONCETTO DI COMPUTABILITÀ MEDIANTE LA FORMALIZZAZIONE DATA DA ALAN M. TURING VERRANNO AFFRONTATI I CONCETTI DI BASE DELLA COMPLESSITÀ ALGORITMICA ED ALCUNE QUESTIONI RIGUARDANTI LA DECIDIBILITÀ. I MODELLI FUNZIONALI E PIÙ IN GENERALE SULLA PROGRAMMAZIONE FUNZIONALE.

IL SECONDO MODULO DEL CORSO SI CONCENTRERÀ SULLA QUESTIONE DEI PARADIGMI INTERATTIVI NELLA TEORIA DELLA COMPUTAZIONE, UTILIZZATI NELLA DESCRIZIONE DI CLASSI DI COMPLESSITÀ MA ANCHE NELLA SEMANTICA DELLE PROVE LOGICHE. IL CORSO È MUTUATO DAL CORSO DI LAUREA IN MATEMATICA E SOSTITUISCE L'INSEGNAMENTO IN410 DEL CORSO DI LAUREA IN MATEMATICA.

P. DEHORNOY, CALCULABILITE ET DECIDABILITE, (1993) SPRINGER-VERLAG (IN FRANCESE);

J.-L. KRIVINE, LAMBDA CALCULUS: TYPES AND MODELS, (1993) ELLIS HORWOOD EDITORE.

M. SIPSER, AN INTRODUCTION TO THE THEORY OF COMPUTATION (2005), COURSE TECHNOLOGY.

M. PEDICINI, APPUNTI DI INFORMATICA TEORICA, (COPRONO PARZIALMENTE I TEMI DEL CORSO ESSENZIALMENTE BASATI SUI TESTI QUI SOPRA): DISPONIBILI SULLA DIRECTORY DEL DOCENTE AL LABORATORIO DI CALCOLO: /USERS/MPEDICIN/IN2/APPUNTI;
TESTI DI APPROFONDIMENTO

DEXTER C. KOZEN, THEORY OF COMPUTATION, SPRINGER-VERLAG (2006).

G. AUSIELLO, G. GAMBOSI, F. D'AMORE LINGUAGGI, MODELLI, COMPLESSITÀ (DRAFT SCARICABILE IN RETE).

M. GABBRIELLI, S. MARTINI LINGUAGGI DI PROGRAMMAZIONE, MCGRAW HILL.

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

AHO, HOPCROFT, ULLMAN, DESIGN AND ANALYSIS OF COMPUTER PROGRAMMING.

A. BERNASCONI, B. CODENOTTI, INTRODUZIONE ALLA COMPLESSITÀ COMPUTAZIONALE, SPRINGER-VERLAG.

H. HERMES, ENUMERABILITY, DECIDABILITY, COMPUTABILITY, DIE GRUNDLEHREN DER MATHEMATICHEN WISSENSHAFTEN IN EINZELDARSTELLUNGEN, N. 127, SPRINGER-VERLAG.

P. H. WINTSON, S. NARASIMHAN, ON TO JAVA, ADDISON-WESLEY (1998).