Portal do Ementário

A disciplina Computabilidade e Complexidade visa dotar os acadêmicos de conhecimentos sobre os principais modelos computacionais utilizados na teoria da computabilidade e dos limites práticos da computação através da teoria da complexidade. Ao final do curso, os acadêmicos deverão ser capazes de trabalhar com modelos computacionais como autômatos e máquinas de Turing (utilizadas na teoria da computabilidade); conhecer e entender os principais conceitos sobre linguagens e gramáticas; realizar a análise de complexidade estrutural de algoritmos, bem como reconhecer os limites fundamentais dos computadores através das teorias da computabilidade e complexidade.

Máquinas de Turing. Hierarquia de Chomsky. Decidibilidade. Computabilidade. Complexidade. Tratabilidade (Algoritmos P e NP).

[1] Hopcroft, J. E.; Motwani, R.; Ullman, J. D.; Introdução à teoria de autômatos: linguagens e computação. 2ed, Ed. Campus, 2002. ISBN: 8535210725. [2] Sipser, M.; Introdução à Teoria da Computação. Ed. Thomson, 2007. ISBN: 9878522104994. [3] Ziviani, N.; Projetos de Algoritmos: com Implementações em Pascal e C. 2ed, Ed. Pioneira Thomson Learning, 2004. ISBN: 8522103909.

[1] Vieira, N. J.; Introdução aos Fundamentos da Computação: Linguagens e Máquinas. Ed. Thomson, 2006. ISBN: 8522105081. [2] Lewis, H. R.; Papadimitriou, C.; Elementos de Teoria da computação. 2ed, Ed. Bookman, 2000. ISBN: 8573075341. [3] Rich, E. A.; Automata, Computability and Complexity: Theory and Applications. 1ed, Ed. Prentice Hall, 2007. ISBN: 9780132288064.