算法设计与分析

第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对策树搜索与a／B-删除

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.12SAT问题属于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.3NP-难解问题可近似计算复杂性

§7.4多项式时间近似方案

§7.5练习

第8章近似算法设计技术

§8.1组合技术

8.1.1MaxSAT问题

8.1.2Maxk-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.4Steiner树问题

§8.4局部搜索技术

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

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

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

§8.5随机近似算法

8.5.1MaxSAT问题的随机算法

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

§8.6练习

参考文献

　　本书主要面向计算机相关专业的高年级本科生和研究生。全书共分8章，其中：第1、2章讨论算法分析技术和算法设计技术；第3、4、5、6章论述NP-完全性理论，特别强调多项式变换和多项式图灵归约的方法及应用；第7章论述NP-难解问题近似算法的基本概念和设计NP-难解问题近似算法的基本方法；第8章讨论近似算法设计的基本理论与技术。　　本书是普通高等教育“十一五”国家级规划教材。本书以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机科学与技术专业的学生提供广泛而坚实的计算机基础知识。主要内容包括算法分析技术，算法设计技术，P类、NP类及NPC类，证明问题属于NPC类的技术，NPC问题子问题的复杂性，拟多项式变换和图灵归约，NP-难解问题近似算法，近似算法设计技术，等等。　　本书包括了算法与复杂性领域的主要内容，可以作为高等学校计算机专业高年级本科生和研究生学习计算机算法设计的教材，也可供广大工程技术人员和自学者学习参考。