Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessita'
Funzioni Calcolabili e non calcolabili, problema della fermata, insiemi ricorsivi e ricorsivamente enumerabili
SLP - Semantica dei Linguaggi di Programmazione
Linguaggi e problemi, accettabilit? e decidibilit? di linguaggi, calcolo non deterministico.
TIC - Teoria dell'Informazione e Codici
Elementi di teoria della complessit?: misure statiche e dinamiche, classi di complessit? spaziali e temporali, le classi di problemi P e di NP
TIC - Teoria dell'Informazione e Codici
La congettura P=NP? NP- completezza. Schema di Dimostrazione di NP- completezza. Enunciato del Teorema di Cook
SLP - Semantica dei Linguaggi di Programmazione
Elementi di Logica: calcolo delle proposizioni, calcolo dei predicati, sistemi formali
* CAL - Calcolabilita'
Elementi di Teoria della Calcolabilità: numerabilità, concetti di algoritmo e modello di calcolo, tesi di Church, macchina Turing e macchina a registri.