算法设计与分析【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

算法设计与分析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-SAT183

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

9.4.3 团问题CLIQUE184

9.4.4 顶点覆盖问题VERTEX-COVER185

9.4.5 子集和问题SUBSET-SUM186

9.4.6 哈密顿回路问题HAM-CYCLE188

9.4.7　旅行售货员问题TSP191

小结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