Sillabo dell'insegnamento

• A - Fondamenti
* CAL - Calcolabilita'
Linguaggi subricorsivi: ricorsione primitiva, sistema T;incompletezza dei formalismi totali;
* CAL - Calcolabilita'
Macchine di Turing e altri formalismi equivalenti; la tesi di Church.
* CAL - Calcolabilita'
Il problema della terminazione, altri problemi indecidibili; il teorema di Rice.
* CAL - Calcolabilita'
Insiemi ricorsivi e ricorsivamente enumerabili; il teorema di Rice-Shapiro.
* CAL - Calcolabilita'
Il teorema del punto fisso di Kleene.
* CAL - Calcolabilita'
Riducibilita'; insiemi produttivi, creativi, immuni, semplici. Calcolabilita' e (in)completezza.
COM - Complessita'
Problemi computazionali;
COM - Complessita'
Modelli di Computazione e misure di Complessita';
COM - Complessita'
Classi e gerarchie di complessita'
COM - Complessita'
classi notevoli; riduzione
COM - Complessita'
P vs NP, Problemi NP-completi
COM - Complessita'
Complessita' con oracoli