 |
-- 會員 / 註冊 --
|
 |
|
|
|
算法設計與分析 ( 簡體 字) |
| 作者：黃宇 編著 | 類別：1. -> 程式設計 -> 演算法 |
| 譯者： |
| 出版社：機械工業出版社 |  3dWoo書號： 47284
詢問書籍請說出此書號！【缺書】
NT售價： 245 元 |
| 出版日：7/1/2017 |
| 頁數： |
| 光碟數：0 |
|
站長推薦：   |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787111572978 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：算法是計算的靈魂(spirit of computing)，而算法設計與分析的基礎知識是計算機科學的基石。算法設計與分析的知識內容很豐富，可以從不同視角進行組織與闡述。一種視角是關注經典的算法問題，如排序、選擇、查找、圖遍歷等；另一種視角是關注經典的算法設計策略，包括分治、貪心、動態規劃等。本書的組織兼顧問題與策略兩種視角。首先按照經典的算法設計策略，將書中的主體內容分為遍歷、分治、貪心、動態規劃4個部分。其次在每個部分之內，又圍繞經典的算法問題來闡述該部分所著重討論的策略。
本書集中討論抽象的即與機器、實現語言無關的算法設計與分析。為此在主體內容之前，我們首先講解計算模型的基礎知識，它是后續抽象討論算法設計與分析的基礎。另外，在本書的最后，我們介紹計算復雜性的基礎知識，試圖讓讀者在了解了各類算法問題、學習了各種算法設計和分析技術之后，對算法問題的難度有一個總體性的認識。此外，一些對于算法設計與分析較為關鍵的數學知識將在附錄中列出。本書的內容是作者在過去多年授課的過程中逐漸積淀而成的，所以它不是對算法設計與分析知識的一個百科全書式的覆蓋，而是對一些重點內容的更專注的討論。
本書內容和組織方式的設計針對一個學期的授課展開。在內容方面，本書可以分為前后兩個部分。前一部分主要圍繞元素的序關系展開，討論排序、選擇、查找這3個經典的算法問題。而這3個問題的求解同時又是分治策略的典型應用。后一部分主要圍繞“圖”這一數學結構展開，講授圖遍歷、最小生成樹、最短路徑等經典圖算法。同時，這些圖算法背后的一個核心問題是圖上特定結構——最小生成樹、最短路徑——的優化。圍繞圖優化，我們展示了貪心策略與動態規劃策略的典型應用。
在授課形式方面，我們將課程分為主課與輔課這兩種形式。主課主要圍繞典型的算法問題、經典的算法展開。而輔課則圍繞算法策略來展開，在講述若干經典問題、經典算法之后，從策略的視角回顧最近階段的經典算法，同時補充新的素材對相應的策略進行進一步的展示。除知識講授之外，實踐也是“算法設計與分析”課程的重要組成部分。算法設計與分析課程的實踐分為兩類：一類是傳統的習題，即緊扣書本知識的習題，如一些簡單定理的證明、緊扣算法細節的一些問題等；另一類是應用題，它需要讀者對一個有一定現實意義的問題進行建模，并用書中的算法知識來求解。本書的應用題大都可以用于算法編程實現的訓練。在實際授課中，我們挑選了部分應用題作為編程實現題，并基于開源的OnlineJudge平臺進行自動評測，取得了良好的效果。
本書的素材主要源自于南京大學計算機系本科生“算法設計與分析”課程的授課內容。其中一部分素材來源于共同授課的其他老師，包括前期負責講授主課并指導輔課教學的陳道蓄老師，以及后期共同分班講授這門課程的錢柱中老師。還有一部分素材來自于經典的算法教科書和國外大學授課教師在其課程網站上發布的課程材料。另外，還要感謝“算法設計與分析”課程的兩位助教魏恒峰和楊怡玲，他們對大量的課程資料進行了整理與提煉。最后要感謝上過這門課的學生，他們創造性的提問與解題時所犯的錯誤都為本書提供了寶貴的素材。
教學建議說明：南京大學計算機系“算法設計與分析”課程的講授采用三種不同形式，即主課、輔課（tutorial）和習題課。
●主課圍繞各個主要知識點進行專題講授。下面列出主課的授課計劃，包括每次課的主題以及所對應的書本中的章節。
●輔課的主要內容是對前一階段主課知識的多角度解讀，以及重點內容的強化。輔課的授課往往以圍繞經典例題的討論為主，以知識點的闡述為輔。
●習題課的講授主要包括書上習題的講解，以及上機評測問題的講解。習題課的講授可以根據具體的教學、上機、考試等情況進行相應的安排。
教學章節教學要求課時主課一 準備知識
（第1章） 計算模型的基礎知識
抽象算法設計與分析的基本概念2主課二 數學基礎
（第2章） 函數漸近增長率的基本概念
簡單蠻力算法的逐步改進2 遞歸方程的基本求解技術
基于Master定理的分治遞歸求解2輔課一 從算法設計與分析的角度重新審視數學的概念2主課三 排序
（第3、6、7章） 線性表的遍歷，從蠻力排序到快速排序2 堆結構的維護
堆結構的應用：堆排序與優先隊列2 合并排序
基于比較的排序的下界2輔課二 排序：從簡單遍歷到分而治之2主課四 選擇
（第8章） 選擇問題的簡單特例
期望線性時間選擇
最壞情況線性時間選擇2主課五 查找
（第9、10章） 折半查找
平衡二叉樹的定義及平衡性分析2 動態等價關系下的查找
并查集的設計與分析2(續)教學章節教學要求課時輔課三 分治策略中的平衡性控制技術2主課六 圖遍歷
（第4、5章） DFS、BFS基本算法框架
DFS框架深入分析2 有向圖中的DFS：拓撲排序、任務調度、強連通片識別2 無向圖中的DFS：尋找割點、尋找橋2輔課四 BFS框架深入分析、圖遍歷的典型應用、DFS和BFS各自特色比較2主課七 圖優化
（第10~14章） 最小生成樹：Prim算法、Kruskal算法2 最短路徑：給定源點最短路徑、所有點對間最短路徑2 從圖優化到一般優化問題求解：貪心策略、動態規劃策略的典型應用4輔課五 圖的貪心遍歷框架、經典圖優化問題的各種變體2主課八 計算復雜性理論初步
（第15~16章） P問題、NP問題基本概念
問題間歸約基本概念2 NP完全問題基本概念
基本的NP完全性證明技術2輔課六 算法設計與分析——過去與未來：抽象算法設計與分析回顧、難問題求解技術簡介（近似算法）、算法設計與分析前沿簡介（隨機算法、在線算法、并行分布式算法等）2 |
內容簡介：本書源于作者“算法設計與分析”課程的10年教學實踐，主要面向計算機專業本科生，以及其他需要學習計算機科學基本知識與了解計算機程序設計背后原理的讀者。
本書的主要特色
內容定位科學。本書定位于講解抽象的——與機器、實現語言無關的——算法設計與分析知識。這一定位有助于讀者脫離具體的機器與編程語言的細節，了解算法設計背后的核心原理。
內容組織合理。本書內容組織兼顧問題和策略兩個維度，圍繞遍歷、分治、貪心、動態規劃這四種經典策略，通過排序、選擇、查找、圖遍歷、圖優化等經典算法問題的逐步深入求解，來展示各種算法設計策略的運用。本書內容具有“自包含（self-contained）”特色，讀者只需具有離散數學的基礎知識以及計算機程序設計的入門知識，即可進行學習。
習題資源豐富。本書為每章內容配備了豐富的習題。習題由淺入深，涵蓋了主要知識點，其中部分習題改編自授課過程中學生常犯的典型錯誤示例。大部分習題不僅可以布置為書面習題，也易于配以輸入輸出數據，用作在線評測試題。 |
目錄：前言
教學建議
第一部分 計算模型
第1章 抽象的算法設計與分析2
1.1 RAM模型的引入2
1.1.1 計算的基本概念2
1.1.2 計算模型的基本概念3
1.1.3 RAM模型4
1.1.4 計算模型的選擇：易用性和精確性6
1.2 抽象算法設計7
1.2.1 算法問題規約7
1.2.2 算法正確性證明：數學歸納法8
1.3 抽象算法分析10
1.3.1 抽象算法的性能指標10
1.3.2 最壞情況時間復雜度分析11
1.3.3 平均情況時間復雜度分析12
1.4 習題13
第2章 從算法的視角重新審視數學的概念16
2.1 數學運算背后的算法操作16
2.1.1 取整x和x16
2.1.2 對數log n17
2.1.3 階乘n!18
2.1.4 常見級數求和?ni=1f(i)19
2.1.5 期望E〔X〕20
2.2 函數的漸近增長率22
2.3 “分治遞歸”求解24
2.3.1 替換法24
2.3.2 分治遞歸與遞歸樹25
2.3.3 Master定理26
2.4 習題27
第二部分 樸素遍歷
第3章 線性表的遍歷32
3.1 基于遍歷的選擇與查找32
3.2 基于遍歷的排序33
3.2.1 選擇排序34
3.2.2 插入排序35
3.3 習題37
第4章 圖的深度優先遍歷39
4.1 圖和圖遍歷39
4.2 有向圖的深度優先遍歷40
4.2.1 有向圖的深度優先遍歷框架40
4.2.2 有向圖的深度優先遍歷樹42
4.2.3 活動區間43
4.3 有向圖的深度優先遍歷應用45
4.3.1 拓撲排序45
4.3.2 關鍵路徑48
4.3.3 有向圖中的強連通片50
4.4 無向圖的深度優先遍歷54
4.4.1 無向圖的深度優先遍歷樹55
4.4.2 無向圖的深度優先遍歷框架56
4.5 無向圖的深度優先遍歷應用57
4.5.1 容錯連通57
4.5.2 尋找割點58
4.5.3 尋找橋60
4.6 習題61
第5章 圖的廣度優先遍歷66
5.1 廣度優先遍歷66
5.1.1 廣度優先遍歷框架67
5.1.2 有向圖的廣度優先遍歷樹70
5.1.3 無向圖的廣度優先遍歷樹70
5.2 廣度優先遍歷的應用72
5.2.1 判斷二分圖72
5.2.2 尋找k度子圖73
5.3 習題74
第三部分 分治策略
第6章 排序：從遍歷到分治78
6.1 快速排序78
6.1.1 插入排序的不足78
6.1.2 快速排序的改進79
6.1.3 快速排序的分析81
6.2 合并排序84
6.3 基于比較的排序的下界86
6.3.1 決策樹的引入87
6.3.2 比較排序最壞情況時間復雜度的下界88
6.3.3 比較排序平均情況時間復雜度的下界88
6.4 習題90
第7章 堆的設計與應用95
7.1 堆的定義95
7.2 堆的抽象維護96
7.2.1 堆的修復96
7.2.2 堆的構建97
7.3 堆的具體實現98
7.4 堆的應用100
7.4.1 堆排序100
7.4.2 基于堆實現優先隊列100
7.5 習題101
第8章 線性時間選擇103
8.1 期望線性時間的選擇103
8.1.1 期望線性時間的選擇算法設計103
8.1.2 期望線性時間的選擇算法分析104
8.2 最壞情況線性時間的選擇106
8.2.1 最壞情況線性時間的選擇算法設計106
8.2.2 最壞情況線性時間的選擇算法分析107
8.3 習題108
第9章 對數時間查找110
9.1 折半查找110
9.1.1 經典折半查找110
9.1.2 折半查找的推廣111
9.2 平衡二叉搜索樹112
9.2.1 二叉搜索樹及其平衡性113
9.2.2 紅黑樹的定義114
9.2.3 紅黑樹的平衡性115
9.3 習題116
第四部分 貪心策略
第10章 最小生成樹120
10.1 Prim算法120
10.1.1 Prim算法的正確性122
10.1.2 Prim算法的實現125
10.1.3 Prim算法的分析126
10.2 Kruskal算法127
10.2.1 Kruskal算法的正確性128
10.2.2 判斷是否成環——基于并查集的實現129
10.2.3 Kruskal算法的實現與分析133
10.3 最小生成樹貪心構建框架MCE134
10.3.1 從MCE框架的角度分析Prim算法135
10.3.2 從MCE框架的角度分析Kruskal算法136
10.4 習題137
第11章 給定源點的最短路徑142
11.1 Dijkstra算法142
11.1.1 Dijkstra算法的設計142
11.1.2 Dijkstra算法的正確性與性能分析144
11.2 從Dijkstra算法到貪心遍歷框架BestFS146
11.3 習題147
第12章 貪心策略的其他應用151
12.1 相容任務調度問題151
12.1.1 直覺的嘗試151
12.1.2 基于任務結束時間的貪心算法152
12.2 Huffman編碼153
12.2.1 可變長度編碼153
12.2.2 最優編碼方案的性質154
12.2.3 貪心的Huffman編碼156
12.3 習題156
第五部分 動態規劃
第13章 最短路徑160
13.1 有向無環圖上的給定源點最短路徑問題160
13.2 傳遞閉包問題和Shortcut算法161
13.3 所有點對最短路徑：基于路徑長度的遞歸163
13.4 Floyd-Warshall算法：基于中繼節點范圍的遞歸164
13.5 習題166
第14章 動態規劃算法168
14.1 動態規劃的動機168
14.2 動態規劃的基本過程169
14.2.1 基于樸素遍歷的遞歸170
14.2.2 未作規劃的遞歸171
14.2.3 采用動態規劃的遞歸171
14.3 動態規劃的應用174
14.3.1 動態規劃的要素174
14.3.2 編輯距離問題175
14.3.3 硬幣兌換問題176
14.3.4 最大和連續子序列問題178
14.3.5 相容任務調度問題179
14.4 習題179
第六部分 計算復雜性理論初步
第15章 多項式時間歸約188
15.1 問題間的歸約188
15.1.1 優化問題和判定問題188
15.1.2 問題間歸約的定義189
15.2 多項式時間：解決問題與完成歸約190
15.2.1 多項式時間可解的問題190
15.2.2 多項式時間歸約191
15.3 習題192
第16章 NP完全問題的基本概念193
16.1 NP完全問題的定義193
16.1.1 NP問題的定義193
16.1.2 NP難與NP完全問題的定義194
16.2 NP完全性證明的初步知識195
16.2.1 一般問題和特例問題195
16.2.2 等價的問題196
16.3 習題197
附錄A 數學歸納法199
附錄B 二叉樹200
參考文獻201 |
| 序： |
|
