2013
2013
Sei collegato come utente non registrato
Riepilogo dell'insegnamento: Calcolabilita' e Complessita'
Informazioni generali
Corso di Laurea Informatica Percorso Sistemi Informatici
CFU 9 Università NAPOLI "Federico II"
Ore di didattica frontale per CFU 8 Settore Scientifico Disciplinare INF/01
   

9 cfu così ripartiti nelle aree:

  • 9 CFU nell'area A - Fondamenti

Sillabo dell'insegnamento

  • A - Fondamenti
    • * ALF - Automi e Linguaggi Formali
      Breve introduzione al corso. Automi deterministici e nondeterministici. Proprieta' di chiusura. Automi Pushdown con relative proprieta' di chiusura.
    • * CAL - Calcolabilita'
      Introduzione alle Macchine di Turing. Macchine di Turing multinastro. Macchine di Turing nondeterministiche. Macchine di Turing Universali.
    • * CAL - Calcolabilita'
      Problemi decidibili e indecidibili. Mapping Reducibility. Linear Bounded Automata e Post Correspondence Problem. Decidibilita' delle teorie logiche.
    • 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
    • COM - Complessita'
      Le classi EXPTIME e EXPSPACE e loro completezza.
    • * 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'
      Misurazione della Complessita' e introduzione alla classe P. La classe dei problemi NP. Problemi NP-Completi.

(*) Le sottoaree con asterisco sono quelle che il GRIN auspica facciano parte in via prioritaria dei sillabi degli insegnamenti assegnati all?area stessa