複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/算法設計與分析（第4版）/23264889
複製
複製成功

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

鎖定
《算法設計與分析（第4版）》是由王曉東編著，清華大學出版社2018年10月出版的普通高等教育“十一五”國家級規劃教材、21世紀大學本科計算機專業系列教材。該書既可用作高等學校計算機專業本科生和研究生學習計算機算法設計的教材，而且也適合工程技術人員和自學讀者學習參考。 [1] 
全書共分11章，由算法引論、遞歸與分治策略、動態規劃、章貪心算法、回溯法、分支限界法、概率算法、NP完全性理論與近似算法、串與序列的算法、算法優化策略、在線算法設計組成。 [2] 
中文名
算法設計與分析（第4版）
作    者
王曉東
類    別
21世紀大學本科計算機專業系列教材等
出版社
清華大學出版社
出版時間
2018年10月1日
開    本
185mm×260mm
裝    幀
平裝
ISBN
9787302510109
字    數
550千字

目錄

  1. 1 成書過程
  2. ▪ 修訂過程
  3. ▪ 出版工作
  1. 2 內容簡介
  2. 3 教材目錄
  3. 4 教學資源
  1. 5 教材特色
  2. 6 作者簡介

算法設計與分析（第4版）成書過程

算法設計與分析（第4版）修訂過程

為了適應培養中國21世紀計算機各類人才的需要，結合中國高等學校教育工作的現狀，立足培養學生能跟上國際計算機科學技術的發展水平，更新教學內容和教學方法，提高教學質量，作者編寫了該書。
《算法設計與分析（第4版）》按照教育部制定的“計算機科學與技術專業規範的教學大綱”編寫，在前三版的基礎下作了相應修改，按照國際計算機學科的教學要求進行整編。 [1]  [3] 

算法設計與分析（第4版）出版工作

《算法設計與分析（第4版）》是在21世紀大學本科計算機專業系列教材編委會的指導下完成出版。
2018年10月1日，《算法設計與分析（第4版）》由清華大學出版社出版。 [4] 
出版工作人員　
責任編輯
封面設計
責任校對
責任印製
張瑞慶
何鳳霞
梁毅
沈露

算法設計與分析（第4版）內容簡介

《算法設計與分析（第4版）》以算法設計策略為知識單元，系統地介紹計算機算法的設計方法與分析技巧，以期為計算機科學與技術學科的學生提供廣泛而堅實的計算機算法基礎知識。 [3] 
第1章中首先介紹算法的基本概念，接着簡要闡述算法的計算複雜性和算法的描述，然後圍繞設計算法常用的基本設計策略組織第2章至第10章的內容。第2章介紹遞歸與分治策略，這是設計有效算法常用的策略，是必須掌握的方法。第3章是動態規劃算法，以實例詳述動態規劃算法的設計思想、適用性以及算法的設計要點。第4章介紹貪心算法，它與動態規劃算法的設計思想有一定的聯繫。第5章和第6章分別介紹回溯法和分支限界法，這兩章所介紹的算法適合處理難解問題。第7章介紹概率算法，對許多難解問題提供解決途徑。第8章介紹NP完全性理論和解NP難問題的近似算法。第9章介紹有關串和序列的算法。第10章通過實例介紹算法設計中常用的算法優化策略。第11章介紹算法設計中較新的研究領域——在線算法設計。 [5] 

算法設計與分析（第4版）教材目錄

第1章算法引論1
7.2.3解非線性方程組195
1.1算法與程序1
7.3舍伍德算法197
1.2表達算法的抽象機制1
7.3.1線性時間選擇算法198
1.3描述算法3
7.3.2跳躍表200
1.4算法複雜性分析10
7.4拉斯維加斯算法205
小結13
7.4.1n後問題206
習題14
7.4.2整數因子分解209
第2章遞歸與分治策略16
7.5蒙特卡羅算法211
2.1遞歸的概念16
7.5.1蒙特卡羅算法的基本思想211
2.2分治法的基本思想21
7.5.2主元素問題213
2.3二分搜索技術23
7.5.3素數測試214
2.4大整數的乘法23
小結217
2.5Strassen矩陣乘法24
習題217
2.6棋盤覆蓋26
第8章NP完全性理論與近似算法221
2.7合併排序28
8.1P類與NP類問題221
2.8快速排序30
8.1.1非確定性圖靈機222
2.9線性時間選擇33
8.1.2P類與NP類語言222
2.10最接近點對問題35
8.1.3多項式時間驗證224
2.11循環賽日程表43
8.2NP完全問題225
小結44
8.2.1多項式時間變換225
習題44
8.2.2Cook定理226
第3章動態規劃50
8.3一些典型的NP完全問題229
3.1矩陣連乘問題50
8.3.1合取範式的可滿足性問題230
3.2動態規劃算法的基本要素55
8.3.23元合取範式的可滿足性問題230
3.3最長公共子序列58
8.3.3團問題231
3.4凸多邊形最優三角剖分61
8.3.4頂點覆蓋問題232
3.5多邊形遊戲64
8.3.5子集和問題233
3.6圖像壓縮67
8.3.6哈密頓迴路問題235
3.7電路佈線69
8.3.7旅行售貨員問題238
3.8流水作業調度72
8.4近似算法的性能238
3.90\|1揹包問題75
8.5頂點覆蓋問題的近似算法240
3.10最優二叉搜索樹80
8.6旅行售貨員問題近似算法241
小結83
8.6.1具有三角不等式性質的旅行售貨員問題242
習題83
8.6.2一般的旅行售貨員問題243
第4章貪心算法85
8.7集合覆蓋問題的近似算法244
4.1活動安排問題85
8.8子集和問題的近似算法246
4.2貪心算法的基本要素88
8.8.1子集和問題的指數時間算法247
4.2.1貪心選擇性質88
8.8.2子集和問題的完全多項式時間近似格式247
4.2.2最優子結構性質89
小結250
4.2.3貪心算法與動態規劃算法的差異89
習題250
4.3最優裝載91
第9章串與序列的算法253
4.4哈夫曼編碼92
9.1子串搜索算法253
4.4.1前綴碼93
9.1.1串的基本概念253
4.4.2構造哈夫曼編碼93
9.1.2KMP算法255
4.4.3哈夫曼算法的正確性95
9.1.3RabinKarp算法258
4.5單源最短路徑96
9.1.4多子串搜索與AC自動機260
4.5.1算法基本思想97
9.2後綴數組與最長公共子串266
4.5.2算法的正確性和計算複雜性98
9.2.1後綴數組的基本概念266
4.6最小生成樹99
9.2.2構造後綴數組的倍前綴算法267
4.6.1最小生成樹性質99
9.2.3構造後綴數組的DC3分治法270
4.6.2Prim算法100
9.2.4最長公共前綴數組與最長公共擴展算法274
4.6.3Kruskal算法102
9.2.5最長公共子串算法276
4.7多機調度問題104
9.3序列比較算法277
4.8貪心算法的理論基礎106
9.3.1編輯距離算法277
4.8.1擬陣106
9.3.2最長公共單調子序列280
4.8.2帶權擬陣的貪心算法107
9.3.3有約束最長公共子序列281
4.8.3任務時間表問題109
小結284
小結113
習題285
習題113
第10章算法優化策略288
第5章回溯法115
10.1算法設計策略的比較與選擇288
5.1回溯法的算法框架115
10.1.1最大子段和問題的簡單算法288
5.1.1問題的解空間115
10.1.2最大子段和問題的分治算法289
5.1.2回溯法的基本思想116
10.1.3最大子段和問題的動態規劃算法291
5.1.3遞歸回溯117
10.1.4最大子段和問題與動態規劃算法的推廣291
5.1.4迭代回溯118
10.2動態規劃加速原理294
5.1.5子集樹與排列樹119
10.2.1貨物儲運問題294
5.2裝載問題120
10.2.2算法及其優化295
5.3批處理作業調度126
10.3問題的算法特徵298
5.4符號三角形問題128
10.3.1貪心策略298
5.5n後問題130
10.3.2對貪心策略的改進299
5.601揹包問題133
10.3.3算法三部曲299
5.7最大團問題136
10.3.4算法實現300
5.8圖的m着色問題138
10.3.5算法複雜性305
5.9旅行售貨員問題140
10.4優化數據結構306
5.10圓排列問題142
10.4.1帶權區間最短路問題306
5.11電路板排列問題144
10.4.2算法設計思想306
5.12連續郵資問題147
10.4.3算法實現方案308
5.13回溯法的效率分析149
10.4.4並查集311
小結152
10.4.5可並優先隊列314
習題152
10.5優化搜索策略318
第6章分支限界法153
小結324
6.1分支限界法的基本思想153
習題324
6.2單源最短路徑問題156
第11章在線算法設計325
6.3裝載問題158
11.1在線算法設計的基本概念325
6.4佈線問題166
11.2頁調度問題327
6.501揹包問題170
11.3勢函數分析329
6.6最大團問題175
11.4k服務問題330
6.7旅行售貨員問題178
11.4.1競爭比的下界330
6.8電路板排列問題181
11.4.2平衡算法331
6.9批處理作業調度184
11.4.3對稱移動算法332
小結189
11.5Steiner樹問題334
習題189
11.6在線任務調度336
第7章概率算法190
11.7負載平衡337
7.1隨機數191
小結338
7.2數值概率算法193
習題338
7.2.1用隨機投點法計算π值193
詞彙索引340
7.2.2計算定積分194
參考文獻345 [2] 

算法設計與分析（第4版）教學資源

  • 配套教材
《算法設計與分析（第4版）習題解答）》是為配合《算法設計與分析（第4版）》而編寫的學習指導書，書號為9787302511069，2018年11月1日由清華大學出版社出版，開本185mm×260mm、626千字。 [6-7] 
  • 課程資源
《算法設計與分析（第4版）》提供電子教案、數字教程、教學課件PPT、其他網絡資源。 [1]  [3]  [8] 

算法設計與分析（第4版）教材特色

  • 按照計算機算法設計策略為知識單元，採用流行且適合於Internet環境的面向對象程序設計語言Java組織編。
  • 書中涵蓋的算法設計策略全面，包括用於問題精確求解的遞歸與分治策略、動態規劃算法貪心策略、回溯算法和分支限界算法，用於求解NP難題的近似算法、串與序列的算法、隨機化算法等。
  • 以問題驅動的方式組織內容，先介紹一種算法設計策略的基本思想，然後從解決計算機科學與應用中出現的實際問題入手，由簡到繁地描述幾個經典的精巧算法，同時對每個算法所需要的時間和空間進行分析。
  • 廣度與深度兼顧，理論與實踐並重。着重強調提高學生的綜合素質的最終目標，用廣度與深度兼顧的教學策略，培養學生的專業興趣，樹立正確的專業思想。
  • 各章配有難易適當的習題，分為理論分析型和應用實踐型兩種，理論分析型的習題側重於算法理論的拿提與擴展，應用實踐的習題期重於算法的實現與具體應用。 [8] 

算法設計與分析（第4版）作者簡介

王曉東，男，福州大學計算機系教授，福建省計算機學會理事長。研究領域是算法設計與算法評價、基於計算機網絡和信息安全的大規模問題求解算法與數據結構、信息可視化技術兒何計算、並行和分佈式算法設計、計算複雜性理論。主持國家精品課程“算法與數據結構”和“算法設計與分析”的課程建設，獲得2005年福建省教學成果一等獎。 [8] 
參考資料