当前位置:首页 > 工业技术
算法设计与分析
算法设计与分析

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

工业技术

  • 电子书积分:10 积分如何计算积分?
  • 作 者:朱大铭,马绍汉编著
  • 出 版 社:北京:高等教育出版社
  • 出版年份:2009
  • ISBN:9787040258714
  • 页数:245 页
图书介绍:本书是普通高等教育“十一五”国家级规划教材。本书以算法设计策略为知识单元,系统地介绍了计算机算法的设计方法与分析技巧,以期为计算机科学与技术学科的学生提供广泛而坚实的计算机基础知识。本书主要内容包括算法分析技术,算法设计技术,P类、NP类及NPC类,证明问题属于NPC类的技术,NPC问题的子问题的复杂性,拟多项式变换和图灵归约,近似算法和概率算法,智能搜索算法等。全书内容丰富,采用Java语言描述算法,简明清晰。
《算法设计与分析》目录

第1章 算法分析技术 1

§1.1 算法及其复杂性 1

§1.2 渐近估计技术及基本规则 4

§1.3 递归算法分析 7

1.3.1 合并排序算法分析 7

1.3.2 一类递推方程的一般解 10

§1.4 大整数相乘的递归算法 14

§1.5 练习 15

第2章 算法设计技术 17

§2.1 分而治之 17

§2.2 贪心技术 21

§2.3 动态规划 23

§2.4 回溯技术 29

2.4.1 对策树搜索与α/β删除 30

2.4.2 一般树的回溯搜索与分支定界 34

§2.5 局部搜索技术 40

§2.6 练习 44

第3章 P类、NP类及NPC类 47

§3.1 问题与算法 47

§3.2 确定型图灵机与P类 49

§3.3 非确定型计算与NP类 55

§3.4 多项式变换与NPC类 59

§3.5 库克定理 63

§3.6 练习 68

第4章 证明问题属于NPC类的技术 69

§4.1 基本的NPC问题 69

§4.2 证明NP-完全性的典型技术 83

4.2.1 限制技术 84

4.2.2 局部替换技术 86

4.2.3 分支设计技术 92

§4.3 练习 95

第5章 NPC问题子问题的复杂性 97

§5.1 2SAT问题属于P类 97

§5.2 几个NPC问题在三角化图上的解 103

5.2.1 三角化图的特征 104

5.2.2 用字典编辑广度优先搜索识别三角化图 106

5.2.3 三角化图上着色、团、独立集及团覆盖问题的算法 112

§5.3 子问题中P和NPC的分界 113

§5.4 练习 119

第6章 拟多项式变换和图灵归约 121

§6.1 判定问题、语言和编码方案 121

§6.2 拟多项式时间算法和强NPC类 123

§6.3 用拟多项式变换证明强NP-完全性 127

§6.4 复杂性类之间的关系 138

§6.5 图灵归约和NP-难解问题 140

§6.6 练习 147

第7章 NP-难解问题近似算法 149

§7.1 近似算法及其性能评估 149

§7.2 近似算法设计 160

7.2.1 满足三角不等式的货郎问题及其近似算法 160

7.2.2 满足三角不等式的货郎问题的最小生成树算法 165

7.2.3 多任务排工问题的近似算法 168

7.2.4 独立任务排工问题 171

§7.3 NP-难解问题可近似计算复杂性 174

§7.4 多项式时间近似方案 177

§7.5 练习 188

第8章 近似算法设计技术 190

§8.1 组合技术 190

8.1.1 MaxSAT问题 190

8.1.2 Maxk-SAT问题 192

8.1.3 图顶点覆盖问题 193

8.1.4 整数排列与换位移动排序 194

8.1.5 集合覆盖问题 200

§8.2 线性规划技术 203

8.2.1 顶点覆盖近似算法 203

8.2.2 集合覆盖近似算法 204

§8.3 原始对偶技术 206

8.3.1 集合覆盖 207

8.3.2 击中集问题 209

8.3.3 最短路问题 213

8.3.4 Steiner树问题 214

§8.4 局部搜索技术 216

8.4.1 Max-3sAT问题的局部搜索算法 217

8.4.2 k-median问题的局部搜索算法 218

8.4.3 设施定位问题的局部搜索近似算法 222

§8.5 随机近似算法 224

8.5.1 MaxSAT问题的随机算法 225

8.5.2 欧氏平面上货郎问题的随机算法 228

§8.6 练习 236

参考文献 239

相关图书
作者其它书籍
返回顶部