| IN3 - Teoria dell'informazione |
| Prof. Lorenzo Tortora de Falco |
| DM, Stanza 300 tel. 06 5488 8223 |
| e-mail: tortora@uniroma3.it |
| Calcolabilità e funzioni ricorsive. Macchina di Turing (deterministica). Indecidibilità eriduzioni algoritmiche. I teoremi di enumerazione, di Rice, del punto fisso. Macchine diTuring non deterministiche. Classi di complessità algoritmica. Teorema di Savitch.Riduzioni polinomiali e completezza. Il teorema di Cook-Levin sulla NP-completezza di SAT. |
| II Semestre Crediti: 6 Prerequisiti: IN2 |
| Insegnamento valido per la PFA |
| Programma esteso: [Versioni disponibili: PDF] |