計算機算法基礎（普通高等教育十五國家級規(guī)劃教材）

第1章數(shù)學預備知識.
1.1集合
1.1.1集合之間的關系
1.1.2冪集
1.1.3集合的運算
1.2計數(shù)方法
1.2.1加法法則及乘法法則
1.2.2一一對應
1.2.3排列
1.2.4組合
1.3母函數(shù)
1.3.1母函數(shù)的性質及應用
1.3.2指數(shù)型母函數(shù)
1.4級數(shù)求和
1.4.1由組合的實際意義產(chǎn)生的計數(shù)公式及級數(shù)求和公式
1.4.2其它的一些常用求和公式
習題一
第2章導引與基本數(shù)據(jù)結構
2.1算法
2.1.1算法的重要特性
2.1.2算法學習的基本內(nèi)容
2.2分析算法
2.2.1計算時間的漸近表示
2.2.2常用的整數(shù)求和公式
2.2.3作時空性能分布圖
2.3.用SPARKS語言寫算法
2.4基本數(shù)據(jù)結構
2.4.1棧和隊列
2.4.2樹
2.4.3集合的樹表示和不相交集合的合并——樹結構應用實例
2.4.4圖
習題二
第3章遞歸算法
3.1遞歸算法的實現(xiàn)機制
3.1.1子程序的內(nèi)部實現(xiàn)原理
3.1.2遞歸過程的內(nèi)部實現(xiàn)原理
3.2遞歸轉非遞歸
3.3遞歸算法設計
3.4遞歸關系式的計算
3.4.1遞歸算法的時間復雜度分析
3.4.2k階線性齊次遞歸關系式的解法
3.4.3線性常系數(shù)非齊次遞歸關系式的解法
習題三
第4章分治法
4.1一般方法
4.2二分檢索
4.2.1二分檢索算法
4.2.2以比較為基礎檢索的時間下界
4.3找最大和最小元素
4.4歸并分類
4.4.1基本方法
4.4.2改進的歸并分類算法
4.4.3以比較為基礎分類的時間下界
4.5快速分類
4.5.1快速分類算法
4.5.2快速分類分析
4.6選擇問題
4.6.1選擇問題算法
4.6.2最壞情況時間是O(n)的選擇算法
4.6.3SELECT2的實現(xiàn)
4.7斯特拉森矩陣乘法
習題四
第5章貪心方法
5.1一般方法
5.2背包問題
5.3帶有限期的作業(yè)排序
5.3.1帶有限期的作業(yè)排序算法
5.3.2一種更快的作業(yè)排序算法
5.4最優(yōu)歸并模式
5.5最小生成樹
5.6單源點最短路徑
習題五
第6章動態(tài)規(guī)劃
6.1一般方法
6.2多段圖
6.3每對結點之間的最短路徑
6.4最優(yōu)二分檢索樹
6.50/1背包問題
6.5.10/1背包問題的實例分析
6.5.2DKP的實現(xiàn)
6.5.3過程DKNAP的分析
6.6可靠性設計
6.7貨郎擔問題
6.8流水線調(diào)度問題
習題六..
第7章基本檢索與周游方法
7.1一般方法
7.1.1二元樹周游
7.1.2樹周游
7.1.3圖的檢索和周游
7.2代碼最優(yōu)化
7.3雙連通分圖和深度優(yōu)先檢索
7.4與/或圖
7.5對策樹
習題七
第8章回溯法
8.1一般方法
8.1.1回溯的一般方法
8.1.2效率估計
8.28-皇后問題
8.3子集和數(shù)問題
8.4圖的著色
8.5哈密頓環(huán)
8.6背包問題
習題八
第9章分枝-限界法
9.1一般方法
9.1.1LC-檢索
9.1.215-謎問題——一個例子
9.1.3LC-檢索的抽象化控制
9.1.4LC-檢索的特性
9.1.5分枝—限界算法
9.1.6效率分析
9.20/1背包問題
9.2.1LC分枝-限界求解
9.2.2FIFO分枝-限界求解
9.3貨郎擔問題
習題九
第10章NP-難度和NP-完全的問題
10.1基本概念
10.1.1不確定的算法
10.1.2NP-難度和NP-完全類
10.2COOK定理
10.3NP-難度的圖問題
10,3.1集團判定問題(CDP)
10.3.2結點覆蓋的判定問題
10.3.3著色數(shù)判定問題(CN)
10.3.4有向哈密頓環(huán)(DHC)
10.3.5貨郎擔判定問題(TSP)
10.3.6與/或圖的判定問題(AOG)
10.4NP-難度的調(diào)度問題
10.4.1相同處理器調(diào)度
10.4.2流水線調(diào)度
10.4.3作業(yè)加工調(diào)度
10.5NP-難度的代碼生成問題
10.5.1有公共子表達式的代碼生成
10.5.2并行賦值指令的實現(xiàn)
10.6若干簡化了的NP-難度問題
習題十
第11章并行算法
11.1并行計算機與并行計算模型
11.2并行算法的基本概念
11.2.1并行算法的復雜性度量
11.2.2并行算法的性能評價
11.2.3并行算法的設計
11.2.4并行算法的描述
11.3SIMD共享存儲模型上的并行算法
11.3.1廣播算法
11.3.2求和算法
11.3.3并行歸并分類算法
11.3.4求圖的連通分支的并行算法
11.4SIMD互連網(wǎng)絡模型上的并行算法
11.4.1超立方模型上的求和算法
11.4.2一維線性模型上的并行排序算法
11.4.3樹形模型上求最小值算法
11.4.4二維網(wǎng)孔模型上的連通分支算法
11.5MIMD共享存儲模型上的并行算法
11.5.1并行求和算法
11.5.2矩陣乘法的并行算法
11.5.3枚舉分類算法
11.5.4二次取中的并行選擇算法
11.5.5并行快速排序算法
11.5.6求最小元的并行算法
11.5.7求單源點最短路徑的并行算法
11.6MIMD異步通信模型上的并行算法
11.6.1選擇問題的并行算法
11.6.2求極值問題的并行算法
11.6.3網(wǎng)絡生成樹的并行算法
習題十一
參考文獻...