算法基礎(chǔ)（翻譯版）

第1章 預(yù)備知識1
1.1 簡介1
1.2 什么是算法1
1.3 程序符號4
1.4 數(shù)學(xué)符號5
1.4.1 命題演算5
1.4.2 集合論6
1.4.3 整數(shù)、實數(shù)和區(qū)間7
1.4.4 函數(shù)和關(guān)系7
1.4.5 量詞8
1.4.6 累加與累積9
1.4.7 雜項10
1.5 證明技巧1——反證法11
1.6 證明技巧2——數(shù)學(xué)歸納法12
1.6.1 數(shù)學(xué)歸納法的法則15
1.6.2 不同顏色的馬18
1.6.3 一般化的數(shù)學(xué)歸納法19
1.6.4 構(gòu)造性歸納22
1.7 一些回顧24
1.7.1 極限24
1.7.2 簡單級數(shù)26
1.7.3 基本組合30
1.7.4 概率基礎(chǔ)32
1.8 習(xí)題38
1.9 參考與深入閱讀43
第2章 基本算法45
2.1 簡介45
2.2 問題和實例45
2.3 算法的效率46
2.4 平均和最壞情況分析48
2.5 什么是基本運算？50
2.6 為什么尋求效率？52
2.7 一些例子53
2.7.1 計算行列式的值53
2.7.2 排序53
2.7.3 大整數(shù)的乘法55
2.7.4 計算最大公約數(shù)55
2.7.5 計算斐波納契序列56
2.7.6 傅立葉變換57
2.8 什么時候算法是確定的？58
2.9 習(xí)題58
2.10 參考與深入閱讀61
第3章 漸近記法62
3.1 引言62
3.2 同階記法62
3.3 其他漸近記法67
3.3.1 Ω記法67
3.3.2 Θ記法68
3.4 條件漸近記法69
3.5 具有多個參數(shù)的漸近記法71
3.6 漸近記法的操作71
3.7 習(xí)題72
3.8 參考與深入閱讀75
第4章 算法分析76
4.1 引言76
4.2 分析控制結(jié)構(gòu)76
4.2.1 先后順序76
4.2.2 For循環(huán)76
4.2.3 遞歸調(diào)用78
4.2.4 while和repeat循環(huán)79
4.3 使用標(biāo)稱80
4.4 補充例子82
4.4.1 選擇排序82
4.4.2 插入排序83
4.4.3 歐幾里德算法83
4.4.4 漢諾塔85
4.4.5 計算行列式的值86
4.5 平均情況分析86
4.6 分期分析87
4.6.1 勢函數(shù)88
4.6.2 賬戶戲法90
4.7 求解遞歸式90
4.7.1 推測90
4.7.2 齊次遞歸式92
4.7.3 非齊次遞歸式96
4.7.4 變量變換100
4.7.5 范圍轉(zhuǎn)換105
4.7.6 漸近遞歸式106
4.8 習(xí)題107
4.9 參考與深入閱讀113
第5章 一些數(shù)據(jù)結(jié)構(gòu)114
5.1 數(shù)組、棧和隊列114
5.2 記錄和指針116
5.3 鏈表117
5.4 圖118
5.5 樹119
5.6 關(guān)聯(lián)表124
5.7 堆126
5.8 二項堆132
5.9 不相交集結(jié)構(gòu)136
5.10 習(xí)題141
5.11 參考與深入閱讀144
第6章 貪婪算法146
6.1 找零錢(1)146
6.2 貪婪算法的一般特性147
6.3 圖：最小生成樹148
6.3.1 Kruskal算法150
6.3.2 Prim算法152
6.4 圖：最短路徑154
6.5 背包問題(1)157
6.6 日程安排160
6.6.1 最小化時間160
6.6.2 有期限的日程安排162
6.7 習(xí)題168
6.8 參考與深入閱讀170
第7章 分治算法171
7.1 簡介：大整數(shù)乘法171
7.2 通用模板174
7.3 二分搜索176
7.4 排序178
7.4.1 歸并排序178
7.4.2 快速排序180
7.5 查找中值184
7.6 矩陣乘法188
7.7 求冪189
7.8 綜合：密碼學(xué)簡介192
7.9 習(xí)題194
7.10 參考與深入閱讀200
第8章 動態(tài)規(guī)劃202
8.1 兩個簡單的例子202
8.1.1 計算二項式系數(shù)202
8.1.2 系列賽203
8.2 找零錢(2)205
8.3 最優(yōu)性原則207
8.4 背包問題(2)208
8.5 最短路徑209
8.6 鏈?zhǔn)骄仃嚦朔?11
8.7 使用遞歸214
8.8 存儲函數(shù)216
8.9 習(xí)題217
8.10 參考與深入閱讀221
第9章 搜索圖223
9.1 圖和游戲：簡介223
9.2 遍歷樹228
9.2.1 預(yù)處理228
9.3 深度優(yōu)先搜索：無向圖230
9.3.1 關(guān)節(jié)點232
9.4 深度優(yōu)先搜索：有向圖233
9.4.1 無環(huán)圖：拓撲排序234
9.5 廣度優(yōu)先搜索236
9.6 回溯法239
9.6.1 背包問題(3)240
9.6.2 八皇后問題242
9.6.3 通用模板244
9.7 分支界限244
9.7.1 分配任務(wù)問題245
9.7.2 背包問題(4)248
9.7.3 一般考慮248
9.8 極小化原則248
9.9 習(xí)題251
9.10 參考與深入閱讀256
第10章 概率算法257
10.1 簡介257
10.2 概率不意味著不確定258
10.3 預(yù)期與平均時間259
10.4 生成偽隨機數(shù)259
10.5 數(shù)值概率算法261
10.5.1 Buffon的針261
10.5.2 數(shù)值積分264
10.5.3 概率計數(shù)265
10.6 Monte Carlo算法267
10.6.1 驗證矩陣乘法267
10.6.2 素數(shù)性測試269
10.6.3 一個數(shù)可能是素數(shù)嗎？272
10.6.4 隨機優(yōu)勢的擴大274
10.7 Las Vegas算法276
10.7.1 重訪八皇后問題278
10.7.2 概率選擇與排序281
10.7.3 通用散列282
10.7.4 大整數(shù)分解因數(shù)284
10.8 習(xí)題287
10.9 參考與深入閱讀293
第11章 并行算法295
11.1 并行計算的模型295
11.2 一些基本的技術(shù)297
11.2.1 計算完全二叉樹297
11.2.2 指針倍增298
11.3 工作量與效率301
11.4 圖論的兩個例子303
11.4.1 最短路徑303
11.4.2 連通分量304
11.5 表達式的并行求值308
11.6 并行排序網(wǎng)絡(luò)312
11.6.1 0-1原理313
11.6.2 并行合并網(wǎng)絡(luò)314
11.6.3 改進的排序網(wǎng)絡(luò)315
11.7 并行排序316
11.7.1 預(yù)備工作316
11.7.2 核心思想317
11.7.3 算法317
11.7.4 細節(jié)概述318
11.8 EREW和CRCW p-ram的一些注意點319
11.9 分布式計算320
11.10 習(xí)題321
11.11 參考與深入閱讀323
第12章 計算復(fù)雜性324
12.1 引言：一個簡單的例子324
12.2 信息理論論證325
12.2.1 排序的復(fù)雜性327
12.2.2 復(fù)雜性對算法設(shè)計的幫助330
12.3 對手論證331
12.3.1 查找數(shù)組的最大項332
12.3.2 測試圖的連通性333
12.3.3 中值再考察333
12.4 線性歸約335
12.4.1 形式定義337
12.4.2 矩陣問題中的歸約338
12.4.3 最短路徑問題中的歸約342
12.5 NP完全性介紹344
12.5.1 P和NP類345
12.5.2 多項式歸約348
12.5.3 NP完全性問題351
12.5.4 一些NP完全性證明353
12.5.5 NP難問題356
12.5.6 非確定性算法357
12.6 復(fù)雜性類縱覽359
12.7 習(xí)題362
12.8 參考與深入閱讀366
第13章 啟發(fā)式和近似算法369
13.1 啟發(fā)式算法369
13.1.1 圖著色369
13.1.2 旅行商371
13.2 近似算法372
13.2.1 度量旅行商372
13.2.2 背包問題（5）374
13.2.3 裝箱問題375
13.3 NP難近似問題377
13.3.1 絕對難近似問題378
13.3.2 相對難近似問題379
13.4 相同，惟一不同380
13.5 近似模式383
13.5.1 重訪裝箱問題383
13.5.2 背包問題（6）384
13.6 習(xí)題386
13.7 參考與深入閱讀389
參考文獻390