算法分析與設(shè)計(jì)

第一部分　基礎(chǔ)工具
　第1章　算法分析　
　　1.1　算法的分析方法學(xué)　
　　　1.1.1　偽代碼　
　　　1.1.2　隨機(jī)存取機(jī)(RAM)模型　
　　　1.1.3　統(tǒng)計(jì)基本操作的數(shù)量　
　　　1.1.4　遞歸算法分析　
　　1.2　漸近符號(hào)　
　　　1.2.1　大O符號(hào)
　　　1.2.2　與大“O”相關(guān)的漸近符號(hào)　
　1.2.3　漸近表示的重要性　
　　1.3　數(shù)學(xué)概覽　
　　　1.3.1　求和　
　　　1.3.2　對(duì)數(shù)和指數(shù)　
　　　1.3.3　簡(jiǎn)單證明技術(shù)　
　　　1.3.4　概率基礎(chǔ)　
　　1.4　算法分析案例研究　
　　　1.4.1　二次時(shí)間前綴平均值算法　
　　　1.4.2　線性時(shí)間前綴平均值算法　
　　1.5　平攤方法　
　　　1.5.1　平攤技術(shù)　
　　　1.5.2　擴(kuò)展數(shù)組實(shí)現(xiàn)分析　
　　1.6　實(shí)驗(yàn)　
　　　1.6.1　實(shí)驗(yàn)組織　
　　　1.6.2　數(shù)據(jù)分析和可視化
　　1.7　習(xí)題　　　　
　　　基礎(chǔ)題　　　　
　　　創(chuàng)新題　　　　
　　　程序設(shè)計(jì)　 　　　
　　1.8　本章注記　　　　
　第2章　基本數(shù)據(jù)結(jié)構(gòu)　　　　
　　2.1　棧和隊(duì)列　　　　
　　　2.1.1　?！　　　?br />　　　2.1.2　隊(duì)列　　　　
　　2.2　向量、表和序列　　　　
　　　2.2.1　向量　　　　
　　　2.2.2　表　　　　
　　　2.2.3　序列　
　　2.3　樹　
　　　2.3.1　樹抽象數(shù)據(jù)類型　
　　　2.3.2　樹的遍歷　
　　　2.3.3　二叉樹　
　　　2.3.4　表示樹的數(shù)據(jù)結(jié)構(gòu)　
　　2.4　優(yōu)先隊(duì)列和堆　
　　　2.4.1　優(yōu)先隊(duì)列抽象數(shù)據(jù)類型　
　　　2.4.2　PQ排序、選擇排序和插入排序　
　　　2.4.3　堆數(shù)據(jù)結(jié)構(gòu)　
　　　2.4.4　堆排序　
　　2.5　字典與散列表　
　　　2.5.1　無(wú)序字典ADT　
　　　2.5.2　散列表　
　　　2.5.3　散列函數(shù)　
　　　2.5.4　壓縮映射　
　　　2.5.5　沖突處理模式　
　　　2.5.6　通用散列　
　　2.6　Java示例：堆　
　　2.7　習(xí)題　
　　　基礎(chǔ)題　
　　　創(chuàng)新題　
　　　程序設(shè)計(jì)　
　　2.8　本章注記　
　第3章　查找樹和跳躍表　
　　3.1　有序字典和二叉查找樹　
　　　3.1.1　有序表　
　　　3.1.2　二叉查找樹　
　　　3.1.3　二叉查找樹中的查找　
　　　3.1.4　二叉查找樹中的插入
　　　3.1.5　二叉查找樹中的刪除　
　　　3.1.6　二叉查找樹的性能　
　　3.2　AVL樹　
　　　3.2.1　更新操作　
　　　3.2.2　性能　
　　3.3　深度有界查找樹　
　　　3.3.1　多路查找樹　
　　　3.3.2　(2,4)樹　
　　　3.3.3　紅黑樹　
　　3.4　伸展樹　
　　　3.4.1　伸展　
　　　3.4.2　伸展過(guò)程的平攤分析　
　　3.5　跳躍表　
　　　3.5.1　查找
　　　3.5.2　更新操作　
　　　3.5.3　跳躍表的概率分析　
　　3.6　Java示例：AVL樹和紅黑樹　
　　　3.6.1　AVL樹的Java實(shí)現(xiàn)
　　　3.6.2　紅黑樹的Java實(shí)現(xiàn)
　　3.7　習(xí)題　
　　　基礎(chǔ)題　
　　　創(chuàng)新題　
　　　程序設(shè)計(jì)　
　　3.8　本章注記　
　第4章　排序、集合和選擇
　　4.1　歸并排序　
　　　4.1.1　分治法　
　　　4.1.2　歸并排序和遞歸方程
　　4.2　集合抽象數(shù)據(jù)類型　
　　　4.2.1　簡(jiǎn)單的集合實(shí)現(xiàn)
　　　4.2.2　具有union-find操作的劃分　
　　　4.2.3　基于樹的劃分實(shí)現(xiàn)
　　4.3　快速排序　
　　4.4　基于比較的排序下界
　　4.5　桶排序和基數(shù)排序　
　　　4.5.1　桶排序　
　　　4.5.2　基數(shù)排序　
　　4.6　比較排序算法　
　　4.7　選擇　
　　　4.7.1　剪枝-查找法　
　　　4.7.2　隨機(jī)化快速選擇　
　　　4.7.3　隨機(jī)化快速選擇分析　
　　4.8　Java示例：原位快速排序　
　　4.9　習(xí)題　
　　　基礎(chǔ)題　
　　　創(chuàng)新題　
　　　程序設(shè)計(jì)　
　　4.10　本章注記
　第5章　基本技術(shù)　
　　5.1　貪心法　
　　　5.1.1　背包問(wèn)題　
　　　5.1.2　任務(wù)調(diào)度　
　　5.2　分治法　
　　　5.2.1　分治遞歸方程　
　　　5.2.2　整數(shù)相乘　
　　　5.2.3　矩陣相乘　
　　5.3　動(dòng)態(tài)規(guī)劃　
　　　5.3.1　矩陣鏈乘　
　　　5.3.2　一般技術(shù)　
　　　5.3.3　0-1背包問(wèn)題
　　5.4　習(xí)題　
　　　基礎(chǔ)題　
　　　創(chuàng)新題　
　　　程序設(shè)計(jì)　
　　5.5　本章注記　
第二部分　圖算法
　第6章　圖　
　　6.1　圖抽象數(shù)據(jù)類型　
　　6.2　圖的數(shù)據(jù)結(jié)構(gòu)
　　　6.2.1　邊表結(jié)構(gòu)　
　　　6.2.2　鄰接表結(jié)構(gòu)
　　　6.2.3　鄰接矩陣結(jié)構(gòu)　
　　6.3　圖的遍歷　
　　　6.3.1　深度優(yōu)先查找　
　　　6.3.2　雙連通分量　
　　　6.3.3　廣度優(yōu)先查找　
　　6.4　有向圖
　　　6.4.1　遍歷有向圖
　　　6.4.2　傳遞閉包　
　　　6.4.3　DFS和垃圾收集　
　　　6.4.4　有向無(wú)環(huán)圖　
　　6.5　Java示例：深度優(yōu)先查找
　　　6.5.1　修飾模式　
　　　6.5.2　DFS引擎
　　　6.5.3　模板方法設(shè)計(jì)模式　
　　6.6　習(xí)題　
　　　基礎(chǔ)題　
　　　創(chuàng)新題　
　　　程序設(shè)計(jì)　
　　6.7　本章注記　
　第7章　加權(quán)圖　
　　7.1　單源點(diǎn)最短路徑　
　　　7.1.1　Dijkstra算法
　　　7.1.2　Bellman-Ford最短路徑算法　
　　　7.1.3　有向無(wú)環(huán)圖中的最短路徑　
　　7.2　所有頂點(diǎn)對(duì)之間的最短路徑　
　　　7.2.1　動(dòng)態(tài)規(guī)劃最短路徑算法　
　　　7.2.2　利用矩陣相乘計(jì)算最短路徑　
　　7.3　最小生成樹　
　　　7.3.1　Kruskal算法　
　　　7.3.2　Prim-Jarník算法
　　　7.3.3　Bar?vka算法　
　　　7.3.4　MST算法比較
　　7.4　Java示例：Dijkstra算法
　　7.5　習(xí)題　
　　　基礎(chǔ)題　
　　　創(chuàng)新題　
　　程序設(shè)計(jì)
　　7.6　本章注記　
　第8章　網(wǎng)絡(luò)流和匹配
　　8.1　流和割　
　　　8.1.1　流網(wǎng)絡(luò)　
　　　8.1.2　割　
　　8.2　最大流　
　　　8.2.1　剩余容量和增大路徑
　　　8.2.2　Ford-Fulkerson算法　
　　　8.2.3　Ford-Fulkerson算法分析　
　　　8.2.4　Edmonds-Karp算法　
　　8.3　最大二分匹配
　　8.4　最小代價(jià)流　
　　　8.4.1　增大回路　
　　　8.4.2　連續(xù)最短路徑　
　　　8.4.3　修改權(quán)值　
　　8.5　Java示例：最小代價(jià)流　
　　8.6　習(xí)題
　　　基礎(chǔ)題
　　創(chuàng)新題
　　　程序設(shè)計(jì)　
　　8.7　本章注記　
第三部分　因特網(wǎng)算法
　第9章　文本處理　
　　9.1　串和模式匹配算法　
　　　9.1.1　串操作　
　　　9.1.2　蠻力模式匹配　
　　　9.1.3　Boyer-Moore算法　
　　　9.1.4　Knuth-Morris-Pratt算法　
　　9.2　trie　
　　　9.2.1　標(biāo)準(zhǔn)trie　
　　　9.2.2　壓縮trie　
　　　9.2.3　后綴trie　
　　　9.2.4　搜索引擎　
　　9.3　文本壓縮　
　　　9.3.1　赫夫曼編碼算法　
　　　9.3.2　修正貪心法　　　
　　9.4　文本相似性測(cè)試　　　
　　　9.4.1　最長(zhǎng)公共子序列問(wèn)題　　
　　　9.4.2　應(yīng)用動(dòng)態(tài)規(guī)劃求解LCS問(wèn)題　　
　　9.5　習(xí)題　　　　
　　　基礎(chǔ)題　　　　
　　　創(chuàng)新題　　　　
　　　程序設(shè)計(jì)　　　　
　　9.6　本章注記　　　
　第10章　數(shù)論和密碼學(xué)　　　　
　　10.1　與數(shù)有關(guān)的基本算法　　　
　　　10.1.1　基本數(shù)論的一些事實(shí)　　　　
　　　10.1.2　歐幾里得GCD算法　　　
　　　10.1.3　模運(yùn)算　　　　
　　　10.1.4　模指數(shù)運(yùn)算　　
　　　10.1.5　模乘法逆元　　　
　　　10.1.6　素性測(cè)試　　　
　　10.2　密碼計(jì)算　　
　　　10.2.1　對(duì)稱加密模式　
　　　10.2.2　公鑰密碼系統(tǒng)　
　　　10.2.3　RSA密碼系統(tǒng)　　　
　　　10.2.4　El Gamal密碼系統(tǒng)　　　
　　10.3　信息安全算法和協(xié)議　　　　
　　　10.3.1　單向散列函數(shù)　　　
　　　10.3.2　時(shí)間戳和認(rèn)證字典　　　　
　　　10.3.3　硬幣拋擲和比特承諾　　　
　　　10.3.4　安全電子傳輸(SET)協(xié)議　　　
　　　10.3.5　密鑰分發(fā)和交換　　　　
　　10.4　快速傅里葉變換　　　　
　　　10.4.1　本原單位根　　
　　　10.4.2　離散傅里葉變換　　
　　　10.4.3　快速傅里葉變換算法　
　　　10.4.4　大整數(shù)相乘　
　　10.5　Java示例：FFT　
　　10.6　習(xí)題　
　　　基礎(chǔ)題　
　　　創(chuàng)新題　
　　程序設(shè)計(jì)
　　10.7　本章注記　
　第11章　網(wǎng)絡(luò)算法　　　　
　　11.1　復(fù)雜性測(cè)度和模型　　　　
　　　11.1.1　網(wǎng)絡(luò)協(xié)議棧　　　　
　　　11.1.2　消息傳遞模型　　　　
　　　11.1.3　網(wǎng)絡(luò)算法的復(fù)雜性測(cè)度　　　
　　11.2　基本分布式算法　　　　
　　　11.2.1　環(huán)網(wǎng)上的領(lǐng)導(dǎo)人選舉　　
　　　11.2.2　樹網(wǎng)上的領(lǐng)導(dǎo)人選舉　　
　　　11.2.3　廣度優(yōu)先查找　　　
　　　11.2.4　最小生成樹　　　　
　　11.3　廣播路由和單播路由　　　　
　　　11.3.1　廣播路由的洪泛算法　　　　
　　　11.3.2　單播路由的距離矢量算法　　
　　　11.3.3　單播路由的鏈路-狀態(tài)算法　　　
　　11.4　多播路由　　　
　　　11.4.1　逆向路徑轉(zhuǎn)發(fā)　　　　
　　　11.4.2　中心樹　　　　
　　　11.4.3　Steiner樹　　　
　　11.5　習(xí)題　　　　
　　　基礎(chǔ)題　　　　
　　　創(chuàng)新題　　　　
　　　程序設(shè)計(jì)　　　　
　　11.6　本章注記　
第四部分　其他主題
　第12章　計(jì)算幾何　　　
　　12.1　范圍樹　　　　
　　　12.1.1　一維范圍查找　　　
　　　12.1.2　二維范圍查找　　　　
　　12.2　優(yōu)先查找樹　　　　
　　　12.2.1　構(gòu)造一棵優(yōu)先查找樹　　
　　　12.2.2　優(yōu)先查找樹中的查找　　　　
　　　12.2.3　優(yōu)先范圍樹　　　　
　　12.3　四叉樹和k-d樹　
　　　12.3.1　四叉樹　　　
　　　12.3.2　k-d樹　　　　
　　12.4　平面掃描技術(shù)　　　　
　　　12.4.1　正交線段相交　　
　　　12.4.2　查找最近點(diǎn)對(duì)　　　
　　12.5　凸包　　　　
　　　12.5.1　幾何對(duì)象表示　　　
　　　12.5.2　點(diǎn)方位測(cè)試　　　
　　　12.5.3　凸包的基本性質(zhì)　　　
　　　12.5.4　禮品包扎算法　　　　
　　　12.5.5　Graham掃描算法　　
　　12.6　Java示例：凸包　　
　　12.7　習(xí)題　　　　
　　　基礎(chǔ)題　　
　　　創(chuàng)新題　　
　　　程序設(shè)計(jì)　　
　　12.8　本章注記　　　　
　第13章　NP完全性　　　　
　　13.1　P類和NP類　　　　
　　　13.1.1　定義復(fù)雜類P和復(fù)雜類NP　　　
　　　13.1.2　NP中的一些有趣問(wèn)題　　　
　　13.2　NP完全性　　
　　　13.2.1　多項(xiàng)式時(shí)間歸約和NP困難度　
　　　13.2.2　Cook-Levin定理　　　　
　　13.3　重要的NP完全問(wèn)題　　　　
　　　13.3.1　CNF-SAT和3SAT　　　
　　　13.3.2　VERTEX-COVER　　　　
　　　13.3.3　CLIQUE和SET-COVER　　　　
　　　13.3.4　SUBSET-SUM和KNAPSACK　　　　
　　　13.3.5　HAMILTONIAN-CYCLE和TSP　　　　
　　13.4　近似算法　　　
　　　13.4.1　多項(xiàng)式時(shí)間的近似模式　　　
　　　13.4.2　VERTEX-COVER的2-近似算法　　　　
　　　13.4.3　TSP特例的2-近似算法　　　　
　　　13.4.4　SET-COVER的對(duì)數(shù)近似算法　　　　
　　13.5　回溯法和分枝限界法　　　　
　　　13.5.1　回溯法　　　　
　　　13.5.2　分枝限界法　　　　
　　13.6　習(xí)題　　　　
　　　基礎(chǔ)題　　　　
　　　創(chuàng)新題　　　　
　　　程序設(shè)計(jì)　　　　
　　13.7　本章注記　　　　
　第14章　算法框架　　　
　　14.1　外存算法　　　　
　　　14.1.1　分層的存儲(chǔ)器管理　　　　
　　　14.1.2　(a, b)樹和B樹　　　　
　　　14.1.3　外存排序　　　
　　14.2　并行算法　
　　　14.2.1　并行計(jì)算模型　
　　　14.2.2　簡(jiǎn)單并行分治法　　　　
　　　14.2.3　串行子集和Brent定理　　　　
　　　14.2.4　遞歸倍增　　　　
　　　14.2.5　并行歸并和排序　　　
　　　14.2.6　找出凸多邊形的直徑　　
　　14.3　在線算法　　　　
　　　14.3.1　高速緩存算法　　
　　　14.3.2　拍賣策略　　　
　　　14.3.3　競(jìng)爭(zhēng)查找樹　　　
　　14.4　習(xí)題　　
　　　基礎(chǔ)題　　
　　　創(chuàng)新題　　
　　程序設(shè)計(jì)
　　14.5　本章注記　　　
附錄A　有用的數(shù)學(xué)知識(shí)　　　
　A.1　對(duì)數(shù)和指數(shù)　　
　A.2　整型函數(shù)和關(guān)系　
　A.3　求和　
　A.4　有用的數(shù)學(xué)技術(shù)　
參考書目　
索引