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

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

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

第1章 算法引论1

1.1 算法1

1.2 算法描述2

1.2.1 算法描述约定2

1.2.2 一个简单问题的求解过程5

1.3 算法分析基础6

1.3.1 算法分析的评估体系6

1.3.2 算法的时间复杂度6

1.3.3 算法的空间复杂度9

1.3.4 NP-完全问题9

1.4 基本数据结构10

1.4.1 栈和队列10

1.4.2 树14

1.4.3 图19

1.5 迭代法22

1.5.1 递推法22

1.5.2 倒推法22

1.5.3 迭代法解方程23

1.6 递归和消除递归25

1.6.1 递归25

1.6.2 消除递归26

本章小结27

习题127

第2章 排序算法29

2.1 排序29

2.1.1 排序问题29

2.1.2 冒泡排序30

2.1.3 交换排序31

2.1.4 选择排序33

2.1.5 插入排序34

2.2 堆排序35

2.2.1 堆35

2.2.2 建堆35

2.2.3 堆排序算法38

2.2.4 堆排序的应用40

2.3 快速排序41

2.3.1 快速排序的描述41

2.3.2 快速排序的性能42

2.3.3 随机化的快速排序算法42

2.3.4 快速排序分析43

2.4 线性时间排序44

2.4.1 排序算法的下界44

2.4.2 计数排序45

2.4.3 基数排序46

2.4.4 桶排序47

2.5 中数排序49

2.5.1 最大和最小元素49

2.5.2 一般选择问题49

本章小结51

习题252

第3章 分治法55

3.1 一般算法55

3.2 二分检索56

3.3 找最大值和最小值59

3.4 归并分类62

3.4.1 基本方法62

3.4.2 改进的归并分类算法66

3.5 快速分类67

3.5.1 快速分类算法67

3.5.2 快速分类分析68

3.6 选择问题70

3.6.1 选择问题算法70

3.6.2 SELECT2的实现70

本章小结72

习题372

第4章 图的搜索算法74

4.1 图的基本概念74

4.1.1 图的定义74

4.1.2 图的基本术语75

4.2 图的检索与遍历77

4.2.1 广度优先检索与遍历77

4.2.2 深度优先检索与遍历80

4.3 回溯法82

4.3.1 回溯法的一般方法82

4.3.2 回溯算法的抽象描述85

4.3.3 n-皇后问题86

4.3.4 子集和数问题88

4.3.5 0/1背包问题90

4.3.6 图的m-着色问题98

4.3.7 哈密顿环101

4.3.8 连续邮资问题103

4.3.9 回溯法的效率估计107

本章小结111

习题4111

第5章 贪心算法114

5.1 算法概述114

5.1.1 贪心选择性质114

5.1.2 最优子结构性质114

5.1.3 活动安排问题115

5.2 背包问题116

5.3 带有限期的作业排序118

5.3.1 带有限期的作业排序算法118

5.3.2 改进的带有限期的作业排序算法121

5.4 最优归并模式124

5.5 哈夫曼编码126

5.5.1 前缀码126

5.5.2 哈夫曼编码127

5.6 最小生成树129

5.6.1 Prim算法130

5.6.2 Kruskal算法133

5.7 单源点最短路径136

本章小结140

习题5141

第6章 动态规划算法145

6.1 一般方法145

6.2 多段图150

6.3 每对结点之间的最短路径152

6.4 最优二分检索树155

6.5 0/1背包问题161

6.5.1 0/1背包问题的实例分析161

6.5.2 DKP的实现165

6.5.3 过程DKNAP的分析167

6.6 可靠性设计168

6.7 货郎担问题170

6.8 流水线调度问题172

本章小结176

习题6176

第7章 分支限界法179

7.1 一般方法179

7.1.1 FIFO和LIFO-检索179

7.1.2 LC-检索180

7.1.3 LC-检索的抽象化描述184

7.1.4 分支限界法解最优化问题185

7.2 0/1背包问题190

7.2.1 LC-分支限界求解191

7.2.2 FIFO-分支限界求解195

7.3 货郎担问题197

7.4 效率分析204

本章小结205

习题7205

第8章 并行算法208

8.1 并行计算机及并行模型208

8.1.1 并行计算机208

8.1.2 并行计算模型211

8.1.3 并行计算机网络212

8.1.4 并行算法的一般术语214

8.2 SIMD共享存储模型的并行算法215

8.2.1 播送算法215

8.2.2 求和算法216

8.2.3 并行k-选择算法217

8.2.4 并行桶排序算法218

8.2.5 有序表搜索并行算法222

8.3 SIMD互联网络模型的并行算法224

8.3.1 网孔上的随机序列搜索算法224

8.3.2 树机上的矩阵和向量乘法226

8.3.3 一维线性阵列上的奇偶转置排序算法228

8.3.4 树机上求最小值算法228

8.3.5 树机上的连通分量算法232

8.4 MIMD共享存储模型的并行算法234

8.4.1 异步枚举排序算法234

8.4.2 单源点最短路径并行算法235

8.4.3 最小生成树并行算法238

8.4.4 Gauss-Seidel算法240

8.4.5 牛顿求根并行算法242

8.5 MIMD异步通信模型的并行算法243

8.5.1 快速排序并行算法243

8.5.2 二维网孔上的矩阵转置并行算法244

8.5.3 矩阵并行分块乘法算法246

8.5.4 分布式矩阵求逆的并行算法247

8.5.5 分布式高斯消去并行算法250

本章小结255

习题8255

第9章 NP-完全问题257

9.1 计算模型257

9.1.1 有限自动机257

9.1.2 下推自动机258

9.1.3 图灵机259

9.2 P类与NP类问题262

9.2.1 多项式时间界（Polynomial time）262

9.2.2 P类问题264

9.2.3 NP类问题264

9.3 NP-完全问题265

9.3.1 判定NP-完全问题的关键概念265

9.3.2 NP-完全性267

9.3.3 Cook定理268

9.4 典型的NP-完全问题272

9.4.1 NP-完全性的证明方法272

9.4.2 典型的NP-完全问题273

9.4.3 NP-完全问题的计算机实现282

本章小结283

习题9285

第10章 近似算法287

10.1 近似算法的性能287

10.2 启发式算法288

10.2.1 图着色问题289

10.2.2 旅行商问题290

10.3 任务安排的近似算法291

10.4 覆盖问题的近似算法295

10.4.1 顶点覆盖问题的近似算法295

10.4.2 集合覆盖问题的近似算法297

10.5 旅行售货员问题近似算法299

10.5.1 具有三角不等式的旅行售货员问题299

10.5.2 一般旅行售货员问题302

10.6 背包问题303

10.7 子集合问题的近似算法305

10.7.1 解子集合问题的指数时间算法305

10.7.2 子集合问题的完全多项式时间近似格式306

本章小结308

习题10308

第11章 概率算法311

11.1 概率算法概述311

11.2 伪随机数312

11.3 数值概率算法313

11.3.1 用随机投点法计算π值313

11.3.2 计算定积分314

11.3.3 解非线性方程组316

11.4 Sherwood算法318

11.4.1 线性时间选择算法319

11.4.2 搜索有序表320

11.4.3 跳跃表324

11.5 Las Vegas算法329

11.5.1 n后问题329

11.5.2 整数因子分解333

11.6 Monte Carlo算法335

11.6.1 Monte Carlo算法的基本思想335

11.6.2 主元素问题337

11.6.3 素数性测试338

本章小结339

习题11340

主要参考文献344