Código: CPTA011
Ementa: Estudo das linguagens formais da Hierarquia
de Chomsky. Estudo dos formalismos matemáticos geradores, e/ou
denotacionais, e reconhecedores de cada uma destas linguagens.
Desenvolvimento da noção de computabilidade e decibilidade, e os
problemas envolvidos, para o desenvolvimento de métodos de redução de
problemas. Apresentação da Tese de Church e do Teorema da Incompletude
de Gödel. Desenvolvimento dos conceitos sobre as classes de problemas P,
NP, NP-Completo e NP-Difícil.
Bibliografia: Bibliografia básica: HOPCROFT, J. et al.. Introdução à Teoria de Autômatos, Linguagens e Computação. Editora: Campus. 2002. LEWIS, H. R., PAPADIMITRIOU, C. H.. Elementos da Teoria da Computação. Editora: Bookman. 2a edição. 2004. MENEZES, P. F. B.. Linguagens Formais e Autômatos. UFRGS. 3a edição. Editora: Sagra Luzzatto. 2002. DIVERIO, T. A. e MENEZES, P. F. B.. Teoria da Computação: Máquinas Universais e Computabilidade. UFRGS. Editora: Sagra Luzzatto. 1999. JONES, N. D.. Computability and Complexity from a Programming Perspective. Editora: The MIT Press. 1997. Bibliografia complementar: EPSTEIN, R., CARNIELLI, W.. Computability: Computable Functions, Logic, and the Foundations of Mathematics. 2nd edition. Editora: Wadsworth, 2000. Pré-requisitos: Lógica aplicada a computação e Matemática discreta. |
Matriz Curricular >