計(jì)算機(jī)算法基礎(chǔ)（第二版）

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