计算理论导引（英文版·第3版）

图书标准信息

• 作者 [美]迈克尔西普塞（Michael Sipser）
• 出版社 机械工业出版社
• 出版时间 2018-07
• 版次 1
• ISBN 9787111602057
• 定价 89.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 458页
• 字数 300千字

【内容简介】

本书由计算理论领域的知名学者MichaelSipser所撰写。他以独特的视角，系统地介绍了计算理论的三大主要内容：自动机与语言，可计算性理论，计算复杂性理论。全书以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。本书可作为计算机专业高年级本科生和研究生的教材，也可作为研究人员的参考书。

【作者简介】

Michael Sipser　美国麻省理工学院应用数学系教授，计算机科学和人工智能实验室（CSAIL）成员。他从事理论计算机科学与其他数学课程的教学工作三十多年，目前为数学系主任。他痴迷于复杂性理论，喜欢复杂性理论的教学工作。

加作者照片

【目录】

CONTENTS

PrefacetotheFirstEdition.iv

To the student.iv

To the educatorv

The frst editionvi

Feedback to the authorvi

Acknowledgments.vii

Preface to the Second Edition.ix

Preface to the Third Edition.xi

0 Introduction.1

0.1 Automata, Computability, and Complexity.1

Complexity theory.2

Computability theory.3

Automata theory3

0.2 Mathematical Notions and Terminology3

Sets.3

Sequences and tuples.6

Functions and relations7

Graphs.10

Strings and languages.13

Boolean logic14

Summary of mathematical terms.16

0.3 Defnitions, Theorems, and Proofs.17

Finding proofs.17

0.4 Typesof Proof21

Proof by construction.21

Proof by contradiction.21

Proof by induction.22

Exercises, Problems, and Solutions.25

PartOne: AutomataandLanguages.29

1 RegularLanguages.31

1.1 Finite Automata.31

Formal defnition of afnite automaton.35

Examples of fnite automata37

Formal defnition of computation40

Designing fnite automata.41

The regular operations44

1.2 Nondeterminism.47

Formal defnition of a nondeterministic fnite automaton53

Equivalence of NFAs and DFAs.54

Closure under the regular operations.58

1.3 Regular Expressions.63

Formal defnition of a regular expression64

Equivalence with fnite automata.66

1.4 Nonregular Languages77

The pumping lemma for regular languages.77

Exercises, Problems, and Solutions.83

2 Context-Free Languages.101

2.1 Context-Free Grammars.102

Formal defnition of acontext-free grammar104

Examples of context-free grammars.105

Designing context-free grammars106

Ambiguity.107

Chomsky normal form108

2.2 Pushdown Automata.111

Formal defnition of a pushdown automaton.113

Example of pushdow automata.114

Equivalence with context-free grammars.117

2.3Non-Context-Free Languages125

The pumping lemma for context-free languages.125

2.4 Deterministic Context-Free Languages.130

Properties of DCFLs.133

Deterministic context-free grammars135

Relationship of DPDAs and DCFGs.146

Parsing and LR(k) grammars.151

Exercises, Problems, and Solutions.154

PartTwo: Computability Theory.163

3 The Church–Turing Thesis.165

3.1 Turing Machines.165

Formal defnition of a Turing machine167

Examples of Turing machines.170

3.2 Variants of Turing Machines.176

Multitape Turing machines176

Nondeterministic Turing machines178

Enumerators180

Equivalence with other models181

3.3 The Defnition of Algorithm182

Hilbert’s problems.182

Terminology for describing Turing machines184

Exercises, Problems, and Solutions.187

4 Decidability.193

4.1 Decidable Languages.194

Decidable problems concerning regular languages.194

Decidable problems concerning context-free languages.198

4.2 Undecidability201

The diagonalization method.202

An undecidable language.207

A Turing-unrecognizable language209

Exercises, Problems, and Solutions.210

5 Reducibility.215

5.1 Undecidable Problems from Language Theory216

Reductions via computation histories.220

5.2 A Simple Undecidable Problem.227

5.3 Mapping Reducibility234

Computable functions.234

Formal defnition of mapping reducibility235

Exercises, Problems, and Solutions.239

6 Advanced Topicsin Computability Theory.245

6.1 The Recursion Theorem.245

Self-reference.246

Terminology for the recursion theorem.249

Applications250

6.2 Decidability of logical theories.252

A decidable theory.255

An undecidable theory.257

6.3 Turing Reducibility260

6.4 A Defnition of Information.261

Minimal length descriptions.262

Optimality of the defnition266

Incompressible strings and randomness.267

Exercises, Problems, and Solutions.270

Part Three: Complexity Theory.273

7 Time Complexity.275

7.1 Measuring Complexity275

Big-O and small-o notation276

Analyzing algorithms.279

Complexity relationships among models.282

7.2 The Class P284

Polynomial time284

Examples of problems in P286

7.3 The Class NP.292

Examples of problemsin NP.295

The Pversus NP question297

7.4 NP-completeness.299

Polynomial time reducibility.300

Defnition of NP-completeness304

The Cook–Levin Theorem304

7.5 Additional NP-complete Problems.311

The vertex cover problem.312

The Hamilto