Introduão a tec

Uma Introducao a Teoria da Computacao ¸˜ ` ¸˜ (Vers˜ o Parcial: 11 de fevereiro de 2005) a Favor n˜ o distribuir a
Michael Sipser Traduzido do original em inglˆ s e Introduction to the Theory of Computation (PWS Publishing Company c 1997) por Ruy J. Guerra B. de Queiroz

´ Indice
Pref´ cio a ` Ao(A) estudante . . . . . . ` Ao(A) educador(a) . . . . A presente edicao . . . . . ¸˜ Realimentacao para o autor ¸˜ Agradecimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v v vi vii vii vii 1 1 1 2 3 3 3 5 6 8 10 11 12 13 13 16 16 17 18 20

0 Introducao ¸˜ 0.1 Autˆ matos, computabilidade, e complexidade . . . . . . . . . . . . o Teoria da complexidade . . . . . . . . . . . . . . . . . . . Teoria da computabilidade . . . . . . . . . . . . . . . . . Teoria dos autˆ matos . . . . . . . . . . . . . . . . . . . . o 0.2 Nocoes matem´ ticas e terminologia . . . . . . . . . . . . . . . . . . ¸˜ a Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . Seq¨ encias e uplas . . . . . . . . . . . . . . . . . . . . . uˆ Funcoes e relacoes . . . . . . . . . . . . . . . . . . . . . ¸˜ ¸˜ Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cadeias e linguagens . . . . . . . . . . . . . . . . . . . . L´ gica booleana . . . . . . . . . . . . . . . . . . . . . . . o Resumo de termos matem´ ticos . . . . . . . . . . . . . . a 0.3 Definicoes, teoremas, e provas . . . . . . . . . . . . . . . . . . . . . . . ¸˜ Encontrando provas . . . . . . . . . . . . . . . . . . . . . 0.4 Tipos de prova . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Provas por construcao . . . . . . . . . . . . . . . . . . . . ¸˜ Prova por contradicao . . . . . . . . . . . . . . . . . . . . ¸˜ Prova por inducao . . . . . . . . . . . . . . . . . . . . . . ¸˜ Exerc´cios e Problemas . .