Informatica Teorica
Corso di laurea Magistrale in Informatica
Programma del corso, testi e modalità d'esame
Programma del corso
Teoria della
calcolabilità
- Prerequisiti matematici
- Funzione coppia
- Linguaggi di programmazione RAM e while
- Sintassi e semantica operazionale
- Compilatori
- Aritmetizzazione di programmi
- Interprete e funzione universale
- Eliminazione del "goto"
- Funzioni ricorsive parziali
- Tesi di Church
- Esistenza di problemi non decidibili
- Passaggio automatico di parametri
- Sistemi di programmazione accettabili
- Teorema di ricorsione
- Insiemi ricorsivi e ricorsivamente numerabili
- Proprietà di chiusura
- Teorema di Rice
Teoria della
complessità
- Introduzione alla complessità sequenziale
- Prerequisiti matematici: la notazione "O grande"
- Macchine di Turing deterministiche
- Risorse computazionali: tempo e spazio
- Classi di complessità in tempo e spazio
- Le classi L, P, PSPACE
- Tesi di Church ristretta
- Macchine di Turing nondeterministiche: tempo e spazio
- Le classi NL, NP, NPSPACE
- Teorema di Savitch
- Riduzioni tra problemi e completezza
- Problemi NP-completi, P-completi, PSPACE-completi
- Teorema di Cook ed esempi di riduzione
Testi consigliati
Per entrambe le parti, sono previste dispense
scaricabili dal sito del corso.
Per approfondimenti, si segnalano i seguenti testi entrambi reperibili
alla biblioteca dpartimentale:
- Teoria della calcolabilità
- A.J. Kfoury, R.N. Mall, M.A. Arbib. A programming approach to computability. Springer-Verlag, 1982.
di cui è disponibile (purtroppo non nella nostra biblioteca) la versione italiana:
- A.J. Kfoury, R.N. Mall, M.A. Arbib. Programmazione e computabilità. Etas libri, 1986.
- Teoria della Complessità
- M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, 1979.
Modalità d'esame
L'esame consiste di una prova scritta (teoria e piccoli esercizi) su tutto il programma del corso.