计算复杂性与算法分析PDF电子书下载

第1章 有限自动机 1

1.1有限自动机与计算机 1

1.1.1计算机的发展 1

1.1.2有限自动机与计算机的关系 1

1.1.3物理机器与自动机 2

1.1.4机器与语言的关系 3

1.1.5语言与文法的关系 4

1.1.6计算机的极限 4

1.2有限自动机的定义 5

1.2.1有限自动机的分类 5

1.2.2有限接受机的定义 5

1.2.3字母表（Alphabet） 6

1.2.4有限自动机对输入字符串的动作 7

1.2.5确定型自动机的构造方法 8

1.3非确定型有限自动机NFA（Nondeterministic Finite Automation） 11

1.3.1非确定型有限自动机的定义 11

1.3.2非确定型自动机与确定型自动机的等价性 14

1.3.3举例 16

1.3.4由非确定型自动机构造等价的确定型自动机所用状态数的比较 18

1.3.5带有ε移动的非确定型自动机 18

1.3.6带有ε移动的非确定型自动机与不含有ε移动的非确定型自动机的等价性 20

1.3.7DFA，NFA，ε-NFA的等价性 22

1.4正则表达式与正则语言 23

1.4.1正则表达式 23

1.4.2DFA所接受的语言 24

1.4.3正则语言能被机器ε-NFA（？NFA，DFA）所接受 26

1.4.4正则表达式所满足的算律 28

1.4.5语言的非正则性判定 29

1.4.6正则语言的封闭性 31

1.4.7正则语言的判定问题 34

1.4.8自动机的等价和最小化 36

第2章 下推自动机 41

2.1上下文无关文法 41

2.1.1上下文无关文法的定义 41

2.1.2语法分析树（又称为推导树） 45

2.2语法分析树与推导过程的定理 46

2.2.1语法分析树的产品定理 46

2.2.2最左推导与最右推导 47

2.2.3歧义性 48

2.3上下文无关文法的简化 48

2.3.1无用变量，终端记号以及ε记号的处理方法 48

2.3.2ε生产公式的处理 50

2.3.3单传生产公式 51

2.3.4固有的歧义性语言的例子 52

2.3.5上下文无关文法的整理 56

2.4下推自动机 58

2.4.1下推自动机的定义 58

2.4.2关于下推自动机的等价定理 64

2.5上下文无关语言的判定问题 77

2.5.1CFL的泵引理 77

2.5.2关于CFL的判定问题 79

第3章 递归函数 81

3.1部分函数与函数运算 81

3.1.1部分函数 81

3.1.2函数运算 81

3.2原始递归函数 82

3.2.1原始递归函数的定义 82

3.2.2原始递归函数的一些基本性质 83

3.3部分递归函数 84

3.3.1部分递归函数的概念 84

3.3.2部分递归函数的性质 85

3.4递归可枚举集 85

第4章 图灵机 87

4.1图灵机的基本概念 87

4.1.1符号串与编码 87

4.1.2图灵机的基本概念 89

4.2图灵可计算函数 92

4.3图灵机的变形 93

4.3.1多带图灵机 93

4.3.2非确定型图灵机 95

4.4通用图灵机 96

4.5对角线方法 97

第5章 计算复杂性理论 99

5.1算法的基本概念 99

5.1.1算法的定义和特征 99

5.1.2算法设计的例子——穷举法 101

5.2计算模型 102

5.2.1布尔函数 103

5.2.2随机存取机（RAM—Random Access Machine）模型 104

5.2.3随机存取存储程序机（RASP—Random Access Stored Program Machine）模型 113

5.3算法复杂度分析的数学基础 116

5.3.1集合论 116

5.3.2逻辑学 118

5.3.3概率论 119

5.3.4求和与递归 123

5.3.5快速估算法 127

第6章 顺序算法设计的基本技术 128

6.1分治策略 128

6.1.1分治策略的基本思想 128

6.1.2分治策略的适用条件 128

6.1.3分治策略的基本步骤 129

6.1.4分治策略的几种变形 130

6.2动态规划 130

6.2.1动态规划基本思想 130

6.2.2动态规划基本步骤 131

6.2.3动态规划算法的基本要素 131

6.2.4备忘录方法 133

6.3回溯法 134

6.3.1问题的解空间 135

6.3.2回溯法的基本思想 135

6.3.3回溯法的一般性描述 136

6.3.4回溯法的效率分析 137

6.4贪心法 138

6.4.1贪心算法 138

6.4.2贪心算法分析 140

6.4.3贪心算法的基本要素 141

6.4.4贪心算法与动态规划算法的差异 142

6.5概率算法 144

6.5.1概率算法的基本思想 145

6.5.2数值概率算法 146

6.5.3蒙特卡罗算法 147

6.5.4其他概率算法 149

参考文献 152