Teoria da Computação

• Carga horária: 60 horas (4 aulas semanais)
• Tipo: Eletiva
• Pré-requisito:
  • Linguagens de Programação
  • Matemática Discreta
• Professor: Alexandre Rademaker

Ementa

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.

Bibliografia

Obrigatória

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

Complementar

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