算法設(shè)計與分析（第4版）

目錄CONTENTS
第1章算法引論1
1.1算法與程序1
1.2表達(dá)算法的抽象機(jī)制1
1.3描述算法3
1.4算法復(fù)雜性分析10
小結(jié)13
習(xí)題14
第2章遞歸與分治策略16
2.1遞歸的概念16
2.2分治法的基本思想21
2.3二分搜索技術(shù)23
2.4大整數(shù)的乘法23
2.5Strassen矩陣乘法24
2.6棋盤覆蓋26
2.7合并排序28
2.8快速排序30
2.9線性時間選擇33
2.10最接近點(diǎn)對問題35
2.11循環(huán)賽日程表43
小結(jié)44
習(xí)題44
第3章動態(tài)規(guī)劃50
3.1矩陣連乘問題50
3.2動態(tài)規(guī)劃算法的基本要素55
3.3最長公共子序列58
3.4凸多邊形最優(yōu)三角剖分61
3.5多邊形游戲64
3.6圖像壓縮67
3.7電路布線69
3.8流水作業(yè)調(diào)度72
3.90\\|1背包問題75
3.10最優(yōu)二叉搜索樹80
小結(jié)83
習(xí)題83
目錄算法設(shè)計與分析(第4版)第4章貪心算法85
4.1活動安排問題85
4.2貪心算法的基本要素88
4.2.1貪心選擇性質(zhì)88
4.2.2最優(yōu)子結(jié)構(gòu)性質(zhì)89
4.2.3貪心算法與動態(tài)規(guī)劃算法的差異89
4.3最優(yōu)裝載91
4.4哈夫曼編碼92
4.4.1前綴碼93
4.4.2構(gòu)造哈夫曼編碼93
4.4.3哈夫曼算法的正確性95
4.5單源最短路徑96
4.5.1算法基本思想97
4.5.2算法的正確性和計算復(fù)雜性98
4.6最小生成樹99
4.6.1最小生成樹性質(zhì)99
4.6.2Prim算法100
4.6.3Kruskal算法102
4.7多機(jī)調(diào)度問題104
4.8貪心算法的理論基礎(chǔ)106
4.8.1擬陣106
4.8.2帶權(quán)擬陣的貪心算法107
4.8.3任務(wù)時間表問題109
小結(jié)113
習(xí)題113
第5章回溯法115
5.1回溯法的算法框架115
5.1.1問題的解空間115
5.1.2回溯法的基本思想116
5.1.3遞歸回溯117
5.1.4迭代回溯118
5.1.5子集樹與排列樹119
5.2裝載問題120
5.3批處理作業(yè)調(diào)度126
5.4符號三角形問題128
5.5n后問題130
5.601背包問題133
5.7最大團(tuán)問題136
5.8圖的m著色問題138
5.9旅行售貨員問題140
5.10圓排列問題142
5.11電路板排列問題144
5.12連續(xù)郵資問題147
5.13回溯法的效率分析149
小結(jié)152
習(xí)題152
第6章分支限界法153
6.1分支限界法的基本思想153
6.2單源最短路徑問題156
6.3裝載問題158
6.4布線問題166
6.501背包問題170
6.6最大團(tuán)問題175
6.7旅行售貨員問題178
6.8電路板排列問題181
6.9批處理作業(yè)調(diào)度184
小結(jié)189
習(xí)題189
第7章概率算法190
7.1隨機(jī)數(shù)191
7.2數(shù)值概率算法193
7.2.1用隨機(jī)投點(diǎn)法計算π值193
7.2.2計算定積分194
7.2.3解非線性方程組195
7.3舍伍德算法197
7.3.1線性時間選擇算法198
7.3.2跳躍表200
7.4拉斯維加斯算法205
7.4.1n后問題206
7.4.2整數(shù)因子分解209
7.5蒙特卡羅算法211
7.5.1蒙特卡羅算法的基本思想211
7.5.2主元素問題213
7.5.3素數(shù)測試214
小結(jié)217
習(xí)題217
第8章NP完全性理論與近似算法221
8.1P類與NP類問題221
8.1.1非確定性圖靈機(jī)222
8.1.2P類與NP類語言222
8.1.3多項式時間驗(yàn)證224
8.2NP完全問題225
8.2.1多項式時間變換225
8.2.2Cook定理226
8.3一些典型的NP完全問題229
8.3.1合取范式的可滿足性問題230
8.3.23元合取范式的可滿足性問題230
8.3.3團(tuán)問題231
8.3.4頂點(diǎn)覆蓋問題232
8.3.5子集和問題233
8.3.6哈密頓回路問題235
8.3.7旅行售貨員問題238
8.4近似算法的性能238
8.5頂點(diǎn)覆蓋問題的近似算法240
8.6旅行售貨員問題近似算法241
8.6.1具有三角不等式性質(zhì)的旅行售貨員問題242
8.6.2一般的旅行售貨員問題243
8.7集合覆蓋問題的近似算法244
8.8子集和問題的近似算法246
8.8.1子集和問題的指數(shù)時間算法247
8.8.2子集和問題的完全多項式時間近似格式247
小結(jié)250
習(xí)題250
第9章串與序列的算法253
9.1子串搜索算法253
9.1.1串的基本概念253
9.1.2KMP算法255
9.1.3RabinKarp算法258
9.1.4多子串搜索與AC自動機(jī)260
9.2后綴數(shù)組與最長公共子串266
9.2.1后綴數(shù)組的基本概念266
9.2.2構(gòu)造后綴數(shù)組的倍前綴算法267
9.2.3構(gòu)造后綴數(shù)組的DC3分治法270
9.2.4最長公共前綴數(shù)組與最長公共擴(kuò)展算法274
9.2.5最長公共子串算法276
9.3序列比較算法277
9.3.1編輯距離算法277
9.3.2最長公共單調(diào)子序列280
9.3.3有約束最長公共子序列281
小結(jié)284
習(xí)題285
第10章算法優(yōu)化策略288
10.1算法設(shè)計策略的比較與選擇288
10.1.1最大子段和問題的簡單算法288
10.1.2最大子段和問題的分治算法289
10.1.3最大子段和問題的動態(tài)規(guī)劃算法291
10.1.4最大子段和問題與動態(tài)規(guī)劃算法的推廣291
10.2動態(tài)規(guī)劃加速原理294
10.2.1貨物儲運(yùn)問題294
10.2.2算法及其優(yōu)化295
10.3問題的算法特征298
10.3.1貪心策略298
10.3.2對貪心策略的改進(jìn)299
10.3.3算法三部曲299
10.3.4算法實(shí)現(xiàn)300
10.3.5算法復(fù)雜性305
10.4優(yōu)化數(shù)據(jù)結(jié)構(gòu)306
10.4.1帶權(quán)區(qū)間最短路問題306
10.4.2算法設(shè)計思想306
10.4.3算法實(shí)現(xiàn)方案308
10.4.4并查集311
10.4.5可并優(yōu)先隊列314
10.5優(yōu)化搜索策略318
小結(jié)324
習(xí)題324
第11章在線算法設(shè)計325
11.1在線算法設(shè)計的基本概念325
11.2頁調(diào)度問題327
11.3勢函數(shù)分析329
11.4k服務(wù)問題330
11.4.1競爭比的下界330
11.4.2平衡算法331
11.4.3對稱移動算法332
11.5Steiner樹問題334
11.6在線任務(wù)調(diào)度336
11.7負(fù)載平衡337
小結(jié)338
習(xí)題338
詞匯索引340
參考文獻(xiàn)345