《算法設計與分析（第4版）》是由王曉東編著，清華大學出版社2018年10月出版的普通高等教育“十一五”國家級規劃教材、21世紀大學本科計算機專業系列教材。該書既可用作高等學校計算機專業本科生和研究生學習計算機算法設計的教材，而且也適合工程技術人員和自學讀者學習參考。
全書共分11章，由算法引論、遞歸與分治策略、動態規劃、章貪心算法、回溯法、分支限界法、機率算法、NP完全性理論與近似算法、串與序列的算法、算法最佳化策略、線上算法設計組成。
基本介紹
- 書名：算法設計與分析（第4版）
- 作者：王曉東
- ISBN：9787302510109
- 類別：21世紀大學本科計算機專業系列教材等
- 出版社：清華大學出版社
- 出版時間：2018年10月1日
- 裝幀：平裝
- 開本：185mm×260mm
- 字數：550千字
成書過程,修訂過程,出版工作,內容簡介,教材目錄,教學資源,教材特色,作者簡介,
成書過程
修訂過程
為了適應培養中國21世紀計算機各類人才的需要，結合中國高等學校教育工作的現狀，立足培養學生能跟上國際計算機科學技術的發展水平，更新教學內容和教學方法，提高教學質量，作者編寫了該書。
《算法設計與分析（第4版）》按照教育部制定的“計算機科學與技術專業規範的教學大綱”編寫，在前三版的基礎下作了相應修改，按照國際計算機學科的教學要求進行整編。
出版工作
《算法設計與分析（第4版）》是在21世紀大學本科計算機專業系列教材編委會的指導下完成出版。
2018年10月1日，《算法設計與分析（第4版）》由清華大學出版社出版。
責任編輯 | 封面設計 | 責任校對 | 責任印製 |
張瑞慶 | 何鳳霞 | 梁毅 | 沈露 |
內容簡介
《算法設計與分析（第4版）》以算法設計策略為知識單元，系統地介紹計算機算法的設計方法與分析技巧，以期為計算機科學與技術學科的學生提供廣泛而堅實的計算機算法基礎知識。
第1章中首先介紹算法的基本概念，接著簡要闡述算法的計算複雜性和算法的描述，然後圍繞設計算法常用的基本設計策略組織第2章至第10章的內容。第2章介紹遞歸與分治策略，這是設計有效算法常用的策略，是必須掌握的方法。第3章是動態規划算法，以實例詳述動態規划算法的設計思想、適用性以及算法的設計要點。第4章介紹貪心算法，它與動態規划算法的設計思想有一定的聯繫。第5章和第6章分別介紹回溯法和分支限界法，這兩章所介紹的算法適合處理難解問題。第7章介紹機率算法，對許多難解問題提供解決途徑。第8章介紹NP完全性理論和解NP難問題的近似算法。第9章介紹有關串和序列的算法。第10章通過實例介紹算法設計中常用的算法最佳化策略。第11章介紹算法設計中較新的研究領域——線上算法設計。
教材目錄
第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.3RabinKarp算法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.601背包問題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.501背包問題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 |
教學資源
- 配套教材
《算法設計與分析（第4版）習題解答）》是為配合《算法設計與分析（第4版）》而編寫的學習指導書，書號為9787302511069，2018年11月1日由清華大學出版社出版，開本185mm×260mm、626千字。
- 課程資源
《算法設計與分析（第4版）》提供電子教案、數字教程、教學課件PPT、其他網路資源。
教材特色
- 按照計算機算法設計策略為知識單元，採用流行且適合於Internet環境的面向對象程式設計語言Java組織編。
- 書中涵蓋的算法設計策略全面，包括用於問題精確求解的遞歸與分治策略、動態規划算法貪心策略、回溯算法和分支限界算法，用於求解NP難題的近似算法、串與序列的算法、隨機化算法等。
- 以問題驅動的方式組織內容，先介紹一種算法設計策略的基本思想，然後從解決計算機科學與套用中出現的實際問題入手，由簡到繁地描述幾個經典的精巧算法，同時對每個算法所需要的時間和空間進行分析。
- 廣度與深度兼顧，理論與實踐並重。著重強調提高學生的綜合素質的最終目標，用廣度與深度兼顧的教學策略，培養學生的專業興趣，樹立正確的專業思想。
- 各章配有難易適當的習題，分為理論分析型和套用實踐型兩種，理論分析型的習題側重於算法理論的拿提與擴展，套用實踐的習題期重於算法的實現與具體套用。
作者簡介
王曉東，男，福州大學計算機系教授，福建省計算機學會理事長。研究領域是算法設計與算法評價、基於計算機網路和信息安全的大規模問題求解算法與數據結構、信息可視化技術兒何計算、並行和分散式算法設計、計算複雜性理論。主持國家精品課程“算法與數據結構”和“算法設計與分析”的課程建設，獲得2005年福建省教學成果一等獎。
