Riepilogo dell'insegnamento: Calcolabilità e Complessità
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