| IN3 - Teoria dell'informazione |
| Prof. Lorenzo Tortora de Falco |
| e-mail: tortora@uniroma3.it |
| Richiami di Teoria della complessità, macchine di Turing, classi di complessità algoritmica, le classi P ed NP, problemi NP completi. Sistemi formali. L'aritmetica di Peano (PA), e le funzioni ricorsive. Funzioni polinomiali e funzioni Kalmar ricorsive. Sottoteorie di PA che caratteriz-zano classi di complessità. Teorema di Cobham. La gerarchia della classe polinomiale. Programmazione funzionale. Lambda-calcolo e proof-nets della logica lineare. Aritmetica funzionale del II ordine.Isomorfismo di Curry-Howard. Sistemi formali per la caratterizzazione implicita delle classi di complessità: logica lineare light e logica lineare elementare. |
| I Semestre Crediti: 6 Prerequisiti: IN2 |
| Programma esteso: [Versioni disponibili PDF ] |