圖書簡介
為了適應培養我國21世紀計算機各類人才的需要，結合我國高等學校教育工作的現狀，立足培養學生能跟上國際計算機科學技術的發展水平，更新教學內容和教學方法，提高教學質量，本書以算法設計策略為知識單元，系統地介紹計算機算法的設計方法與分析技巧，以期為計算機科學與技術學科的學生提供廣泛而堅實的計算機算法基礎知識。
本書內容豐富， 觀點新穎，理論聯繫實際。不僅可用作高等學校計算機專業本科生和研究生學習計算機算法設計的教材，而且也適合廣大工程技術人員和自學讀者學習參考。
圖書目錄
第1章算法引論11.1算法與程式1
1.2表達算法的抽象機制1
1.3描述算法3
1.4算法複雜性分析11
小結14
習題14
第2章遞歸與分治策略16
2.1遞歸的概念16
2.2分治法的基本思想22
2.3二分搜尋技術23
2.4大整數的乘法24
2.5Strassen矩陣乘法25
2.6棋盤覆蓋26
2.7合併排序28
2.8快速排序30
2.9線性時間選擇33
2.10最接近點對問題36
2.11循環賽日程表43
小結44
習題45
第3章動態規劃50
3.1矩陣連乘問題50
3.2動態規划算法的基本要素55
3.3最長公共子序列58
3.4凸多邊形最優三角剖分61
3.5多邊形遊戲64目錄算法設計與分析(第3版)3.6圖像壓縮67
3.7電路布線70
3.8流水作業調度72
3.90\|1背包問題75
3.10最優二叉搜尋樹80
小結83
習題84
第4章貪心算法85
4.1活動安排問題85
4.2貪心算法的基本要素88
4.2.1貪心選擇性質88
4.2.2最優子結構性質88
4.2.3貪心算法與動態規划算法的差異89
4.3最優裝載91
4.4哈夫曼編碼92
4.4.1前綴碼93
4.4.2構造哈夫曼編碼93
4.4.3哈夫曼算法的正確性95
4.5單源最短路徑97
4.5.1算法基本思想97
4.5.2算法的正確性和計算複雜性99
4.6最小生成樹100
4.6.1最小生成樹性質100
4.6.2Prim算法100
4.6.3Kruskal算法102
4.7多機調度問題104
4.8貪心算法的理論基礎106
4.8.1擬陣107
4.8.2帶權擬陣的貪心算法108
4.8.3任務時間表問題110
小結113
習題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批處理作業調度126
5.4符號三角形問題128
5.5n後問題130
5.601背包問題133
5.7最大團問題136
5.8圖的m著色問題138
5.9旅行售貨員問題140
5.10圓排列問題142
5.11電路板排列問題144
5.12連續郵資問題147
5.13回溯法的效率分析149
小結152
習題152
第6章分支限界法153
6.1分支限界法的基本思想153
6.2單源最短路徑問題156
6.3裝載問題158
6.4布線問題167
6.501背包問題171
6.6最大團問題175
6.7旅行售貨員問題178
6.8電路板排列問題182
6.9批處理作業調度184
小結189
習題189
第7章機率算法190
7.1隨機數191
7.2數值機率算法193
7.2.1用隨機投點法計算π值193
7.2.2計算定積分194
7.2.3解非線性方程組196
7.3舍伍德算法198
7.3.1線性時間選擇算法198
7.3.2跳躍表200
7.4拉斯維加斯算法205
7.4.1n後問題206
7.4.2整數因子分解209
7.5蒙特卡羅算法211
7.5.1蒙特卡羅算法的基本思想211
7.5.2主元素問題213
7.5.3素數測試214
小結217
習題217
第8章NP完全性理論221
8.1計算模型221
8.1.1隨機存取機RAM222
8.1.2隨機存取存儲程式機RASP228
8.1.3RAM模型的變形與簡化231
8.1.4圖靈機235
8.1.5圖靈機模型與RAM模型的關係236
8.1.6問題變換與計算複雜性歸約238
8.2P類與NP類問題239
8.2.1非確定性圖靈機239
8.2.2P類與NP類語言240
8.2.3多項式時間驗證241
8.3NP完全問題243
8.3.1多項式時間變換243
8.3.2Cook定理244
8.4一些典型的NP完全問題247
8.4.1合取範式的可滿足性問題247
8.4.23元合取範式的可滿足性問題248
8.4.3團問題249
8.4.4頂點覆蓋問題250
8.4.5子集和問題251
8.4.6哈密頓迴路問題252
8.4.7旅行售貨員問題256
小結256
習題257
第9章近似算法259
9.1近似算法的性能259
9.2頂點覆蓋問題的近似算法260
9.3旅行售貨員問題近似算法262
9.3.1具有三角不等式性質的旅行售貨員問題262
9.3.2一般的旅行售貨員問題263
9.4集合覆蓋問題的近似算法264
9.5子集和問題的近似算法267
9.5.1子集和問題的指數時間算法267
9.5.2子集和問題的完全多項式時間近似格式268
小結270
習題270
第10章算法最佳化策略273
10.1算法設計策略的比較與選擇273
10.1.1最大子段和問題的簡單算法273
10.1.2最大子段和問題的分治算法274
10.1.3最大子段和問題的動態規划算法275
10.1.4最大子段和問題與動態規划算法的推廣276
10.2動態規劃加速原理279
10.2.1貨物儲運問題279
10.2.2算法及其最佳化279
10.3問題的算法特徵283
10.3.1貪心策略283
10.3.2對貪心策略的改進283
10.3.3算法三部曲285
10.3.4算法實現285
10.3.5算法複雜性290
10.4最佳化數據結構291
10.4.1帶權區間最短路問題291
10.4.2算法設計思想291
10.4.3算法實現方案293
10.4.4並查集296
10.4.5可並優先佇列298
10.5最佳化搜尋策略302
小結308
習題309
第11章線上算法設計310
11.1線上算法設計的基本概念310
11.2頁調度問題312
11.3勢函式分析314
11.4k服務問題315
11.4.1競爭比的下界315
11.4.2平衡算法316
11.4.3對稱移動算法317
11.5Steiner樹問題320
11.6線上任務調度321
11.7負載平衡322
小結323
習題324
辭彙索引325
參考文獻330
