计算理论

全书分为计算理论基础知识、算法设计与分析、系统建模与推理三部分。其中，计算理论基础知识包含了四个模块，分别是预备知识、自动机与语言、可计算性理论和计算复杂性理论，该部分又针对每一个知识模块细分了章节，由浅入深。在算法设计与分析部分，划分了五个章节，分别是分治策略、动态规划、贪心算法、下界和回溯法。在系统建模与推理中，重点划分出基于模型的验证一章，主要介绍基于有穷状态机的系统属性验证方法。本书可作为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 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 042 2 . 3 Finite automata and regular expressions 044 2 . 4 Regular language and non -regular language … … … … … … … … … 048 2 . 5 state minimization … … 052 2 . 6 Algorithmic aspects of finite automata 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) 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 097 5 . 2 Halting problem 105 Exercise 5 1 15 chapter 6 undecidability 6 . 1 undecidable problems from language theory " 118 6 . 2 undecidable problems about grammars 124 6 . 3 An undecidable tiling problem … 125 6 . 4 Formal definition of mapping reducibility 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 132 144 154 163 178 193 197 200 第 部分 可计算性理论 第 4 章 图灵机 4. 1 图灵机(TM)定义 … 073 4. 2 丘奇 图灵论题 …… … 073 4. 3 图灵机的变形 …… …… … 084 4. 4 用图灵机进行计算 …… … 092 4. 5 算法的定义 093 习题 4 095 第 5 章 可判定性 5 . 1 可判定性语言 097 5 . 2 停机问题 105 习题 5 115 第 6 章 不可判定性 6 . 1 语言理论中的不可判定问题 118 6 . 2 与文法有关的不可判定问题 124 6 . 3 不可判定的铺砖问题 125 6 . 4 映射可归约性的形式定义 127 习题 6 131 第 部分 计算复杂性理论 第 7 章 时间复杂性 7 . 1 度量复杂性 132 7 . 2 P 类 144 7 . 3 NP 类 154 7. 4 NP 完全性 163 7. 5 典型的 NP 完全问题 178 习题 7 193 第 8 章 空间复杂度 8 . 1 萨维奇定理 196 8 . 2 PSPACE 类 197 8. 3 PSPACE 完全性 199 8. 4 L 类和 NL 类 200 002 目录 contents 8 . 5 NL-completeness 202 8 . 6 NL equals CONL 204 Exercise 8 207 part V Algorithm Design and Analysis chapter 9 Divide and conquer strategy 9 . 1 Basic idea of divide and conquer 209 9 . 2 Binary search 212 9 . 3 Matrix multiplication 215 9 . 4 Merge sort 218 9 . 5 Quick sort 222 Exercise 9 229 chapter 10 Dynamic programming 10 . 1 Basic idea of dynamic programming … … 231 10 . 2 The shortest path problem of multi-seg- ment graphs 233 10 . 3 Multiplication problem of matrix chain 238 10 . 4 The longest common subsequence problem 243 10 . 5 0/1 knapsack problem 247 Exercise 10 252 chapter 11 Greedy Algorithm 11 . 1 Basic idea of greedy algorithm … … 254 11 . 2 The single-source shortest path problem … … 258 11 . 3 The minimum spanning tree problem … … 265 Exercise 1 1 281 chapter 12 Lower Bounds 12 . 1 Trivial lower bounds 283 12 . 2 Decision tree model 284 12 . 3 Algebraic decision tree model 289 12 . 4 Linear time reductions 291 8. 5 NL 完全性 202 8 . 6 NL 等于 CONL 204 习题 8 207 第V部分 算法设计与分析 第 9 章 分治策略 9 . 1 分治法的基本思想 209 9 . 2 二分搜索 212 9 . 3 矩阵乘法 215 9 . 4 合并排序 218 9 . 5 快速排序 222 习题 9 229 第 10 章 动态规划 10 . 1 动态规划的基本思想 231 10 . 2 多段图最短路径问题 233 10 . 3 矩阵连乘问题 238 10 . 4 最长公共子序列问题 243 10 . 5 0/1 背包问题 247 习题 10 252 第 11 章 贪心算法 11 . 1 贪心算法的基本思想 254 11 . 2 单源最短路径问题 258 11 . 3 最小生成树问题 266 习题 11 281 第 12 章 下界 12. 1 平凡下界 283 12. 2 判定树模型 284 12. 3 代数判定树模型 289 12. 4 线性时间归约 291 003 计算理论 Theory of computation Exercise 12 … … … … …… … … … … 296 习题 12 … … … … … … … … … … … … … 296 chapter 13 Backtracking Method 13 . 1 Basic idea of backtracking method 297 13 . 2 n-queens problem 300 13 . 3 m-coloring problem of graphs 302 13 . 4 0/1 knapsack problem 304 Exercise 13 309 part V Modelling and Reasoning about systems chapter 14 Model-based verification 14 . 1 Formal verification and model checking 310 14 . 2 syntax and semantics of linear temporal logic 316 14 . 3 syntax and semantics of computation tree logic 320 14 . 4 system verification technologies based on FSM 327 Exercise 14 345 References 348 第 13 章 回溯法 13 . 1 回溯法的基本思想 297 13 . 2 n 个皇后问题 300 13. 3 图的 m 着色问题 302 13 . 4 0/1 背包问题 304 习题 13 309 第V部分 系统建模与推理 第 14 章 基于模型的验证 14. 1 形式化验证和模型检测 310 14. 2 线性时态逻辑的语法与语义 316 14. 3 分支时态逻辑的语法与语义 320 14. 4 基于有穷状态机的系统验证技术 327 习题 14 345 参考文献 348 004