第1章 算法引論
1.1 算法
1.2 算法描述
1.2.1 算法描述約定
1.2.2 一個(gè)簡(jiǎn)單問(wèn)題的求解過(guò)程
1.3 算法分析基礎(chǔ)
1.3.1 算法分析的評(píng)估體系
1.3.2 算法的時(shí)間復(fù)雜度
1.3.3 算法的空間復(fù)雜度
1.3.4 NP-完全問(wèn)題
1.4 基本數(shù)據(jù)結(jié)構(gòu)
1.4.1 棧和隊(duì)列
1.4.2 樹(shù)
1.4.3 圖
1.5 迭代法
1.5.1 遞推法
1.5.2 倒推法
1.5.3 迭代法解方程
1.6 遞歸和消除遞歸
1.6.1 遞歸
1.6.2 消除遞歸
本章小結(jié)
習(xí)題1


第2章 排序算法
2.1 排序
2.1.1 排序問(wèn)題
2.1.2 冒泡問(wèn)題
2.1.3 交換排序
2.1.4 選擇排序
2.1.5 插入排序
2.2 堆排序
2.2.1 堆
2.2.2 建堆
2.2.3 堆排序算法
2.2.4 堆排序的應(yīng)用
2.3 快速排序
2.3.1 快速排序的描述
2.3.2 快速排序的性能
2.3.3 隨機(jī)化的快速排序算法
2.3.4 快速排序分析
2.4 線性時(shí)間排序
2.4.1 排序算法的下界
2.4.2 計(jì)數(shù)排序
2.4.3 基數(shù)排序
2.4.4 桶排序
2.5 中數(shù)排序
2.5.1 最大和最小元素
2.5.2 一般選擇問(wèn)題
本章小結(jié)
習(xí)題2


第3章 分治法
3.1 一般算法
3.2 二分檢索
3.3 找最大值和最小值
3.4 歸并分類
3.4.1 基本方法
3.4.2 改進(jìn)的歸并算法
3.5 快速分類
3.5.1 快速分類算法
3.5.2 快速分類分析
3.6 選擇問(wèn)題
3.6.1 選擇問(wèn)題算法
3.6.2 SELECT2實(shí)現(xiàn)
本章小結(jié)
習(xí)題3


第4章 圖的搜索算法
4.1 圖的基本概念
4.1.1 圖的定義
4.1.2 圖的基本術(shù)語(yǔ)
4.2 圖的檢索與遍歷
4.2.1 廣度優(yōu)先檢索與遍歷
4.2.2 深度優(yōu)先檢索與遍歷
4.3 回溯法
4.3.1 回溯法的一般方法
4.3.2 回溯算法的抽象描述
4.3.3 n-皇后問(wèn)題
4.3.4 子集和數(shù)問(wèn)題
4.3.5 0/1背包問(wèn)題
4.3.6 圖的m-著色問(wèn)題
4.3.7 哈密頓環(huán)
4.3.8 連續(xù)郵資問(wèn)題
4.3.9 回溯法的效率估計(jì)
本章小結(jié)
習(xí)題4
第5章 貪心算法
5.1 算法概述
5.1.1貪心選擇性質(zhì)
5.1.2 最優(yōu)子結(jié)構(gòu)性質(zhì)
5.1.3活動(dòng)安排問(wèn)題
5.2 背包問(wèn)題
5.3 帶有限期的作業(yè)排序
5.3.1 帶有限期的作業(yè)排序算法
5.3.2 改進(jìn)的帶有限期的作業(yè)排序算法
5.4 最優(yōu)歸并模式
5.5 哈夫曼編碼
5.5.1 前綴碼
5.5.2 哈夫曼編碼
5.6 最小生成樹(shù)
5.6.1 Prim算法
5.6.2 Kruskal算法
5.7 單源點(diǎn)最短路徑
本章小結(jié)
習(xí)題5


第6章 動(dòng)態(tài)規(guī)劃算法
6.1 一般方法
6.2 多段圖
6.3 每對(duì)結(jié)點(diǎn)之間的最短路徑
6.4 最優(yōu)二分檢索樹(shù)
6.5 0/1背包問(wèn)題
6.5.1 0/1背包問(wèn)題實(shí)現(xiàn)的實(shí)例分析
6.5.2 DKP的實(shí)現(xiàn)
6.5.3 過(guò)程DKNAP的分析
6.6 可靠性設(shè)計(jì)
6.7 貨郎擔(dān)問(wèn)題
6.8 流水線調(diào)度問(wèn)題
本章小結(jié)
習(xí)題6


第7章 分支限界法
7.1 一般方法
7.1.1 FIFO和LIFO-檢索
7.1.2 LC-檢索
7.1.3 LC-檢索的抽象化描述
7.1.4 分支限界法解最優(yōu)化問(wèn)題
7.2 0/1背包問(wèn)題
7.2.1 LC-分支限界求解
7.2.2 FIFO –分支限界求解
7.3 貨郎擔(dān)問(wèn)題
7.4 效率分析
本章小結(jié)
習(xí)題7


第8章 并行算法
8.1 并行計(jì)算機(jī)及并行模型
8.1.1 并行計(jì)算機(jī)
8.1.2 并行計(jì)算模型
8.1.3 并行計(jì)算機(jī)網(wǎng)絡(luò)
8.1.4 并行算法的一般術(shù)語(yǔ)
8.2 SIMD共享存儲(chǔ)模型的并行算法
8.2.1 播送算法
8.2.2 求和算法
8.2.3 并行k-選擇算法
8.2.4 并行桶排序算法
8.2.5 有序表搜索并行算法
8.3 SIMD互聯(lián)網(wǎng)絡(luò)模型的并行算法
8.3.1 網(wǎng)孔上的隨機(jī)序列搜索算法
8.3.2 樹(shù)機(jī)上的矩陣和向量乘法
8.3.3 一維線性陳列上的奇偶轉(zhuǎn)置排序算法
8.3.4 樹(shù)機(jī)上求最小值算法
8.3.5 樹(shù)機(jī)上的連通分量算法
8.4 MIMD共享存儲(chǔ)模型的并行算法
8.4.1 異步枚舉排序算法
8.4.2 單源點(diǎn)最短路徑并行算法
8.4.3 最小生成樹(shù)并行算法
8.4.4 Gauss-Seidel算法
8.4.5 牛頓求根并行算法
8.5 MIMD異步通信模型的并行算法
8.5.1 快速排序并行算法
8.5.2 二維網(wǎng)孔上的矩陣轉(zhuǎn)置并行算法
8.5.3 矩陣并行分塊乘法算法
8.5.4 分布式矩陣求逆的并行算法
8.5.5 分布式高斯消去并行算法
本章小結(jié)
習(xí)題8


第9章 NP-完全問(wèn)題
9.1 計(jì)算模型
9.1.1 有限自動(dòng)機(jī)
9.1.2 下推自動(dòng)機(jī)
9.1.3 圖靈機(jī)
9.2 P類與NP類問(wèn)題
9.2.1 多項(xiàng)式時(shí)間界
9.2.2 P類問(wèn)題
9.2.3 NP類問(wèn)題
9.3 NP-完全問(wèn)題
9.3.1 判定NP-完全問(wèn)題的關(guān)鍵概念
9.3.2 NP-完全性
9.3.3 Cook定理
9.4 典型的NP-完全問(wèn)題
9.4.1 NP-完全性的證明方法
9.4.2 典型的NP-完全問(wèn)題
9.4.3 NP-完全問(wèn)題的計(jì)算機(jī)實(shí)現(xiàn)
本章小結(jié)
習(xí)題9


第10章 近似算法
10.1 近似算法的性能
10.2 啟發(fā)式算法
10.2.1 圖著色問(wèn)題
10.2.2 旅行商問(wèn)題
10.3 任務(wù)安排的近似算法
10.4 覆蓋問(wèn)題的近似算法
10.4.1 頂點(diǎn)覆蓋問(wèn)題的近似算法
10.4.2 集合覆蓋問(wèn)題的近似算法
10.5 旅行售貨員問(wèn)題近似算法
10.5.1 具有三角不等式的旅行售貨員問(wèn)題
10.5.2 一般旅行售貨員問(wèn)題
10.6 背包問(wèn)題
10.7 子集合問(wèn)題的近似算法
10.7.1 解子集合問(wèn)題的指數(shù)時(shí)間算法
10.7.2 子集合問(wèn)題的完全多項(xiàng)式時(shí)間近似格式
本章小結(jié)
習(xí)題10


第11章 概率算法
11.1 概率算法概述
11.2 偽隨機(jī)數(shù)
11.3 數(shù)值概率算法
11.3.1 用隨機(jī)投點(diǎn)法計(jì)算圓周率值
11.3.2 計(jì)算定積分
11.3.3 解非線性方程組
11.4 Sherwood算法
11.4.1 線性時(shí)間選擇算法
11.4.2 搜索有序表
11.4.3 跳躍表
11.5 Las Vegas算法
11.5.1 n后問(wèn)題
11.5.2 整數(shù)因子分解
11.6 Monte Carlo算法
11.6.1 Monte Carlo算法的基本思想
11.6.2 主元素問(wèn)題
11.6.3 素?cái)?shù)性測(cè)試
本章小結(jié)
習(xí)題11


主要參考文獻(xiàn)