Sillabo dell'insegnamento

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