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]