《算法設計與分析（第2版）》是由李春葆主編，2018年清華大學出版社出版的高等學校數據結構課程系列教材。該教材適合作為高等院校“算法設計與分析”課程的教材，也可供ACM和各類程式設計競賽者參考。
該教材介紹了各種常用的算法設計策略，包括遞歸、分治法、蠻力法、回溯法、分枝限界法、貪心法、動態規劃、機率算法和近似算法等，並討論了各種圖算法和計算幾何設計算法。書中配有圖表、練習題、上機實驗題和線上編程題。
基本介紹
- 書名：算法設計與分析（第2版）
- 作者：李春葆
- ISBN：9787302500988
- 類別：高等學校數據結構課程系列教材
- 頁數：444頁
- 出版社：清華大學出版社
- 出版時間：2018年8月1日
- 裝幀：平裝
- 開本：16開
- 字數：699千字
- CIP核字號：2018102226
成書過程,修訂情況,出版工作,內容簡介,教材目錄,教學資源,教材特色,作者簡介,
成書過程
修訂情況
該教材是根據“問題模型化，求解算法化，設計最最佳化”，並結合課程組全體教師多年的教學經驗編寫的。該教材的編寫得到了湖北省教育廳和武漢大學教學研究項目《計算機科學與技術專業課程體系改革》的幫助；得到了清華大學出版社的魏江江主任的支持；此外，王冰飛老師參與了編輯工作。
該教材在編寫過程中參考了很多同行的教材和網路部落格，特別是“牛客網”中企業面試、筆試題和資源，河南工程學院張天伍老師和使用該教材第1版的多位老師指正多處問題和錯誤。
出版工作
2018年8月1日，該教材由清華大學出版社出版。
| 責任編輯 | 封面設計 | 責任校對 | 責任印製 |
|---|---|---|---|
魏江江、王冰飛 | 劉鍵 | 梁毅 | 李紅英 |
內容簡介
全書由12章構成，各章的內容如下。
第1章概論：介紹算法的概念、算法分析方法和STL在算法設計中的套用。
第2章遞歸算法設計技術：介紹遞歸的概念、遞歸算法設計方法和相關示例、遞歸算法到非遞歸算法的轉化以及遞推式的計算。
第3章分治法：介紹分治法的策略和求解過程，討論採用分治法求解排序問題、查找問題、最大連續子序列和問題、大整數乘法問題及矩陣乘法問題的典型算法，並簡要介紹了並行計算的概念。
第4章蠻力法：介紹蠻力法的特點、蠻力法的基本套用示例、遞歸在蠻力法中的套用以及圖的深度優先和廣度優先遍歷算法。
第5章回溯法：介紹解空間概念和回溯法算法框架，討論採用回溯法求解0/1背包問題、裝載問題、子集和問題、n皇后問題、圖的m著色問題、任務分配問題、活動安排問題和流水作業調度問題的典型算法。
第6章分枝限界法：介紹分枝限界法的特點和算法框架、佇列式分枝限界法和優先佇列式分枝限界法，討論採用分枝限界法求解0/1背包問題、圖的單源最短路徑、任務分配問題和流水作業調度問題的典型算法。
第7章貪心法：介紹貪心法的策略、求解過程和貪心法求解問題應具有的性質，討論採用貪心法求解活動安排問題、背包問題、最優裝載問題、田忌賽馬問題、多機調度問題、哈夫曼編碼和流水作業調度問題的典型算法。
第8章動態規劃：介紹動態規劃的原理和求解步驟，討論採用動態規劃法求解整數拆分問題、最大連續子序列和問題、三角形最小路徑問題、最長公共子序列問題、最長遞增子序列問題、編輯距離問題、0/1背包問題、完全背包問題、資源分配問題、會議安排問題和滾動數組的典型算法。
第9章圖算法設計：討論構造圖最小生成樹的兩種算法（Prim和Kruskal算法，並查集的套用）、求圖的最短路徑的4種算法（Dijkstra、Bellman Ford、SPFA和Floyd），並採用5種算法策略求解旅行商問題（TSP問題），最後介紹網路流的相關概念以及求最大流和最小費用最大流的算法。
第10章計算幾何：介紹計算幾何中常用的矢量運算以及求解凸包問題、最近點對問題和最遠點對問題的典型算法。
第11章計算複雜性理論簡介：介紹圖靈機計算模型、P類和NP類問題以及NPC問題。
第12章機率算法和近似算法：介紹這兩類算法的特點和基本的算法設計方法。書中帶“*”符號的章節作為選學內容。
教材目錄
第1章概論1.1算法的概念 1.1.1什麼是算法 1.1.2算法描述 1.1.3算法和數據結構 1.1.4算法設計的基本步驟 1.2算法分析 1.2.1算法時間複雜度分析 1.2.2算法空間複雜度分析 1.3算法設計工具——STL 1.3.1STL概述 1.3.2常用的STL容器 1.3.3STL在算法設計中的套用 1.4練習題 1.5上機實驗題 1.6線上編程題 第2章遞歸算法設計技術 2.1什麼是遞歸 2.1.1遞歸的定義 2.1.2何時使用遞歸 2.1.3遞歸模型 2.1.4遞歸算法的執行過程 2.2遞歸算法設計 2.2.1遞歸與數學歸納法 2.2.2遞歸算法設計的一般步驟 2.2.3遞歸數據結構及其遞歸算法設計 2.2.4基於歸納思想的遞歸算法設計 2.3遞歸算法設計示例 2.3.1簡單選擇排序和冒泡排序 2.3.2求解n皇后問題 2.4*遞歸算法轉化為非遞歸算法 2.4.1用循環結構替代遞歸過程 2.4.2用棧消除遞歸過程 2.5遞推式的計算 2.5.1用特徵方程求解遞歸方程 2.5.2用遞歸樹求解遞歸方程 2.5.3用主方法求解遞歸方程 2.6練習題 2.7上機實驗題 2.8線上編程題 第3章分治法 3.1分治法概述 3.1.1分治法的設計思想 3.1.2分治法的求解過程 3.2求解排序問題 3.2.1快速排序 3.2.2歸併排序 3.3求解查找問題 3.3.1查找最大和次大元素 3.3.2折半查找 3.3.3尋找一個序列中第k小的元素 3.3.4尋找兩個等長有序序列的中位數 3.4求解組合問題 3.4.1求解最大連續子序列和問題 3.4.2求解棋盤覆蓋問題 3.4.3求解循環日程安排問題 3.5求解大整數乘法和矩陣乘法問題 3.5.1求解大整數乘法問題 3.5.2求解矩陣乘法問題 3.6並行計算簡介 3.6.1並行計算概述 3.6.2並行計算模型 3.6.3快速排序的並行算法 3.7練習題 3.8上機實驗題 3.9線上編程題 第4章蠻力法 4.1蠻力法概述 4.2蠻力法的基本套用 4.2.1採用直接窮舉思路的一般格式 4.2.2簡單選擇排序和冒泡排序 4.2.3字元串匹配 4.2.4求解最大連續子序列和問題 4.2.5求解冪集問題 4.2.6求解簡單01背包問題 4.2.7求解全排列問題 4.2.8求解任務分配問題 4.3遞歸在蠻力法中的套用 4.3.1用遞歸方法求解冪集問題 4.3.2用遞歸方法求解全排列問題 4.3.3用遞歸方法求解組合問題 4.4圖的深度優先和廣度優先遍歷 4.4.1圖的存儲結構 4.4.2深度優先遍歷 4.4.3廣度優先遍歷 4.4.4求解迷宮問題 4.5練習題 4.6上機實驗題 4.7線上編程題 第5章回溯法 5.1回溯法概述 5.1.1問題的解空間 5.1.2什麼是回溯法 5.1.3回溯法的算法框架及其套用 5.1.4回溯法與深度優先遍歷的異同 5.1.5回溯法的時間分析 5.2求解01背包問題 5.3求解裝載問題 5.3.1求解簡單裝載問題 5.3.2求解複雜裝載問題 5.4求解子集和問題 5.4.1求子集和問題的解 5.4.2判斷子集和問題是否存在解 5.5求解n皇后問題 5.6求解圖的m著色問題 5.7求解任務分配問題 5.8求解活動安排問題 5.9求解流水作業調度問題 5.10練習題 5.11上機實驗題 5.12線上編程題 第6章分枝限界法 6.1分枝限界法概述 6.1.1什麼是分枝限界法 6.1.2分枝限界法的設計思想 6.1.3分枝限界法的時間性能 | 6.2求解01背包問題6.2.1採用佇列式分枝限界法求解 6.2.2採用優先佇列式分枝限界法求解 6.3求解圖的單源最短路徑 6.3.1採用佇列式分枝限界法求解 6.3.2採用優先佇列式分枝限界法求解 6.4求解任務分配問題 6.5求解流水作業調度問題 6.6練習題 6.7上機實驗題 6.8線上編程題 第7章貪心法 7.1貪心法概述 7.1.1什麼是貪心法 7.1.2用貪心法求解的問題應具有的性質 7.1.3貪心法的一般求解過程 7.2求解活動安排問題 7.3求解背包問題 7.4求解最優裝載問題 7.5求解田忌賽馬問題 7.6求解多機調度問題 7.7哈夫曼編碼 7.8求解流水作業調度問題 7.9練習題 7.10上機實驗題 7.11線上編程題 第8章動態規劃 8.1動態規劃概述 8.1.1從求解斐波那契數列看動態規劃法 8.1.2動態規劃的原理 8.1.3動態規劃求解的基本步驟 8.1.4動態規劃與其他方法的比較 8.2求解整數拆分問題 8.3求解最大連續子序列和問題 8.4求解三角形最小路徑問題 8.5求解最長公共子序列問題 8.6求解最長遞增子序列問題 8.7求解編輯距離問題 8.8求解01背包問題 8.9求解完全背包問題 8.10求解資源分配問題 8.11求解會議安排問題 8.12滾動數組 8.12.1什麼是滾動數組 8.12.2用滾動數組求解01背包問題 8.13練習題 8.14上機實驗題 8.15線上編程題 第9章圖算法設計 9.1求圖的最小生成樹 9.1.1最小生成樹的概念 9.1.2用普里姆算法構造最小生成樹 9.1.3克魯斯卡爾算法 9.2求圖的最短路徑 9.2.1狄克斯特拉算法 9.2.2貝爾曼福特算法 9.2.3SPFA算法 9.2.4弗洛伊德算法 9.3求解旅行商問題 9.3.1旅行商問題描述 9.3.2採用蠻力法求解TSP問題 9.3.3採用動態規劃求解TSP問題 9.3.4採用回溯法求解TSP問題 9.3.5採用分枝限界法求解TSP問題 9.3.6採用貪心法求解TSP問題 9.4網路流 9.4.1相關概念 9.4.2求最大流 9.4.3割集與割量 9.4.4求最小費用最大流 9.5練習題 9.6上機實驗題 9.7線上編程題 第10章計算幾何 10.1向量運算 10.1.1向量的基本運算 10.1.2判斷一個點是否在一個矩形內 10.1.3判斷一個點是否在一條線段上 10.1.4判斷兩條線段是否平行 10.1.5判斷兩條線段是否相交 10.1.6判斷一個點是否在多邊形內 10.1.7求3個點構成的三角形的面積 10.1.8求一個多邊形的面積 10.2求解凸包問題 10.2.1禮品包裹算法 10.2.2Graham掃描算法 10.3求解最近點對問題 10.3.1用蠻力法求最近點對 10.3.2用分治法求最近點對 10.4求解最遠點對問題 10.4.1用蠻力法求最遠點對 10.4.2用旋轉卡殼法求最遠點對 10.5練習題 10.6上機實驗題 10.7線上編程題 第11章計算複雜性理論簡介 11.1計算模型 11.1.1求解問題的分類 11.1.2圖靈機模型 11.2P類和NP類問題 11.3NPC問題 11.4練習題 第12章機率算法和近似算法 12.1機率算法 12.1.1什麼是機率算法 12.1.2蒙特卡羅類型機率算法 12.1.3拉斯維加斯類型機率算法 12.1.4舍伍德類型機率算法 12.2近似算法 12.2.1什麼是近似算法 12.2.2求解旅行商問題的近似算法 12.3練習題 12.4上機實驗題 12.5線上編程題 附錄A書中部分算法清單 參考文獻 |
（註：目錄排版順序為從左列至右列）
教學資源
- 配套教材
該教材配有配套教材——《算法設計與分析（第2版）學習與實驗指導》，該配套教材涵蓋所有練習題、上機實驗題和線上編程題的參考答案。
| 書名 | 書號 | 出版社 | 作者 |
|---|---|---|---|
《算法設計與分析（第2版）學習與實驗指導》 | 9787302501459 | 清華大學出版社 | 李春葆 |
- 課程資源
該教材每個知識點都配套了視頻講解，提供PPT課件、源碼、答案、教學大綱、題庫、書中全部源程式代碼（在VC++6.0中調試通過）等教學資源。
教材特色
該教材具有如下特色：
- 該教材每種算法策略從設計思想、算法框架入手，由易到難地講解經典問題的求解過程，使讀者既能學到求解問題的方法，又能通過對算法策略的反覆套用掌握其核心原理；
- 書中列舉具有典型性的求解問題，剖析採用相關算法策略求解的思路，展示算法設計的過程；
- 該教材注重求解問題的多維性，同一個問題採用多種算法策略實現，如0/1背包問題採用回溯法、分枝限界法和動態規劃求解，旅行商問題採用5種算法策略求解；通過不同算法策略的比較，使學生更容易體會到每一種算法策略的設計特點和各自的優缺點，以提高算法設計的效率；
- 該教材強調實驗和動手能力的培養，算法講解不僅包含思路描述，而且以C/C++完整程式的形式呈現，同時給出了上機實驗題和線上編程題，大部分是中國國內外IT企業面試筆試題（谷歌、微軟、阿里巴巴、騰訊、網易等）和ACM競賽題。
