算法设计与分析PDF电子书下载

1引论 1

1.1什么是算法 1

1.2分析算法的准则 2

1.3描述算法的语言和基本的数据结构 5

思考题与习题 7

2分治与递归 9

2.1折半查找 10

2.2搜索二叉排序树 12

2.2.1二叉排序树的定义 13

2.2.2搜索二叉排序树 13

2.2.3向二叉排序树中插入新结点 14

2.2.4从二叉排序树中删除一个结点 16

2.2.5平衡的二叉排序树 16

2.3快速排序 19

2.4归并排序 22

2.5大整数乘法 24

2.6矩阵乘积的Strassen算法 27

思考题与习题 30

3贪心算法 32

3.1最小生成树 32

3.2单源最短路径 35

3.3旅行商问题 38

思考题与习题 41

4动态规划 43

4.1动态规划在最短路径中的应用 44

4.2矩阵连乘积问题 48

4.3求最长公共子序列 52

4.4凸多边形的最优三角形剖分 54

4.5旅行商问题 57

思考题与习题 60

5回溯法 63

5.1树的深度优先遍历 64

5.2数的全排列 65

5.3八皇后问题 69

5.4 0-1背包问题 72

5.5旅行商问题 75

思考题与习题 77

6分支限界法 78

6.1最小耗费搜索 79

6.2背包问题 83

6.3旅行商问题 85

思考题与习题 88

7.1.1字符串的概念 89

7.1 串概念及简单串匹配算法 89

7字符串 89

7.1.2串的匹配 90

7.1.3简单串模式匹配算法 91

7.2 Knuth-Morris-Pratt（KMP）算法 92

7.2.1 KMP算法 92

7.2.2改进的KMP算法 97

7.3 Boyer-Moore算法 98

7.3.1 Boyer-Moore算法 98

7.4 Karp-Rabin串匹配随机算法 99

思考题与习题 102

8 NP完全问题与近似算法 103

8.1确定型图灵机 104

8.2非确定型图灵机 107

8.3 Cook定理和NP完全理论 108

8.3.1 NP完全理论 110

8.3.2Cook定理 112

8.3.3若干NP完全问题 116

8.4 NP完全问题的近似算法 119

8.4.1 0-1背包问题 120

8.4.2旅行商问题 121

思考题与习题 124

9概率算法 126

9.1随机抽样 128

9.2判定素数的概率算法 130

9.2.1 Fermat素数测试法 130

9.2.2 Miller-Rabin素数判定概率算法 131

思考题与习题 132

10数据压缩算法 133

10.1 ASCII码压缩算法 134

10.2哈夫曼编码 135

10.3字典法 139

10.4 LZ算法 140

10.4.1 LZ77算法 141

10.4.2LZ78算法 143

10.4.3 LZW算法 145

思考题与习题 147

11公钥密码学基础 148

11.1公钥密码体制的应用与基本思想 149

11.2背包公钥密码 151

11.3 RSA公钥密码体制 152

10.4数字签名和Hash算法 154

思考题与习题 155

参考文献 156