BCC244 - Teoria da Computação - 2024-2Carga horária da disciplina: 4 horas/aula Professor(es) em 2024-2
ObjetivosAo final do curso é esperado que os alunos compreendam as definições e propriedades de modelos matemáticos de computação: linguagens, autômatos e gramáticas. Também é esperado que os alunos compreendam a noção de decidibilidade de problemas e que tenham uma noção sobre como reconhecer problemas computacionalmente decidíveis e não decidíveis.EmentaLinguagens regulares, expressões regulares, autômatos de estados finitos; linguagens e gramáticas livres de contexto, autômatos de pilha; linguagens e gramáticas sensíveis ao contexto; máquinas de Turing, tese de Church-Turing; computabilidade e decidibilidade; hierarquia de Chomsky.Conteúdo Programático- Introdução: alfabetos, strings e linguagens- Autômatos de Estados Finitos Deterministas e não Deterministas - Expressões Regulares - Minimização de Autômatos Finitos - Propriedades de Linguagens Regulares - Lema do Bombeamento para Linguagens Regulares (LRs) - Gramáticas e Linguagens Livres de Contexto (LLC) - Ambiguidade - Propriedades de LLCs - Autômatos de Pilha - Forma normal de Chomsky - Gramáticas Regulares e Gramáticas Sensíveis ao Contexto - Lema do Bombeamento para LLCs - Máquinas de Turing - Tese de Church-Turing - Problemas de Decisão - Indecidibilidade do Problema da Parada - Problemas decidíveis e não decidíveis sobre linguagens Bibliografia- VIEIRA, Newton José. Introdução aos fundamentos da computação: linguagens e máquinas. São Paulo: Thomson Pioneira, 2006.- SIPSER, Michael. Introdução à teoria da computação. São Paulo. Thomson Learning, 2007. - SUDKAMP, Thomas A. Languages and machines: an introduction to the theory of computer Science. 2 ed. Addison Wesley, 1997. Bibliografia complementar- LEWIS, Harry R.; PAPADIMITRIOU, Christos H. Elementos de teoria da computação. 2. ed. Porto Alegre: Bookman, 2000.- DAVIS, Martin. Computability and unsolvability. New York: Dover, 1982. - LEEUWEN, J. Van. Handbook theoretical computer science. Amsterdam: Elsevier Cambridge, Mass.: MIT., 1990. - EPSTEIN, Richard L.; CARNIELLI, Walter A. Computability, computable functions, logic and the foundations of mathematics. Pacif. Grove: Wadsworth, 1989. - MENDELSON, Elliott. Introduction to mathematical logic. 3. ed. Pacific Grove, CA: Wadsworth & Brooks / Cole Advanced Brooks & Software, 1987. |
Departamento de Computação | ICEB | Universidade Federal de Ouro Preto
Campus Universitário Morro do Cruzeiro | CEP 35400-000 | Ouro Preto - MG, Brasil
Telefone: +55 31 3559-1692 | decom@ufop.edu.br