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

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

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

第1章 引论1

1.1 算法分析3

1.2 算法的渐近性态分析5

1.2.1 渐近表示法6

1.2.2 大O表示法中的误区6

1.2.3 大O的特性7

1.2.4 紧凑大O界9

1.2.5 常用的大O表达式10

1.2.6 渐近下界——Ω表示法10

1.3 搜索有序表11

1.2.7 ？及小o表示法11

练习116

第2章 算法设计技术和分析方法18

2.1 穷举算法和贪心算法18

2.2 回溯方法26

2.2.1 构造解空间26

2.2.2 回溯和裁剪27

2.2.3 收费公路重建问题29

2.3 分支限界算法33

2.4 动态规划36

2.4.1 阶段的划分37

2.4.3 将递归算法变换成非递归算法38

2.4.2 根据子问题的特性建立计算最优解的递归算法38

2.5 分治方法40

2.6 随机化算法42

2.6.1 如何选取随机数序列43

2.6.2 随机算法的分类46

2.6.3 拉斯维加斯选择算法46

2.6.4 蒙特卡罗方法49

2.6.5 模拟退火算法50

2.7 一类递归方程的解51

2.8 母函数方法54

练习255

3.1 大整数相乘算法57

第3章 计算的算术复杂性57

3.2 矩阵的乘积59

3.2.1 Winograd矩阵乘积算法59

3.2.2 Strassen矩阵乘法60

3.3 快速傅里叶变换和卷积62

3.3.1 预备知识63

3.3.2 向量卷积63

3.3.3 离散傅里叶变换63

3.4 判定素数的算法65

3.5 RSA数据加密算法67

3.6 数据压缩算法69

3.6.1 ACSII码压缩方法69

练习370

3.6.2 模式置换压缩方法70

第4章 排序算法72

4.1 冒泡排序算法72

4.2 基于比较的排序算法时间复杂性下界76

4.3 分配排序技术76

4.3.1 基数排序算法77

4.3.2 分配分块排序算法79

4.3.3 分配和归并混合排序算法80

4.3.4 循环分组散列和循环两路归并排序算法82

4.4 Quick排序的随机算法84

练习487

5.2 线性期望时间的选择算法88

5.1 最大元素和最小元素选择问题88

第5章 选择问题88

5.3 最坏情形下线性时间的选择算法90

练习591

第6章 字符串匹配92

6.1 简单的字符串匹配算法92

6.2 Knuth-Morris-Pratt串匹配算法93

6.3 Boyer-Moore串匹配算法96

6.4 KARP-RABIN串匹配算法98

6.5 允许k-差别的近似串匹配算法100

6.6 求最长公共子序列算法102

练习6104

7.1 网络路由的概念107

第7章 网络路由算法107

7.2 LS路由算法108

7.3 DV路由算法110

7.4 分层路由112

7.5 无QoS约束的组播路由算法113

7.5.1 最小生成树算法114

7.5.2 无约束的Steiner树算法114

7.6 基于时延约束的组播路由算法114

7.7 无线移动通信网络的路由算法116

7.7.1 支持单向链路的路由选择算法116

7.7.2 附加处理模块119

练习7121

8.1.1 什么是好算法122

第8章 NP难解问题与近似算法122

8.1 NP难解问题的基本理论122

8.1.2 NP完全性124

8.1.3 绕过NP完全性问题126

8.2 NP完全问题的近似解法126

8.2.1 近似算法的性能127

8.2.2 顶点覆盖问题的近似算法127

8.3 旅行商问题128

8.3.1 最邻近策略128

8.3.2 最短链路策略129

8.4.1 依次着色算法130

8.4 图的着色问题130

8.4.2 四色猜想132

8.4.3 Ramsey数133

练习8134

第9章 生物信息处理算法135

9.1 DNA计算的基本原理与模型及算法135

9.2 序列比对的基本问题139

9.2.1 序列比对的记分方法139

9.2.2 替换矩阵140

9.2.3 空格罚分141

9.3 生物序列比对模型及算法141

9.3.1 双序列比对141

9.3.2 多序列比对及其比对模型142

9.3.3 多序列比对方法144

9.3.4 多序列比对算法的分析与比较148

练习9151

第10章 并行计算基础152

10.1 并行处理技术及其应用152

10.2 并行计算机分类153

10.2.1 Flynn分类法153

10.2.2 Handler分类法153

10.2.3 按机器体系结构分类154

10.3 并行计算机的处理器的互连方式155

10.3.1 一维线性阵列结构155

10.3.2 二维网格结构156

10.3.4 树网结构157

10.3.3 树结构157

10.3.5 超立方连接结构158

10.3.6 q维网格结构159

10.3.7 洗牌-交换网络159

10.3.8 蝶形结构160

10.4 并行计算模型160

10.4.1 SIMD互连网络模型160

10.4.2 共享存储的SIMD模型161

10.4.3 MIMD并行计算模型161

10.5.2 Minsky猜想162

10.5.3 Amdahl定律162

10.5.1 Grosch定律162

10.5 并行计算的若干理论162

10.6 并行算法基础163

10.6.1 并行算法的基本概念163

10.6.2 并行算法的复杂性163

10.6.3 并行算法的形式描述165

10.6.4 并行算法设计的基本技术165

练习10167

第11章 并行求和算法168

11.1 SIMD-MC2二维网格机器上的同步并行求和算法168

11.2 SIMD-CC超立方机器上的同步并行求和算法170

11.3 SIMD-SE洗牌交换网络上的同步并行求和算法171

11.4 SIMD-SM机器上的同步并行求和算法172

11.5 MIMD-SM机器上的异步并行求和算法174

练习11175

第12章 并行排序算法177

12.1 线性阵列上的奇偶转置排序同步并行算法177

12.2 线性阵列上的奇偶归拆排序同步并行算法178

12.3 树机器上的最小抽取排序同步并行算法180

12.4 树机器上的桶分配和归并排序同步并行算法184

12.5 共享存储并行系统上的Valiant归并和排序同步并行算法185

12.5.1 Valiant归并同步并行算法186

12.6 共享存储MIMD-TC模型上的快速排序异步并行算法189

12.5.2 Valiant排序同步并行算法189

12.7 MIMD-SM机器上基于散列技术的异步并行排序算法192

12.8 共享存储并行系统上Multisets排序的最优并行算法194

12.9 SMP Clusters系统上的并行外部排序算法199

练习12201

第13章 并行查找与并行串匹配203

13.1 共享存储器并行系统上范围查找同步并行算法203

13.2 共享存储器并行系统上任意两序列公共元素的同步并行查找算法205

13.3 共享存储器并行系统上KARP-RABIN串匹配并行算法209

13.4 PRAM模型上允许k-差别的近似串匹配并行算法210

13.4.1 波前式并行计算编辑距离的允许k-差别的近似串匹配动态规划并行算法210

13.4.2 水平和斜向双并行计算编辑距离的允许k-差别的近似串匹配并行算法213

练习13216

第14章 数值并行算法217

14.1 SIMD-SM机器上基于LDU分解的方程组求解同步并行算法217

14.2 MIMD-SM机器上的矩阵相乘异步并行算法218

14.3 SIMD-SM机器上非线性方程求根同步并行算法220

练习14221

第15章 数据库操作并行算法222

15.1 选择、投影和集合操作并行算法222

15.1.1 并行选择算法223

15.1.2 并行投影算法225

15.1.3 关系元组集合操作并行算法228

15.2.1 并行嵌套循环连接算法231

15.2 并行连接算法231

15.2.2 基于排序和合并方法的并行连接算法232

15.2.3 基于Hash方法的并行连接算法234

练习15239

附录 并行MULTIPASCAL系统简介及并行程序实例240

附录1 并行MULTIPASCAL系统简介240

附录1.1 并行MULTIPASCAL系统的上机操作步骤240

附录1.2 并行MULTIPASCAL语句简介240

附录2 基于散列技术的（m，n）选择并行算法及程序实例242

附录2.1 并行散列选择算法的设计242

附录2.2 并行散列选择程序实例244

参考文献250