本書不僅講解傳統(tǒng)的算法設(shè)計(jì)策略和技巧，而且關(guān)注算法領(lǐng)域不斷涌現(xiàn)的新概念、新方法和新應(yīng)用，幫助讀者把握技術(shù)熱點(diǎn)及發(fā)展趨勢(shì)。書中引入了降維技術(shù)、并行算法、隨機(jī)算法、層次化存儲(chǔ)結(jié)構(gòu)算法和流算法等新內(nèi)容，大量使用概率分析和隨機(jī)化技術(shù)，并包含眾多新穎的示例，特別是強(qiáng)調(diào)計(jì)算模型和計(jì)算環(huán)境，不再局限于理想化的隨機(jī)存取機(jī)模型。全書內(nèi)容簡(jiǎn)潔明快，并配有豐富的習(xí)題和拓展閱讀資料，適合作為高等院校計(jì)算機(jī)相關(guān)專業(yè)的教材，也適合業(yè)界技術(shù)人員閱讀參考。
出版者的話
譯者序
前言
致謝
第1章 模型與分析1
1.1 計(jì)算斐波那契數(shù)1
1.2 快速乘法3
1.3 計(jì)算模型3
1.4 隨機(jī)算法簡(jiǎn)介4
1.4.1 另一種隨機(jī)算法6
1.5 其他計(jì)算模型8
1.5.1 外部存儲(chǔ)器模型8
1.5.2 并行模型8
拓展閱讀10
習(xí)題10
第2章 概率基礎(chǔ)與尾部不等式13
2.1 概率基礎(chǔ)13
2.2 尾部不等式17
2.3 生成隨機(jī)數(shù)20
2.3.1 生成具有任意分布的隨機(jī)變量21
2.3.2 由順序文件生成隨機(jī)變量21
2.3.3 生成隨機(jī)置換23
拓展閱讀25
習(xí)題25
第3章 熱身問(wèn)題27
3.1 計(jì)算最大公因子的歐幾里得算法27
3.1.1 擴(kuò)展歐幾里得算法27
3.1.2 在密碼學(xué)中的應(yīng)用28
3.2 尋找第k小的元素28
3.2.1 選擇隨機(jī)的劃分元29
3.2.2 中位數(shù)的中位數(shù)30
3.3 詞的排序32
3.4 可歸并的堆34
3.4.1 歸并二項(xiàng)堆35
3.5 一個(gè)簡(jiǎn)單的半動(dòng)態(tài)詞典35
3.5.1 勢(shì)能法與平攤分析36
3.6 下界37
拓展閱讀39
習(xí)題39
第4章 優(yōu)化Ⅰ：蠻力法與貪婪策略42
4.1 啟發(fā)式搜索方法42
4.1.1 博弈樹44
4.2 貪婪算法的框架46
4.2.1 最大支撐樹49
4.2.2 尋找最小權(quán)值子集49
4.2.3 一個(gè)調(diào)度問(wèn)題50
4.3 最小支撐樹算法的高效數(shù)據(jù)結(jié)構(gòu)51
4.3.1 并查集的一種簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)52
4.3.2 更快的方案53
4.3.3 增長(zhǎng)最慢的函數(shù)54
4.3.4 整合55
4.3.5 僅做道路壓縮56
4.4 其他不同形式的貪婪策略57
4.5 與貪婪策略的折中58
4.6 梯度下降59
4.6.1 應(yīng)用63
拓展閱讀65
習(xí)題66
第5章 優(yōu)化Ⅱ：動(dòng)態(tài)規(guī)劃69
5.1 背包問(wèn)題70
5.2 上下文無(wú)關(guān)文法的解析71
5.3 最長(zhǎng)單調(diào)子序列72
5.4 函數(shù)逼近74
5.5 最大似然估計(jì)的Viterbi算法75
5.6 樹中的最大權(quán)獨(dú)立集76
拓展閱讀76
習(xí)題77
第6章 查找80
6.1 跳表——一個(gè)簡(jiǎn)單的字典80
6.1.1 跳表的構(gòu)造80
6.1.2 分析81
6.1.3 更強(qiáng)的尾部估計(jì)82
6.2 樹堆：隨機(jī)查找樹83
6.3 全域哈希86
6.3.1 全域哈希函數(shù)的存在性88
6.4 完美哈希函數(shù)88
6.4.1 將期望界轉(zhuǎn)換為最差情況的界89
6.5 一個(gè)復(fù)雜度為log log N的優(yōu)先級(jí)隊(duì)列89
拓展閱讀91
習(xí)題92
第7章 多維查找與幾何算法94
7.1 區(qū)間樹與范圍樹94
7.1.1 一維范圍查找94
7.1.2 二維范圍查找96
7.2 kd樹97
7.3 優(yōu)先級(jí)查找樹99
7.4 平面凸包101
7.4.1 Jarvis March算法102
7.4.2 Graham掃描算法102
7.4.3 排序與凸包103
7.5 快速凸包算法104
7.5.1 分析105
7.5.2 期望運(yùn)行時(shí)間106
7.6 使用持久化數(shù)據(jù)結(jié)構(gòu)的點(diǎn)定位107
7.7 增量構(gòu)造法109
拓展閱讀111
習(xí)題111
第8章 字符串匹配與指紋函數(shù)114
8.1 RabinKarp指紋字符串查找算法114
8.2 KMP算法117
8.2.1 KMP算法的分析120
8.2.2 模式分析120
8.3 字典樹及其應(yīng)用121
拓展閱讀123
習(xí)題123
第9章 快速傅里葉變換及其應(yīng)用125
9.1 多項(xiàng)式求值與插值125
9.1.1 多項(xiàng)式相乘126
9.2 CooleyTukey算法126
9.3 蝶形網(wǎng)絡(luò)128
9.4 SchonageStrassen快速乘法算法129
9.5 廣義字符串匹配131
9.5.1 基于卷積的方法131
拓展閱讀133
習(xí)題133
第10章 圖算法135
10.1 深度優(yōu)先搜索135
10.2 深度優(yōu)先搜索的應(yīng)用138
10.2.1 強(qiáng)連通分支138
10.2.2 雙連通分支140
10.3 道路問(wèn)題142
10.3.1 BellmanFord單源最短道路算法143
10.3.2 Dijkstra單源最短道路算法143
10.3.3 任意兩點(diǎn)之間的最短道路算法145
10.4 計(jì)算賦權(quán)圖中的支撐子145
10.5 全局最小割148
10.5.1 收縮算法149
10.5.2 最小割的概率149
拓展閱讀150
習(xí)題151
第11章 最大流及其應(yīng)用153
11.1 最大流的性質(zhì)與算法155
11.1.1 最大流與最小割155
11.1.2 FordFulkerson算法156
11.1.3 EdmondKarp可增廣道路策略157
11.1.4 單調(diào)性引理及迭代次數(shù)的界158
11.2 最大流的應(yīng)用159
11.2.1 邊不相交的道路159
11.2.2 二部圖的匹配159
11.2.3 環(huán)流問(wèn)題162
11.2.4 項(xiàng)目規(guī)劃164
拓展閱讀165
習(xí)題165
第12章 NP完全性與近似算法168
12.1 分類與可歸約性170
12.2 CookLevin定理172
12.3 常見的NP完全問(wèn)題173
12.4 NP完全性的證明175
12.4.1 頂點(diǎn)覆蓋及相關(guān)問(wèn)題175
12.4.2 圖的3著色問(wèn)題176
12.4.3 背包問(wèn)題及相關(guān)問(wèn)題177
12.5 其他重要的復(fù)雜度類179
12.6 使用近似算法處理困難性181
12.6.1 最大背包問(wèn)題182
12.6.2 最小集合覆蓋183
12.6.3 幾何旅行商問(wèn)題184
12.6.4 3著色問(wèn)題185
12.6.5 最大割問(wèn)題185
拓展閱讀186
習(xí)題186
第13章 降維188
13.1 隨機(jī)投影與JohnsonLindenstrauss引理188
13.2 高斯消元法191
13.3 奇異值分解及其應(yīng)用192
13.3.1 矩陣代數(shù)與SVD定理192
13.3.2 使用SVD的低秩近似194
13.3.3 低秩近似的應(yīng)用196
13.3.4 聚類問(wèn)題197
13.3.5 SVD定理的證明199
拓展閱讀200
習(xí)題200
第14章 并行算法201
14.1 并行計(jì)算模型201
14.2 排序和比較問(wèn)題202
14.2.1 尋找最大值202
14.2.2 排序204
14.3 并行前綴208
14.4 基本的圖算法212
14.4.1 列表排名212
14.4.2 連通分支214
14.5 基本的幾何算法216
14.6 并行模型之間的關(guān)系217
14.6.1 網(wǎng)格上的路由218
拓展閱讀220
習(xí)題220
第15章 層次化存儲(chǔ)結(jié)構(gòu)及高速緩存223
15.1 層次化存儲(chǔ)模型223
15.2 矩陣轉(zhuǎn)置224
15.2.1 矩陣乘法225
15.3 在外部存儲(chǔ)器中進(jìn)行排序226
15.3.1 我們可以改進(jìn)這個(gè)算法嗎227
15.4 高速緩存參數(shù)無(wú)關(guān)的算法設(shè)計(jì)228
15.4.1 參數(shù)無(wú)關(guān)的矩陣轉(zhuǎn)置229
拓展閱讀231
習(xí)題232
第16章 流數(shù)據(jù)模型233
16.1 引言233
16.2 查找流中的頻繁元素233
16.3 流中的相異元素236
16.4 頻數(shù)矩問(wèn)題及其應(yīng)用238
16.4.1 均值的中位數(shù)241
16.4.2 二階頻數(shù)矩的特例241
16.5 流模型下界的證明243
拓展閱讀244
習(xí)題245
附錄A 遞推關(guān)系與生成函數(shù)247
參考文獻(xiàn)253
書單推薦
