前辅文
 第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 练习
 参考文献