共找到6條詞條名為演算法設計與分析的結果 展開
演演算法設計與分析
第二版
《演演算法設計與分析（第二版）》是西安電子科技大學出版社出版的一本圖書。作 者是霍紅衛。書中以類高級程序設計語言對演演算法所作的簡明描述，使得稍微具有程序設計語言知識的人即可讀懂。此外，書中以大量圖例說明每個演演算法的工作過程，使得演演算法更加易於理解和掌握。
全書共8章，內容包括演演算法基礎、基本演演算法設計和分析技術(分治法、動態規劃、貪心法、回溯法和分枝限界法)、圖演演算法以及NP完全性理論。
本書可作為高等院校與計算機相關的各專業“演演算法設計”課程的教材，也可作為計算機領域的相關科研人員的參考書。此外，本書還可供參加ACM程序設計大賽的演演算法愛好者參考
第1章 演演算法基礎 1
1.1 演演算法 1
1.1.1 冒泡排序 1
1.1.2 循環不變式和冒泡排序演演算法的正確性 2
1.1.3 偽代碼使用約定 3
1.2 演演算法分析 4
1.2.1 冒泡排序演演算法分析 5
1.2.2 最壞情況和平均情況分析 6
1.2.3 增長的數量級 6
1.3 演演算法的運行時間 7
1.3.1 函數增長 7
1.3.2 漸近表示 8
習題 10
第2章 分治法 13
2.1 遞歸與遞歸方程 13
2.1.1 遞歸的概念 13
2.1.2 替換方法 16
2.1.3 遞歸樹方法 17
2.1.4 主方法 18
2.2 分治法 20
2.2.1 分治法的基本思想 20
2.2.2 二叉查找演演算法 21
2.3 分治法應用實例 24
2.3.1 找最大值與最小值 24
2.3.2 Strassen矩陣乘法 26
2.3.3 整數相乘 27
2.3.4 歸併排序 28
2.3.5 快速排序 33
2.3.6 線性時間選擇 37
2.3.7 最近點對問題 41
習題 44
第3章 動態規劃 49
3.1 用表代替遞歸 49
3.2 0－1背包問題 52
3.3 矩陣鏈乘問題 54
3.4 動態規劃的基本元素 60
3.5 備忘錄方法 64
3.6 裝配線調度問題 70
3.7 最長公共子序列 73
3.8 最優二分檢索樹 77
3.9 凸多邊形最優三角剖分 84
習題 88
第4章 貪心法 98
4.1 背包問題 98
4.2 活動選擇問題 101
4.3 貪心演演算法的基本元素 105
4.4 哈夫曼編碼 107
4.5 最小生成樹演演算法 113
4.5.1 最小生成樹的基本原理 113
4.5.2 Kruskal演演算法 116
4.5.3 Prim演演算法 120
4.5.4 Boruvka演演算法 124
4.5.5 比較與改進 126
4.6 貪心演演算法的理論基礎 126
4.7 作業調度問題 130
習題 131
第5章 回溯法 136
5.1 回溯法的基本原理 136
5.2 n皇后問題 140
5.3 子集和數問題 143
5.4 0－1背包問題 146
5.5 著色問題 149
習題 152
第6章 分枝限界法 155
6.1 分枝限界法的基本思想 155
6.2 0－1背包問題 159
6.3 作業調度問題 167
習題 170
第7章 圖演演算法 172
7.1 圖的表示 172
7.2 廣度優先搜索 173
7.3 Dijkstra演演算法 175
7.4 BellmanFord演演算法 182
7.5 FloydWarshall演演算法 184
習題 185
第8章 NP完全性 189
8.1 P類問題和NP類問題 189
8.1.1 複雜類P和複雜類NP 190
8.1.2 NP中的有趣問題 192
8.2 NP完全性 194
8.2.1 多項式時間歸約和NP難度 194
8.2.2 Cook定理 195
8.3 典型的NP完全問題 196
8.3.1 CNF3SAT問題和3SAT問題 198
8.3.2 頂點覆蓋問題 200
8.3.3 團問題和集合覆蓋問題 202
8.3.4 子集和數問題與背包問題 203
8.3.5 哈密爾頓迴路問題和TSP問題 205
習題 208
附錄A 習題選解 211
附錄B 索引 226
參考文獻 231
