算法設計與分析（第3版）

《算法設計與分析（第3版）》是2015年由清華大學出版社出版的圖書。

基本介紹

• 書名：算法設計與分析（第3版）
• 作者：王曉東
• ISBN：9787302348641
• 定價：35元
• 出版社：清華大學出版社
• 出版時間：2015-1-15
• 裝幀：平裝

圖書簡介

為了適應培養我國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.601背包問題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.501背包問題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