電磁場與電磁波

第1章 算法引論11.1 算法與程序1
1.2 表達算法的抽象機制1
1.3 描述算法3
1.4 算法復(fù)雜性分析13
小結(jié)16
習題17
第2章 遞歸與分治策略19
2.1 遞歸的概念19
2.2 分治法的基本思想26
2.3 二分搜索技術(shù)27
2.4 大整數(shù)的乘法28
2.5 Strassen矩陣乘法30
2.6 棋盤覆蓋32
2.7 合并排序34
2.8 快速排序37
2.9 線性時間選擇39
2.10 最接近點對問題43
2.11 循環(huán)賽日程表53
小結(jié)54
習題54
第3章 動態(tài)規(guī)劃61
3.1 矩陣連乘問題62
目 錄算法設(shè)計與分析(第2版)3.2 動態(tài)規(guī)劃算法的基本要素67
3.3 最長公共子序列71
3.4 凸多邊形最優(yōu)三角剖分75
3.5 多邊形游戲79
3.6 圖像壓縮82
3.7 電路布線85
3.8 流水作業(yè)調(diào)度88
3.9 0-1背包問題92
3.10 最優(yōu)二叉搜索樹98
小結(jié)101
習題102
第4章 貪心算法107
4.1 活動安排問題107
4.2 貪心算法的基本要素110
4.2.1 貪心選擇性質(zhì)111
4.2.2 最優(yōu)子結(jié)構(gòu)性質(zhì)111
4.2.3 貪心算法與動態(tài)規(guī)劃算法的差異111
4.3 最優(yōu)裝載114
4.4 哈夫曼編碼116
4.4.1 前綴碼117
4.4.2 構(gòu)造哈夫曼編碼117
4.4.3 哈夫曼算法的正確性119
4.5 單源最短路徑121
4.5.1 算法基本思想121
4.5.2 算法的正確性和計算復(fù)雜性123
4.6 最小生成樹125
4.6.1 最小生成樹性質(zhì)125
4.6.2 Prim算法126
4.6.3 Kruskal算法128
4.7 多機調(diào)度問題130
4.8 貪心算法的理論基礎(chǔ)133
4.8.1 擬陣133
4.8.2 帶權(quán)擬陣的貪心算法134
4.8.3 任務(wù)時間表問題137
小結(jié)141
習題141
第5章 回溯法146
5.1 回溯法的算法框架146
5.1.1 問題的解空間146
5.1.2 回溯法的基本思想147
5.1.3 遞歸回溯149
5.1.4 迭代回溯150
5.1.5 子集樹與排列樹151
5.2 裝載問題152
5.3 批處理作業(yè)調(diào)度160
5.4 符號三角形問題162
5.5 n后問題165
5.6 0\|1背包問題168
5.7 最大團問題171
5.8 圖的m著色問題174
5.9 旅行售貨員問題177
5.10 圓排列問題179
5.11 電路板排列問題181
5.12 連續(xù)郵資問題185
5.13 回溯法的效率分析187
小結(jié)190
習題191
第6章 分支限界法195
6.1 分支限界法的基本思想195
6.2 單源最短路徑問題198
6.3 裝載問題202
6.4 布線問題211
6.5 0\|1背包問題216
6.6 最大團問題222
6.7 旅行售貨員問題225
6.8 電路板排列問題229
6.9 批處理作業(yè)調(diào)度232
小結(jié)237
習題238
第7章 概率算法240
7.1 隨機數(shù)241
7.2 數(shù)值概率算法244
7.2.1 用隨機投點法計算π值244
7.2.2 計算定積分245
7.2.3 解非線性方程組247
7.3 舍伍德算法250
7.3.1 線性時間選擇算法250
7.3.2 跳躍表252
7.4 拉斯維加斯算法259
7.4.1 n后問題260
7.4.2 整數(shù)因子分解264
7.5 蒙特卡羅算法266
7.5.1 蒙特卡羅算法的基本思想266
7.5.2 主元素問題268
7.5.3 素數(shù)測試270
小結(jié)273
習題273
第8章 NP完全性理論278
8.1 計算模型279
8.1.1 隨機存取機RAM279
8.1.2 隨機存取存儲程序機RASP287
8.1.3 RAM模型的變形與簡化291
8.1.4 圖靈機295
8.1.5 圖靈機模型與RAM模型的關(guān)系297
8.1.6 問題變換與計算復(fù)雜性歸約299
8.2 P類與NP類問題301
8.2.1 非確定性圖靈機301
8.2.2 P類與NP類語言302
8.2.3 多項式時間驗證304
8.3 NP完全問題305
8.3.1 多項式時間變換305
8.3.2 Cook定理307
8.4 一些典型的NP完全問題310
8.4.1 合取范式的可滿足性問題311
8.4.2 3元合取范式的可滿足性問題312
8.4.3 團問題313
8.4.4 頂點覆蓋問題314
8.4.5 子集和問題315
8.4.6 哈密頓回路問題317
8.4.7 旅行售貨員問題322
小結(jié)323
習題323
第9章 近似算法326
9.1 近似算法的性能327
9.2 頂點覆蓋問題的近似算法328
9.3 旅行售貨員問題近似算法329
9.3.1 具有三角不等式性質(zhì)的旅行售貨員問題330
9.3.2 一般的旅行售貨員問題331
9.4 集合覆蓋問題的近似算法333
9.5 子集和問題的近似算法336
9.5.1 子集和問題的指數(shù)時間算法336
9.5.2 子集和問題的完全多項式時間近似格式337
小結(jié)340
習題340
第10章 算法優(yōu)化策略345
10.1 算法設(shè)計策略的比較與選擇345
10.1.1 最大子段和問題的簡單算法345
10.1.2 最大子段和問題的分治算法346
10.1.3 最大子段和問題的動態(tài)規(guī)劃算法348
10.1.4 最大子段和問題與動態(tài)規(guī)劃算法的推廣349
10.2 動態(tài)規(guī)劃加速原理352
10.2.1 貨物儲運問題352
10.2.2 算法及其優(yōu)化353
10.3 問題的算法特征357
10.3.1 貪心策略357
10.3.2 對貪心策略的改進357
10.3.3 算法三部曲359
10.3.4 算法實現(xiàn)360
10.3.5 算法復(fù)雜性366
10.4 優(yōu)化數(shù)據(jù)結(jié)構(gòu)366
10.4.1 帶權(quán)區(qū)間最短路問題366
10.4.2 算法設(shè)計思想367
10.4.3 算法實現(xiàn)方案369
10.4.4 并查集373
10.4.5 可并優(yōu)先隊列376
10.5 優(yōu)化搜索策略380
小結(jié)388
習題388
第11章 在線算法設(shè)計391
11.1 在線算法設(shè)計的基本概念391
11.2 頁調(diào)度問題393
11.3 勢函數(shù)分析395
11.4 k服務(wù)問題397
11.4.1 競爭比的下界397
11.4.2 平衡算法399
11.4.3 對稱移動算法399
11.5 Steiner樹問題403
11.6 在線任務(wù)調(diào)度405
11.7 負載平衡406
小結(jié)407
習題407
詞匯索引409
參考文獻415