全书分为计算理论基础知识、算法设计与分析、系统建模与推理三部分。其中，计算理论基础知识包含了四个模块，分别是预备知识、自动机与语言、可计算性理论和计算复杂性理论，该部分又针对每一个知识模块细分了章节，由浅入深。在算法设计与分析部分，划分了五个章节，分别是分治策略、动态规划、贪心算法、下界和回溯法。在系统建模与推理中，重点划分出基于模型的验证一章，主要介绍基于有穷状态机的系统属性验证方法。本书可作为1～2个学期的计算理论导论课程教材，适用于数学、计算机科学、信息安全、物联网工程等各个专业的本科生、研究生（含留学生）学习。

contents


I Preliminary knowledge
chapter 1 sets , Relations , and Languages 1 . 1 sets … 001
1 . 2 Relations and functions … … … … 005
1 . 3 special types of binary relations

1 . 4 Finite and infinite sets … … … … 016
1 . 5 Three fundamental principle … … 019 1 . 6 Finite representations of languages
\t 025
Exercise 1 … … 032 part I Automata and Languages
chapter 2 Finite Automata
2 . 1 Deterministic finite automata 037 2 . 2 Non-deterministic finite automata
\t 042
2 . 3 Finite automata and regular expressions
\t 044
2 . 4 Regular language and non -regular
language … … … … … … … … … 048
2 . 5 state minimization … … 052 2 . 6 Algorithmic aspects of finite automata
\t 054
Exercise 2 … … 058 chapter 3 context-Free Languages
3 . 1 context-free grammar(CFG) … … 061 3 . 2 parse trees 062
3 . 3 pushdown automata(PDA) … … … … 067
3 . 4 context-free grammar and pushdown
automata … … 068 3 . 5 context-free and non -context-free
languages … … … …… … … … 069
Exercise 3 … … … … … … … … … … 072


目 录

第 I 部分 预备知识
第 1 章 集合、关系 语言
1 . 1 集合 … 0o1
1 . 2 关系与函数 … … …… … 005
1 . 3 特殊类型的二元关系 … … … … 010

1 . 4 有穷集合与无穷集合 … … 016
1 . 5 三个基本原理 …… … … … 019
1 . 6 语言的有穷表示 …… … 025

习题 1 … … … … … … … … … … … … 032
第 I 部分 自动机与语言
第 2 章 有穷自动机
2. 1 确定型有穷自动机 … … … 037
2. 2 非确定型有穷自动机 … … … 042

2. 3 有穷自动机与正则表达式 … 044

2. 4 正则语言与非正则语言 … … 048

2. 5 状态最小化 …… … … … … 052
2. 6 有穷自动机的算法 …… … 054

习题 2 … … … … … … …… … … 058
第 3 章 上下文无关语言
3 . 1 上下文无关文法(CFG) … 061
3 . 2 语法分析树 …… …… … 062
3 . 3 下推自动机(PDA) … … 067 3 . 4 上下文无关文法与下推自动机 … 068
3 . 5 上下文无关语言与非上下文无关语言

习题 3 … … … … … …… … … … … … … 072





计算理论
Theory of computation



part Theory of computability
chapter 4 Turing Machine
4 . 1 Definition of Turing machine(TM)
\t 073
4 . 2 church-Turing thesis … … … … … 073
4 . 3 variants of Turing machine …… 084 4 . 4 compulting with Tulring machine … 092
4 . 5 Definition of algorithm … … … … … 093
Exercise 4 095 chapter 5 Decidability
5 . 1 Decidable languages \t 097
5 . 2 Halting problem \t 105
Exercise 5 1 15
chapter 6 undecidability
6 . 1 undecidable problems from language
theory " \t 118
6 . 2 undecidable problems about grammars
\t 124
6 . 3 An undecidable tiling problem … 125 6 . 4 Formal definition of mapping reducibility
\t 127
Exercise 6 131
part V Theory of computational complexity

chapter 7 Time complexity
7 . 1 Measulring complexity … … … … …
7 . 2 class P … …
7 . 3 class NP … … … … …
7 . 4 NP-completeness … … … … …
7 . 5 Typical NP-complete problems …
Exercise 7
chapter 8 space complexity
8 . 1 savitch's theorem … … 8 . 2 class PSPACE … …
8 . 3 PSPACE-completeness … …
8 . 4 class L and NL \t
132 144 154 163 178 193


197

200



第 部分 可计算性理论
第 4 章 图灵机
4. 1 图灵机(TM)定义 … 073

4. 2 丘奇 图灵论题 …… … 073
4. 3 图灵机的变形 …… …… … 084
4. 4 用图灵机进行计算 …… … 092
4. 5 算法的定义 \t 093
习题 4 \t 095
第 5 章 可判定性
5 . 1 可判定性语言 \t 097
5 . 2 停机问题 \t 105
习题 5 \t 115
第 6 章 不可判定性
6 . 1 语言理论中的不可判定问题 \t 118

6 . 2 与文法有关的不可判定问题 \t 124

6 . 3 不可判定的铺砖问题 \t 125
6 . 4 映射可归约性的形式定义 \t 127

习题 6 \t 131

第 部分 计算复杂性理论

第 7 章 时间复杂性
7 . 1 度量复杂性 \t 132
7 . 2 P 类 \t 144
7 . 3 NP 类 \t 154
7. 4 NP 接近性 \t 163
7. 5 典型的 NP 接近问题 \t 178
习题 7 \t 193
第 8 章 空间复杂度
8 . 1 萨维奇定理 \t 196
8 . 2 PSPACE 类 \t 197
8. 3 PSPACE 接近性 \t 199
8. 4 L 类和 NL 类 \t 200



002

目录
contents



8 . 5 NL-completeness \t 202
8 . 6 NL equals CONL \t 204
Exercise 8 \t 207

part V Algorithm Design and Analysis
chapter 9 Divide and conquer strategy 9 . 1 Basic idea of divide and conquer
\t 209
9 . 2 Binary search \t 212
9 . 3 Matrix multiplication \t 215
9 . 4 Merge sort \t 218
9 . 5 Quick sort \t 222
Exercise 9 229 chapter 10 Dynamic programming
10 . 1 Basic idea of dynamic programming
\t … … 231
10 . 2 The shortest path problem of multi-seg-
ment graphs \t 233
10 . 3 Multiplication problem of matrix chain
\t 238
10 . 4 The longest common subsequence
problem \t 243
10 . 5 0/1 knapsack problem \t 247
Exercise 10 \t 252
chapter 11 Greedy Algorithm
11 . 1 Basic idea of greedy algorithm
\t … … 254
11 . 2 The single-source shortest path problem
\t … … 258
11 . 3 The minimum spanning tree problem
\t … … 265
Exercise 1 1 \t 281
chapter 12 Lower Bounds
12 . 1 Trivial lower bounds 283
12 . 2 Decision tree model \t 284
12 . 3 Algebraic decision tree model
\t 289
12 . 4 Linear time reductions 291


8. 5 NL 接近性 \t 202
8 . 6 NL 等于 CONL \t 204
习题 8 \t 207
第V部分 算法设计与分析
第 9 章 分治策略
9 . 1 分治法的基本思想 \t 209

9 . 2 二分搜索 \t 212
9 . 3 矩阵乘法 \t 215
9 . 4 合并排序 \t 218
9 . 5 快速排序 \t 222
习题 9 \t 229
第 10 章 动态规划
10 . 1 动态规划的基本思想 \t 231

10 . 2 多段图最短路径问题 \t 233

10 . 3 矩阵连乘问题 \t 238

10 . 4 最长公共子序列问题 \t 243

10 . 5 0/1 背包问题 \t 247
习题 10 \t 252
第 11 章 贪心算法
11 . 1 贪心算法的基本思想 \t 254

11 . 2 单源最短路径问题 \t 258

11 . 3 最小生成树问题 \t 266

习题 11 \t 281
第 12 章 下界
12. 1 平凡下界 \t 283
12. 2 判定树模型 \t 284
12. 3 代数判定树模型 \t 289

12. 4 线性时间归约 \t 291



003

计算理论
Theory of computation

Exercise 12 … … … … …… … … … … 296 习题 12 … … … … … … … … … … … … … 296


chapter 13 Backtracking Method
13 . 1 Basic idea of backtracking method
\t 297
13 . 2 n-queens problem \t 300
13 . 3 m-coloring problem of graphs
\t 302
13 . 4 0/1 knapsack problem \t 304
Exercise 13 \t 309
part V Modelling and Reasoning about systems
chapter 14 Model-based verification
14 . 1 Formal verification and model checking
\t 310
14 . 2 syntax and semantics of linear
temporal logic \t 316
14 . 3 syntax and semantics of computation
tree logic \t 320
14 . 4 system verification technologies based
on FSM \t 327
Exercise 14 \t 345

References \t 348


第 13 章 回溯法
13 . 1 回溯法的基本思想 \t 297

13 . 2 n 个皇后问题 \t 300
13. 3 图的 m 着色问题 \t 302

13 . 4 0/1 背包问题 \t 304
习题 13 \t 309

第V部分 系统建模与推理

第 14 章 基于模型的验证
14. 1 形式化验证和模型检测 \t 310

14. 2 线性时态逻辑的语法与语义 \t 316

14. 3 分支时态逻辑的语法与语义 \t 320

14. 4 基于有穷状态机的系统验证技术
\t 327
习题 14 \t 345

参考文献 \t 348





















004