掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
闖進數學世界――探秘歷史名題
-
>
中醫基礎理論
-
>
當代中國政府與政治(新編21世紀公共管理系列教材)
-
>
高校軍事課教程
-
>
思想道德與法治(2021年版)
-
>
毛澤東思想和中國特色社會主義理論體系概論(2021年版)
-
>
中醫內科學·全國中醫藥行業高等教育“十四五”規劃教材
算法設計與分析:C++語言描述 版權信息
- ISBN：9787121483325
- 條形碼：9787121483325 ; 978-7-121-48332-5
- 裝幀：平塑
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
算法設計與分析:C++語言描述 內容簡介
本書為普通高等教育“十一五”國家級規劃教材。 本書內容分為3部分：算法和算法分析、算法設計策略及求解困難問題。第1部分介紹算法問題求解基礎和算法分析基礎，以及兩種新的數據結構：伸展樹與跳表；第2部分討論常用的算法設計策略，包括基本搜索和遍歷方法、分治法、貪心法、動態規劃法、回溯法和分枝限界法；第3部分介紹NP完全問題、隨機算法、近似算法、遺傳算法和密碼算法，并對現代密碼學和數論做了簡要論述。 本書結構清晰、內容翔實、邏輯嚴謹、講解深入淺出。書中算法有完整的C++程序，這些程序構思精巧，有詳細注釋，并且已在C++環境下編譯通過能正確運行。它們既是講解算法設計的示例，幫助理解和掌握復雜抽象的算法設計，也是很好的C++程序設計示例。書中包含大量實例，并附有豐富的習題，便于教學和自學。 本書可作為高等學校計算機及其他相關專業本科生和研究生“算法設計與分析”課程的教材或參考書，是“算法與數據結構”或“數據結構”課程有益的教學參考書，也可供計算機相關從業者及其他希望了解和學習算法知識的人員參考。
算法設計與分析:C++語言描述 目錄
第1部分 算法和算法分析第1章 算法問題求解基礎 11.1 算法概述 11.1.1 什么是算法 11.1.2 為什么學習算法 31.2 問題求解方法 31.2.1 問題和問題求解 41.2.2 問題求解過程 41.2.3 軟件生命周期 51.3 算法設計與分析 51.3.1 算法問題求解過程 51.3.2 如何設計算法 61.3.3 如何表示算法 61.3.4 如何確認算法 6第1部分 算法和算法分析
第1章 算法問題求解基礎 1
1.1 算法概述 1
1.1.1 什么是算法 1
1.1.2 為什么學習算法 3
1.2 問題求解方法 3
1.2.1 問題和問題求解 4
1.2.2 問題求解過程 4
1.2.3 軟件生命周期 5
1.3 算法設計與分析 5
1.3.1 算法問題求解過程 5
1.3.2 如何設計算法 6
1.3.3 如何表示算法 6
1.3.4 如何確認算法 6
1.3.5 如何分析算法 7
1.4 遞歸和歸納 7
1.4.1 遞歸 7
1.4.2 遞歸算法示例 9
1.4.3 歸納證明 11
習題1 13
第2章 算法分析基礎 14
2.1 算法復雜度 14
2.1.1 什么是好的算法 14
2.1.2 影響程序執行時間的因素 15
2.1.3 算法的時間復雜度 16
2.1.4 使用程序步分析算法 17
2.1.5 算法的空間復雜度 18
2.2 漸近表示法 19
2.2.1 大O記號 19
2.2.2 Ω記號 20
2.2.3 Θ記號 21
2.2.4 小o記號 21
2.2.5 算法按時間復雜度分類 21
2.3 遞推關系 22
2.3.1 遞推方程 22
2.3.2 替換方法 23
2.3.3 迭代方法 23
2.3.4 遞歸樹 23
2.3.5 主方法 25
2.4 分攤分析 25
2.4.1 聚集分析 26
2.4.2 會計方法 26
2.4.3 勢能方法 27
習題2 28
第3章 伸展樹與跳表 31
3.1 伸展樹 31
3.1.1 二叉搜索樹 31
3.1.2 自調節樹和伸展樹 31
3.1.3 伸展操作 32
3.1.4 伸展樹類 34
3.1.5 旋轉的實現 34
3.1.6 插入運算的實現 35
3.1.7 分攤分析 37
3.2 跳表 39
3.2.1 什么是跳表 39
3.2.2 跳表類 40
3.2.3 層次分配 42
3.2.4 插入運算的實現 43
3.2.5 性能分析 44
習題3 45第2部分 算法設計策略第4章 基本搜索和遍歷方法 46
4.1 基本概念 46
4.2 圖的搜索和遍歷 47
4.2.1 搜索方法 47
4.2.2 鄰接表類 48
4.2.3 廣度優先搜索 49
4.2.4 深度優先搜索 51
4.3 雙連通分量 53
4.3.1 基本概念 53
4.3.2 發現關節點 54
4.3.3 構造雙連通圖 58
4.4 與或圖 58
4.4.1 問題分解 58
4.4.2 判斷與或樹是否可解 60
4.4.3 構建解樹 61
4.5 區間*值查詢（RMQ） 62
4.5.1 區間信息維護與查詢 62
4.5.2 ST算法求解RMQ問題 63
4.6 *近公共祖先（LCA） 65
4.6.1 概述 65
4.6.2 倍增法求解LCA問題 66
4.6.3 在線RMQ法求解LCA問題 68
4.6.4 Tarjan算法求解LCA問題 70
習題4 73
第5章 分治法 75
5.1 一般方法 75
5.1.1 分治法的基本思想 75
5.1.2 算法分析 76
5.1.3 數據結構 77
5.2 求*大、*小元 78
5.2.1 分治法求解 78
5.2.2 時間分析 79
5.3 二分搜索 80
5.3.1 分治法求解 80
5.3.2 對半搜索 81
5.3.3 二叉判定樹 82
5.3.4 搜索算法的時間下界 84
5.4 排序問題 85
5.4.1 合并排序 85
5.4.2 快速排序 87
5.4.3 排序算法的時間下界 91
5.5 選擇問題 92
5.5.1 分治法求解 92
5.5.2 隨機選擇主元 93
5.5.3 線性時間選擇算法 94
5.5.4 時間分析 96
5.5.5 允許重復元素的選擇算法 97
5.6 斯特拉森矩陣乘法 97
5.6.1 分治法求解 97
5.6.2 斯特拉森矩陣乘法簡介 98
習題5 99
第6章 貪心法 102
6.1 一般方法 102
6.2 背包問題 103
6.2.1 問題描述 103
6.2.2 貪心法求解 104
6.2.3 算法正確性 105
6.3 帶時限的作業排序問題 106
6.3.1 問題描述 106
6.3.2 貪心法求解 107
6.3.3 算法正確性 108
6.3.4 可行性判定 108
6.3.5 作業排序貪心算法 109
6.3.6 改進算法 110
6.4 *佳合并模式 112
6.4.1 問題描述 113
6.4.2 貪心法求解 113
6.4.3 算法正確性 115
6.5 *小代價生成樹 116
6.5.1 問題描述 116
6.5.2 貪心法求解 116
6.5.3 普里姆算法 117
6.5.4 克魯斯卡爾算法 119
6.5.5 算法正確性 121
6.6 單源*短路徑 122
6.6.1 問題描述 122
6.6.2 貪心法求解 122
6.6.3 迪杰斯特拉算法 123
6.6.4 算法正確性 125
6.7 磁帶*優存儲 127
6.7.1 單帶*優存儲 127
6.7.2 多帶*優存儲 128
6.8 貪心法的基本要素 129
6.8.1 *優量度標準 129
6.8.2 *優子結構 129
習題6 130
第7章 動態規劃法 133
7.1 一般方法和基本要素 133
7.1.1 一般方法 133
7.1.2 基本要素 134
7.1.3 多段圖問題 134
7.1.4 資源分配問題 137
7.1.5 關鍵路徑問題 138
7.2 每對結點間的*短路徑 140
7.2.1 問題描述 140
7.2.2 動態規劃法求解 140
7.2.3 弗洛伊德算法 141
7.2.4 算法正確性 143
7.3 矩陣連乘 143
7.3.1 問題描述 143
7.3.2 動態規劃法求解 144
7.3.3 矩陣連乘算法 145
7.3.4 備忘錄方法 147
7.4 *長公共子序列 147
7.4.1 問題描述 147
7.4.2 動態規劃法求解 148
7.4.3 *長公共子序列算法 149
7.4.4 改進算法 151
7.5 *優二叉搜索樹 151
7.5.1 問題描述 151
7.5.2 動態規劃法求解 151
7.5.3 *優二叉搜索樹算法 153
7.6 0/1背包問題 155
7.6.1 問題描述 155
7.6.2 動態規劃法求解 155
7.6.3 0/1背包問題算法框架 157
7.6.4 0/1背包問題算法 160
7.6.5 性能分析 162
7.6.6 使用啟發式方法 163
7.7 流水線作業調度 164
7.7.1 問題描述 164
7.7.2 動態規劃法求解 165
7.7.3 Johnson算法 167
習題7 168
第8章 回溯法 170
8.1 一般方法 170
8.1.1 基本概念 170
8.1.2 剪枝函數和回溯法 171
8.1.3 回溯法的效率分析 173
8.2 n-皇后問題 173
8.2.1 問題描述 173
8.2.2 回溯法求解 174
8.2.3 n-皇后算法 175
8.2.4 時間分析 176
8.3 子集和數問題 177
8.3.1 問題描述 177
8.3.2 回溯法求解 177
8.3.3 子集和數算法 178
8.4 圖著色問題 180
8.4.1 問題描述 180
8.4.2 回溯法求解 180
8.4.3 圖著色算法 181
8.4.4 時間分析 182
8.5 哈密頓環問題 182
8.5.1 問題描述 182
8.5.2 哈密頓環算法 183
8.6 0/1背包問題 184
8.6.1 問題描述 184
8.6.2 回溯法求解 184
8.6.3 限界函數 185
8.6.4 0/1背包問題算法 186
8.7 批處理作業調度 188
8.7.1 問題描述 188
8.7.2 回溯法求解 188
8.7.3 批處理作業調度算法 188
習題8 190
第9章 分枝限界法 192
9.1 一般方法 192
9.1.1 分枝限界法概述 192
9.1.2 LC分枝限界法 194
9.1.3 15謎問題 195
9.2 求*優解的分枝限界法 197
9.2.1 上下界函數 197
9.2.2 FIFO分枝限界法 198
9.2.3 LC分枝限界法 199
9.3 帶時限的作業排序 200
9.3.1 問題描述 200
9.3.2 分枝限界法求解 200
9.3.3 帶時限的作業排序算法 201
9.4 0/1背包問題 203
9.4.1 問題描述 203
9.4.2 分枝限界法求解 203
9.4.3 0/1背包問題算法 204
9.5 旅行商問題 207
9.5.1 問題描述 207
9.5.2 分枝限界法求解 207
9.6 批處理作業調度 211
9.6.1 問題描述 211
9.6.2 分枝限界法求解 211
9.6.3 批處理作業調度算法 212
習題9 215第3部分 求解困難問題第10章 NP完全問題 217
10.1 基本概念 217
10.1.1 不確定算法和不確定機 218
10.1.2 可滿足性問題 220
10.1.3 P類問題和NP類問題 221
10.1.4 NP難度問題和NP完全問題 221
10.2 Cook定理和證明 222
10.2.1 Cook定理 222
10.2.2 簡化的不確定機模型 222
10.2.3 證明Cook定理 223
10.3 一些典型的NP完全問題 227
10.3.1 *大集團 227
10.3.2 頂點覆蓋 228
10.3.3 三元CNF可滿足性 229
10.3.4 圖的著色數 230
10.3.5 有向哈密頓環 231
10.3.6 恰切覆蓋 233
10.3.7 子集和數 234
10.3.8 分劃 235
習題10 236
第11章 隨機算法 238
11.1 基本概念 238
11.1.1 隨機算法概述 238
11.1.2 隨機數發生器 238
11.1.3 隨機算法分類 239
11.2 拉斯維加斯算法 240
11.2.1 標記重復元素算法 240
11.2.2 性能分析 241
11.2.3 n-皇后問題 242
11.2.4 拉斯維加斯算法和回溯法的結合算法 244
11.3 蒙特卡羅算法 245
11.3.1 多數元素問題 246
11.3.2 素數測試問題 247
11.3.3 偽素數測試問題 248
11.3.4 米勒-拉賓算法 249
11.4 舍伍德算法 250
11.4.1 快速排序舍伍德算法 250
11.4.2 性能分析 251
11.4.3 舍伍德算法的其他應用 251
習題11 252
第12章 近似算法 253
12.1 近似算法的性能 253
12.1.1 基本概念 253
12.1.2 絕對性能保證 253
12.1.3 相對性能保證 254
12.1.4 近似方案 255
12.2 絕對近似算法的應用 255
12.2.1 *多程序存儲問題 255
12.2.2 NP難度問題 256
12.3 ?-近似算法的應用 257
12.3.1 頂點覆蓋問題 257
12.3.2 旅行商問題 258
12.3.3 NP難度?-近似旅行商問題 259
12.3.4 具有三角不等式性質的旅行商問題 260
12.3.5 多機調度問題 261
12.4 ?(n)-近似算法 263
12.4.1 集合覆蓋問題 263
展開全部
算法設計與分析:C++語言描述 作者簡介
陳慧南，教授，南京郵電大學計算機學院，主持了多項信息產業部基金項目的研究工作，并負責了多項企業辦公自動化和信息管理網絡系統的研制開發。出版多本教材。曾獲江蘇省普通高校教學成果三等獎，其主持的《數據結構》課程獲江蘇省高校一類優秀課程。
書友推薦
- >
姑媽的寶刀
- >
巴金－再思錄
- >
推拿
- >
名家帶你讀魯迅:朝花夕拾
- >
中國人在烏蘇里邊疆區:歷史與人類學概述
- >
中國歷史的瞬間
- >
二體千字文
- >
企鵝口袋書系列·偉大的思想20:論自然選擇(英漢雙語)
本類暢銷
