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

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

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

第1章 绪论1

1.1 算法在计算机科学体系中的地位1

1.1.1 计算机理论模型和计算问题的分类1

1.1.2 利用计算机求解问题2

1.1.3 计算机科学的知识体系3

1.1.4 算法是计算机科学的重要主题4

1.1.5 算法设计与分析的意义5

1.2 算法的概念5

1.3 算法分析7

1.3.1 算法正确性分析7

1.3.2 算法复杂度分析8

1.4 算法设计方法10

习题10

第2章 数学基础12

2.1 复杂度函数的阶12

2.1.1 函数阶的定义12

2.1.2 函数阶的性质15

2.2 标准符号和通用函数15

2.2.1 flour函数和ceiling函数15

2.2.2 求和16

2.3 递归方程19

2.3.1 常系数线性递归方程19

2.3.2 非常系数线性递归方程21

2.3.3 生成函数22

2.3.4 分治算法递归方程23

习题27

第3章 分治算法29

3.1 分治算法原理29

3.2 大整数乘法31

3.3 Strassen矩阵乘法32

3.4 快速傅里叶变换33

3.5 最邻近点问题35

3.6 平面点集的凸包38

3.6.1 求解凸包问题的蛮力算法38

3.6.2 GrahamScan算法41

3.6.3 凸包问题的分治算法43

3.7 基于剪枝搜索方法的分治算法44

3.7.1 剪枝搜索方法44

3.7.2 线性时间选择算法45

3.7.3 二元线性规划的线性时间算法46

3.7.4 1－圆心问题的线性时间算法51

习题55

第4章 动态规划算法57

4.1 动态规划原理57

4.2 最长公共子序列59

4.3 矩阵链乘法63

4.4 0-1背包问题66

4.5 最优二叉搜索树69

4.6 评注74

习题75

第5章 贪心算法77

5.1 贪心算法的基本原理77

5.2 活动选择问题79

5.3 哈夫曼编码问题81

5.4 最小生成树问题85

5.4.1 Kruskal算法85

5.4.2 Prim算法87

5.5 贪心算法的理论基础90

5.5.1 拟阵90

5.5.2 加权拟阵上的贪心算法91

5.6 单位时间任务调度问题93

习题94

第6章 平摊分析96

6.1 平摊分析方法96

6.1.1 聚集方法96

6.1.2 会计方法98

6.1.3 势能方法99

6.2 动态表性能的平摊分析101

6.2.1 动态表及其操作101

6.2.2 动态表的扩张102

6.2.3 动态表扩张和收缩104

6.3 斐波那契堆及其操作代价的平摊分析106

6.3.1 斐波那契堆106

6.3.2 斐波那契堆操作算法及其平摊代价108

6.3.3 斐波那契堆最大度的上界112

6.4 并查集及其操作代价的平摊分析113

6.4.1 并查集及其基本性质113

6.4.2 阿克曼函数及其逆函数115

6.4.3 并查集上操作序列代价的平摊分析116

习题118

第7章 最大值最小值方法120

7.1 网络流120

7.1.1 最大流问题和最小割问题120

7.1.2 Ford-Fulkerson算法124

7.1.3 Edmonds-Karp算法126

7.1.4 推送复标算法128

7.1.5 复标前置算法133

7.2 匹配算法138

7.2.1 匹配与覆盖138

7.2.2 最大二分匹配140

7.2.3 一般图上的最大匹配144

7.2.4 最大权值二分匹配147

7.2.5 稳定二分匹配150

习题152

第8章 树的搜索策略154

8.1 问题解空间的树表示154

8.2 典型搜索策略157

8.2.1 广度优先搜索157

8.2.2 深度优先搜索158

8.2.3 爬山法159

8.2.4 最佳优先搜索160

8.2.5 分支限界法161

8.3 分支限界法的应用163

8.3.1 用分支限界法求解人员分配问题163

8.3.2 用分支限界法求解旅行商问题166

8.3.3 用分支限界法求解0-1背包问题169

8.4 A*算法及其应用171

8.5 博弈树和α-β剪枝174

8.5.1 博弈树及其评估174

8.5.2 α-β剪枝176

习题178

第9章 随机算法179

9.1 随机算法概述179

9.2 数值随机算法180

9.2.1 随机投点法180

9.2. 2平均值方法181

9.3 随机选择和拉斯维加斯算法182

9.3.1 随机选择算法182

9.3.2 拉斯维加斯算法184

9.4 快速排序和舍伍德算法185

9.4.1 快速排序算法描述185

9.4.2 快速排序算法的性能分析186

9.4.3 随机快速排序算法187

9.4.4 舍伍德算法188

9.5 素数测试和蒙特卡罗算法189

9.5.1 素数测试随机算法189

9.5.2 蒙特卡罗算法190

9.6 最小割随机算法190

习题192

第10章 近似算法194

10.1 近似算法的性能分析194

10.2 基于组合优化的近似算法195

10.2.1 顶点覆盖问题的近似算法195

10.2.2 装箱问题的近似算法196

10.2.3 最短并行调度问题的近似算法197

10.2.4 旅行商问题的近似算法198

10.2.5 子集和问题的完全多项式近似模式199

10.3 基于贪心思想的近似算法202

10.3.1 集合覆盖问题的近似算法202

10.3.2 不相交路径问题的近似算法204

10.4 基于局部搜索的近似算法205

10.4.1 最大割问题的近似算法205

10.4.2 设施定位问题的近似算法207

10.5 基于动态规划的近似算法210

10.5.1 0-1背包问题的完全多项式近似模式210

10.5.2 装箱问题的多项式近似模式212

10.6 基于线性规划的近似算法215

10.6.1 线性规划及对偶定理215

10.6.2 加权集合覆盖问题的线性规划表示216

10.6.3 舍入法及随机舍入法217

10.6.4 对偶拟合方法219

10.6.5 原偶模式220

10.7 不可近似性222

10.7.1 鸿沟归约与不可近似性222

10.7.2 PCP定理224

10.7.3 MAX-3SAT问题的不可近似性225

10.7.4 α,β－鸿沟归约与不可近似性227

习题228

第11章 在线算法230

11.1 在线算法与竞争度分析230

11.2 欧几里得最小生成树问题的在线算法231

11.2.1 在线贪心算法231

11.2.2 在线随机算法232

11.3 凸包在线算法235

11.4 线性链表在线更新算法238

11.5 最短并行调度在线算法240

习题246

参考文献248