Teoria da Computação

Objetivo Geral

Proporcionar ao aluno um conhecimento básico de Linguagens Formais; habilitar o aluno a utilizar técnicas para demonstrar que certos problemas são impossíveis de serem resolvidos por um computador e que certos problemas, mesmo sendo possíveis de serem resolvidos por uma máquina, demandam tempo e/ou espaço em memória impraticáveis.

Ementa

Estudo dos fundamentos matemáticos da computabilidade. Gramáticas. Linguagens Regulares, Livres-de-Contexto e Sensíveis-ao-Contexto. Tipos de Reconhecedores. Operações com linguagens. Propriedades das Linguagens. Autômatos de Estados Finitos Determinístico e não Determinístico. Autômatos de Pilha. Máquinas de Turing Universais. Tese de Church-Turing. Hierarquia de Chomsky. Funções Recursivas. Enumerabilidade e decidibilidade. Problemas indecidíveis. Teorema da Incompletude de Godel. Modelos abstratos de máquinas programáveis.

Bibliografia Básica

• GERSTING, J. L. Fundamentos matemáticos para ciência da computação. Rio de Janeiro: LTC, 2015. (RB=7189)
• HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J. D. Introdução à teoria de autômatos, linguagens e computação. 2 ed. Rio de Janeiro: Campus, 2002. (RB=83)
• VIEIRA, J. N. Introdução aos fundamentos da computação. São Paulo: Thomson, 2015.(RB=7158)

Bibliografia Complementar

• DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabilidade. 2 ed. Porto Alegre: Bookman, 2008.
• HARRY, R. Lewis e CHRISTOS H. Elementos de teoria da computação. 2 ed. Porto Alegre: Bookman, 2008.
• SIPSER, M. Introdução à teoria da computação. São Paulo: Thomson Pioneira, 2015. 502 p. (RB=7186)