计算机数学:计算复杂性理论与NPC、NP难问题的求解

第一章 线性规划

1. 1 线性规划的基本概念

1. 2 单纯形算法

1. 3 字典序单纯形算法

1. 4 对偶理论

1. 5 内点算法

第二章 多面体理论

2. 1 多面体的定义及其维数

2. 2 用有效不等式与边界面来描述多面体

2. 3 用极点和极射向表示多面体

第三章 图与网络规划

3. 1 图的基本知识

3. 1. 1 图

3. 1. 2 有向图

3. 1. 3 图的表示

3. 2 几类重要的图

3. 3 最短路间题

3. 4 最小权支撑树问题

3. 5 最大流问题

第四章 动态规划方法

.4. 1 多阶段决策问题与动态规划的基本概念

4. 2 动态规划方法的基本思想与最优性定理

4. 3 最小权问题

4. 4 背包问题

4. 4. 1 o-1背包问题

4. 4. 2 整数背包问题

4. 5 旅行商问题

第五章 算法复杂性概论

5. 1 引言

5. 2 基本概念

5. 3 多项式时间算法与指数时间算法

第六章 问题复奈性的分类

6. 1 判定问题与语言

6. 2 算法的严格定义与p类问题

6. 3 np类问题

6. 4 多项式变换与md完全问题

6. 5 co-md完全问题

6. 6 co-np类问题

6. 7 np困难问题

6. 8 空间复杂性简介

第七章 证明问题为np完全的或p的方法

7. 1 证明问题为npc的一般步骤

7. 2 限制法(restriction)

7. 3 局部置换法(local replacement)

7. 4 分量设计法(component design)

7. 5 证明问题属于p类的方法

第八章 np完全理论在分析、求解新问题中的应用

8. 1 分析新问题复杂性的双向研究方法

8. 2 子问题分析法

8. 3 求解npc问题的算法类型

第九章 近似算法的性能度量与np完全理论的应用

9. 1 近似算法的性能度量

9. 2 np完全理论在限定问题可近似程度中的应用

第十章 一般整数规划的基本性质

10. 1 一般整数规划问题

10. 2 整数规划与线性规划之间的关系

10. 3 整数规划问题解的有界性

10. 4 整数规划问题的计算复杂性

第十一章 割平面算法

11. 1 分数割平面算法

11. 2 整数割平面算法

11. 3 导出有效不等式的方法

11. 3. 1 取整方法

11. 3. 2 同余方法

11. 3. 3 合并方法

11. 3. 4 超加函数法

11. 4 混合整数规划问题的求解

11. 5 覆盖问题的割平面算法

11. 5. 1 覆盖问题的描述

11. 5. 2 覆盖问题的割平面算法

第十二章 分解算法

12. 1 拉格朗日松弛法

12. 2 benders分解

12. 3 一般分解方法

12. 4 选址问题的分解算法

第十三章 分枝定界法

13. 1 一般分枝定界法

13. 2 使用线性规划松弛的分枝定界算法

13. 2. 1 剪枝准则

13. 2. 2 分枝方法

13. 2. 3 结节选取方法

13. 2. 4 分枝变量选择方法

13. 3 0-1背包问题的分枝定界算法。

第十四章 匹配问题

14. 1 匹配问题简介

14. 2 最大匹配问题

14. 2. 1 二部图的匹配算法

14. 2. 2 非二部图的匹配算法

14. 3 加权匹配问题

14. 3. 1 指派问题的求解

14. 3. 2 一般加权匹配问题

14. 4 b匹配问题与其他相关论题

14. 4. 1 b匹配问题

14. 4. 2 匹配理论与算法的应用

第十五章 近似算法的设计与分类

15. 1 近似算法概述

15. 2 贪婪算法(greedy algorithms)

15. 3 局部搜索法(local search heuristics)

15. 4 原始-对偶法

15. 5 近似算法的其他设计方法

15. 6 近似算法的分类

15. 6. 1 定常近似比算法

15. 6. 2 近似策略

15. 6. 3 最好可能近似比算法

15. 6. 4 比最好还要好的近似算法

15. 6. 5 与真正最优值仅一步之遥的近似

第十六章 对称旅行商问题

16. 1 有效不等式的构造

16. 2 松弛问题的构造

16. 3 近似算法

16. 3. 1 最近邻法

16. 3. 2 最近插人法

16. 3. 3 贪婪可行法

16. 3. 4 k边交换法

16. 3. 5 三角不等式与贪婪型算法的性能

16. 3. 6 支撑树加倍法

16. 3. 7 支撑树加完美匹配法

16. 4 精确算法

16. 4. 1 指派问题加分枝定界算法

16. 4. 2 拉格朗日松弛加分枝定界算法

16. 4. 3 分数割平面加分枝定界算法

参考文献