算法設計與分析 pdf epub mobi txt 電子書 下載 2025

簡體網頁||繁體網頁

☆☆☆☆☆

黃宇 著

齣版社： 機械工業齣版社

ISBN：9787111572978

版次：1

商品編碼：12145209

品牌：機工齣版

包裝：平裝

叢書名： 麵嚮CS2013計算機專業規劃教材

開本：16開

齣版時間：2017-08-01

用紙：膠版紙

頁數：198

內容簡介

本書講授算法設計與分析的基礎知識。首先介紹計算模型的基本概念；其次圍繞遍曆、分治、貪心、動態規劃這四個經典算法設計策略，講解瞭排序、選擇、查找、圖遍曆、小生成樹、短路徑等經典算法問題；後介紹瞭計算復雜性的基礎知識。本書主要麵嚮計算機專業本科生，以及其他需要學習計算機科學基礎知識與瞭解計算機程序設計背後原理的讀者。

目錄

前言
教學建議
第一部分　計算模型
第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

前言/序言

算法是計算的靈魂(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

評分☆☆☆☆☆

很不錯，慢慢研究

評分☆☆☆☆☆

書不到兩百頁，比較簡練，甚至有點偏少瞭。感覺不太適閤小白。

評分☆☆☆☆☆

考研用的書長得比較好

評分☆☆☆☆☆

書不到兩百頁，比較簡練，甚至有點偏少瞭。感覺不太適閤小白。

評分☆☆☆☆☆

考研用的書長得比較好

評分☆☆☆☆☆

書不到兩百頁，比較簡練，甚至有點偏少瞭。感覺不太適閤小白。

評分☆☆☆☆☆

非常好

評分☆☆☆☆☆

講得還比較清楚

評分☆☆☆☆☆

書不到兩百頁，比較簡練，甚至有點偏少瞭。感覺不太適閤小白。