Teoria da Computação

Algoritmos, conjuntos, indução e cardinalidade. Máquinas de Turing. Funções recursivas. Algoritmos de Markov. A tese de Church-Turing. Indecidibilidade . Problemas intratáveis. Classes de problemas intratáveis.

Obrigatória: 

  • Brainerd, W. S., & Landweber, L. H. (1974). Theory of Computation. John Wiley & Sons.
  • Diverio, T. A., & Menezes, P. B. (1999). Teoria da Computação: Máquinas Universais e Computabilidade. Sagra-Luzzatto.
  • Epstein, R. L., & Carnielli, W. A. (2008). Computability: Computable Functions Logic and the Foundations of Math. Advanced Reasoning Forum.

Complementar: 

  • Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2001). Introduction to Automata Theory, Languages and Computation (2 ed.). Addison Wesley.
  • Sipser, M. (2007). Introdução à Teoria da Computação. Thomson Pioneira.
  • Sipser, M. (2006). Introduction to the Theory of Computation. Cengage Learning.
  • Gurari, E., & Gurari, E. (1989). An introduction to the theory of computation (Vol. 338). Computer Science Press Rockville.
  • Manna, Z. (2003). Mathematical theory of computation. Courier Dover Publications.
A⁻ A A⁺
High contrast