電磁場與電磁波

第1章 算法引論11.1 算法與程序1
1.2 表達算法的抽象機制1
1.3 描述算法3
1.4 算法復雜性分析13
小結16
習題17
第2章 遞歸與分治策略19
2.1 遞歸的概念19
2.2 分治法的基本思想26
2.3 二分搜索技術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
小結54
習題54
第3章 動態(tài)規(guī)劃61
3.1 矩陣連乘問題62
目 錄算法設計與分析(第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è)調度88
3.9 0-1背包問題92
3.10 最優(yōu)二叉搜索樹98
小結101
習題102
第4章 貪心算法107
4.1 活動安排問題107
4.2 貪心算法的基本要素110
4.2.1 貪心選擇性質111
4.2.2 最優(yōu)子結構性質111
4.2.3 貪心算法與動態(tài)規(guī)劃算法的差異111
4.3 最優(yōu)裝載114
4.4 哈夫曼編碼116
4.4.1 前綴碼117
4.4.2 構造哈夫曼編碼117
4.4.3 哈夫曼算法的正確性119
4.5 單源最短路徑121
4.5.1 算法基本思想121
4.5.2 算法的正確性和計算復雜性123
4.6 最小生成樹125
4.6.1 最小生成樹性質125
4.6.2 Prim算法126
4.6.3 Kruskal算法128
4.7 多機調度問題130
4.8 貪心算法的理論基礎133
4.8.1 擬陣133
4.8.2 帶權擬陣的貪心算法134
4.8.3 任務時間表問題137
小結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è)調度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
小結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è)調度232
小結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
小結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模型的關系297
8.1.6 問題變換與計算復雜性歸約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
小結323
習題323
第9章 近似算法326
9.1 近似算法的性能327
9.2 頂點覆蓋問題的近似算法328
9.3 旅行售貨員問題近似算法329
9.3.1 具有三角不等式性質的旅行售貨員問題330
9.3.2 一般的旅行售貨員問題331
9.4 集合覆蓋問題的近似算法333
9.5 子集和問題的近似算法336
9.5.1 子集和問題的指數(shù)時間算法336
9.5.2 子集和問題的完全多項式時間近似格式337
小結340
習題340
第10章 算法優(yōu)化策略345
10.1 算法設計策略的比較與選擇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 算法復雜性366
10.4 優(yōu)化數(shù)據結構366
10.4.1 帶權區(qū)間最短路問題366
10.4.2 算法設計思想367
10.4.3 算法實現(xiàn)方案369
10.4.4 并查集373
10.4.5 可并優(yōu)先隊列376
10.5 優(yōu)化搜索策略380
小結388
習題388
第11章 在線算法設計391
11.1 在線算法設計的基本概念391
11.2 頁調度問題393
11.3 勢函數(shù)分析395
11.4 k服務問題397
11.4.1 競爭比的下界397
11.4.2 平衡算法399
11.4.3 對稱移動算法399
11.5 Steiner樹問題403
11.6 在線任務調度405
11.7 負載平衡406
小結407
習題407
詞匯索引409
參考文獻415