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

第1章　算法概述 1

1.1 算法概念 1

1.1.1　什么是算法 1

1.1.2　抽象表达算法机制 2

1.2 算法的复杂度 4

1.2.1 算法三性态 4

1.2.2 算法复杂度 5

1.3 算法设计与分析的步骤 12

1.3.1 利用算法进行问题求解的过程 12

1.3.2 如何设计算法 13

1.3.3 如何表示算法 14

1.3.4 如何确认算法 14

1.3.5 如何分析算法 14

1.4 算法描述语言简介 16

1.4.1 C语言中的标准数据类型 16

1.4.2 C语言中的运算符 17

1.4.3 C语言中的语句简介 18

小结 20

习题一 20

一、选择题 20

二、填空题 21

三、简答题 22

四、计算题 22

五、上机题 23

第2章 递归技术 24

2.1 递归技术概述 24

2.1.1 什么是递归技术 24

2.1.2 递归技术的基本思想 26

2.2 Hanoi塔问题 27

2.3 递归方程的建立与求解 28

2.3.1 递推法 29

2.3.2 生成函数法 30

2.3.3 特征方程法 31

2.3.4 数学归纳法 32

2.3.5 不规则解法 33

2.4 递归消除 33

2.4.1 简单递归消除 34

2.4.2 基于栈的递归消除 36

小结 38

习题二 38

一、选择题 38

二、填空题 38

三、简答题 38

四、计算题 38

五、上机题 39

第3章 分治法 40

3.1 分治法概述 40

3.1.1 什么是分治法 40

3.1.2 分治法的基本思想 41

3.1.3 分治法的基本要素 41

3.2 二分检索技术 41

3.2.1 二分检索算法描述 42

3.2.2 最坏情况分析 42

3.2.3 平均复杂度分析 44

3.2.4 以比较为基础的检索时间下界 45

3.3 找第K小元素 47

3.3.1 分划点m的选取 47

3.3.2 随机选择算法 49

3.4 分治乘法 50

3.4.1 大整数相乘 50

3.4.2 多项式乘法 51

3.4.3 矩阵乘法 58

3.5 棋盘覆盖 59

3.6 分治合并排序 61

3.6.1 什么是合并 62

3.6.2 合并排序的基本思想 62

3.6.3 二路合并排序算法 63

3.7 分治快速排序 65

3.7.1　快速排序的基本思想 65

3.7.2　示例 67

3.8　常见分治 68

3.8.1　快速傅立叶变换 68

3.8.2　傅立叶变换的逆变换 70

3.8.3　利用傅立叶理论求解多项式相乘 71

小结 72

习题三 72

一、选择题 72

二、填空题 72

三、简答题 72

四、计算题 72

五、上机题 73

第4章　贪心法 74

4.1　贪心算法概述 74

4.1.1　什么是贪心法 74

4.1.2　贪心法的基本思想 75

4.1.3　贪心法基本要素 75

4.2　背包问题 77

4.3　磁带存储 81

4.3.1　单磁带最优存储 81

4.3.2　多磁带最优存储 83

4.4　作业调度 84

4.4.1　顺序选择法 85

4.4.2　最大期限选择法 86

4.5　启发式算法 88

4.6　贪心法的理论基础 91

4.6.1　拟阵 91

4.6.2　带权拟阵的贪心算法 92

4.6.3　任务时间表问题 94

4.7　常见贪心算法问题 97

4.7.1 最优装载 97

4.7.2 哈夫曼编码 99

4.7.3 单源最短路径 100

4.7.4 最小生成树 101

小结 103

习题四 104

一、选择题 104

二、填空题 104

三、简答题 104

四、计算题 104

五、上机题 105

第5章 动态规划 106

5.1 动态规划概述 106

5.1.1 什么是动态规划 106

5.1.2 动态规划的基本思想 106

5.1.3 动态规划的基本要素 108

5.2 最短路径 109

5.3 0/1背包问题 112

5.4 多矩阵乘积 120

5.5 货郎担问题 125

5.6 资源分配 127

小结 130

习题五 130

一、选择题 130

二、填空题 130

三、简答题 131

四、计算题 131

五、上机题 131

第6章 回溯法 132

6.1 概述 132

6.1.1 什么是回溯法 132

6.1.2 回溯法的基本思想 133

6.1.3 回溯法的算法框架与符号 133

6.2 n-皇后问题 135

6.3 图的m着色问题 140

6.3.1 图m着色问题的回溯法求解 140

6.3.2 图m着色问题的递归回溯算法 140

6.4 批处理作业调度问题 141

6.5 其他常见回溯法问题 142

6.5.1 最大团问题 142

6.5.2 旅行售货员问题 143

6.5.3 连续邮资问题 144

6.5.4 电路板排列问题 145

小结 147

习题六 147

一、选择题 147

二、填空题 147

三、简答题 147

四、计算题 147

五、上机题 147

第7章 分支限界法 148

7.1 概述 148

7.1.1 什么是分支限界法 148

7.1.2 分支限界的基本思想 148

7.2 复杂的有限期作业调度问题 149

7.3 贷郎担问题的分支限界法 151

7.4 其他分支限界问题 154

7.4.1 布线问题 154

7.4.2 0/1背包问题 157

7.4.3 单源最短路径的分支限界法 160

7.5 分支限界法与回溯法的比较 162

小结 163

习题七 163

一、选择题 163

二、填空题 163

三、简答题 163

四、计算题 164

五、上机题 164

第8章 概率算法概述 165

8.1 概率算法概述 165

8.1.1 什么是概率算法 165

8.1.2 概率算法的基本思想 166

8.2 数值概率算法 167

8.3 蒙特卡罗算法 168

8.4 其他概率算法 169

8.4.1 舍伍德算法 169

8.4.2 拉斯维加斯算法 170

小结 173

习题八 173

一、选择题 173

二、填空题 173

三、简答题 173

四、计算题 173

五、上机题 173

第9章 NP问题 174

9.1 NP问题概述 174

9.2 P类与NP类问题 175

9.2.1 非确定性图灵机 175

9.2.2 P类与NP类语言 176

9.2.3 多项式时间验证 177

9.3 NP完全问题 178

9.3.1 多项式时间变换 178

9.3.2 Cook定理 179

9.4 一些典型的NP完全问题 182

9.4.1 合取范式的可满足性问题CNF-SAT 183

9.4.2 三元合取范式的可满足性问题3-SAT 183

9.4.3 团问题CLIQUE 184

9.4.4 顶点覆盖问题VERTEX-COVER 185

9.4.5 子集和问题SUBSET-SUM 186

9.4.6 哈密顿回路问题HAM-CYCLE 188

9.4.7　旅行售货员问题TSP 191

小结 192

习题九 192

一、选择题 192

二、填空题 192

三、简答题 192

四、计算题 192

五、上机题 193

第10章　近似算法 194

10.1　近似算法概述 194

10.1.1　什么是近似算法 194

10.1.2　近似算法的基本思想及性能 194

10.2 顶点覆盖问题的近似算法 196

10.3 集合覆盖问题的近似算法 198

10.4 子集合问题的近似算法 199

10.4.1 子集和问题的指数时间算法 200

10.4.2 子集合问题的完全多项式时间近似格式 200

小结 202

习题十 202

一、选择题 202

二、填空题 202

三、简答题 203

四、计算题 203

五、上机题 203

第11章 新型算法 204

11.1 加密算法概述 204

11.2 初等数论 205

11.3 DES以及3重DES算法 208

11.3.1 DES算法 208

11.3.2 三重DES算法 210

11.4 AES算法 213

11.4.1 Rijndael加密算法描述 214

11.4.2 Rijndael解密算法描述 215

11.5 RSA算法 215

小结 216

习题十一 216

一、选择题 216

二、填空题 217

三、简答题 217

四、计算题 217

五、上机题 217

第12章 并行算法 218

12.1 并行算法概述 218

12.2 并行计算机 218

12.2.1 并行计算机分类 218

12.2.2 并行计算机的处理机互连方式 222

12.2.3 并行计算模型 224

12.3 并行算法 228

12.3.1 数据并行模型 229

12.3.2 消息传递模型 230

12.3.3 共享变量模型 231

12.4 并行算法编程实现 231

12.4.1 枚举排序 232

12.4.2 快速排序 233

12.4.3 并行正则采样排序 234

小结 235

习题十二 236

一、选择题 236

二、填空题 236

三、简答题 236

四、计算题 236

五、上机题 236

第13章 上机实训 237

13.1 递归技术应用 237

13.2 运用贪心算法求解实际问题 239

13.2.1 套汇问题 239

13.2.2 汽车加油问题 239

13.3 动态规划法应用 240

13.3.1 最好费用购物 240

13.3.2 租用游艇问题 242

13.4 回溯法应用 242

13.4.1 重排九宫问题 243

13.4.2 智力拼图问题 247

13.5 分支限界法应用 251

13.5.1 0/1问题的栈式分支限界法 251

13.5.2 用最大堆存储活结点的优先队列式分支限界法 253

小结 255

参考文献 256