算法设计与分析PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 入门1

1.1问题1

1.2算法的概念1

1.3算法的正确性3

1.4算法的效率5

1.5问题的下界9

1.6小结10

习题11

实验题12

第2章 渐近符号13

2.1 Θ符号13

2.2 Ο符号15

2.3 Ω符号16

2.4渐近符号的性质17

2.5常用函数的直观含义18

2.6小结18

习题19

第3章 算法分析方法20

3.1概率分析20

3.2分摊分析22

3.2.1合计方法23

3.2.2记账方法25

3.2.3势能方法27

3.3实验分析29

3.4小结30

习题31

第4章 递归32

4.1算法思想32

4.1.1递归算法的应用33

4.1.2递归与迭代40

4.2递归方程的求解41

4.2.1替换方法41

4.2.2递归树方法43

4.2.3公式法45

4.3多项式求值实验47

4.4小结48

习题48

实验题49

第5章 分治算法50

5.1算法思想50

5.2合并排序51

5.3快速排序53

5.4大整数乘法56

5.5矩阵乘法58

5.6残缺棋盘游戏59

5.7快速傅里叶变换（FFT）62

5.8小结63

习题63

实验题65

第6章 动态规划66

6.1算法思想66

6.2装配线调度问题68

6.3矩阵链乘法问题73

6.4最长公共子序列问题77

6.5 0/1背包问题81

6.6最优二叉搜索树问题84

6.7动态规划的基本性质88

6.8小结92

习题92

实验题94

第7章 贪心算法95

7.1算法思想95

7.2任务选择问题95

7.3背包问题100

7.4哈夫曼编码问题102

7.5缓存维护问题106

7.6任务选择问题实验108

7.7小结109

习题109

实验题111

第8章 图算法112

8.1图的搜索问题113

8.1.1宽度优先搜索113

8.1.2深度优先搜索117

8.2最小生成树问题121

8.2.1 Kruskal算法122

8.2.2 Prim算法124

8.3最短路径问题125

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

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

8.4小结134

习题135

实验题137

第9章 网络流与匹配138

9.1最大流问题138

9.1.1 FordFulkerson方法140

9.1.2最短路径增广算法145

9.1.3 Dinic算法148

9.1.4 MPM算法151

9.1.5最大流问题的变形152

9.2最小费用流问题153

9.2.1消除回路算法154

9.2.2最小费用路算法156

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

9.3匹配问题160

9.3.1二分图匹配163

9.3.2一般图的匹配167

9.4小结172

习题172

实验题174

第10章 线性规划175

10.1线性规划问题175

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

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

10.2求解算法180

10.2.1图解法180

10.2.2单纯形算法181

10.3对偶188

10.4小结192

习题192

实验题193

第11章NP完全理论194

11.1判定问题195

11.2 P和NP197

11.3 NPC201

11.3.1 NPC的定义201

11.3.2电路可满足性问题203

11.4 NPC的证明206

11.4.1可满足性问题206

11.4.2 3-CNF可满足性问题208

11.4.3团问题210

11.4.4顶点覆盖问题212

11.5其他NP完全问题213

11.6小结215

习题215

第12章 回溯218

12.1算法思想218

12.2装载问题222

12.3 0/1背包问题226

12.4着色问题228

12.5 n皇后问题230

12.6旅行商问题232

12.7流水作业调度问题234

12.8零件切割问题236

12.9小结238

习题238

实验题240

第13章 分支限界241

13.1算法思想241

13.2装载问题243

13.3 0/1背包问题251

13.4可满足性问题254

13.5旅行商问题256

13.6流水作业调度问题258

13.7 0/1背包问题实验260

13.8小结261

习题262

实验题263

第14章 启发式搜索264

14.1算法思想264

14.2 A搜索265

14.2.1最短路径问题267

14.2.2 8数字问题268

14.3博弈搜索算法271

14.3.1α和β剪支273

14.3.2分硬币游戏275

14.3.3井字博弈275

14.4小结281

习题281

实验题283

第15章 数论284

15.1数论基础284

15.2最大公约数287

15.3同余289

15.4模幂运算294

15.5数论的应用295

15.5.1 Hash函数295

15.5.2 RSA公钥加密系统296

15.6小结299

习题299

实验题300

第16章 计算几何301

16.1叉积及其应用301

16.2计算任意线段的交点304

16.3凸包306

16.3.1礼物包装算法307

16.3.2 Graham扫描法309

16.3.3分治算法求凸包310

16.4最近点对316

16.5 Voronoi图318

16.5.1 Voronoi图的定义及其性质318

16.5.2 Voronoi图的构造321

16.5.3 Voronoi图的应用325

16.6小结327

习题327

实验题328

参考文献329