Disciplina: 2035020 - TEORIA DA COMPUTAÇÃO
Horas Aula: 3
Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE
Plano de Ensino
Voltar
Ementa
Teoria de autômatos e linguagens formais, maquinas de Turing e teoria das funções recursivas, decidibilidade, noções de computabilidade e classes de complexidade básicas, hierarquia de Chomsky.
Conteúdo
1.Teoria de autômatos e linguagens formais.
2.Maquinas de Turing e teoria das funções recursivas.
3.Decidibilidade, noções de computabilidade.
4.Classes de complexidade básicas, hierarquia de Chomsky.
Bibliografia
ATALLAH, M.J. Algorithms and Theory of Computation Handbook. London: CRC Press, 1999.
BLUM, L.; CUCKER, F.; SHUB, M.; SMALE, S. Complexity and Real Computation. New York: Springer, 1998.
GAREY, M.R.; JONHSON, D.S. Computers and Intractability: a guide to the theory of NP-Completeness. New York: W. H. Freeman and Company,1997.
JONES, N.D. Computability and Complexity. London: MIT Press, 1997.
LEWIS, H.R; PAPPADIMITRIOU, C.H. Elementos de Teoria da Computação. Porto Alegre: Bookman, 2000.
HOPCROFT, J.E.; MOTWANI, R.; ULLMAN, J.D. Introduction to Automata Theory, Languages and Computation, 3rd ed., Addison-Wesley, 2006.
Bibliografia(continuação)
Não informado
Bibliografia complementar
Não informado
