《計算機算法設計與分析（第4版）》是王曉東主編，2012年2月電子工業出版社出版的“十二五”普通高等教育本科國家級規劃教材、高等學校規劃教材。該教材適合作為大學計算機科學與技術、軟體工程、信息安全信息與計算科學等專業本科生和研究生教材，可作為ACM程式設計大賽培訓教材，也適合廣大丁程技術人員學習參考。
全書以算法設計策略為知識單元，介紹了計算機算法的設計方法與分析技巧。全書共8章，主要內容包括：算法概述、遞歸與分治策略、動態規劃、貪心算法、回溯法、分支限界法、隨機化算法、線性規劃與網路流等。書中既涉及經典與實用算法及實例分析，又包括算法熱點領域追蹤。章首增加了學習要點提示，章末配有算法分析題和算法實現題。
基本介紹
- 書名：計算機算法設計與分析（第4版）
- 作者：王曉東
- 類別：“十二五”普通高等教育本科國家級規劃教材
- 出版社：電子工業出版社
- 出版時間：2012年2月
- 頁數：312 頁
- 開本：16 開
- 裝幀：平裝
- ISBN：9787121158391
- 字數：499千字
- CIP核字號：2012019893
成書過程,修訂過程,出版工作,內容簡介,教材目錄,教學資源,教材特色,作者簡介,
成書過程
修訂過程
該教材為了適應21世紀中國培養計算機各類人才的需要，結合中國高等學校教育工作的現狀，追蹤國際計算機科學技術的發展水平編寫而成，更新了教學內容和教學方法。
該教材修正了第3版中發現的一些錯誤，並將各章的習題分為算法分析題和算法實現題兩部分，增加了算法實踐性內容，以期加強教學實踐環節。具體修改如下：
- 增加了1.3 節NP完全性理論；
- 刪除了理論性較強的3.12節動態規劃加速原理、4.8節貪心算法的理論基礎、第9章NP完全性理論與近似算法。
該教材在編寫過程中，得到了全國高等學校計算機專業教學指導委員會的支持。福州大學“211工程”計算機與信息工程重點學科實驗室為該教材的寫作提供了優良的設備和工作環境。傅清祥教授、吳英傑博士、傅仰耿博士和朱達欣副教授參加了該教材有關章節的討論，對該教材的內容及各章節的編排提出了修改意見。田俊教授認真審閱了全書。
出版工作
2012年2月，該教材電子工業出版社出版。
策劃編輯 | 責任編輯 |
|---|---|
童占梅 | 童占梅 |
內容簡介
全書共分8章。
第1章介紹算法的基本概念，並對算法的計算複雜性和算法的描述做了簡要闡述。然後圍繞算法設計常用的基本設計策略組織了第2~8章的內容。
第2章介紹遞歸與分治策略，它是設計有效算法最常用的策略。
第3章是動態規划算法，以具體實例詳述動態規划算法的設計思想、適用性及算法的設計要點。
第4章介紹貪心算法，它也是一種重要的算法設計策略，它與動態規划算法的設計思想有一定的聯繫，但其效率更高。
第5章和第6章分別介紹回溯法和分支限界法。這兩章所介紹的算法適合處理難解問題。
第7章介紹隨機化算法，對許多難解問題提供了高效的解決途徑。
第8章介紹實用性很強的線性規劃與網路流算法。許多實際套用問題可以轉化為線性規劃和網路流問題，並可用第8章中的算法有效求解。
教材目錄
第1章 算法概述 1.1 算法與程式 1.2 算法複雜性分析 1.3 NP完全性理論 算法分析題1 算法實現題1 第2章 遞歸與分治策略 2.1 遞歸的概念 2.2 分治法的基本思想 2.3 二分搜尋技術 2.4 大整數的乘法 2.5 Strassen矩陣乘法 2.6 棋盤覆蓋 2.7 合併排序 2.8 快速排序 2.9 線性時間選擇 2.10 最接近點對問題 2.11 循環賽日程表 算法分析題2 算法實現題2 第3章 動態規劃 3.1 矩陣連乘問題 3.2 動態規划算法的基本要素 3.3 最長公共子序列 3.4 最大子段和 3.5 凸多邊形最優三角剖分 3.6 多邊形遊戲 3.7 圖像壓縮 3.8 電路布線 3.9 流水作業調度 3.10 0-1背包問題 3.11 最優二叉搜尋樹 算法分析題3 算法實現題3 第4章 貪心算法 4.1 活動安排問題 4.2 貪心算法的基本要素 4.3 最優裝載 4.4 哈夫曼編碼 4.5 單源最短路徑 4.6 最小生成樹 4.7 多機調度問題 算法分析題4 算法實現題4 第5章 回溯法 5.1 回溯法的算法框架 5.2 裝載問題 5.3 批處理作業調度 5.4 符號三角形問題 5.5 n後問題 5.6 0-1背包問題 5.7 最大團問題 5.8 圖的m著色問題 5.9 旅行售貨員問題 5.10 圓排列問題 5.11 電路板排列問題 5.12 連續郵資問題 5.13 回溯法的效率分析 算法分析題5 算法實現題5 第6章 分支限界法 6.1 分支限界法的基本思想 6.2 單源最短路徑問題 6.3 裝載問題 | 6.4 布線問題 6.5 0-1背包問題 6.6 最大團問題 6.7 旅行售貨員問題 6.8 電路板排列問題 6.9 批處理作業調度 算法分析題6 算法實現題6 第7章 隨機化算法 7.1 隨機數 7.2 數值隨機化算法 7.2.1 用隨機投點法計算π值 7.2.2 計算定積分 7.2.3 解非線性方程組 7.3 舍伍德(Sherwood)算法 7.3.1 線性時間選擇算法 7.3.2 搜尋有序表 7.3.3 跳躍表 7.4 拉斯維加斯（Las Vegas）算法 7.4.1 n後問題 7.4.2 整數因子分解 7.5 蒙特卡羅（Monte Carlo）算法 7.5.1 蒙特卡羅算法的基本思想 7.5.2 主元素問題 7.5.3 素數測試 算法分析題7 算法實現題7 第8章 線性規劃與網路流 8.1 線性規劃問題和單純形算法 8.1.1 線性規劃問題及其表示 8.1.2 線性規劃基本定理 8.1.3 約束標準型線性規劃問題的單純形算法 8.1.4 將一般問題轉化為約束標準型 8.1.5 一般線性規劃問題的兩階段單純形算法 8.1.6 單純形算法的描述和實現 8.1.7 退化情形的處理 8.1.8 套用舉例 8.2 最大網路流問題 8.2.1 網路與流 8.2.2 增廣路算法 8.2.3 預流推進算法 8.2.4 最大流問題的變換與套用 8.3 最小費用流問題 8.3.1 最小費用流 8.3.2 消圈算法 8.3.3 最小費用路算法 8.3.4 網路單純形算法 8.3.5 最小費用流問題的變換與套用算法分析題8 算法實現題8 附錄A C++概要 1.變數、指針和引用 2.函式與參數傳遞 3. C++的類 4.類的對象 5.構造函式與析構函式 6.運算符重載 7.友元函式 8.內聯函式 9.結構 10.聯合 11.異常 12.模板 13.動態存儲分配 參考文獻 |
（註：目錄排版順序為從左列至右列）
教學資源
- 配套教材
該教材有配套教材——《計算機算法設計與分析習題解答（第2版）》。
書名 | 書號 | 出版社 | 出版時間 | 作者 |
|---|---|---|---|---|
《計算機算法設計與分析習題解答（第2版）》 | 9787121161346 | 電子工業出版社 | 2012-06 | 王曉東 |
- 課程資源
該教材提供電子課件和教學網站服務。
教材特色
該教材採用面向對象的C++語言作為算法描述手段。在各章的論述中，首先介紹一種算法設計策略的基本思想，然後從解決計算機科學和套用中的實際問題入手，由簡到繁地描述幾個經典的精巧算法。同時對每個算法所需的時間和空間進行分析。在為各種算法設計策略選擇用於展示其設計思想與技巧的具體套用問題時，該教材有意重複選擇某些經典問題。同時通過對解同一問題的不同算法的比較。
作者簡介
王曉東，男，1957年出生，山東人，中共黨員，福建工程學院副院長、教授、博士生導師，福建省計算機學會理事長。先後擔任福州大學計算機系主任、數學與計算機科學學院院長，2007年8月起擔任泉州師範學院副院長。主講課程有算法與數據結構、算法設計與分析、文獻閱讀與選題報告。
