32
INTRODUÇÃO À COMPUTAÇÃO TEORIA DA MICHAEL SIPSER TRADUÇÃO DA

Introdução à Teoria da Computação - tradução da 2a ed. norte-americana

Embed Size (px)

DESCRIPTION

Autor: Michael Sipser

Citation preview

Esta obra apresenta a teoria da computação por meio de teoremas e pro-vas, sempre com a preocupação do autor em mostrar a intuição por trás dosresultados e em amenizar a leitura destas últimas, apresentando, para cadateorema, uma idéia da prova .

Com este livro, através da prática de resolução de problemas, os alunos,nos exercícios, revisarão definições e conceitos da área e, nos problemas, irãose deparar com atividades que exigem maior engenhosidade.

Os três últimos capítulos são novos, e esta 2ª edição incorpora as suges-tões de professores e alunos enviadas ao autor ao longo dos anos.

Contém material para mais de um semestre de curso, propiciando flexi-bilidade para escolha de tópicos a serem mais ou menos explorados.

Livro-texto para as disciplinas teoria da computação, fundamentos dacomputação e linguagens formais e autômatos nos cursos de Ciência da Com-putação, Engenharia da Computação e Matemática Computacional.

“ ”

Aplicações

INTRODUÇÃO À

COMPUTAÇÃO

TEORIA DA

MICHAEL SIPSER

INTRODUÇÃO À

COMPUTAÇÃO

TEORIA DA

MICHAEL SIPSER

MIC

HA

EL

S

IP

SE

RIN

TR

OD

ÃO

À T

EO

RIA

DA

CO

MP

UTA

ÇÃ

O

Outras Obras

Inteligência Computacional Aplicada àAdministração, Economia e Engenharia emMatlab

Introdução à Ciência da Computação

Introdução aos Fundamentos daComputação

Lógica para Computação

Modelos Clássicos de Computação

2 edição atualizadaa

®

Hime Aguiar e Oliveira Junior (coord.), AndréMachado Caldeira, Maria Augusta SoaresMachado, Reinaldo Castro Souza e RicardoTanscheit

Ricardo Daniel Fedeli, Enrico Giulio FrancoPolloni e Fernando Eduardo Peres

Newton José Vieira

Flávio Soares Corrêa da Silva, Marcelo Fingere Ana Cristina Vieira de Melo

Flávio Soares Corrêa da Silva e Ana CristinaVieira de Melo

Para suas soluções de curso e aprendizado,

visite www.cengage.com.br

TRADUÇÃO DA

TRADUÇÃO DA

Dados Internacionais de Catalogação na Publicação (CIP)(Câmara Brasileira do Livro, SP, Brasil)

Sipser, MichaelIntrodução à teoria da computação / Michael Sipser

tradução técnica Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. -- São Pau lo:Cengage Learning, 2007.

Título Original: Introduction to the theory of compu-tation.

"Tradução da segunda edição norte-americana"ISBN 978-85-221-0886-2

1. Complexidade computacional 2. Computação 3. Teo-ria da máquina I. Título.

07-2663 CDD-551.3

Índice para catálogo sistemático:

1. Teoria da computação : Matemática 511.3

Introdução à teoria da computação

Michael Sipser

Gerente Editorial: Patricia La Rosa

Editora de Desenvolvimento: Danielle Mendes Sales

Supervisor de Produção Editorial: Fábio Gonçalves

Produtora Editorial: Renata Siqueira Campos

Supervisora de Produção Gráfica: Fabiana Alencar Albuquerque

Título Original: Introduction to the Theory of Computacion – Second edition ISBN:

Copidesque: Maria Alice da Costa

Tradução Técnica: Ruy José Guerra Barretto de Queiroz

Revisão: Maria Augusta F. Medeiros Antonangelo

Revisão Técnica: Newton José Vieira

Diagramação: Newton José Vieira

Capa: Eduardo Bertolini

© Cengage Learning Edições Ltda.

Todos os direitos reservados. Nenhuma parte deste livro po-derá ser reproduzida, sejam quais forem os meios empregados, sem a permissão, por escrito, da Editora.Aos infratores aplicam-se as sanções previstas nos artigos

, , e da Lei no . , de de fevereiro de .

© Cengage Learning. Todos os direitos reservados.

ISBN- :

Cengage LearningCondomínio E-Business Park Rua Werner Siemens, – Prédio – Espaço Lapa de Baixo – CEP - – São Paulo – SP Tel.: ( ) - – Fax: ( ) -SAC: 8

Para suas soluções de curso e aprendizado, visitewww.cengage.com.br

Para informações sobre nossos produtos, entre em contato pelo telefone

Para permissão de uso de material desta obra, envie seu pedido para [email protected]

Impresso no Brasil.Printed in Brazil.1 2 3 4 5 6 11 10 09 08 07

A Ina, Rachel e Aaron

S U M A R I O

Prefacio a Primeira Edicao xiiiAo(A) aluno(a) . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiAo(A) professor(a) . . . . . . . . . . . . . . . . . . . . . . . . . xivA edicao atual . . . . . . . . . . . . . . . . . . . . . . . . . . . xvFeedback para o autor . . . . . . . . . . . . . . . . . . . . . . . . xviAgradecimentos . . . . . . . . . . . . . . . . . . . . . . . . . . xvi

Prefacio a Segunda Edicao xix

0 Introducao 10.1 Automatos, Computabilidade e Complexidade . . . . . . . . . . . 1

Teoria da complexidade . . . . . . . . . . . . . . . . . . . . . . 2Teoria da computabilidade . . . . . . . . . . . . . . . . . . . . 3Teoria dos automatos . . . . . . . . . . . . . . . . . . . . . . . 3

0.2 Nocoes e Terminologia Matematicas . . . . . . . . . . . . . . . . 3Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Sequencias e uplas . . . . . . . . . . . . . . . . . . . . . . . . . 6Funcoes e relacoes . . . . . . . . . . . . . . . . . . . . . . . . . 7Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10Cadeias e linguagens . . . . . . . . . . . . . . . . . . . . . . . . 13Logica booleana . . . . . . . . . . . . . . . . . . . . . . . . . . 14Resumo dos termos matematicos . . . . . . . . . . . . . . . . . 16

0.3 Definicoes, Teoremas e Provas . . . . . . . . . . . . . . . . . . . 17Encontrando provas . . . . . . . . . . . . . . . . . . . . . . . . 18

0.4 Tipos de Prova . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Prova por construcao . . . . . . . . . . . . . . . . . . . . . . . 21Prova por contradicao . . . . . . . . . . . . . . . . . . . . . . . 22Prova por inducao . . . . . . . . . . . . . . . . . . . . . . . . . 23

Exercıcios, Problemas e Solucoes . . . . . . . . . . . . . . . . . . . . 26

vii

viii SUMARIO

Parte Um: Automatos e Linguagens 29

1 Linguagens Regulares 311.1 Automatos Finitos . . . . . . . . . . . . . . . . . . . . . . . . . . 31

Definicao formal de um automato finito . . . . . . . . . . . . . 35Exemplos de automatos finitos . . . . . . . . . . . . . . . . . . 37Definicao formal de computacao . . . . . . . . . . . . . . . . . 40Projetando automatos finitos . . . . . . . . . . . . . . . . . . . 41As operacoes regulares . . . . . . . . . . . . . . . . . . . . . . . 44

1.2 Nao-determinismo . . . . . . . . . . . . . . . . . . . . . . . . . . 48Definicao formal de um automato finito nao-determinıstico . . 54Equivalencia de AFNs e AFDs . . . . . . . . . . . . . . . . . . 56Fecho sob as operacoes regulares . . . . . . . . . . . . . . . . . 60

1.3 Expressoes Regulares . . . . . . . . . . . . . . . . . . . . . . . . . 65Definicao formal de uma expressao regular . . . . . . . . . . . 66Equivalencia com automatos finitos . . . . . . . . . . . . . . . 68

1.4 Linguagens Nao-regulares . . . . . . . . . . . . . . . . . . . . . . 79O lema do bombeamento para linguagens regulares . . . . . . . 79

Exercıcios, Problemas e Solucoes . . . . . . . . . . . . . . . . . . . . 85

2 Linguagens Livres-do-Contexto 1032.1 Gramaticas Livres-do-Contexto . . . . . . . . . . . . . . . . . . . 104

Definicao formal de uma gramatica livre-do-contexto . . . . . 106Exemplos de gramaticas livres-do-contexto . . . . . . . . . . . 107Projetando gramaticas livres-do-contexto (GLC) . . . . . . . . 108Ambiguidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110Forma normal de Chomsky . . . . . . . . . . . . . . . . . . . . 111

2.2 Automato com Pilha . . . . . . . . . . . . . . . . . . . . . . . . . 114Definicao formal de um automato com pilha . . . . . . . . . . 115Exemplos de automatos com pilha . . . . . . . . . . . . . . . . 117Equivalencia com gramaticas livres-do-contexto . . . . . . . . . 120

2.3 Linguagens Nao-livres-do-contexto . . . . . . . . . . . . . . . . . 128O lema do bombeamento para linguagens livres-do-contexto . 128

Exercıcios, Problemas e Solucoes . . . . . . . . . . . . . . . . . . . . 133

Parte Dois: Teoria da Computabilidade 141

3 A Tese de Church-Turing 1433.1 Maquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . . . 143

Definicao formal de uma maquina de Turing . . . . . . . . . . 146Exemplos de maquinas de Turing . . . . . . . . . . . . . . . . . 149

3.2 Variantes de Maquinas de Turing . . . . . . . . . . . . . . . . . . 154Maquinas de Turing multifita . . . . . . . . . . . . . . . . . . . 155Maquinas de Turing nao-determinısticas . . . . . . . . . . . . . 157Enumeradores . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

SUMARIO ix

Equivalencia com outros modelos . . . . . . . . . . . . . . . . 1603.3 A Definicao de Algoritmo . . . . . . . . . . . . . . . . . . . . . . 161

Os problemas de Hilbert . . . . . . . . . . . . . . . . . . . . . 162Terminologia para descrever maquinas de Turing . . . . . . . . 164

Exercıcios, Problemas e Solucoes . . . . . . . . . . . . . . . . . . . . 167

4 Decidibilidade 1734.1 Linguagens Decidıveis . . . . . . . . . . . . . . . . . . . . . . . . 174

Problemas decidıveis concernentes a linguagens regulares . . . 174Problemas decidıveis concernentes a linguagens livres-do-con-

texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1784.2 O Problema da Parada . . . . . . . . . . . . . . . . . . . . . . . . 182

O metodo da diagonalizacao . . . . . . . . . . . . . . . . . . . 183O problema da parada e indecidıvel . . . . . . . . . . . . . . . 188Uma linguagem Turing-irreconhecıvel . . . . . . . . . . . . . . 191

Exercıcios, Problemas e Solucoes . . . . . . . . . . . . . . . . . . . . 192

5 Redutibilidade 1975.1 Problemas Indecidıveis da Teoria de Linguagens . . . . . . . . . . 198

Reducoes via historias de computacao . . . . . . . . . . . . . . 2035.2 Um Problema Indecidıvel Simples . . . . . . . . . . . . . . . . . 2095.3 Redutibilidade por Mapeamento . . . . . . . . . . . . . . . . . . 216

Funcoes computaveis . . . . . . . . . . . . . . . . . . . . . . . 217Definicao formal de redutibilidade por mapeamento . . . . . . 218

Exercıcios, Problemas e Solucoes . . . . . . . . . . . . . . . . . . . . 222

6 Topicos Avancados em Teoria da Computabilidade 2296.1 O Teorema da Recursao . . . . . . . . . . . . . . . . . . . . . . . 229

Auto-referencia . . . . . . . . . . . . . . . . . . . . . . . . . . 230Terminologia para o teorema da recursao . . . . . . . . . . . . 233Aplicacoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234

6.2 Decidibilidade de Teorias Logicas . . . . . . . . . . . . . . . . . . 236Uma teoria decidıvel . . . . . . . . . . . . . . . . . . . . . . . . 239Uma teoria indecidıvel . . . . . . . . . . . . . . . . . . . . . . 241

6.3 Turing-Redutibilidade . . . . . . . . . . . . . . . . . . . . . . . . 2446.4 Uma Definicao de Informacao . . . . . . . . . . . . . . . . . . . . 246

Descricoes de comprimento mınimo . . . . . . . . . . . . . . . 247Otimalidade da definicao . . . . . . . . . . . . . . . . . . . . . 250Cadeias incompressıveis e aleatoriedade . . . . . . . . . . . . . 251

Exercıcios, Problemas e Solucoes . . . . . . . . . . . . . . . . . . . . 255

Parte Tres: Teoria da Complexidade 259

7 Complexidade de Tempo 2617.1 Medindo Complexidade . . . . . . . . . . . . . . . . . . . . . . . 261

x SUMARIO

Notacao O-grande e o-pequeno . . . . . . . . . . . . . . . . . 262Analisando algoritmos . . . . . . . . . . . . . . . . . . . . . . . 265Relacionamentos de complexidade entre modelos . . . . . . . . 268

7.2 A Classe P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271Tempo polinomial . . . . . . . . . . . . . . . . . . . . . . . . . 272Exemplos de problemas em P . . . . . . . . . . . . . . . . . . . 273

7.3 A Classe NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279Exemplos de problemas em NP . . . . . . . . . . . . . . . . . . 283A questao P versus NP . . . . . . . . . . . . . . . . . . . . . . . 285

7.4 NP-completude . . . . . . . . . . . . . . . . . . . . . . . . . . . 287Redutibilidade em tempo polinomial . . . . . . . . . . . . . . . 288Definicao de NP-completude . . . . . . . . . . . . . . . . . . . 292O Teorema de Cook-Levin . . . . . . . . . . . . . . . . . . . . 293

7.5 Problemas NP-completos Adicionais . . . . . . . . . . . . . . . . 300O problema da cobertura de vertices . . . . . . . . . . . . . . . 300O problema do caminho hamiltoniano . . . . . . . . . . . . . . 302O problema da soma de subconjuntos . . . . . . . . . . . . . . 309

Exercıcios, Problemas e Solucoes . . . . . . . . . . . . . . . . . . . . 311

8 Complexidade de Espaco 3218.1 Teorema de Savitch . . . . . . . . . . . . . . . . . . . . . . . . . . 3248.2 A Classe PSPACE . . . . . . . . . . . . . . . . . . . . . . . . . . 3268.3 PSPACE-completude . . . . . . . . . . . . . . . . . . . . . . . . 328

O problema TQBF . . . . . . . . . . . . . . . . . . . . . . . . 328Estrategias vencedoras para jogos . . . . . . . . . . . . . . . . . 332Geografia generalizada . . . . . . . . . . . . . . . . . . . . . . 334

8.4 As Classes L e NL . . . . . . . . . . . . . . . . . . . . . . . . . . 3408.5 NL-completude . . . . . . . . . . . . . . . . . . . . . . . . . . . 343

Busca em grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 3458.6 NL e Igual a coNL . . . . . . . . . . . . . . . . . . . . . . . . . . 347

Exercıcios, Problemas e Solucoes . . . . . . . . . . . . . . . . . . . . 349

9 Intratabilidade 3559.1 Teoremas de Hierarquia . . . . . . . . . . . . . . . . . . . . . . . 356

Completude de espaco exponencial . . . . . . . . . . . . . . . . 3649.2 Relativizacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369

Limites do metodo da diagonalizacao . . . . . . . . . . . . . . 3719.3 Complexidade de Circuitos . . . . . . . . . . . . . . . . . . . . . 373

Exercıcios, Problemas e Solucoes . . . . . . . . . . . . . . . . . . . . 383

10 Topicos Avancados em Teoria da Complexidade 38710.1 Algoritmos de Aproximacao . . . . . . . . . . . . . . . . . . . . . 38710.2 Algoritmos Probabilısticos . . . . . . . . . . . . . . . . . . . . . . 390

A classe BPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390Primalidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393Programas ramificantes le-uma-vez . . . . . . . . . . . . . . . . 398

SUMARIO xi

10.3 Alternacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403Tempo e espaco alternante . . . . . . . . . . . . . . . . . . . . 405A hierarquia de tempo polinomial . . . . . . . . . . . . . . . . 410

10.4 Sistemas de Prova Interativa . . . . . . . . . . . . . . . . . . . . . 410Nao-isomorfismo de grafos . . . . . . . . . . . . . . . . . . . . 411Definicao do modelo . . . . . . . . . . . . . . . . . . . . . . . 412IP = PSPACE . . . . . . . . . . . . . . . . . . . . . . . . . . . 413

10.5 Computacao Paralela . . . . . . . . . . . . . . . . . . . . . . . . . 424Circuitos booleanos uniformes . . . . . . . . . . . . . . . . . . 424A classe NC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426P-completude . . . . . . . . . . . . . . . . . . . . . . . . . . . 429

10.6 Criptografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430Chaves secretas . . . . . . . . . . . . . . . . . . . . . . . . . . 430Criptossistemas de chave-publica . . . . . . . . . . . . . . . . . 432Funcoes unidirecionais . . . . . . . . . . . . . . . . . . . . . . 433Funcoes alcapao . . . . . . . . . . . . . . . . . . . . . . . . . . 435

Exercıcios, Problemas e Solucoes . . . . . . . . . . . . . . . . . . . . 437

Bibliografia Selecionada 441

Indice Remissivo 447

P R E F A C I O AP R I M E I R A E D I C A O

AO(A) ALUNO(A)

Bem-vindo(a)!

Voce esta prestes a embarcar no estudo de uma materia fascinante e importante:a teoria da computacao. Ela compreende as propriedades matematicas funda-mentais do hardware, do software e das aplicacoes de computadores. Estudandoesse tema, buscamos determinar o que pode e o que nao pode ser computado,quao rapidamente, com quanto de memoria e sobre que tipo de modelo compu-tacional. O assunto tem conexoes obvias com a pratica da engenharia e, comoem muitas ciencias, tambem tem aspectos puramente filosoficos.

Sei que muitos de voces estao ansiosos para estudar esse material, mas algunspodem nao estar aqui por sua propria escolha. Voce pode querer obter um grauem ciencia ou engenharia da computacao, e um curso em teoria e requerido –sabe-se la por que. Afinal de contas, a teoria nao e obscura, aborrecida e, piorainda, irrelevante?

Para ver que a teoria nao e nem obscura nem aborrecida, ao contrario bastantecompreensıvel e ate interessante, continue a ler. A ciencia da computacao teoricade fato tem muitas ideias grandes e fascinantes, mas tambem muitos detalhespequenos e, as vezes, tediosos que podem ser cansativos. Aprender qualquerassunto e trabalho arduo, contudo, fica mais facil e mais divertido se este fordevidamente apresentado. Meu objetivo principal ao escrever este livro e expora voce os aspectos genuinamente excitantes da teoria da computacao, sem entrar

xiii

xiv PREFACIO A PRIMEIRA EDICAO

em detalhes cansativos. E claro que a unica maneira de determinar se teoria lheinteressa e tentar aprende-la.

A teoria e relevante para a pratica. Ela prove ferramentas conceituais queos praticantes usam em engenharia da computacao. Projetar uma nova lingua-gem de programacao para uma aplicacao especializada? O que voce aprendeusobre gramaticas neste curso vem bem a calhar. Lidar com a busca por cadeiase casamento de padroes? Lembre-se de automatos finitos e expressoes regulares.Confrontado com um problema que parece requerer mais tempo de computadordo que voce pode suportar? Pense no que voce aprendeu sobre NP-completude.Varias areas de aplicacao, tais como protocolos criptograficos modernos, se sus-tentam em princıpios teoricos que voce vai aprender aqui.

A teoria tambem e relevante para voce porque ela lhe mostra um lado maissimples, e mais elegante, dos computadores, os quais normalmente consideramoscomo maquinas complicadas. Os melhores projetos e aplicacoes de computado-res sao concebidos com elegancia em mente. Um curso teorico pode elevar seusentido estetico e ajuda-lo a construir sistemas mais bonitos.

Finalmente, a teoria e boa para voce porque seu estudo expande sua mente.A tecnologia de computadores muda rapidamente. O conhecimento tecnicoespecıfico, embora util hoje, fica desatualizado em apenas uns poucos anos. Con-sidere, por outro, lado as habilidades de pensar, de exprimir-se clara e precisa-mente para resolver problemas e de saber quando voce nao resolveu um pro-blema. Essas habilidades tem valor duradouro. Estudar teoria o treina nessasareas.

Consideracoes praticas a parte, quase todo mundo que trabalha com compu-tadores tem curiosidade sobre essas criacoes impressionantes, suas capacidades esuas limitacoes. Um novo ramo da matematica cresceu nos ultimos 30 anos pararesponder a certas questoes basicas. Aqui esta uma que permanece sem solucao:se eu lhe der um numero grande, digamos, com 500 dıgitos, voce pode encontrarseus fatores (os numeros que o dividem) em uma quantidade de tempo razoavel?Mesmo usando um supercomputador, ninguem atualmente conhece como fa-zer isso para todos os casos durante o tempo de vida do universo! O problema dafatoracao esta relacionado a certos codigos secretos em criptossistemas moder-nos. Encontre um maneira rapida de fatorar e a fama sera toda sua!

AO(A) PROFESSOR(A)

Este livro pretende ser um texto para o final da graduacao ou o inıcio da pos-graduacao em teoria da computacao. Contem um tratamento do assunto conce-bido em torno de teoremas e provas. Fiz algum esforco para acomodar os alunoscom pouca experiencia previa em provar teoremas, mas penso que aqueles maisexperientes terao uma vida mais facil.

Meu objetivo principal ao apresentar o material foi torna-lo claro e interes-sante. Ao fazer isso, enfatizei a intuicao e “a visao do todo” em detrimento dealguns detalhes de nıvel mais baixo.

Por exemplo, muito embora apresente, na Introducao, o metodo de prova porinducao, juntamente com outros preliminares matematicos, ele nao desempenha

PREFACIO A PRIMEIRA EDICAO xv

um papel importante subsequentemente. Geralmente nao apresento as pro-vas por inducao usuais da correcao de varias construcoes relativas a automatos.Se apresentadas claramente, essas construcoes convencem e nao necessitam demuito argumento. Uma inducao pode confundir em vez de esclarecer porque apropria inducao e uma tecnica um tanto sofisticada que muitos achammisteriosa.Ao trabalhar-se o obvio com uma inducao, corre-se o risco de ensinar aos alunosque uma prova matematica e uma manipulacao formal em vez de ensina-los oque e e o que nao e um argumento convincente.

Um segundo exemplo ocorre nas Partes II e III, nas quais descrevo algorit-mos em prosa em vez de pseudocodigo. Nao gasto muito tempo programandomaquinas de Turing (ou quaisquer outros modelos formais). Os alunos hoje vemcom uma formacao em programacao e acham que a tese de Church-Turing eauto-evidente. Daı, nao apresento simulacoes excessivamente longas de um mo-delo por outro para estabelecer sua equivalencia.

Alem de dar uma intuicao adicional e suprimir alguns detalhes, dou o quepoderia ser chamado uma apresentacao classica do material. Muitos teoricosacharao a escolha do material, a terminologia e a ordem de apresentacao consis-tentes com as de outros livros-texto largamente utilizados. Introduzi uma ter-minologia original em apenas uns poucos lugares, quando achei a terminologia-padrao particularmente obscura ou confusa. Por exemplo, introduzo o termoredutibilidade por mapeamento em vez de redutibilidade muitos-para-um.

A pratica por meio de resolucao de problemas e essencial para aprender qual-quer assunto matematico. Neste livro, os problemas sao organizados em duascategorias principais denominadas Exercıcios e Problemas. Os Exercıcios revisamas definicoes e os conceitos. Os Problemas requerem alguma engenhosidade. Osproblemas marcados com um asterisco sao mais difıceis. Tentei tornar tanto osExercıcios quanto os Problemas desafios interessantes.

A EDICAO ATUAL

A Introducao a Teoria da Computacao apareceu primeiramente como uma edicaopreliminar em capa mole. A edicao atual difere da primeira de varias maneirassubstanciais. Os tres ultimos capıtulos sao novos: o Capıtulo 8, sobre comple-xidade de espaco; o Capıtulo 9, a respeito de intratabilidade demonstravel; e oCapıtulo 10, sobre topicos avancados em teoria da complexidade. O Capıtulo 6foi expandido para incluir varios topicos avancados em teoria da computabili-dade. Outros capıtulos foram melhorados pela inclusao de exemplos e exercıciosadicionais.

Os comentarios de instrutores e alunos que usaram a edicao preliminar foramuteis para o polimento da Introducao e dos Capıtulos 1 a 7. Obviamente, oserros que eles reportaram foram corrigidos nesta edicao.

Os Capıtulos 6 e 10 dao um apanhado de varios topicos mais avancadosem teorias da computabilidade e da complexidade. Nao se pretende que elescompreendam uma unidade coesa da maneira que os capıtulos remanescen-tes o fazem. Esses capıtulos foram incluıdos para permitir ao instrutor sele-cionar topicos opcionais que podem ser de interesse do aluno mais exigente.

xvi PREFACIO A PRIMEIRA EDICAO

Os proprios topicos variam amplamente. Alguns, como Turing-redutibilidade ealternacao, sao extensoes diretas de outros conceitos no livro. Outros, tais comoteorias logicas decidıveis e criptografia, sao breves introducoes a grandes areas.

FEEDBACK PARA O AUTOR

A Internet prove novas oportunidades para a interacao entre autores e leitores.Tenho recebido muitas mensagens eletronicas oferecendo sugestoes, elogios,crıticas e reportando erros na edicao preliminar. Continue a se corresponder!Tento responder a cada mensagem pessoalmente, quando o tempo permite. Oendereco eletronico para correspondencia relacionada a este livro esipserbook�math.mit.edu .Uma pagina na Internet que contem uma lista de erros e mantida no enderecoa seguir. Outros materiais podem ser adicionados aquela pagina para ajudar aprofessores e alunos. Diga-me o que gostaria de ver ali. O endereco ehttp://www-math.mit.edu/~sipser/book.html .AGRADECIMENTOS

Eu nao poderia ter escrito este livro sem a ajuda de muitos amigos, colegas e deminha famılia.

Quero agradecer aos professores que ajudaram a dar forma a meu ponto devista cientıfico e estilo educacional. Cinco deles se destacam. Meu orientadorde tese, Manuel Blum, a quem devo uma nota especial por sua maneira unica deinspirar os alunos atraves da clareza de pensamento, entusiasmo e cuidado. Ele eum modelo para mim e para muitos outros. Sou agradecido a Richard Karp, porme introduzir a teoria da complexidade; a John Addison, por me ensinar logica epor passar aqueles maravilhosos conjuntos de tarefas para casa; a Juris Hartma-nis, por me introduzir a teoria da computacao; e a meu pai, por me introduzir namatematica, aos computadores e na arte de ensinar.

Este livro foi desenvolvido a partir de notas de um curso que ensinei no MITdurante os ultimos 15 anos. Os alunos em minhas turmas tomaram tais notascom base em minhas aulas. Espero que eles me perdoem por nao poder citar atodos. Meus assistentes de ensino, durante anos, Avrim Blum, Thang Bui, An-drew Chou, Benny Chor, Stavros Cosmadakis, Aditi Dhagat, Wayne Goddard,Parry Husbands, Dina Kravets, Jakov Kucan, Brian O’Neill, Ioana Popescu eAlex Russell, me ajudaram a editar e a expandir essas notas e me forneceramalguns dos problemas para tarefas de casa.

Quase tres anos atras, Tom Leighton me persuadiu a escrever um livro-textosobre a teoria da computacao. Eu vinha pensando em faze-lo durante algumtempo, mas foi preciso a persuasao de Tom para fazer a teoria virar pratica. Agra-deco seus conselhos generosos sobre escrever livros e sobre muitas outras coisas.

Quero agradecer a Eric Bach, Peter Beebee, Cris Calude, Marek Chrobak,Anna Chefter, Guang-Ien Cheng, Elias Dahlhaus, Michael Fischer, Steve Fisk,

PREFACIO A PRIMEIRA EDICAO xvii

Lance Fortnow, Henry J. Friedman, Jack Fu, Seymour Ginsburg, Oded Gol-dreich, Brian Grossman, David Harel, Micha Hofri, Dung T. Huynh, NeilJones, H. Chad Lane, Kevin Lin, Michael Loui, Silvio Micali, Tadao Murata,Christos Papadimitriou, Vaughan Pratt, Daniel Rosenband, Brian Scassellati,Ashish Sharma, Nir Shavit, Alexander Shen, Ilya Shlyakhter, Matt Stallman,Perry Susskind, Y. C. Tay, Joseph Traub, Osamu Watanabe, Peter Widmayer,David Williamson, Derick Wood e Charles Yang, pelos comentarios, sugestoes,e assistencia a medida que a escrita progrediu.

As seguintes pessoas acrescentaram comentarios que melhoraram este livro:Isam M. Abdelhameed, Eric Allender, Michelle Atherton, Rolfe Blodgett, AlBriggs, Brian E. Brooks, Jonathan Buss, Jin Yi Cai, Steve Chapel, David Chow,Michael Ehrlich, Yaakov Eisenberg, Farzan Fallah, Shaun Flisakowski, HjalmtyrHafsteinsson, C. R. Hale, Maurice Herlihy, Vegard Holmedahl, Sandy Irani,Kevin Jiang, Rhys Price Jones, James M. Jowdy, David M. Martin Jr., ManriqueMata-Montero, Ryota Matsuura, Thomas Minka, Farooq Mohammed, TadaoMurata, Jason Murray, Hideo Nagahashi, Kazuo Ohta, Constantine Papageor-giou, Joseph Raj, Rick Regan, Rhonda A. Reumann, Michael Rintzler, ArnoldL. Rozenberg, Larry Roske, Max Rozenoer, Walter L. Ruzzo, Sanatan Sahgal,Leonard Schulman, Steve Seiden, Joel Seiferas, Ambuj Singh, David J. Stucki,Jayram S. Thathachar, H. Venkateswaran, Tom Whaley, Christopher Van Wyk,Kyle Young e Kyoung Hwan Yun.

Robert Sloan usou uma versao anterior do manuscrito deste livro em umaturma para a qual ele lecionou e me passou inestimaveis comentarios e ideiasde sua experiencia com o manuscrito. Mark Herschberg, Kazuo Ohta e LatanyaSweeney leram partes domanuscrito e sugerirammelhoramentos extensos. ShafiGoldwasser me ajudou com o material do Capıtulo 10.

Recebi suporte tecnico especializado de William Baxter, da Superscript, queescreveu o pacote de macros LATEX que implementa a diagramacao do livro, ede Larry Nolan, do departamento de matematica do MIT, que mantem tudofuncionando.

Foi um prazer trabalhar com o pessoal da PWS Publishing na criacao do pro-duto final. Menciono Michael Sugarman, David Dietz, Elise Kaiser, MoniqueCalello, Susan Garland e Tanja Brull, porque tive maior contato com eles, massei que muitos outros estiveram envolvidos tambem. Obrigado a Jerry Moore,pela preparacao de texto, a Diane Levy, pelo projeto da capa, e a Catherine Haw-kes, pela diagramacao do livro.

Agradeco a National Science Foundation pelo apoio fornecido sob o grantCCR-9503322.

Meu pai, Kenneth Sipser, e irma, Laura Sipser, converteram os diagramasdo livro para a forma eletronica. Minha outra irma, Karen Fisch, nos salvouem varias emergencias computacionais, e minha mae, Justine Sipser, ajudou comos conselhos maternos. Agradeco-os por contribuir sob circunstancias difıceis,incluindo prazos insanos e software recalcitrante.

xviii PREFACIO A PRIMEIRA EDICAO

Por fim, meu amor vai para minha esposa, Ina, e minha filha, Rachel. Obri-gado por terem suportado tudo.

Cambridge, Massachusetts Michael SipserOutubro de 1996

P R E F A C I O A S E G U N D AE D I C A O

A julgar pelas comunicacoes eletronicas que tenho recebido de muitos de voces,a maior deficiencia da primeira edicao e que ela nao prove solucoes para nenhumdos problemas. Portanto, aqui estao elas. Todo capıtulo agora possui uma novasecao, intitulada Solucoes Selecionadas, que da respostas a uma porcao represen-tativa dos exercıcios e problemas daquele capıtulo. Para compensar a perda dosproblemas resolvidos como desafios interessantes para tarefa de casa, adicioneitambem uma variedade de novos problemas. Os instrutores podem solicitar umManual do Instrutor que contem solucoes adicionais contatando o representantede vendas para a sua regiao designado em www. ourse. om .

Um bom numero de leitores teria apreciadomaior cobertura de certos topicos“padrao”, particularmente o Teorema de Myhill–Nerode e o Teorema de Rice.Atendi parcialmente a esses leitores desenvolvendo esses topicos nos problemasresolvidos. Nao incluı o Teorema de Myhill–Nerode no corpo principal do textoporque acredito que este curso deveria proporcionar somente uma introducao aautomatos finitos e nao uma investigacao profunda. Nomeu ponto de vista, o pa-pel de automatos finitos aqui e para os estudantes explorarem ummodelo formalsimples de computacao como um preludio para modelos mais poderosos e proverexemplos convenientes para topicos subsequentes. E claro que algumas pessoasprefeririam um tratamento mais completo, enquanto outras acham que eu deve-ria omitir toda referencia a (ou pelo menos dependencia de) automatos finitos.Nao coloquei o Teorema de Rice no corpo principal do texto porque, embora elepossa ser uma “ferramenta” util para provar indecidibilidade, alguns estudantespodem usa-lo mecanicamente sem de fato entender o que esta acontecendo. Por

xix

xx PREFACIO A SEGUNDA EDICAO

outro lado, usar reducoes para provar indecidibilidade da uma preparacao maisvaliosa para as reducoes que aparecem em teoria da complexidade.

Devo aos meus assistentes de ensino, Ilya Baran, Sergi Elizalde, Rui Fan, Jo-nathan Feldman, Venkatesan Guruswami, Prahladh Harsha, Christos Kapoutsis,Julia Khodor, Adam Klivans, Kevin Matulef, Ioana Popescu, April Rasala, SofyaRaskhodnikova e Iuliu Vasilescu que me ajudaram a desenvolver alguns dos no-vos problemas e solucoes. Ching Law, Edmond Kayi Lee e Zulfikar Ramzantambem contribuıram para as solucoes. Agradeco a Victor Shoup por aparecercom uma maneira simples de reparar a lacuna na analise do algoritmo de prima-lidade probabilıstico que aparece na primeira edicao.

Aprecio os esforcos das pessoas na Course Technology por incentivar-mee as outras partes deste projeto, especialmente Alyssa Pratt e Aimee Poi-rier. Meus agradecimentos a Gerald Eisman, Weizhen Mao, Rupak Majum-dar, Chris Umans e Christopher Wilson por suas revisoes. Devo a JerryMoore por seu excelente trabalho editorial e a Laura Segel, da ByteGraphics(lauras�bytegraphi s. om), pela elaboracao maravilhosamente precisa das fi-guras.

O volume de mensagens eletronicas recebidas tem sido mais do que eu espe-rava. Ler todas essas mensagens de muitas pessoas de varios lugares diferentestem sido absolutamente prazeroso, e tenho tentado responde-las em algum mo-mento – peco desculpas aquelas que ficaram sem respostas. Relacionei aqui aspessoas que deram sugestoes que especificamente contribuıram para esta edicao,mas agradeco a todos por sua correspondencia.

Luca Aceto, Arash Afkanpour, Rostom Aghanian, Eric Allender, KarunBakshi, Brad Ballinger, Ray Bartkus, Louis Barton, Arnold Beckmann, MihirBellare, Kevin Trent Bergeson, Matthew Berman, Rajesh Bhatt, SomenathBiswas, Lenore Blum, Mauro A. Bonatti, Paul Bondin, Nicholas Bone, IanBratt, Gene Browder, Doug Burke, Sam Buss, Vladimir Bychkovsky, Bruce Car-neal, Soma Chaudhuri, Rong-Jaye Chen, Samir Chopra, Benny Chor, JohnClausen, Allison Coates, Anne Condon, Jeffrey Considine, John J. Crashell,Claude Crepeau, Shaun Cutts, Susheel M. Daswani, Geoff Davis, Scott Dex-ter, Peter Drake, Jeff Edmonds, Yaakov Eisenberg, Kurtcebe Eroglu, GeorgEssl, Alexander T. Fader, Farzan Fallah, Faith Fich, Joseph E. Fitzgerald, PerryFizzano, David Ford, Jeannie Fromer, Kevin Fu, Atsushi Fujioka, Michel Gal-ley, K. Ganesan, Simson Garfinkel, Travis Gebhardt, Peymann Gohari, GaneshGopalakrishnan, Steven Greenberg, Larry Griffith, Jerry Grossman, Rudolf deHaan, Michael Halper, Nick Harvey, Mack Hendricks, Laurie Hiyakumoto,Steve Hockema, Michael Hoehle, Shahadat Hossain, Dave Isecke, Ghaith Issa,Raj D. Iyer, Christian Jacobi, Thomas Janzen, Mike D. Jones, Max Kanovitch,Aaron Kaufman, Roger Khazan, Sarfraz Khurshid, Kevin Killourhy, SeungjooKim, Victor Kuncak, Kanata Kuroda, Suk Y. Lee, Edward D. Legenski, Li-WeiLehman, Kong Lei, Zsolt Lengvarszky, Jeffrey Levetin, Baekjun Lim, Karen Li-vescu, Thomas Lasko, Stephen Louie, TzerHung Low, Wolfgang Maass, ArashMadani, Michael Manapat, Wojciech Marchewka, David M. Martin Jr., AndersMartinson, Lyle McGeoch, Alberto Medina, Kurt Mehlhorn, Nihar Mehta, Al-bert R. Meyer, Thomas Minka, Mariya Minkova, Daichi Mizuguchi, G. Allen

PREFACIO A SEGUNDA EDICAO xxi

Morris III, Damon Mosk-Aoyama, Xiaolong Mou, Paul Muir, German Muller,Donald Nelson, Gabriel Nivasch, Mary Obelnicki, Kazuo Ohta, Thomas M.Oleson, Jr., Curtis Oliver, Owen Ozier, Rene Peralta, Alexander Perlis, HolgerPetersen, Detlef Plump, Robert Prince, David Pritchard, Bina Reed, NicholasRiley, Ronald Rivest, Robert Robinson, Christi Rockwell, Phil Rogaway, MaxRozenoer, John Rupf, Teodor Rus, Larry Ruzzo, Brian Sanders, Cem Say, KimSchioett, Joel Seiferas, Joao Carlos Setubal, Geoff Lee Seyon, Mark Skandera,Bob Sloan, Geoff Smith, Marc L. Smith, Stephen Smith, Alex C. Snoeren, GuySt-Denis, Larry Stockmeyer, Radu Stoleru, David Stucki, Hisham M. Sueyllam,Kenneth Tam, Elizabeth Thompson, Michel Toulouse, Eric Tria, ChittaranjanTripathy, Dan Trubow, Hiroki Ueda, Giora Unger, Kurt L. Van Etten, JesirVargas, Bienvenido Velez-Rivera, Kobus Vos, Alex Vrenios, Sven Waibel, MarcWaldman, Tom Whaley, Anthony Widjaja, Sean Williams, Joseph N. Wilson,Chris Van Wyk, Guangming Xing, Vee Voon Yee, Cheng Yongxi, Neal Young,Timothy Yuen, Kyle Yung, Jinghua Zhang, Lilla Zollei.

Mais do que tudo, agradeco a minha famılia – Ina, Rachel e Aaron – por suapaciencia, compreensao e amor enquanto eu me sentava por horas a fio em frentea tela do meu computador.

Cambridge, Massachusetts Michael SipserDezembro de 2004

0

I N T R O D U C A O

Vamos comecar com uma visao geral daquelas areas da teoria da computacaoque apresentamos neste curso. Em seguida, voce tera chance de aprender e/ourevisar alguns conceitos matematicos que vai precisar adiante.

0.1

AUTOMATOS, COMPUTABILIDADE ECOMPLEXIDADE

Este livro enfoca tres areas tradicionalmente centrais da teoria da computacao:automatos, computabilidade e complexidade. Elas sao interligadas pela questao:

Quais sao as capacidades e limitacoes fundamentais dos computadores?

Essa questao nos leva a decada de 1930, quando logicos matematicos comecarama explorar em primeira mao o significado de computacao. Os avancos tec-nologicos desde aqueles tempos tem aumentado enormemente nossa capacidadede computar e tem trazido essa questao do domınio da teoria para o mundo dointeresse pratico.

Em cada uma das tres areas — automatos, computabilidade e complexidade— essa questao e interpretada diferentemente e as respostas variam conforme a

1

2 Capıtulo 0 / Introducao

interpretacao. Apos este capıtulo introdutorio, exploraremos cada area em umaparte separada deste livro. Aqui, introduzimos essas partes em ordem reversaporque comecando do final voce pode entender melhor a razao para o inıcio.

TEORIA DA COMPLEXIDADE

Os problemas computacionais vem em diferentes variedades: alguns sao faceise outros, difıceis. Por exemplo, o problema da ordenacao e facil. Digamosque voce precise arranjar uma lista de numeros em ordem ascendente. Mesmoum pequeno computador pode ordenar um milhao de numeros rapidamente.Compare isso a um problema de escalonamento. Digamos que voce tenha deencontrar um escalonamento de aulas para a universidade inteira que satisfacaalgumas restricoes razoaveis, como duas aulas nao podem ter lugar na mesmasala ao mesmo tempo. O problema do escalonamento parece ser muito maisdifıcil que o problema da ordenacao. Se voce tem somente mil aulas, encontraro melhor escalonamento pode requerer seculos, ate mesmo com um supercom-putador.

O que faz alguns problemas computacionalmente difıceis e outros faceis?

Essa e a questao central da teoria da complexidade. Notavelmente, nao sabemosa resposta para essa questao, embora ela tenha sido intensamente pesquisada du-rante os ultimos 35 anos. Adiante, exploramos essa fascinante questao e algumasde suas ramificacoes.

Em uma das importantes conquistas da teoria da complexidade ate agora, ospesquisadores descobriram um elegante esquema para classificar os problemasconforme sua dificuldade computacional. Ele e analogo a tabela periodica paraclassificar elementos segundo suas propriedades quımicas. Usando esse esquema,podemos demonstrar ummetodo para dar evidencia de que certos problemas saocomputacionalmente difıceis, ainda que sejamos incapazes de provar que eleso sao.

Voce tem varias opcoes quando se depara com um problema que parece sercomputacionalmente difıcil. Primeiro, entendendo qual aspecto do problema ea raiz da dificuldade, voce pode ser capaz de altera-lo de modo que o problemaseja mais facilmente soluvel. Segundo, pode ser capaz de se contentar com umasolucao menos do que perfeita para o problema. Em certos casos, encontrarsolucoes que apenas aproximam a solucao perfeita e relativamente facil. Ter-ceiro, alguns problemas sao difıceis somente na situacao do pior caso, porem, saofaceis na maioria das vezes. Dependendo da aplicacao, voce pode ficar satisfeitocom um procedimento que, ocasionalmente, e lento, mas, em geral, roda rapida-mente. Finalmente, voce pode considerar tipos alternativos de computacao, taiscomo computacao aleatorizada, que podem acelerar certas tarefas.

Uma area aplicada que tem sido afetada diretamente pela teoria da comple-xidade e o velho campo da criptografia. Na maioria das areas, um problemacomputacional facil e preferıvel a um difıcil, porque os faceis sao mais baratos deresolver. A criptografia e incomum pois requer especificamente problemas com-putacionais que sejam difıceis, em vez de faceis, visto que os codigos secretos tem

0.2 NOCOES E TERMINOLOGIA MATEMATICAS 3

de ser difıceis de quebrar sem a chave secreta ou senha. A teoria da complexidadetem mostrado aos criptografos o caminho dos problemas computacionalmentedifıceis em torno dos quais eles tem projetado novos codigos revolucionarios.

TEORIA DA COMPUTABILIDADE

Durante a primeira metade do seculo XX, matematicos como Kurt Godel, AlanTuring e Alonzo Church descobriram que certos problemas basicos nao podemser resolvidos por computadores. Um exemplo desse fenomeno e o problema dese determinar se um enunciado matematico e verdadeiro ou falso. Essa tarefa e ofeijao-com-arroz dos matematicos. Parece uma questao natural para a resolucaopor computador, pois ela reside estritamente dentro do domınio da matematica.Mas nenhum algoritmo de computador pode realizar essa tarefa.

Entre as consequencias desse resultado profundo estava o desenvolvimentode ideias concernentes a modelos teoricos de computadores que, em algum mo-mento, ajudariam a levar a construcao de computadores reais.

As teorias da computabilidade e da complexidade estao intimamente relacio-nadas. Na teoria da complexidade, o objetivo e classificar os problemas comofaceis e difıceis, enquanto na teoria da computabilidade a classificacao dos pro-blemas e feita por meio da separacao entre os que sao soluveis e os que nao osao. A teoria da computabilidade introduz varios dos conceitos usados na teoriada complexidade.

TEORIA DOS AUTOMATOS

A teoria dos automatos lida com as definicoes e propriedades de modelos ma-tematicos de computacao. Esses modelos desempenham um papel em diversasareas aplicadas da ciencia da computacao. Um modelo, chamado automato finito,e usado em processamento de texto, compiladores e projeto de hardware. Ou-tro modelo, denominado gramatica livre-do-contexto, e utilizado em linguagensde programacao e inteligencia artificial.

A teoria dos automatos e excelente para se comecar a estudar a teoria dacomputacao. As teorias da computabilidade e da complexidade requerem umadefinicao precisa de um computador. A teoria dos automatos permite praticarcom definicoes formais de computacao, pois introduz conceitos relevantes a ou-tras areas nao-teoricas da ciencia da computacao.

0.2

NOCOES E TERMINOLOGIA MATEMATICAS

Como em qualquer assunto matematico, comecamos com uma discussao dosobjetos matematicos basicos, ferramentas e notacoes que esperamos usar.

4 Capıtulo 0 / Introducao

CONJUNTOS

Um conjunto e um grupo de objetos representado como uma unidade. Os con-juntos podem conter qualquer tipo de objeto, incluindo numeros, sımbolos e atemesmo outros conjuntos. Os objetos em um conjunto sao chamados elementosou membros. Os conjuntos podem ser descritos formalmente de varias maneiras.Uma delas e listar seus elementos dentro de chaves. Por conseguinte, o conjuntof7; 21; 57gcontem os elementos 7, 21 e 57. Os sımbolos 2 e 62 denotam pertinencia e nao-pertinencia, respectivamente. Escrevemos 7 2 f7; 21; 57g e 8 62 f7; 21; 57g. Paradois conjuntos A e B, dizemos que A e um subconjunto de B, descrito comoA � B, se todo membro de A tambem for um membro de B. Dizemos que A esubconjunto proprio de B, descrito como A ( B, se A for um subconjunto de Be nao for igual a B.

A ordem de descricao dos elementos de um conjunto nao importa, nema repeticao de seus membros. Obtemos o mesmo conjunto escrevendof57; 7; 7; 7; 21g. Se desejamos levar em consideracao o numero de ocorrenciasde membros chamamos o grupo um multiconjunto rm vez de um conjunto.Portanto f7g e f7; 7g sao diferentes como multiconjuntos, mas identicos comoconjuntos. Um conjunto infinito contem uma quantidade infinita de elementos.Nao podemos escrever uma lista de todos os elementos de um conjunto infinito;portanto, as vezes usamos a notacao “: : :” para dizer, “continue a sequencia parasempre.” Por isso, escrevemos o conjunto de numeros naturais N comof1; 2; 3; : : :g:O conjunto de inteiros Z e escritof : : : ;�2;�1; 0; 1; 2; : : :g:O conjunto com 0 membros e denominado o conjunto vazio e e descrito como ;.

Quando desejamos descrever um conjunto contendo elementos de acordocom alguma regra, escrevemos fnjregra sobre ng: Assim, fnjn = m2 para algumm 2 Ng significa o conjunto de quadrados perfeitos.

Se temos dois conjuntosA e B, a uniao de A e B, escrita A[B, e o conjuntoque obtemos combinando todos os elementos em A e B em um unico conjunto.A intersecao de A e B, escrita A \ B, e o conjunto de elementos que estao emambos, A e B. O complemento de A, descrito como A, e o conjunto de todos oselementos sob consideracao que nao estao em A.

Como e frequentemente o caso em matematica, um desenho ajuda a escla-recer um conceito. Para os conjuntos, usamos um tipo de desenho chamadodiagrama de Venn. Ele representa os conjuntos como regioes delimitadas porlinhas circulares. Seja INICIAL-t o conjunto de todas as palavras em ingles quecomecam com a letra “t.” Por exemplo, na figura a seguir o cırculo representa oconjunto INICIAL-t. Varios membros desse conjunto estao representados comopontos dentro do cırculo.

0.2 NOCOES E TERMINOLOGIA MATEMATICAS 5

rrr��

XX

INICIAL-tterrific

tundra

theory

FIGURA 0.1

Diagrama de Venn para o conjunto das palavras em ingles comecandocom a letra “t”.

De maneira semelhante, representamos o conjunto FINAL-z de palavras emingles que terminam com a letra “z” na figura a seguir.

rrr��

XX

FINAL-zquartz

jazz

razzmatazz

FIGURA 0.2

Diagrama de Venn para o conjunto das palavras em ingles terminandocom a letra “z”.

Para representar ambos os conjuntos no mesmo diagrama de Venn, temos quedesenha-los de modo que se sobreponham, indicando que eles compartilham al-guns elementos, como mostrado na Figura 0.3. Por exemplo, a palavra topaz estaem ambos os conjuntos. A figura tambem contem um cırculo para o conjuntoINICIAL-j. Ele nao se sobrepoe com o cırculo para INICIAL-t porque nenhumapalavra reside em ambos os conjuntos.

INICIAL-t FINAL-z INICIAL-j

r r

topaz jazz

FIGURA 0.3

Cırculos que se sobrepoem indicam elementos em comum.

6 Capıtulo 0 / Introducao

Os proximos dois diagramas de Venn mostram a uniao e a intersecao de con-juntos A e B.

FIGURA 0.4

Diagramas para (a) A [ B e (b) A \B.

SEQUENCIAS E UPLAS

Uma sequencia de objetos e uma lista desses objetos na mesma ordem. Ge-ralmente designamos uma sequencia escrevendo a lista entre parenteses. Porexemplo, a sequencia 7, 21, 57 seria escrita como(7; 21; 57):Em um conjunto a ordem nao importa, mas em uma sequencia sim. Daı,(7; 21; 57) nao e o mesmo que (57; 7; 21). A repeticao realmente importa emuma sequencia, mas nao em um conjunto. Portanto, (7; 7; 21; 57) e diferente deambas as outras sequencias, enquanto o conjunto f7; 21; 57g e identico ao con-junto f7; 7; 21; 57g.

Como os conjuntos, sequencias podem ser finitas ou infinitas. As sequenciasfinitas frequentemente sao chamadas uplas. Uma sequencia com k elementose uma k-upla. Dessa forma, (7; 21; 57) e uma 3-upla. Uma 2-upla e tambemchamada de par.

Conjuntos e sequencias podem aparecer como elementos de outros conjuntose sequencias. Por exemplo, o conjunto das partes de A e o conjunto de todos ossubconjuntos de A. Se A for o conjunto f0; 1g, o conjunto das partes de A e oconjunto f ;; f0g; f1g; f0; 1g g: O conjunto de todos os pares cujos elementossao 0s e 1s e f (0; 0); (0; 1); (1; 0); (1; 1) g.

Se A e B sao dois conjuntos, o produto cartesiano ou produto cruzado de Ae B, descrito como A � B; e o conjunto de todos os pares nos quais o primeiroelemento e um membro de A e o segundo e um membro de B.

EXEMPLO 0.5

Se A = f1; 2g e B = fx; y; zg,A�B = f (1; x); (1; y); (1; z); (2; x); (2; y); (2; z) g:

Esta obra apresenta a teoria da computação por meio de teoremas e pro-vas, sempre com a preocupação do autor em mostrar a intuição por trás dosresultados e em amenizar a leitura destas últimas, apresentando, para cadateorema, uma idéia da prova .

Com este livro, através da prática de resolução de problemas, os alunos,nos exercícios, revisarão definições e conceitos da área e, nos problemas, irãose deparar com atividades que exigem maior engenhosidade.

Os três últimos capítulos são novos, e esta 2ª edição incorpora as suges-tões de professores e alunos enviadas ao autor ao longo dos anos.

Contém material para mais de um semestre de curso, propiciando flexi-bilidade para escolha de tópicos a serem mais ou menos explorados.

Livro-texto para as disciplinas teoria da computação, fundamentos dacomputação e linguagens formais e autômatos nos cursos de Ciência da Com-putação, Engenharia da Computação e Matemática Computacional.

“ ”

Aplicações

INTRODUÇÃO À

COMPUTAÇÃO

TEORIA DA

MICHAEL SIPSER

INTRODUÇÃO À

COMPUTAÇÃO

TEORIA DA

MICHAEL SIPSER

MIC

HA

EL

S

IP

SE

RIN

TR

OD

ÃO

À T

EO

RIA

DA

CO

MP

UTA

ÇÃ

O

Outras Obras

Inteligência Computacional Aplicada àAdministração, Economia e Engenharia emMatlab

Introdução à Ciência da Computação

Introdução aos Fundamentos daComputação

Lógica para Computação

Modelos Clássicos de Computação

2 edição atualizadaa

®

Hime Aguiar e Oliveira Junior (coord.), AndréMachado Caldeira, Maria Augusta SoaresMachado, Reinaldo Castro Souza e RicardoTanscheit

Ricardo Daniel Fedeli, Enrico Giulio FrancoPolloni e Fernando Eduardo Peres

Newton José Vieira

Flávio Soares Corrêa da Silva, Marcelo Fingere Ana Cristina Vieira de Melo

Flávio Soares Corrêa da Silva e Ana CristinaVieira de Melo

Para suas soluções de curso e aprendizado,

visite www.cengage.com.br

TRADUÇÃO DA

TRADUÇÃO DA