Portal do Ementário

Desenvolver a capacidade de raciocínio abstrato. Assimilar os principais conceitos e resultados de matemática discreta e utilizá-los como ferramenta para aplicações em computação. Entender o ferramental teórico que descreve os mecanismos de computação do ponto de vista matemático. Compreender os limites da computação algorítmica e suas implicações práticas. Entender os fundamentos da análise de complexidade de problemas clássicos.

Fundamentos de matemática discreta. Alfabetos, strings e linguagens. Hierarquia de Chomsky: linguagens, gramáticas geradoras e máquinas reconhecedoras. Linguagens regulares e autômatos finitos. Linguagens recursivas e máquinas de Turing. Tese de Chuch-Turing. Decidibilidade. Teoria de complexidade: classes de problemas P, NP, NP-Complete e P-Space. Redução de problemas e complexidade.

LEWIS, H.R.; PAPADIMITRIOU, C.H., Elementos de teoria da computação, 2a. edição, Editora Bookman, 2000. DIVERIO, T.A.; MENEZES, P.B., Teoria da computação: máquinas universais e computabilidade, 2a. edição, Editora Sagra, 2000. HOPCROFT, J.E.; MOTWANI, R.; ULLMAN, J.D., Introdução à teoria de autômatos, linguagens e computação, 1a. edição, Editora Campus, 2003.

SUDKAMP, T.A., Languages and Machines, 2a. edição, Editora Addison-Wesley, 1997. SIPSER, M., Introdução à teoria da computação, 1a. edição, Editora Thompson, 2007. GAREY, M.R.; JOHNSON, D.S., Computers and intractability: a guide to the theory of NP-completeness, 1a. edição, Editora Freeman, 1979. ARORA, S.; BARAK, B., Computational complexity: a modern approach, 1a. edição, Editora Cambridge, 2009. GERSTING, J.L., Fundamentos matemáticos para a ciência da computação: um tratamento moderno de matemática discreta, 5a. edição, Editora LTC, 2004.