Livro Teoria da Computa

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

´
Indice
Pref´acio
` estudante . . . . . .
Ao(A)
` educador(a) . . . .
Ao(A)
A presente edic¸a˜ o . . . . .
Realimentac¸a˜ o para o autor
Agradecimentos . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

0 Introduc¸a˜ o
0.1 Autˆomatos, computabilidade, e complexidade . . . . . . . . . . . .
Teoria da complexidade . . . . . . . . . . . . . . . . . . .
Teoria da computabilidade . . . . . . . . . . . . . . . . .
Teoria dos autˆomatos . . . . . . . . . . . . . . . . . . . .
0.2 Noc¸o˜ es matem´aticas e terminologia . . . . . . . . . . . . . . . . . .
Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . .
Seq¨ueˆ ncias e uplas . . . . . . . . . . . . . . . . . . . . .
Func¸o˜ es e relac¸o˜ es . . . . . . . . . . . . . . . . . . . . .
Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Cadeias e linguagens . . . . . . . . . . . . . . . . . . . .
L´ogica booleana . . . . . . . . . . . . . . . . . . . . . . .
Resumo de termos matem´aticos . . . . . . . . . . . . . .
0.3 Definic¸o˜ es, teoremas, e provas . . . . . . . . . . . . . . . . . . . . . . .
Encontrando provas . . . . . . . . . . . . . . . . . . . . .
0.4 Tipos de prova . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Provas por construc¸a˜ o . . . . . . . . . . . . . . . . . . . .
Prova por contradic¸a˜ o . . . . . . . . . . . . . . . . . . . .
Prova por induc¸a˜ o . . . . . . . . . . . . . . . . . . . . . .
Exerc´ıcios e Problemas . . . . . . . . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.