電磁場(chǎng)與電磁波

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