現代算法設計與分析 Design and Analysis of Algorithms: A Contemporary Perspective

Sandeep Sen

印度理工學院德里分校計算機科學與工程系教授，印度國家科學院院士，印度科學院院士，
研究領域包括隨機算法、計算幾何、動態圖算法和計算模型等。曾在IBM研究實驗室、
微軟研究實驗室、北卡羅萊納大學教堂山分校等機構擔任訪問研究員。

Amit Kumar

印度理工學院德里分校計算機科學與工程系教授，印度科學院院士，研究領域包括組合優化、調度、圖論和聚類等。
曾任職於貝爾實驗室，並曾在微軟印度研究院和IBM印度研究院擔任訪問教授。

出版者的話
譯者序
前言
致謝

第1章　模型與分析1
　1.1　計算斐波那契數1
　1.2　快速乘法3
　1.3　計算模型3
　1.4　隨機算法簡介4
　　1.4.1　另一種隨機算法6
　1.5　其他計算模型8
　　1.5.1　外部存儲器模型8
　　1.5.2　並行模型8
　拓展閱讀10
　習題10

第2章　概率基礎與尾部不等式13
　2.1　概率基礎13
　2.2　尾部不等式17
　2.3　生成隨機數20
　　2.3.1　生成具有任意分佈的隨機變量21
　　2.3.2　由順序文件生成隨機變量21
　　2.3.3　生成隨機置換23
　拓展閱讀25
　習題25

第3章　熱身問題27
　3.1　計算最大公因子的歐幾里得算法27
　　3.1.1　擴展歐幾里得算法27
　　3.1.2　在密碼學中的應用28
　3.2　尋找第k小的元素28
　　3.2.1　選擇隨機的劃分元29
　　3.2.2　中位數的中位數30
　3.3　詞的排序32
　3.4　可歸並的堆34
　　3.4.1　歸並二項堆35
　3.5　一個簡單的半動態詞典35
　　3.5.1　勢能法與平攤分析36
　3.6　下界37
　拓展閱讀39
　習題39

第4章　優化Ⅰ：蠻力法與貪婪策略42
　4.1　啟發式搜索方法42
　　4.1.1　博弈樹44
　4.2　貪婪算法的框架46
　　4.2.1　最大支撐樹49
　　4.2.2　尋找最小權值子集49
　　4.2.3　一個調度問題50
　4.3　最小支撐樹算法的高效數據結構51
　　4.3.1　並查集的一種簡單數據結構52
　　4.3.2　更快的方案53
　　4.3.3　增長最慢的函數54
　　4.3.4　整合55
　　4.3.5　僅做道路壓縮56
　4.4　其他不同形式的貪婪策略57
　4.5　與貪婪策略的折中58
　4.6　梯度下降59
　　4.6.1　應用63
　拓展閱讀65
　習題66

第5章　優化Ⅱ：動態規劃69
　5.1　背包問題70
　5.2　上下文無關文法的解析71
　5.3　最長單調子序列72
　5.4　函數逼近74
　5.5　最大似然估計的Viterbi算法75
　5.6　樹中的最大權獨立集76
　拓展閱讀76
　習題77

第6章　查找80
　6.1　跳錶——一個簡單的字典80
　　6.1.1　跳錶的構造80
　　6.1.2　分析81
　　6.1.3　更強的尾部估計82
　6.2　樹堆：隨機查找樹83
　6.3　全域哈希86
　　6.3.1　全域哈希函數的存在性88
　6.4　完美哈希函數88
　　6.4.1　將期望界轉換為最差情況的界89
　6.5　一個復雜度為log log N的優先級隊列89
　拓展閱讀91
　習題92

第7章　多維查找與幾何算法94
　7.1　區間樹與範圍樹94
　　7.1.1　一維範圍查找94
　　7.1.2　二維範圍查找96
　7.2　kd樹97
　7.3　優先級查找樹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　期望運行時間106
　7.6　使用持久化數據結構的點定位107
　7.7　增量構造法109
　拓展閱讀111
　習題111

第8章　字符串匹配與指紋函數114
　8.1　RabinKarp指紋字符串查找算法114
　8.2　KMP算法117
　　8.2.1　KMP算法的分析120
　　8.2.2　模式分析120
　8.3　字典樹及其應用121
　拓展閱讀123
　習題123

第9章　快速傅里葉變換及其應用125
　9.1　多項式求值與插值125
　　9.1.1　多項式相乘126
　9.2　CooleyTukey算法126
　9.3　蝶形網絡128
　9.4　SchonageStrassen快速乘法算法129
　9.5　廣義字符串匹配131
　　9.5.1　基於捲積的方法131
　拓展閱讀133
　習題133

第10章　圖算法135
　10.1　深度優先搜索135
　10.2　深度優先搜索的應用138
　　10.2.1　強連通分支138
　　10.2.2　雙連通分支140
　10.3　道路問題142
　　10.3.1　BellmanFord單源最短道路算法143
　　10.3.2　Dijkstra單源最短道路算法143
　　10.3.3　任意兩點之間的最短道路算法145
　10.4　計算賦權圖中的支撐子145
　10.5　全局最小割148
　　10.5.1　收縮算法149
　　10.5.2　最小割的概率149
　拓展閱讀150
　習題151

第11章　最大流及其應用153
　11.1　最大流的性質與算法155
　　11.1.1　最大流與最小割155
　　11.1.2　FordFulkerson算法156
　　11.1.3　EdmondKarp可增廣道路策略157
　　11.1.4　單調性引理及迭代次數的界158
　11.2　最大流的應用159
　　11.2.1　邊不相交的道路159
　　11.2.2　二部圖的匹配159
　　11.2.3　環流問題162
　　11.2.4　項目規劃164
　拓展閱讀165
　習題165

第12章　NP完全性與近似算法168
　12.1　分類與可歸約性170
　12.2　CookLevin定理172
　12.3　常見的NP完全問題173
　12.4　NP完全性的證明175
　　12.4.1　頂點覆蓋及相關問題175
　　12.4.2　圖的3著色問題176
　　12.4.3　背包問題及相關問題177
　12.5　其他重要的復雜度類179
　12.6　使用近似算法處理困難性181
　　12.6.1　最大背包問題182
　　12.6.2　最小集合覆蓋183
　　12.6.3　幾何旅行商問題184
　　12.6.4　3著色問題185
　　12.6.5　最大割問題185
　拓展閱讀186
　習題186

第13章　降維188
　13.1　隨機投影與JohnsonLindenstrauss引理188
　13.2　高斯消元法191
　13.3　奇異值分解及其應用192
　　13.3.1　矩陣代數與SVD定理192
　　13.3.2　使用SVD的低秩近似194
　　13.3.3　低秩近似的應用196
　　13.3.4　聚類問題197
　　13.3.5　SVD定理的證明199
　拓展閱讀200
　習題200

第14章　並行算法201
　14.1　並行計算模型201
　14.2　排序和比較問題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　並行模型之間的關系217
　　14.6.1　網格上的路由218
　拓展閱讀220
　習題220

第15章　層次化存儲結構及高速緩存223
　15.1　層次化存儲模型223
　15.2　矩陣轉置224
　　15.2.1　矩陣乘法225
　15.3　在外部存儲器中進行排序226
　　15.3.1　我們可以改進這個算法嗎227
　15.4　高速緩存參數無關的算法設計228
　　15.4.1　參數無關的矩陣轉置229
　拓展閱讀231
　習題232

第16章　流數據模型233
　16.1　引言233
　16.2　查找流中的頻繁元素233
　16.3　流中的相異元素236
　16.4　頻數矩問題及其應用238
　　16.4.1　均值的中位數241
　　16.4.2　二階頻數矩的特例241
　16.5　流模型下界的證明243
　拓展閱讀244
　習題245

附錄A　遞推關系與生成函數247
參考文獻253