2013
2013
Sei collegato come utente non registrato
Riepilogo dell'insegnamento: Calcolabilità e Complessità
Informazioni generali
Corso di Laurea Informatica Percorso Laurea in Informatica
CFU 9 Università PISA
Ore di didattica frontale per CFU 8 Settore Scientifico Disciplinare INF/01
Commento Insegnamento Fondamentale: III anno

9 cfu così ripartiti nelle aree:

  • 9 CFU nell'area A - Fondamenti

Sillabo dell'insegnamento

  • A - Fondamenti
    • * CAL - Calcolabilita'
      Il modello delle machine di turing.
    • * CAL - Calcolabilita'
      Linguaggi calcolabili, MdT universale
    • * CAL - Calcolabilita'
      Funzioni ricorsive e linguaggi di programmazione, Totalità e diagonalizzazione
    • * CAL - Calcolabilita'
      Riducibilità, problemi insolubili
    • * CAL - Calcolabilita'
      Funzioni di misura di tempo e spazio
    • COM - Complessita'
      Classi (tempo/spazio) deterministiche e non. P- e NP-completezza
    • * ALF - Automi e Linguaggi Formali
      Automi a stati finiti e linguaggi regolari
    • * ALF - Automi e Linguaggi Formali
      Grammatiche Libere e Push down automata
    • * ALF - Automi e Linguaggi Formali
      Problemi di decisione e automi

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