- 作 者：朱大铭，马绍汉编著
- 出 版 社：北京：高等教育出版社
- 出版年份：2009
- ISBN：9787040258714
- 注意：在使用云解压之前，请认真核对实际PDF页数与内容!
在线云解压
价格(点数)
购买连接
说明
转为PDF格式
9
（在线云解压服务）
云解压服务说明
1、本站所有的云解压默认都是转为PDF格式，该格式图书只能阅读和打印，不能再次编辑。
云解压下载及付费说明
1、所有的电子图书云解压均转换为PDF格式，支持电脑、手机、平板等各类电子设备阅读；可以任意拷贝文件到不同的阅读设备里进行阅读。
2、云解压在提交订单后一般半小时内处理完成,最晚48小时内处理完成。(非工作日购买会延迟)
第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