《算法設計與分析（第2版）》是由屈婉玲、劉田、張立昂、王捍貧編著，2016年清華大學出版社出版的21世紀大學本科計算機專業系列教材、普通高等教育“十一五”國家級規劃教材。該教材適合作為大學計算機科學與技術、軟體工程、信息安全、信息與計算科學等專業本科生和研究生的教學用書，也可以作為從事實際問題求解的算法設計與分析工作的科技人員的參考。
該教材為計算機類專業核心課程“算法設計與分析”教材，全書以算法設計技術和分析方法為主線來組織各知識單元，主要內容包括基礎知識、分治策略、動態規劃、貪心法等。
基本介紹
- 書名：算法設計與分析（第2版）
- 作者：屈婉玲、劉田、張立昂、王捍貧
- ISBN：9787302424505
- 類別：普通高等教育“十一五”國家級規劃教材
- 頁數：297頁
- 出版社：清華大學出版社
- 出版時間：2016年2月1日
- 裝幀：平裝
- 開本：16開
- 字數：475千字
- CIP核字號：2015307076
成書過程,修訂情況,出版工作,內容簡介,教材目錄,教學資源,教材特色,作者簡介,
成書過程
修訂情況
該教材的第1~4章由屈婉玲完成，第5~6章由王捍貧完成，第7~8章由張立昂完成，第9~10章由劉田完成。
在編寫過程中，作者參考了中國國內外多種版本的算法設計與分析以及計算複雜性方面的教材、論文和專著，從中吸取了一些好的思路和素材；李曉明教授審閱了初稿並提出了修改意見。
出版工作
2016年2月1日，該教材由清華大學出版社出版。
| 責任編輯 | 封面設計 | 責任校對 | 責任印製 |
|---|---|---|---|
張瑞慶 | 何鳳霞 | 焦麗麗 | 沈露 |
內容簡介
該教材為計算機類專業核心課程“算法設計與分析”教材，全書以算法設計技術和分析方法為主線來組織各知識單元。全書共10章，第1章是基礎知識，介紹和算法設計與分析有關的基本概念、符號和數學知識；第2~5章分別闡述分治策略、動態規劃、貪心法、回溯與分支限界等算法設計技術；第6章介紹算法分析與問題的計算複雜度；第7章是NP完全性理論；第8章是近似算法；第9章是隨機算法；第10章介紹處理難解問題的策略。
教材目錄
第1章基礎知識11.1有關算法的基本概念1 1.2算法的偽碼描述5 1.3算法的數學基礎6 1.3.1函式的漸近的界6 1.3.2求和的方法10 1.3.3遞推方程求解方法12 習題1 21 第2章分治策略26 2.1分治策略的基本思想26 2.1.1兩個熟悉的例子26 2.1.2分治算法的一般性描述27 2.2分治算法的分析技術27 2.3改進分治算法的途徑31 2.3.1通過代數變換減少子問題個數31 2.3.2利用預處理減少遞歸內部的計算量34 2.4典型實例37 2.4.1快速排序算法37 2.4.2選擇問題40 2.4.3n-1次多項式在全體2n次方根上的求值44 習題2 47 第3章動態規劃52 3.1動態規劃的設計思想52 3.1.1多起點、多終點的最短路徑問題52 3.1.2使用動態規劃技術的必要條件54 3.2動態規划算法的設計要素55 3.2.1子問題的劃分和遞推方程56 3.2.2動態規划算法的遞歸實現57 3.2.3動態規划算法的疊代實現58 3.2.4一個簡單實例的計算過程59 3.3動態規划算法的典型套用60 3.3.1投資問題60 3.3.2背包問題63 3.3.3最長公共子序列LCS65 3.3.4圖像壓縮68 3.3.5最大子段和72 3.3.6最優二分檢索樹75 3.3.7生物信息學中的動態規划算法79 習題3 82 第4章貪心法87 4.1貪心法的設計思想87 4.2關於貪心法的正確性證明90 4.3對貪心法得不到最優解情況的處理94 4.4貪心法的典型套用98 4.4.1最優前綴碼98 4.4.2最小生成樹103 4.4.3單源最短路徑108 習題4 110 第5章回溯與分支限界114 5.1回溯算法的基本思想和適用條件114 5.1.1幾個典型的例子114 5.1.2回溯算法的適用條件118 5.2回溯算法的設計步驟119 5.2.1回溯算法的遞歸實現和疊代實現119 5.2.2幾個典型的例子120 5.3回溯算法的效率估計和改進途徑122 5.4分支限界124 5.4.1背包問題125 5.4.2最大團問題127 5.4.3貨郎問題127 5.4.4圓排列問題129 5.4.5連續郵資問題131 習題5 132 第6章線性規劃134 6.1線性規劃模型134 6.1.1模型134 6.1.2二維線性規劃的圖解法137 6.2標準形138 6.2.1標準形基本概念138 6.2.2標準形的可行解的性質140 6.3單純形法142 6.3.1確定初始基本可行解143 6.3.2最優性檢驗143 6.3.3基變換144 6.3.4單純形表146 6.3.5人工變數和兩階段法148 6.3.6單純形法的有限終止154 6.4對偶性155 6.4.1對偶線性規劃155 6.4.2對偶單純形法159 6.5整數線性規劃的分支限界算法160 習題6 165 第7章網路流算法171 7.1最大流問題171 7.1.1網路流及其性質171 7.1.2FordFulkerson算法173 7.1.3Dinic有效算法176 7.2最小費用流184 7.2.1Floyd算法184 7.2.2最小費用流的負迴路算法186 | 7.2.3最小費用流的最短路徑算法188 7.3運輸問題189 7.3.1確定初始調運方案191 7.3.2改進調運方案191 7.3.3表上作業法193 7.4二部圖匹配194 7.4.1二部圖的最大匹配194 7.4.2賦權二部圖的匹配197 習題7 203 第8章算法分析與問題的計算複雜度208 8.1平凡下界209 8.2直接計數求解該問題所需要的最少運算210 8.3決策樹211 8.4檢索算法的時間複雜度分析212 8.5排序算法的時間複雜度分析214 8.5.1冒泡排序算法214 8.5.2堆排序算法215 8.5.3排序算法的決策樹與算法類時間複雜度的下界220 8.6選擇算法的時間複雜度分析222 8.6.1找最大和最小問題223 8.6.2找第二大問題224 8.6.3找中位數的問題226 8.7通過歸約確認問題計算複雜度的下界228 習題8 229 第9章NP完全性231 9.1P類與NP類231 9.1.1易解的問題與難解的問題231 9.1.2判定問題233 9.1.3NP類235 9.2多項式時間變換與NP完全性236 9.2.1多項式時間變換236 9.2.2NP完全性及其性質238 9.2.3CookLevin定理——第一個NP完全問題239 9.3幾個NP完全問題239 9.3.1最大可滿足性與三元可滿足性240 9.3.2頂點覆蓋、團與獨立集241 9.3.3哈密頓迴路與貨郎問題243 9.3.4恰好覆蓋245 9.3.5子集和、背包、裝箱與雙機調度247 9.3.6整數線性規劃249 習題9 252 第10章近似算法255 10.1近似算法及其近似比255 10.2多機調度問題256 10.2.1貪心的近似算法256 10.2.2改進的貪心近似算法257 10.3貨郎問題258 10.3.1最鄰近法258 10.3.2最小生成樹法259 10.3.3最小權匹配法260 10.4背包問題261 10.4.1一個簡單的貪心算法261 10.4.2多項式時間近似方案261 10.4.3偽多項式時間算法與完全多項式時間近似方案262 習題10 264 第11章隨機算法266 11.1機率論預備知識266 11.2對隨機快速排序算法的分析268 11.3隨機算法的分類及其局限性270 11.3.1拉斯維加斯型隨機算法270 11.3.2蒙特卡洛型隨機算法270 11.3.3隨機算法的局限性271 11.4素數檢驗和多項式恆等檢驗271 11.4.1素數檢驗271 11.4.2多項式恆等檢驗272 11.5隨機遊動算法274 11.5.1有限馬氏鏈及其表示274 11.5.2求解二元布爾可滿足性問題的隨機遊動算法275 習題11 276 第12章處理難解問題的策略277 12.1對問題施加限制277 12.1.1二元可滿足性問題278 12.1.2霍恩公式可滿足性問題279 12.2固定參數算法280 12.3改進指數時間算法282 12.4啟發式方法284 12.5平均情形的複雜性285 12.6難解算例生成287 12.6.1相變現象與難解性287 12.6.2隱藏解的難解算例289 12.7基於統計物理的訊息傳遞算法290 12.7.1訊息傳遞算法與回溯法、局部搜尋算法的比較290 12.7.2用訊息傳遞算法求解3SAT問題291 12.8量子算法簡介292 12.8.1量子比特292 12.8.2正交測量293 12.8.3量子門294 12.8.4一個量子算法295 習題12 297 參考文獻298 |
（註：目錄排版順序為從左列至右列）
教學資源
- 配套教材
該教材配套有學習指導與習題解析用書——《算法設計與分析習題解答與學習指導（第2版）》。
| 書名 | 書號 | 出版社 | 作者 |
|---|---|---|---|
《算法設計與分析習題解答與學習指導（第2版）》 | 9787302429555 | 清華大學出版社 | 屈婉玲、劉田、張立昂、王捍貧 |
- 課程資源
該教材還提供PPT電子教案，MOOC視頻教學資源。
教材特色
該教材突出對問題本身的分析和求解方法的闡述，從問題建模、算法設計與分析、改進措施等方面給出適當的建議，同時也簡要介紹了計算複雜性理論的核心內容和處理難解問題的一些新技術。
該教材的主要特點是：
- 該教材沒有過多地關注實現細節，算法描述採用偽碼，突出對問題本身的分析和求解方法的闡述，從問題建模、算法設計與分析、改進措施等方面給出適當的建議；
- 該教材比較系統地介紹了一些關於問題複雜度的分析方法；
- 該教材用清晰易懂的語言，對計算複雜性理論的核心內容和針對難解問題的處理策略加以簡單的介紹，希望為那些從事複雜問題求解的讀者提供一點幫助；
- 該教材的素材來自多年的教學積澱，選材適當，組織合理，先引入基本概念和數學基礎知識，然後進入算法設計與分析的核心內容；在敘述中不但注意理論的嚴謹，也選擇了生動有趣的例子，每章都配有難度適當的練習。
作者簡介
屈婉玲，女，北京大學信息科學技術學院及軟體與微電子學院教授、博士生導師。主講算法分析與複雜性理論、算法分析與設計等研究生必修課。研究方向為算法設計與分析、軟體形式化方法。
劉田，博士，北京大學信息科學技術學院副教授。主要研究方向為算法分析與計算複雜性理論。長期主講“集合論與圖論”、“理論計算機科學基礎”等課程，2006年和2013年先後兩次獲得了北京大學教學優秀獎。
張立昂，北京大學信息科學技術學院教授、博士生導師，一直從事數學和理論計算機科學的教學與研究工作，主要研究方向是計算複雜性理論和算法設計與分析，曾獲得北京市教學成果獎一等獎和教育部科技進步二等獎。
王捍貧，博士，北京大學信息科學技術學院教授、博士生導師、軟體研究所副所長、中國人工智慧學會離散智慧型計算專委會主任，長期從事離散數學、形式化方法及算法設計與分析的教學和研究工作，曾獲得北京市教學成果獎一等獎。
