前辅文
第1 章 算法分析技术
§1.1 算法及其复杂性
§1.2 渐近估计技术及基本规则
§1.3 递归算法分析
1.3.1 合并排序算法分析
1.3.2 一类递推方程的一般解
§1.4 大整数相乘的递归算法
§1.5 练习
第2 章 算法设计技术
§2.1 分而治之
§2.2 贪心技术
§2.3 动态规划
§2.4 回溯技术
2.4.1 对策树搜索与α/β-删除
2.4.2 一般树的回溯搜索与分支定界
§2.5 局部搜索技术
§2.6 练习
第3 章 P 类、NP 类及NPC 类
§3.1 问题与算法
§3.2 确定型图灵机与P 类
§3.3 非确定型计算与NP 类
§3.4 多项式变换与NPC 类
§3.5 库克定理
§3.6 练习
第4 章 证明问题属于NPC 类的技术
§4.1 基本的NPC 问题
§4.2 证明NP-完全性的典型技术
4.2.1 限制技术
4.2.2 局部替换技术
4.2.3 分支设计技术
§4.3 练习
第5 章 NPC 问题子问题的复杂性
§5.1 2SAT 问题属于P 类
§5.2 几个NPC 问题在三角化图上的解
5.2.1 三角化图的特征
5.2.2 用字典编辑广度优先搜索识别三角化图
5.2.3 三角化图上着色、团、独立集及团覆盖问题的算法
§5.3 子问题中P 和NPC 的分界
§5.4 练习
第6 章 拟多项式变换和图灵归约
§6.1 判定问题、语言和编码方案
§6.2 拟多项式时间算法和强NPC 类
§6.3 用拟多项式变换证明强NP-完全性
§6.4 复杂性类之间的关系
§6.5 图灵归约和NP-难解问题
§6.6 练习
第7 章 NP-难解问题近似算法
§7.1 近似算法及其性能评估
§7.2 近似算法设计
7.2.1 满足三角不等式的货郎问题及其近似算法
7.2.2 满足三角不等式的货郎问题的最小生成树算法
7.2.3 多任务排工问题的近似算法
7.2.4 独立任务排工问题
§7.3 NP-难解问题可近似计算复杂性
§7.4 多项式时间近似方案
§7.5 练习
第8 章 近似算法设计技术
§8.1 组合技术
8.1.1 MaxSAT 问题
8.1.2 Maxk-SAT 问题
8.1.3 图顶点覆盖问题
8.1.4 整数排列与换位移动排序
8.1.5 集合覆盖问题
§8.2 线性规划技术
8.2.1 顶点覆盖近似算法
8.2.2 集合覆盖近似算法
§8.3 原始对偶技术
8.3.1 集合覆盖
8.3.2 击中集问题
8.3.3 最短路问题
8.3.4 Steiner 树问题
§8.4 局部搜索技术
8.4.1 Max-3SAT 问题的局部搜索算法
8.4.2 k-median 问题的局部搜索算法
8.4.3 设施定位问题的局部搜索近似算法
§8.5 随机近似算法
8.5.1 MaxSAT 问题的随机算法
8.5.2 欧氏平面上货郎问题的随机算法
§8.6 练习
参考文献
