算法设计与分析

图书标准信息

• 作者 张德富；曾华琳；沈思淇
• 出版社 清华大学出版社
• 出版时间 2024-01
• 版次 1
• ISBN 9787302632764
• 定价 65.00元
• 装帧 其他
• 开本 16开
• 页数 272页
• 字数 411千字

【内容简介】

本书主要取材于算法设计与分析领域经典和发展潮流方面的内容，包括非常经典的算法设计技术，例如，递归、分治算法、动态规划、贪心算法、图算法、分支限界、回溯； 也包括一些高级的算法设计，例如，网络流和匹配、线性规划、启发式搜索。在算法分析方面，本书介绍了概率分析、分摊分析和实验分析方法。在算法理论方面，本书介绍了问题的下界、算法的正确性证明，以及NP接近理论等内容。

本书还包括大量的问题实例，给出了相应的设计与分析方法，并精选了一些习题，供读者练习，以巩固所学的算法。在工业应用领域，许多实际问题和疑难问题都需要有效的求解算法，因此，本书提供了设计有效算法的基础，以及大量可供选择的解决途径。

本书可作为计算机科学与技术系、数学系、软件学院等专业和学院的本科生及研究生的教材，也可作为有志参加程序设计竞赛的学生进行学习和训练的参考书。

【目录】

第1章 概念入门1

1.1问题模型1

1.2算法的概念1

1.3算法的正确性3

1.4算法的效率4

1.5问题的下界8

1.6小结9

习题9

实验题10

第2章 渐近符号11

2.1Θ符号11

2.2O符号13

2.3Ω符号14

2.4渐近符号的性质14

2.5常用函数的直观含义15

2.6小结16

习题16

第3章 算法分析方法18

3.1概率分析18

3.2分摊分析20

3.2.1合计方法21

3.2.2记账方法23

3.2.3势能方法25

3.3实验分析26

3.4小结28

习题28

第4章 递归算法29

4.1算法思想29

4.1.1递归算法的应用30

4.1.2递归与迭代36

4.2递归方程的求解37

4.2.1替换法37

4.2.2递归树法39

4.2.3公式法41

4.3多项式求值实验42

4.4小结43

习题43

实验题44

第5章 分治算法45

5.1算法思想45

5.2合并排序46

5.3快速排序48

5.4大整数乘法51

5.5矩阵乘法52

5.6残缺棋盘游戏53

5.7快速傅里叶变换55

5.8小结57

习题57

实验题58

第6章 动态规划算法59

6.1算法思想59

6.2装配线调度问题61

6.3矩阵链乘法问题65

6.4最长公共子序列问题68

6.50/1背包问题72

6.6很优二叉搜索树问题74

6.7动态规划的基本性质78

6.8小结81

习题81

实验题83

第7章 贪心算法84

7.1算法思想84

7.2任务选择问题84

7.3背包问题89

7.4哈夫曼编码问题90

7.5缓存维护问题94

7.6任务选择问题实验95

7.7小结96

习题97

实验题98

第8章 图算法99

8.1图的搜索问题100

8.1.1宽度优先搜索100

8.1.2深度优先搜索104

8.2最小生成树问题108

8.2.1Kruskal算法108

8.2.2Prim算法110

8.3最短路径问题112

8.3.1单个源点的最短路径问题114

8.3.2所有点对的最短路径问题118

8.4小结121

习题121

实验题123

第9章 网络流与匹配124

9.1优选流问题124

9.1.1FordFulkerson算法125

9.1.2最短路径增广算法131

9.1.3Dinic算法134

9.1.4MPM算法137

9.1.5优选流问题的变形138

9.2最小费用流问题139

9.2.1消除回路算法140

9.2.2最小费用路算法141

9.2.3最小费用路算法的改进144

9.3匹配问题146

9.3.1二分图匹配148

9.3.2一般图的匹配151

9.4小结156

习题157

实验题159

第10章 线性规划160

10.1线性规划问题160

10.1.1线性规划问题的标准形式161

10.1.2线性规划问题的松弛形式163

10.2求解算法164

10.2.1图解法164

10.2.2单纯形算法165

10.3对偶172

10.4小结176

习题176

实验题177

第11章 NP接近理论178

11.1判定问题179

11.2P和NP181

11.3NPC184

11.3.1NPC的定义184

11.3.2电路可满足性问题186

11.4NPC的证明189

11.4.1可满足性问题189

11.4.23-CNF可满足性问题191

11.4.3团问题193

11.4.4顶点覆盖问题194

11.5其他NP接近问题195

11.6小结197

习题198

第12章 回溯算法200

12.1算法思想200

12.2装载问题204

12.30/1背包问题207

12.4着色问题210

12.5n皇后问题211

12.6旅行商问题213

12.7流水作业调度问题215

12.8零件切割问题217

12.9小结219

习题219

实验题220

第13章 分支限界算法221

13.1算法思想221

13.2装载问题223

13.30/1背包问题230

13.4可满足性问题233

13.5旅行商问题235

13.6流水作业调度问题236

13.70/1背包问题实验239

13.8小结239

习题240

实验题241

第14章 启发式搜索242

14.1算法思想242

14.2A*搜索算法243

14.2.1最短路径问题245

14.2.2八数字问题246

14.3博弈搜索算法248

14.3.1α和β剪支250

14.3.2分硬币游戏252

14.3.3井字博弈253

14.4小结257

习题257

实验题259

参考文献260