算法設(shè)計技巧與分析

第一部分  基本概念和算法導(dǎo)引
第1章  算法分析基本概念
  1.1  引言
  1.2  歷史背景
  1.3  二分搜索
  1.4合并兩個已排序的表
  1.5  選擇排序
  1.6  插入排序
  1.7  自底向上合并排序
  1.8時間復(fù)雜性
  1.9空間復(fù)雜陛
  1.10最優(yōu)算法
  1.11如何估計算法運(yùn)行時間
  1.12最壞情況和平均情況的分析
  1.13平攤分析
  1.14輸人大小和問題實(shí)例
  1.15練習(xí)
  1.16參考注釋
第2章  數(shù)學(xué)預(yù)備知識
  2.1  集合、關(guān)系和函數(shù)
  2.2  證明方法
  2.3  對數(shù)
  2.4底函數(shù)和頂函數(shù)
  2.5  階乘和二項式系數(shù)
  2.6  鴿巢原理
  2.7  和式
  2.8  遞推關(guān)系
  2.9  練習(xí)
第3章數(shù)據(jù)結(jié)構(gòu)
  3.1  引言
  3.2  鏈表
  3.3  圖
3.4  樹
  3.5  根樹
  3.6  二叉樹
  3.7  練習(xí)
  3.8  參考注釋
第4章  堆和不相交集數(shù)據(jù)結(jié)構(gòu)
  4.1  引言
  4.2  堆
  4.3不相交集數(shù)據(jù)結(jié)構(gòu)
  4.4  練習(xí)
  4.5  參考注釋
第二部分  基于遞歸的技術(shù)
第5章歸納法
  5.1  引言
  5.2兩個簡單的例子
  5.3  基數(shù)排序
  5.4  整數(shù)冪
  5.5  多項式求值(Homer規(guī)則)
  5.6  生成排列
  5.7尋找多數(shù)元素
  5.8  練習(xí)
  5.9  參考注釋
第6章  分治
  6.1  引言
  6.2  二分搜索
  6.3  合并排序
  6.4  分治范式
  6.5  尋找中項和第K小元素
  6.6  快速排序
  6.7大整數(shù)乘法
  6.8  矩陣乘法
  6.9最近點(diǎn)對問題
  6.10練習(xí)
  6.11參考注釋
第7章動態(tài)規(guī)劃
  7.1  引言
  7.2最長公共子序列問題
  7.3矩陣鏈相乘
    7.4動態(tài)規(guī)劃范式
  7.5  所有點(diǎn)對的最短路徑問題
  7。6  背包問題
  7.7  練習(xí)
  7.8  參考注釋
第三部分  最先割技術(shù)
第8章貪心算法
  8.1  引言
  8.2最短路徑問題
  8.3  最小耗費(fèi)生成樹(Kmskal算法)
  8.4最小耗費(fèi)生成樹(Prim算法)
  8.5  文件壓縮
  8.6  練習(xí)  
  8.7  參考注釋
第9章  圖的遍歷
  9.1  引言
  9.2深度優(yōu)先搜索
  9.3  深度優(yōu)先搜索的應(yīng)用
  9.4廣度優(yōu)先搜索
  9.5  廣度優(yōu)先搜索的應(yīng)用
  9.6  練習(xí)
  9.7  參考注釋
第四部分  問題的復(fù)雜性
第10章  NP完全問題
  10.1  引言
  10.2  P類
  10.3  NP類  
  10.4  NP完全問題  
  10.5  co-NP類
  10.6 NH類
  10.7  四種類之間的關(guān)系
  10.8  練習(xí)
  10.9  參考注釋
第11章  計算復(fù)雜性引論
  11.1  引言
  11.2計算模型：圖靈機(jī)
  11.3  K帶圖靈機(jī)和時間復(fù)雜性
  11.4  離線圖靈機(jī)和空間復(fù)雜性
  11.5  帶壓縮和線性增速
  11.6  復(fù)雜性類之間的關(guān)系
  11.7  歸約
  11.8  完全性
  11.9  多項式時間層次
  11.10練習(xí)
  11.11參考注釋
第12章  下界
  12.1  引言
  12.2  平凡下界
  12.3決策樹模型
  12.4代數(shù)決策樹模型
  12.5線性時間歸約
  12.6  練習(xí)
  12.7參考注釋
第五部分  克服困難性
第13章  回溯法
  13.1  引言
  13.2  3著色問題
  13.3  8皇后問題
  13.4一般回溯方法
  13.5分支限界法
  13.6  練習(xí)
  13.7  參考注釋
第14章  隨機(jī)算法
  14.1  引言
  14.2  LasVegas和MonteCarlo算法
  14.3  隨機(jī)化快速排序
  14.4隨機(jī)化的選擇算法
  14.5  測試串的相等性
  14.6  模式匹配
  14.7  隨機(jī)取樣
  14.8素數(shù)性測試 
  14.9練習(xí)      
  14.10參考注釋
   15章  近似算法
  15.1  引言
  15.2  基本定義
  15.3  差界
  15.4相對性能界
  15.5  多項式近似方案
  15.6完全多項式近似方案
  15.7  練習(xí)
  15.8  參考注釋
第六部分  域指定問題的迭代改進(jìn)
第16章  網(wǎng)絡(luò)流
  16.1  引言
  16.2  預(yù)備知識
  16.3 Ford-Fulkerson方法
  16.4最大容量增值
  16.5最短路徑增值
  16.6  Dinic算法  
  16.7  MPM算法
  16.8  練習(xí)
  16.9  參考注釋
第17章  匹配
  17.1  引言
  17.2  預(yù)備知識
  17.3  網(wǎng)絡(luò)流方法
  17.4  二分圖的匈牙利樹方法
  17.5  一般圖中的最大匹配
  17.6  二分圖的O(n的2.5次方)算法
  17.7  練習(xí)
  17.8  參考注釋
第七部分  計算幾何技術(shù)
第18章  幾何掃描
  18.1  引言
  18.2幾何預(yù)備知識
  18.3計算線段的交點(diǎn)
  18.4  凸包問題
  18.5計算點(diǎn)集的直徑
  18.6  練習(xí)
  18.7  參考注釋
第19章  Voronoi圖解
  19.1  引言
  19.2最近點(diǎn)Voronoi圖解
  19.3 Vomnoi圖解的應(yīng)用
  19.4最遠(yuǎn)點(diǎn)Voronoi圖解
  19.5  最遠(yuǎn)點(diǎn)Voronoi圖解的應(yīng)用  
  19.6  練習(xí)
  19.7  參考注釋
參考文獻(xiàn)