算法设计与分析 / 高等院校电气信息类专业“互联网+”创新规划教材
￥48.00定价
作者： 汪国华，李艳娟
出版时间：2022-03
出版社：北京大学出版社
- 北京大学出版社
- 9787301328736
- 1版
- 455298
- 60240039-2
- 16开
- 2022-03
- 272
- 计算机科学与技术
- 本科
作者简介
内容简介
本书共8章，主要从算法的分析与设计两个方面进行介绍。首先，系统地介绍了算法分析的基本方法，包括非递归算法和递归算法，并详细介绍了Master定理。然后，系统地介绍了各种算法设计策略，包括分治策略、动态规划算法、贪心算法、回溯法、分支限界法、线性规划与网络流等。对于每种算法设计策略，从该策略的基本思想、适用问题、算法步骤或框架、应用范例等多个方面详细讲解，对于复杂的算法设计策略还给出了相关例题。书中包含大量的范例和对应的实现代码，让读者对算法设计策略的基本思想和核心设计步骤有深入的理解与掌握，能够让读者掌握各种算法设计策略的精髓，能够提高读者的算法设计能力，能够让读者具备分析具体问题、选择算法设计策略、给出算法代码的能力。
本书主要作为普通高校教材，适用于计算机科学与技术相关专业的本科和研究生阶段的教材，也可以作为从事实际问题求解的研究工作者的入门教材。
本书主要作为普通高校教材，适用于计算机科学与技术相关专业的本科和研究生阶段的教材，也可以作为从事实际问题求解的研究工作者的入门教材。
目录
第1章 算法概述 ································· 1
1.1 引言·············································· 3
1.2 算法的概念····································· 4
1.3 算法复杂性分析······························· 8
1.4 本章小结······································· 16
习题···················································· 17
第2章 递归与分治策略 ······················19
2.1 递归············································· 22
2.2 分治策略······································· 28
2.3 分治法求解查找问题························ 30
2.4 分治法求解排序问题························ 33
2.5 分治法求解复杂计算问题·················· 38
2.6 分治法求解组合问题························ 51
2.7 本章小结······································· 55
习题···················································· 56
第3章 动态规划算法··························59
3.1 动态规划的基本概念························ 62
3.2 备忘录方法···································· 64
3.3 动态规划算法的总体设计思想和
基本要素······································· 65
3.4 矩阵连乘问题································· 67
3.5 最长公共子序列问题························ 74
3.6 0-1背包问题 ·································· 80
3.7 最大子段和问题······························ 83
3.8 凸多边形最优三角剖分····················· 88
3.9 本章小结······································· 90
习题···················································· 91
第4章 贪心算法 ································94
4.1 生活中的贪心算法··························· 96
4.2 贪心算法的基本思想························ 98
4.3 活动安排问题································100
4.4 最优装载问题································104
4.5 哈夫曼编码···································108
4.6 贪心算法的正确性验证····················116
4.7 本章小结······································117
习题···················································117
第5章 回溯法·································· 120
5.1 回溯法的基本思想··························122
5.2 回溯法的算法框架··························123
5.3 装载问题······································127
5.4 批处理作业调度问题·······················130
5.5 符号三角形问题·····························133
5.6 0-1背包问题 ·································135
5.7 最大团问题···································138
5.8 旅行商问题···································141
5.9 连续邮资问题································145
5.10 回溯法的效率分析 ························148
5.11 本章小结·····································149
习题···················································149
第6章 分支限界法··························· 154
6.1 分支限界法的基本思想····················157
6.2 装载问题······································161
6.3 布线问题······································171
6.4 0-1背包问题 ·································177
目 录
算法设计与分析（文前+1-4）.indd 7 2022/3/9 15:25:03
算法设计与分析
VIII
6.5 最大团问题···································182
6.6 旅行商问题···································185
6.7 本章小结······································189
习题···················································190
第7章 随机算法 ······························ 193
7.1 随机算法的设计思想·······················196
7.2 随机数发生器································197
7.3 数值随机算法································199
7.4 舍伍德算法···································200
7.5 拉斯维加斯算法·····························203
7.6 蒙特卡罗算法································208
7.7 本章小结······································210
习题···················································210
第8章 线性规划与网络流················· 212
8.1 线性规划概述································215
8.2 单纯形法的设计思想与步骤··············221
8.3 单纯形法的描述与分析····················232
8.4 网络最大流问题·····························235
8.5 最小费用流问题·····························244
8.6 本章小结······································257
习题···················································257
参考文献 ·········································· 261
1.1 引言·············································· 3
1.2 算法的概念····································· 4
1.3 算法复杂性分析······························· 8
1.4 本章小结······································· 16
习题···················································· 17
第2章 递归与分治策略 ······················19
2.1 递归············································· 22
2.2 分治策略······································· 28
2.3 分治法求解查找问题························ 30
2.4 分治法求解排序问题························ 33
2.5 分治法求解复杂计算问题·················· 38
2.6 分治法求解组合问题························ 51
2.7 本章小结······································· 55
习题···················································· 56
第3章 动态规划算法··························59
3.1 动态规划的基本概念························ 62
3.2 备忘录方法···································· 64
3.3 动态规划算法的总体设计思想和
基本要素······································· 65
3.4 矩阵连乘问题································· 67
3.5 最长公共子序列问题························ 74
3.6 0-1背包问题 ·································· 80
3.7 最大子段和问题······························ 83
3.8 凸多边形最优三角剖分····················· 88
3.9 本章小结······································· 90
习题···················································· 91
第4章 贪心算法 ································94
4.1 生活中的贪心算法··························· 96
4.2 贪心算法的基本思想························ 98
4.3 活动安排问题································100
4.4 最优装载问题································104
4.5 哈夫曼编码···································108
4.6 贪心算法的正确性验证····················116
4.7 本章小结······································117
习题···················································117
第5章 回溯法·································· 120
5.1 回溯法的基本思想··························122
5.2 回溯法的算法框架··························123
5.3 装载问题······································127
5.4 批处理作业调度问题·······················130
5.5 符号三角形问题·····························133
5.6 0-1背包问题 ·································135
5.7 最大团问题···································138
5.8 旅行商问题···································141
5.9 连续邮资问题································145
5.10 回溯法的效率分析 ························148
5.11 本章小结·····································149
习题···················································149
第6章 分支限界法··························· 154
6.1 分支限界法的基本思想····················157
6.2 装载问题······································161
6.3 布线问题······································171
6.4 0-1背包问题 ·································177
目 录
算法设计与分析（文前+1-4）.indd 7 2022/3/9 15:25:03
算法设计与分析
VIII
6.5 最大团问题···································182
6.6 旅行商问题···································185
6.7 本章小结······································189
习题···················································190
第7章 随机算法 ······························ 193
7.1 随机算法的设计思想·······················196
7.2 随机数发生器································197
7.3 数值随机算法································199
7.4 舍伍德算法···································200
7.5 拉斯维加斯算法·····························203
7.6 蒙特卡罗算法································208
7.7 本章小结······································210
习题···················································210
第8章 线性规划与网络流················· 212
8.1 线性规划概述································215
8.2 单纯形法的设计思想与步骤··············221
8.3 单纯形法的描述与分析····················232
8.4 网络最大流问题·····························235
8.5 最小费用流问题·····························244
8.6 本章小结······································257
习题···················································257
参考文献 ·········································· 261
