計算機數學：計算復雜性理論與NPC、NP難問題的求解

第一章 線性規(guī)劃
1. 1 線性規(guī)劃的基本概念
1. 2 單純形算法
1. 3 字典序單純形算法
1. 4 對偶理論
1. 5 內點算法
第二章 多面體理論
2. 1 多面體的定義及其維數
2. 2 用有效不等式與邊界面來描述多面體
2. 3 用極點和極射向表示多面體
第三章 圖與網絡規(guī)劃
3. 1 圖的基本知識
3. 1. 1 圖
3. 1. 2 有向圖
3. 1. 3 圖的表示
3. 2 幾類重要的圖
3. 3 最短路間題
3. 4 最小權支撐樹問題
3. 5 最大流問題
第四章 動態(tài)規(guī)劃方法
4. 1 多階段決策問題與動態(tài)規(guī)劃的基本概念
4. 2 動態(tài)規(guī)劃方法的基本思想與最優(yōu)性定理
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完全理論在限定問題可近似程度中的應用
第十章 一般整數規(guī)劃的基本性質
10. 1 一般整數規(guī)劃問題
10. 2 整數規(guī)劃與線性規(guī)劃之間的關系
10. 3 整數規(guī)劃問題解的有界性
10. 4 整數規(guī)劃問題的計算復雜性
第十一章 割平面算法
11. 1 分數割平面算法
11. 2 整數割平面算法
11. 3 導出有效不等式的方法
11. 3. 1 取整方法
11. 3. 2 同余方法
11. 3. 3 合并方法
11. 3. 4 超加函數法
11. 4 混合整數規(guī)劃問題的求解
11. 5 覆蓋問題的割平面算法
11. 5. 1 覆蓋問題的描述
11. 5. 2 覆蓋問題的割平面算法
第十二章 分解算法
12. 1 拉格朗日松弛法
12. 2 Benders分解
12. 3 一般分解方法
12. 4 選址問題的分解算法
第十三章 分枝定界法
13. 1 一般分枝定界法
13. 2 使用線性規(guī)劃松弛的分枝定界算法
13. 2. 1 剪枝準則
13. 2. 2 分枝方法
13. 2. 3 結節(jié)選取方法
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 與真正最優(yōu)值僅一步之遙的近似
第十六章 對稱旅行商問題
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 分數割平面加分枝定界算法
參考文獻