本书是普通高等教育“十一五”国家级规划教材。本书以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机科学与技术专业的学生提供广泛而坚实的计算机基础知识。主要内容包括算法分析技术，算法设计技术，P类，NP类及NPC类，证明问题属于NPC类的技术，NPC问题子问题的复杂性，拟多项式变换和图灵归约，NP-难解问题近似算法，近似算法设计技术，等等。
本书包括了算法与复杂性领域的主要内容，可以作为高等学校计算机专业高年级本科生和研究生学习计算机算法设计的教材，也可供广大工程技术人员和自学者学习参考。
- 前辅文
- 第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 练习
- 参考文献
