Teoria da Computação

Código: PINF6035
Curso: Mestrado em Informática
Créditos: 4
Carga horária: 60
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.