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

**章 线性规划
1.1 线性规划的基本概念
1.2 单纯形算法
1.3 字典序单纯形算法
1.4 对偶理论
1.5 内点算法
第二章 多面体理论
2.1 多面体的定义及其维数
2.2 用有效不等式与边界面来描述多面体
2.3 用极点和极射向表示多面体
第三章 图与网络规划
3.1 图的基本知识
3.2 几类重要的图
3.3 *短路间题
3.4 *小权支撑树问题
3.5 *大流问题
第四章 动态规划方法
4.1 多阶段决策问题与动态规划的基本概念
4.2 动态规划方法的基本思想与*优性定理
4.3 *小权问题
4.4 背包问题
4.5 旅行商问题
第五章 算法复杂性概论
5.1 引言
5.2 基本概念
5.3 多项式时间算法与指数时间算法
第六章 问题复奈性的分类
6.1 判定问题与语言
6.2 算法的严格定义与P类问题。
6.3 NP类问题
6.4 多项式变换与MD完全问题
6.5 强MD完全问题
6.6 CO-NP类问题
6.7 NP困难问题
6.8 空间复杂性简介
第七章 证明问题为NP完全的或P的方法
7.1 证明问题为NPC的一般步骤
7.2 限制法(Restr1ct1on)
7.3 局部置换法(Local Rep1acement)
7.4 分量设计法(Component Des1gn)
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.4 混合整数规划问题的求解
11.5 覆盖问题的割平面算法
第十二章 分解算法
12.1 拉格朗日松弛法
12.2 Benders分解
12.3 一般分解方法
12.4 选址问题的分解算法
第十三章 分枝定界法
13.1 一般分枝定界法
13.2 使用线性规划松弛的分枝定界算法
13.3 0-1背包问题的分枝定界算法。
第十四章 匹配问题
14.1 匹配问题简介
14.2 *大匹配问题
14.3 加权匹配问题
14.4 b匹配问题与其他相关论题
第十五章 近似算法的设计与分类
15.1 近似算法概述
15.2 贪婪算法(Greedy Algor1thms)
15.3 局部搜索法(Local Search Heur1st1cs)
15.4 原始-对偶法
15.5 近似算法的其他设计方法
15.6 近似算法的分类
第十六章 对称旅行商问题
16.1 有效不等式的构造
16.2 松弛问题的构造
16.3 近似算法
16.4 精确算法
参考文献