算法設(shè)計(jì)

第1章 算法概述
1.1 問(wèn)題、算法和程序
1.2 兩個(gè)典型問(wèn)題的求解
1.2.1 排序問(wèn)題
1.2.2 穩(wěn)定匹配問(wèn)題
1.3 算法的復(fù)雜度分析
1.4 小結(jié)
習(xí)題1
第2章 基本數(shù)據(jù)結(jié)構(gòu)
2.1 鏈表
2.1.1 普通鏈表
2.1.2 泛型鏈表
2.1.3 雙向鏈表
2.2 堆棧和隊(duì)列
2.2.1 堆棧
2.2.2 隊(duì)列
2.2.3 優(yōu)先級(jí)隊(duì)列
2.3 樹(shù)
2.3.1 樹(shù)
2.3.2 二叉樹(shù)
2.3.3 堆
2.4 圖
2.4.1 圖的基本概念
2.4.2 圖的存儲(chǔ)方式
2.5 小結(jié)
習(xí)題2
第3章 蠻力法
3.1 字符串匹配
3.2 矩陣相乘
3.3 子集和問(wèn)題
3.4 冒泡排序
3.5 若干最優(yōu)化問(wèn)題
3.5.1 最近點(diǎn)對(duì)問(wèn)題
3.5.2 0-1背包問(wèn)題
3.5.3 子集和問(wèn)題的最優(yōu)化版本
3.5.4 最大獨(dú)立集和最小頂點(diǎn)覆蓋
3.5.5 旅行商問(wèn)題
3.6 小結(jié)
習(xí)題3
第4章 遞歸和分治法
4.1 遞歸
4.1.1 遞歸的基本概念
4.1.2 遞歸算法的效率分析
4.1.3 漢諾塔問(wèn)題
4.1.4 冪集和全排列
4.2 樹(shù)和圖中的一些遞歸問(wèn)題
4.2.1 二叉樹(shù)的遍歷
4.2.2 圖的遍歷
4.3 分治法的基本思想
4.4 最近點(diǎn)對(duì)問(wèn)題的分治算法
4.5 歸并排序和快速排序
4.5.1 歸并排序
4.5.2 快速排序
4.6 大數(shù)乘法和Strassen矩陣乘法
4.6.1 大數(shù)乘法
4.6.2 Strassen矩陣乘法
4.7 小結(jié)
習(xí)題4
第5章 動(dòng)態(tài)規(guī)劃法
5.1 動(dòng)態(tài)規(guī)劃法的基本思想
5.1.1 重疊子問(wèn)題
5.1.2 最優(yōu)性原則
5.2 計(jì)算二項(xiàng)式系數(shù)
5.3 最長(zhǎng)連續(xù)上升子序列問(wèn)題
5.4 最大子段和
5.4.1 一維數(shù)組的最大子段和
5.4.2 二維數(shù)組的最大子段和
5.5 序列比較
5.5.1 最長(zhǎng)公共子序列問(wèn)題
5.5.2 序列比對(duì)問(wèn)題
5.6 矩陣連乘問(wèn)題
5.7 圖中的路徑
5.7.1 Floyd算法
5.7.2 Warshall算法
5.7.3 Kleen抽象算法
5.8 多階段決策問(wèn)題
5.9 動(dòng)態(tài)規(guī)劃的備忘錄方法
5.10 小結(jié)
習(xí)題5
第6章 貪心法
6.1 找零錢(qián)問(wèn)題
6.2 最大數(shù)量裝載問(wèn)題
6.3 最小生成樹(shù)
6.3.1 Prim算法
6.3.2 Kruskal算法
6.3.3 破圈算法
6.4 單源最短路徑
6.5 往返運(yùn)輸問(wèn)題
6.6 區(qū)間活動(dòng)安排問(wèn)題
6.7 單位時(shí)間任務(wù)調(diào)度問(wèn)題
6.8 哈夫曼樹(shù)
6.9 小結(jié)
習(xí)題6
第7章 回溯和分支限界
7.1 回溯和分支限界法的基本思想
7.1.1 狀態(tài)空間
7.1.2 狀態(tài)空間樹(shù)與搜索策略
7.1.3 剪枝函數(shù)
7.2 0-1背包問(wèn)題
7.2.1 定義剪枝函數(shù)
7.2.2 回溯算法
7.2.3 分支限界算法
7.3 旅行商問(wèn)題
7.3.1 回溯算法
7.3.2 分支限界算法
7.4 圖著色問(wèn)題
7.5 N皇后問(wèn)題
7.6 任務(wù)分配問(wèn)題
7.7 小結(jié)
習(xí)題7
第8章 迭代改進(jìn)法
8.1 線性規(guī)劃與單純形法
8.1.1 線性規(guī)劃問(wèn)題
8.1.2 線性規(guī)劃的幾何意義
8.1.3 單純形法
8.2 二部圖匹配問(wèn)題
8.3 最大流
8.3.1 流網(wǎng)絡(luò)
8.3.2 最大流問(wèn)題
8.3.3 最小割問(wèn)題
8.4 小結(jié)
習(xí)題8
第9章 計(jì)算復(fù)雜性與NP理論
9.1 多項(xiàng)式時(shí)間歸約
9.2 計(jì)算模型
9.2.1 形式語(yǔ)言與問(wèn)題編碼
9.2.2 圖靈機(jī)模型
9.2.3 不確定性圖靈機(jī)
9.2.4 圖靈機(jī)與可計(jì)算性
9.3 計(jì)算復(fù)雜性分類(lèi)--P和NP
9.3.1 P類(lèi)問(wèn)題
9.3.2 NP類(lèi)問(wèn)題
9.4 NP完全問(wèn)題
9.4.1 第一個(gè)NP完全問(wèn)題
9.4.2 NP完全性的證明
9.4.3 更多的NP完全問(wèn)題
9.5 小結(jié)
習(xí)題9
第10章 近似算法
10.1 絕對(duì)近似算法--平面圖著色
10.2 相對(duì)近似算法--常數(shù)近似比
10.2.1 頂點(diǎn)覆蓋問(wèn)題
10.2.2 最短工期問(wèn)題
10.2.3 旅行商問(wèn)題
10.2.4 反饋集問(wèn)題
10.3 相對(duì)近似算法--函數(shù)近似比
10.3.1 無(wú)重合路徑問(wèn)題
10.3.2 集合覆蓋問(wèn)題
10.4 相對(duì)近似算法--任意近似比
10.4.1 0-1背包問(wèn)題的PTAS
10.4.2 子集和問(wèn)題的FPTAS
10.5 小結(jié)
習(xí)題10
第11章 參數(shù)化算法
11.1 頂點(diǎn)覆蓋問(wèn)題的參數(shù)化算法
11.1.1 參數(shù)化問(wèn)題與搜索樹(shù)方法
11.1.2 問(wèn)題簡(jiǎn)約：消除高度數(shù)頂點(diǎn)
11.1.3 增強(qiáng)的問(wèn)題簡(jiǎn)約與搜索樹(shù)方法
11.2 反饋集問(wèn)題的參數(shù)化算法
11.2.1 問(wèn)題簡(jiǎn)約
11.2.2 搜索樹(shù)方法
11.2.3 改進(jìn)的搜索樹(shù)方法
11.3 支配集問(wèn)題的參數(shù)化算法
11.4 參數(shù)化的計(jì)算復(fù)雜性框架
11.5 小結(jié)
習(xí)題11
第12章 隨機(jī)算法
12.1 隨機(jī)算法的基本概念
12.1.1 近似計(jì)算圓周率的隨機(jī)算法
12.1.2 隨機(jī)數(shù)的生成
12.1.3 拋硬幣問(wèn)題
12.2 舍伍德算法
12.2.1 隨機(jī)化快速排序
12.2.2 有序鏈表搜索
12.3 蒙特卡洛算法
12.3.1 眾數(shù)問(wèn)題
12.3.2 素?cái)?shù)判定問(wèn)題
12.4 拉斯維加斯算法
12.4.1 隨機(jī)取樣問(wèn)題
12.4.2 N皇后問(wèn)題
12.4.3 大整數(shù)分解問(wèn)題
12.5 小結(jié)
習(xí)題12
第13章 現(xiàn)代優(yōu)化算法
13.1 禁忌搜索
13.1.1 禁忌搜索的基本思想
13.1.2 禁忌搜索算法框架與應(yīng)用
13.2 模擬退火
13.2.1 模擬退火算法的基本思想
13.2.2 模擬退火算法框架與應(yīng)用
13.3 遺傳算法
13.3.1 遺傳算法的基本思想
13.3.2 遺傳算法框架與應(yīng)用
13.3.3 遺傳算法的其他變種
13.4 蟻群算法
13.4.1 蟻群算法的基本思想
13.4.2 蟻群算法框架與應(yīng)用
13.5 粒子群算法
13.5.1 粒子群算法的基本思想
13.5.2 粒子群算法框架與應(yīng)用
13.5.3 粒子群算法的其他變種
13.6 差分進(jìn)化算法
13.6.1 差分進(jìn)化算法的基本思想
13.6.2 差分進(jìn)化算法框架與應(yīng)用
13.6.3 差分進(jìn)化算法的其他變種
13.7 小結(jié)
習(xí)題13
附錄A 偽代碼語(yǔ)法規(guī)則