计算机数学：计算复杂性理论与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 分数割平面加分枝定界算法
参考文献