計算機算法基礎（第二版）

第一章 導引與基本數(shù)據結構
1.1 算法
1.2 分析其法
1.2.1 計算時間的漸近表示
1.2.2 常用的整數(shù)求和公式
1.2.3 作時空性能分布圖
1.3 用SPARKS語言寫算法
1.4 基本數(shù)據結構
1.4.1 棧和隊列
1.4.2 樹
1.4.3 集合的樹表示和不相交集合的合并——樹結構應用實例
1.4.4 圖
1.5 遞歸和消去遞歸
1.5.1 遞歸
1.5.2 消去遞歸
習題—
第二章 分治法
2.1 一般方法
2.2 二分檢索
2.2.1 二分檢索算法
2.2.2 以比較為基礎檢索的時間下界
2.3 找最大和最小元素
2.4 歸并分類
2.4.1 基本方法
2.4.2 改進的歸并分類算法
2.4.3 以比較為基礎分類的時間下界
2.5 快速分類
2.5.1 快速分類算法
2.5.2 快速分類分析
2.6 選擇問題
2.6.1 選擇問題算法
2.6.2 最壞情況時間是O（n）的選擇算法
2.6.3 SELECT2的實現(xiàn)
2.7 斯特拉森矩陣乘法
習題二
第三章 貪心方法
3.1 一般方法
3.2 背包問題
3.3 帶有限期的作業(yè)排序
3.3.1 帶有限期的作業(yè)排序算法
3.3.2 一種更快的作業(yè)排序算法
3.4 最優(yōu)歸并模式
3.5 最小生成樹
3.6 單源點最短路徑
習題三
第四章 動態(tài)規(guī)劃
4.1 一般方法
4.2 多段圖
4.3 每對結點之間的最短路徑
4.4 最優(yōu)二分檢索樹
4.5 0/1背包問題
4.5.1 0/1背包問題的實例分析
4.5.2 DKP的實現(xiàn)
4.5.3 過程DKNAP的分析
4.6 可靠性設計
4.7 貨郎擔問題
4.8 流水線調度問題
習題四
第五章 基本檢索與周游方法
5.1 一般方法
5.1.1 二元樹周游
5.1.2 樹周游
5.1.3 圖的檢索和周游
5.2 代碼是優(yōu)化
5.3 雙速通分留和深度優(yōu)先檢索
5.4 與/或圖
5.5 對策樹
習題五
第六章 回溯法
6.1 一般方法
6.1.1 回溯的一般方法
6.1.2 效率估計
6.2 8-皇后問題
6.3 子集和數(shù)問題
6.4 圖的著色
6.5 哈密頓環(huán)
6.6 背包問題
習題六
第七章 分枝-限界法
7.1 一般方法
7.1.1 LC-檢索
7.1.2 15-談問題——一個例子
7.1.3 LC-檢索的抽象化控制
7.1.4 LC-檢索的特性
7.1.5 分枝-限界算法
7.1.6 效率分析
7.2 0/1背包問題
7.2.1 LC分枝-限界求解
7.2.2 FIFO分枝-限界未解
7.3 貨郎擔問題
習題七
第八章 NP-難度和NP-完全的問題
8.1 基本概念
8.1.1 不確定的算法
8.1.2 NP-難度和NP-完全類
8.2 COOK定理
8.3 NP-難度的圖問題
8.3.1 集團判定問題（CDP）
8.3.2 結點覆蓋的判定問題
8.3.3 著色數(shù)判定問題（CN）
8.3.4 有向哈密頓環(huán)（DHC）
8.3.5 貨郎擔判定問題（TSP）
8.3.6 與/或圖的判定問題（AOG）
8.4 NP-難度的調度問題
8.4.1 相同處理器調度
8.4.2 流水線調度
8.4.3 作業(yè)加工調度
8.5 NP-難度的代碼生成問題
8.5.1 有公共子表達式的代碼生成
8.5.2 并行賦值指令的實現(xiàn)
8.6 若干簡化了的NP-難度問題
習題八
第九章 并行算法
9.1 并行計算機與并行計算模型
9.2 并行算法的基本概念
9.2.1 并行算法的復雜性度量
9.2.2 并行算法的性能評價
9.2.3 并行算法的設計
9.2.4 并行算法的描述
9.3 SIMD共享存儲模型上的并行算法
9.3.1 廣播算法
9.3.2 求和算法
9.3.3 并行歸并分類算法
9.3.4 求目的連通分支的并行算法
9.4 SIMD互連網絡模型上的并行算法
9.4.1 起立方模型上的求和算法
9.4.2 一維線性模型上的共行排序算法
9.4.3 樹型模型上求最小值算法
9.4.4 二維網孔模型上的連通分支算法
9.5 MIMD共享存儲模型上的并行算法
9.5.1 并行求和算法
9.5.2 矩陣乘法的并行算法
9.5.3 枚舉分類算法
9.5.4 二次取中的并行選擇算法
9.5.5 并行快速排序算法
9.5.6 求最小元的并行算法
9.5.7 求單源點最短路徑的并行算法
9.6 MIMD異步通信模型上的并行算法
9.6.1 選擇問題的并行算法
9.6.2 求極值問題的并行算法
9.6.3 網絡生成樹的并行算法
習題九
參考文獻