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

第1章 算法概述 1

1.1算法的概念 1

1.1.1算法的定义和特性 2

1.1.2求解问题的基本过程 4

1.1.3算法设计示例——计算最大公约数 5

1.2算法设计与分析任务 5

1.3算法分析准则 6

1.4算法分析基础 7

1.4.1常用数学术语 7

1.4.2对数与指数 8

1.4.3数学证明法 9

1.5算法复杂性分析方法 10

1.5.1复杂度函数 11

1.5.2最好、最坏和平均情况 13

1.5.3渐进分析 15

1.5.4阶的证明方法 16

小结 17

习题 18

第2章 递归与分治策略 19

2.1递归的概念 19

2.2具有递归特性的问题 19

2.3递归过程的设计与实现 23

2.4递归算法分析 25

2.4.1替换法 25

2.4.2递归树法 30

2.4.3主方法 32

2.5分治法的基本思想 33

2.6分治法的适用条件 34

2.7分治法的基本步骤 34

2.8分治法典型示例 35

2.8.1 n个数中求出最大／最小值 35

2.8.2快速排序 37

2.8.3大整数乘法 41

2.8.4折半查找 44

2.8.5矩阵乘法 46

小结 50

习题 50

第3章 动态规划 52

3.1动态规划基础 52

3.1.1动态规划的基本思想 52

3.1.2动态规划的基本要素 53

3.1.3动态规划的基本步骤 53

3.1.4动态规划示例——组合数问题 54

3.2线性动态规划——合唱队形问题 56

3.3区域动态规划——矩阵连乘问题（最佳次序） 59

3.4背包动态规划——0—1背包问题 66

3.5树形动态规划——最优二叉搜索树 74

小结 82

习题 83

第4章 贪心算法 86

4.1贪心算法基础 86

4.1.1贪心算法的基本思想 86

4.1.2贪心算法的基本要素 87

4.1.3贪心算法适合的问题 88

4.1.4贪心算法的基本步骤 88

4.1.5贪心算法示例——背包问题 89

4.2汽车加油问题 92

4.3最优服务次序问题 95

4.4区间相交问题 97

4.5单源最短路径 101

小结 105

习题 106

第5章 回溯法 108

5.1回溯法基础 108

5.1.1回溯法的基本思想 108

5.1.2回溯法的解空间 109

5.1.3回溯算法实现 112

5.1.4回溯法的基本步骤 114

5.1.5回溯法示例——运动员最佳配对问题 114

5.2子集和问题 117

5.3 n皇后问题 120

5.4连续邮资问题 125

5.5哈密顿回路 129

小结 133

习题 133

第6章 分支限界法 136

6.1分支限界法基础 136

6.1.1分支限界法的基本思想 136

6.1.2分支限界法示例——迷宫问题 137

6.1.3分支限界法的分类 139

6.2单源最短路径 142

6.3八数码问题 147

6.4旅行售货员问题 153

小结 157

习题 158

第7章 随机算法 160

7.1随机算法基础 160

7.1.1伪随机数 160

7.1.2实例分析 161

7.2数值随机算法 163

7.3舍伍德算法 164

7.3.1基本的舍伍德型随机算法 165

7.3.2线性表的快速查找 168

7.4拉斯维加斯算法 170

7.4.1拉斯维加斯算法的基本思想 170

7.4.2分班问题 172

7.5蒙特卡罗算法 175

7.5.1蒙特卡罗算法的基本思想 176

7.5.2蒙特卡罗算法的基本概念 177

7.5.3主元素问题 178

7.5.4素数测试 180

小结 183

习题 184

第8章NP完全性理论 188

8.1计算模型 188

8.1.1计算模型的概念 188

8.1.2 RAM模型 190

8.1.3 RASP模型 194

8.1.4 RASP模型与RAM模型的关系 196

8.1.5 RAM和RASP模型的简化 198

8.1.6图灵机模型 200

8.1.7图灵机模型与RAM、RASP模型的关系 205

8.2 P类与NP类问题 208

8.2.1非确定性图灵机 208

8.2.2 P类与NP类语言 210

8.3 NP完全问题 211

8.3.1多项式变换与问题归约 212

8.3.2 NP完全问题的定义 213

8.3.3一些典型的NP完全问题的证明 214

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

8.4.1近似算法的性能 215

8.4.2顶点覆盖问题的近似算法 216

8.4.3集合覆盖问题的近似算法 220

小结 221

习题 222

第9章 神经网络智能算法 223

9.1神经网络简介 223

9.1.1神经网络的组成 224

9.1.2神经网络的分类 225

9.1.3神经网络的学习规则 226

9.1.4神经网络的特征 228

9.2反向传播模型及其算法 229

9.2.1 BP神经网络学习算法 229

9.2.2 BP神经网络的设计 231

9.2.3 BP神经网络的缺点 233

9.3 BP模型示例 234

9.3.1神经网络字母识别过程 234

9.3.2用BP神经网络实现两类模式分类 235

9.3.3用神经网络实现医学影像乳腺癌分类 235

小结 236

习题 236

附录 试题及参考答案 237

参考文献 245