Teoria da Computação
Teoria da Computação
Esta seção responde a duas perguntas que antecedem qualquer projeto de algoritmo: o que pode ser computado? e a que custo?
A primeira leva à decidibilidade e ao problema da parada; a segunda, às classes de complexidade e ao problema P versus NP. As duas têm consequências práticas diretas — saber que um problema é indecidível evita perder tempo procurando algoritmo, e saber que é NP-completo redireciona o esforço para aproximações e heurísticas.
Ordem sugerida
Autômatos finitos e linguagens formais primeiro, porque são concretos e aparecem em expressões regulares e compiladores. Depois máquinas de Turing, decidibilidade e complexidade.
Referências
- Michael Sipser (2012). Introduction to the Theory of Computation. Cengage Learning.
- John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. Pearson.
- Sanjeev Arora; Boaz Barak (2009). Computational Complexity: A Modern Approach. Cambridge University Press.