第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
参考文献
展开
