Teoria da Computação

Ementa

Autômatos Finitos, linguagens formais e gramáticas. Máquinas de Turing. A Tese de Church-Turing, turing completude e modelos físicos de computação. Computabilidade. Complexidade de Kolmogorov. Complexidade Computacional (P vs NP, NP-completude, Classes de complexidade aleatorizadas e outras classes de complexidade).

Bibliografia

1. S. Arora; and B. Barak. Computational Complexity: A Modern Approach. Princeton, 2009. 

2. C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1993. 

3. J. E. Hopcroft; R. Motwani; and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 3rd edition, 2006.

4. M. Sipser. Introduction to the Theory of Computation. Cengage Learning, 3rd edition, 2012.