計算機算法設計與分析（第5版）

《計算機算法設計與分析（第5版）》是2018年電子工業出版社出版的圖書，作者是王曉東。

基本介紹

• 中文名：計算機算法設計與分析（第5版）
• 作者：王曉東
• 類別："十二五”普通高等教育本科國家級規劃教材
• 出版社：電子工業出版社
• 出版時間：2018年8月
• 頁數：356 頁
• 開本：16 開
• 裝幀：平裝
• ISBN：9787121344398
• 版面字數：570千字

成書過程

為了適應21世紀中國培養計算機各類人才的需要，該課程結合中國高等學校教育工作的現狀（截至2018年8月），追蹤國際計算機科學技術的發展水平，更新了教學內容和教學方法。

《計算機算法設計與分析（第5版）》由王曉東擔任主編；傅清祥教授、吳英傑教授、傅仰耿博士和朱達欣教授參加了該教材有關章節的討論，對該教材內容及各章節的編排提出了意見；田俊教授審閱了全書。該教材在編寫過程中，得到了全國高等學校計算機專業教學指導委員會的支持。福州大學“211工程”計算機與信息工程重點學科實驗室和福建工程學院為該教材的寫作提供了設備和工作環境。

2018年8月，該教材由電子工業出版社出版。

內容簡介

《計算機算法設計與分析（第5版）》共9章，具體如下：

第1章介紹算法的基本概念，並對算法的計算複雜性和算法的描述做了闡述。然後圍繞算法設計常用的基本設計策略組織了第2～9章的內容。

第2章介紹遞歸與分治策略。

第3章介紹動態規划算法，以具體實例講述動態規划算法的設計思想、適用性及算法的設計要點。

第4章介紹貪心算法，它也是一種算法設計策略，它與動態規划算法的設計思想有一定的聯繫。

第5章和第6章分別介紹回溯法和分支限界法。這兩章所介紹的算法適合處理難解問題。

第7章介紹隨機化算法，對難解問題提供了解決途徑。

第8章介紹線性規劃與網路流算法。許多實際套用問題可以轉化為線性規劃和網路流問題，並可用第8章中的算法有效求解。

第9章介紹在大數據和人工智慧中有套用的串和序列的算法。

目錄

目 錄 第1章 算法概述 1 1.1 算法與程式 1 1.2 算法複雜性分析 1 1.3 NP完全性理論 4 算法分析題1 7 算法實現題1 7 第2章 遞歸與分治策略 11 2.1 遞歸的概念 11 2.2 分治法的基本思想 16 2.3 二分搜尋技術 17 2.4 大整數的乘法 18 2.5 Strassen矩陣乘法 19 2.6 棋盤覆蓋 20 2.7 合併排序 22 2.8 快速排序 24 2.9 線性時間選擇 26 2.10 最接近點對問題 29 2.11 循環賽日程表 35 算法分析題2 36 算法實現題2 40 第3章 動態規劃 46 3.1 矩陣連乘問題 47 3.2 動態規划算法的基本要素 51 3.3 最長公共子序列 54 3.4 最大子段和 57 3.5 凸多邊形最優三角剖分 62 3.6 多邊形遊戲 65 3.7 圖像壓縮 68 3.8 電路布線 70 3.9 流水作業調度 71 3.10 0-1背包問題 74 3.11 最優二叉搜尋樹 79 算法分析題3 81 算法實現題3 82 第4章 貪心算法 95 4.1 活動安排問題 95 4.2 貪心算法的基本要素 98 4.3 最優裝載 100 4.4 哈夫曼編碼 101 4.5 單源最短路徑 105 4.6 最小生成樹 108 4.7 多機調度問題 111 算法分析題4 113 算法實現題4 113 第5章 回溯法 120 5.1 回溯法的算法框架 120 5.2 裝載問題 125

5.3 批處理作業調度 131 5.4 符號三角形問題 133 5.5 n後問題 135 5.6 0-1背包問題 137 5.7 最大團問題 140 5.8 圖的m著色問題 142 5.9 旅行售貨員問題 144 5.10 圓排列問題 146 5.11 電路板排列問題 148 5.12 連續郵資問題 151 5.13 回溯法的效率分析 153 算法分析題5 155 算法實現題5 156 第6章 分支限界法 167 6.1 分支限界法的基本思想 167 6.2 單源最短路徑問題 170 6.3 裝載問題 172 6.4 布線問題 178 6.5 0-1背包問題 181 6.6 最大團問題 185 6.7 旅行售貨員問題 187 6.8 電路板排列問題 190 6.9 批處理作業調度 193 算法分析題6 197 算法實現題6 198 第7章 隨機化算法 207 7.1 隨機數 208 7.2 數值隨機化算法 209 7.3 舍伍德算法 214 7.4 拉斯維加斯算法 225 7.5 蒙特卡羅算法 231 算法分析題7 236 算法實現題7 239 第8章 線性規劃與網路流 243 8.1 線性規劃問題和單純形算法 243 8.2 最大網路流問題 256 8.3 最小費用流問題 274 算法分析題8 292 算法實現題8 293 第9章 串與序列的算法 306 9.1 子串搜尋算法 306 9.2 後綴數組與最長公共字串 318 9.3 序列比較算法 328 算法分析題9 336 算法實現題9 338 附錄A C++概要 342 參考文獻 349

（註：目錄排版順序為從左列至右列）

教學資源

• 配套教材

《計算機算法設計與分析（第5版）》有配套教材——《計算機算法設計與分析習題解答（第5版）》。

書名	ISNB	出版社	出版時間	作者
《計算機算法設計與分析習題解答（第5版）》	9787121344381	電子工業出版社	2018年10月	王曉東

教材特色

《計算機算法設計與分析（第5版）》修正了第4版中發現的一些錯誤，並將各章的習題分為算法分析題和算法實現題兩部分，增加了算法實踐性內容，增加了有關串和序列的算法內容。

該教材各章的論述中，首先介紹一種算法設計策略的基本思想，然後從解決計算機科學和套用中的實際問題入手，描述幾個算法。同時對每個算法所需的時間和空間進行分析，使讀者既能學到一些常用的算法，也能通過對算法設計策略的反覆套用，牢固掌握這些算法設計的基本策略。該教材選擇某些問題，通過對解同一問題的不同算法的比較，使讀者體會到每種算法的設計要點。

該教材採用面向對象的C++語言作為算法描述手段，在保持C++優點的同時，儘量使算法描述簡明、清晰。每章的章首為學習要點提示，章末配有難易適度的習題，分為算法分析題和算法實現題兩部分，以強化實踐環節。

作者簡介

王曉東：男，1957年生，山東人，福建工程學院副院長，教授，博士生導師，福建省計算機學會理事長。主講課程：算法與數據結構、算法設計與分析、文獻閱讀與選題報告。