Tradução sipser teoria da computação

Capítulo 0
Introdução

Vamos iniciar com uma visão geral das áreas da Teoria da Computação que apresentamos no curso. Então você terá a chance de aprender e/ou revisar alguns conceitos matemáticos necessários adiante.

1 - Autômatos, Computabilidade e Complexidade Este livro focaliza três áreas tradicionalmente centrais da Teoria da Computação: Autômatos, Computabilidade e Complexidade. Eles são ligados pela questão:
Quais as capacidades e limitações fundamentais dos computadores? Esta questão nos leva de volta à década de 30, quando lógicos matemáticos começaram a explorar o significado de computação. Os avanços na tecnologia desde aquela época aumentaram muito nossa capacidade de computar e trouxeram essa questão do domínio da Teoria da Computação para o mundo das preocupações práticas. Em cada uma dessas áreas - autômatos, computabilidade e complexidade - esta questão é interpretada de forma diferente e as respostas variam de acordo com a interpretação. Seguindo esse capítulo introdutório, exploraremos cada área numa parte separada do livro. Aqui, introduzimos essas partes em ordem inversa pois dessa forma entende-se melhor a razão do começo. Teoria da Complexidade Problemas de computador surgem em diferentes variedades; alguns são fáceis e alguns são difíceis. Por exemplo, o problema da ordenação é fácil. Imagine que seja necessário ordenar uma lista de números em ordem crescente. Mesmo um computador de pequena capacidade poderia ordenar um milhão de números rapidamente. Compare este problema a um problema de organização dos horários de aulas em uma Universidade. Imagine que você precise organizar tais horários de modo que duas aulas nunca aconteçam na mesma sala e no mesmo horário. Tal problema parece ser muito mais difícil que o anterior, relacionado à ordenação. Se houvessem centenas de aulas, encontrar o melhor horário talvez levasse séculos, mesmo com o uso de um computador de grande capacidade.
O que faz alguns problemas de