Universidade Federal do Espírito Santo

Portal do Ementário

Informações Gerais
Disciplina:
Teoria da Computação ( PINF6035 )
Unidade:
Coordenação do Programa de Pós-Graduação em Informática
Tipo:
Optativa
Período Ideal no Curso:
Sem período ideal
Nota Mínima para Aprovação:
6.00
Carga Horária:
60
Número de Créditos:
4

Objetivos

Ementa
* Indução e recursão: classes indutivas, relações, ordem, prova, correçãode programas * Alfabetos, linguagens, sistemas formais * Autômatos finitos * Expressões regulares e linguagens * Linguagens livres de contexto, gramáticas e autômatos * Máquinas de Turing, computabilidade e decidibilidade * Problemas intratáveis e classes de complexidade

Bibliografia
* J. E. Holpcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd Edition, Addison Wesley, 2000. * H. B. Curry, Foundations of Mathematical Logic, 2nd Edition, Dover Pubns, 1977.

Bibliografia Complementar
Carregando...