Sillabo dell'insegnamento

• A - Fondamenti
* CAL - Calcolabilita'
Prerequisiti matematici; funzione coppia
* CAL - Calcolabilita'
Linguaggi di programmazione RAM e while ? Sintassi e semantica operazionale ? Compilatori ? Aritmetizzazione di programmi ? Interprete e funzione universale ? Eliminazione del "goto" ? Funzioni ricorsive parziali
* CAL - Calcolabilita'
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
COM - Complessita'
? 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
COM - Complessita'
? Le classi L, P, PSPACE ? Tesi di Church ristretta ? Macchine di Turing nondeterministiche: tempo e spazio ? Le classi NL, NP, NPSPACE
COM - Complessita'
? Teorema di Savitch ? Riduzioni tra problemi e completezza ? Problemi NP-completi, P-completi, PSPACE-completi ? Teorema di Cook ed esempi di riduzione