计算理论:双语版9787568419550

第I部分 预备知识

第1章 集合、关系、语言

1.1 集合

1.2 关系与函数

1.3 特殊类型的二元关系

1.4 有穷集合与无穷集合

1.5 三个基本原理

1.6 语言的有穷表示

习题1

第Ⅱ部分 自动机与语言

第2章 有穷自动机

2.1 确定型有穷自动机

2.2 非确定型有穷自动机

2.3 有穷自动机与正则表达式

2.4 正则语言与非正则语言

2.5 状态最小化

2.6 有穷自动机的算法

习题2

第3章 上下文无关语言

3.1 上下文无关文法（CFG）

3.2 语法分析树

3.3 下推自动机（PDA）

3.4 上下文无关文法与下推自动机

3.5 上下文无关语言与非上下文无关语言

习题3

第Ⅲ部分 可计算性理论

第4章 图灵机

4.1 图灵机（TM）定义

4.2 丘奇一图灵论题

4.3 图灵机的变形

4.4 用图灵机进行计算

4.5 算法的定义

习题4

第5章 可判定性

5.1 可判定性语言

5.2 停机问题

习题5

第6章 不可判定性

6.1 语言理论中的不可判定问题

6.2 与文法有关的不可判定问题

6.3 不可判定的铺砖问题

6.4 映射可归约性的形式定义

习题6

第Ⅳ部分 计算复杂性理论

第7章 时间复杂性

7.1 度量复杂性

7.2 P类

7.3 NP类

7.4 NP完全性

7.5 典型的NP完全问题

习题7

第8章 空间复杂度

8.1 萨维奇定理

8.2 PSPACE类

8.3 PSPACE完全性

8.4 L类和舰类

8.5 NL完全性

8.6 NL等于coNL

习题8

第V部分 算法设计与分析

第9章 分治策略

9.1 分治法的基本思想

9.2 二分搜索

9.3 矩阵乘法

9.4 合并排序

9.5 快速排序

习题9

第10章 动态规划

10.1 动态规划的基本思想

10.2 多段图最短路径问题

10.3 矩阵连乘问题

10.4 最长公共子序列问题

10.5 0／1背包问题

习题10

第11章 贪心算法

11.1 贪心算法的基本思想

11.2 单源最短路径问题

11.3 最小生成树问题

习题11

第12章 下界

12.1 平凡下界

12.2 判定树模型

12.3 代数判定树模型

12.4 线性时间归约

习题12

第13章 回溯法

13.1 回溯法的基本思想

13.2 n个皇后问题

13.3 图的m着色问题

13.4 0／1背包问题

习题13

第Ⅵ部分 系统建模与推理

第14章 基于模型的验证

14.1 形式化验证和模型检测

14.2 线性时态逻辑的语法与语义

14.3 分支时态逻辑的语法与语义

14.4 基于有穷状态机的系统验证技术

习题14

参考文献

计算理论主要包括算法学、计算复杂性理论、可计算性理论、自动机理论和形式语言理论等。本书将它们分为六大部分，并结合大量的图例、公式以及代码，带领读者由浅入深地了解计算理论，并在每一章节的最后设置相当数量的习题帮助读者巩固所学知识。除此之外，本书还包含算法分析和系统建模与推理两部分内容，将其作为计算理论知识的应用，帮助读者更好地理解和运用所学计算理论基本原理。同时，本书为双语版本，采用双语双栏的形式排版，方便读者对照阅读，从而培养读者的专业外语阅读能力。