Riepilogo dell'insegnamento: Calcolabilita' e Complessita'
9 cfu così ripartiti nelle aree:
- 9 CFU nell'area A - Fondamenti
Sillabo dell'insegnamento
- A - Fondamenti
- *
CAL - Calcolabilita'
Problemi decidibili e indecidibili. Mapping Reducibility. Linear Bounded Automata e Post Correspondence Problem. Decidibilita' delle teorie logiche.
-
COM - Complessita'
Misurazione della Complessita' e introduzione alla classe P. La classe dei problemi NP. Problemi NP-Completi.
-
L - Logica
Introduzione alle logiche temporali lineari. Problemi decisionali per LTL. Confronto tra i poteri espressivi di LTL, QLTL e delle espressioni omega-regolari.
- *
ALF - Automi e Linguaggi Formali
Introduzione agli automi alternanti. Il problema del vuoto. Algoritmi per la risoluzione del problema del vuoto per automi nondeterministici e alternanti
- *
ALF - Automi e Linguaggi Formali
Introduzione agli automi nondeterministici su parole infinite. Espressioni omega-regolari. Proprieta' di chiusura, di proiezione, di determinizzazione, di inclusione e di complementazione.
-
COM - Complessita'
Space Complexity. Savitch's Theorem e la classe PSPACE. PSPACE-completeness.
-
COM - Complessita'
Le classi EXPTIME e EXPSPACE e loro completezza.
- *
CAL - Calcolabilita'
Introduzione alle Macchine di Turing. Macchine di Turing multinastro. Macchine di Turing nondeterministiche. Macchine di Turing Universali.
- *
ALF - Automi e Linguaggi Formali
Breve introduzione al corso. Automi deterministici e nondeterministici. Proprieta' di chiusura. Automi Pushdown con relative proprieta' di chiusura.
(*) Le sottoaree con asterisco sono quelle che il GRIN auspica facciano parte in via prioritaria dei sillabi degli insegnamenti assegnati all?area stessa