掃一掃
關(guān)注中圖網(wǎng)
官方微博
本類五星書更多>
-
>
闖進數(shù)學(xué)世界――探秘歷史名題
-
>
中醫(yī)基礎(chǔ)理論
-
>
當(dāng)代中國政府與政治(新編21世紀(jì)公共管理系列教材)
-
>
高校軍事課教程
-
>
思想道德與法治(2021年版)
-
>
毛澤東思想和中國特色社會主義理論體系概論(2021年版)
-
>
中醫(yī)內(nèi)科學(xué)·全國中醫(yī)藥行業(yè)高等教育“十四五”規(guī)劃教材
算法設(shè)計與分析(第3版 版權(quán)信息
- ISBN：9787302457206
- 條形碼：9787302457206 ; 978-7-302-45720-6
- 裝幀：平裝-膠訂
- 冊數(shù)：暫無
- 重量：暫無
- 所屬分類：>>
算法設(shè)計與分析(第3版 本書特色
《算法設(shè)計與分析（第3版）》系統(tǒng)地介紹了算法設(shè)計與分析的概念和方法，共4篇內(nèi)容。第1篇介紹算法設(shè)計與分析的基本概念，結(jié)合窮舉法、排序問題及其他一些算法，對算法的時間復(fù)雜性的概念及復(fù)雜性的分析方法作了較為詳細(xì)的敘述；第2篇以算法設(shè)計技術(shù)為綱，從合并排序、堆排序、離散集合的umon和find操作開始，進而介紹遞歸技術(shù)、分治法、貪婪法、動態(tài)規(guī)劃、回溯法、分支與限界法和隨機算法等算法設(shè)計技術(shù)及其復(fù)雜性分析；第3篇介紹計算機應(yīng)用領(lǐng)域里的一些算法，如圖和網(wǎng)絡(luò)流，以及計算幾何中的一些問題；第4篇介紹算法設(shè)計與分析中的一些理論問題，如NP完全問題、計算復(fù)雜性問題、下界理論問題，*后介紹近似算法及其性能分析。
《算法設(shè)計與分析（第3版）》內(nèi)容選材適當(dāng)、編排合理、由淺入深、循序漸進、互相銜接、逐步展開，并附有大量實例，既注重算法的思想方法、推導(dǎo)過程和正確性的證明技術(shù)，也注重算法所涉及的數(shù)據(jù)結(jié)構(gòu)、算法的具體實現(xiàn)和算法的工作過程。
《算法設(shè)計與分析（第3版）》可作為高等院校計算機專業(yè)本科生和研究生的教材，也可作為計算機科學(xué)與應(yīng)用的科學(xué)技術(shù)人員的參考資料。
《算法設(shè)計與分析（第3版）》特色：
選材適當(dāng)、編排合理、由淺入深、循序漸進、互相銜接、逐步展開。 《算法設(shè)計與分析（第3版）》系統(tǒng)地介紹了算法設(shè)計與分析的概念和方法，共4篇內(nèi)容。第1篇介紹算法設(shè)計與分析的基本概念，結(jié)合窮舉法、排序問題及其他一些算法，對算法的時間復(fù)雜性的概念及復(fù)雜性的分析方法作了較為詳細(xì)的敘述；第2篇以算法設(shè)計技術(shù)為綱，從合并排序、堆排序、離散集合的umon和find操作開始，進而介紹遞歸技術(shù)、分治法、貪婪法、動態(tài)規(guī)劃、回溯法、分支與限界法和隨機算法等算法設(shè)計技術(shù)及其復(fù)雜性分析；第3篇介紹計算機應(yīng)用領(lǐng)域里的一些算法，如圖和網(wǎng)絡(luò)流，以及計算幾何中的一些問題；第4篇介紹算法設(shè)計與分析中的一些理論問題，如NP完全問題、計算復(fù)雜性問題、下界理論問題，*后介紹近似算法及其性能分析。
《算法設(shè)計與分析（第3版）》內(nèi)容選材適當(dāng)、編排合理、由淺入深、循序漸進、互相銜接、逐步展開，并附有大量實例，既注重算法的思想方法、推導(dǎo)過程和正確性的證明技術(shù)，也注重算法所涉及的數(shù)據(jù)結(jié)構(gòu)、算法的具體實現(xiàn)和算法的工作過程。
《算法設(shè)計與分析（第3版）》可作為高等院校計算機專業(yè)本科生和研究生的教材，也可作為計算機科學(xué)與應(yīng)用的科學(xué)技術(shù)人員的參考資料。
《算法設(shè)計與分析（第3版）》特色：
選材適當(dāng)、編排合理、由淺入深、循序漸進、互相銜接、逐步展開。
盡可能用通俗的語言來表達(dá)深奧的問題，對實現(xiàn)算法的思想方法、推導(dǎo)過程、實現(xiàn)的步驟、所涉及的數(shù)據(jù)結(jié)構(gòu)和□量的描述盡可能詳細(xì)，易于學(xué)生深刻地理解和掌握算法的工作原理，學(xué)會如何設(shè)計和實現(xiàn)算法。
對算法的理論基礎(chǔ)和定理的證明給予足夠的重視，定義的敘述盡可能嚴(yán)謹(jǐn)，方法推導(dǎo)、定理證明的邏輯盡可能嚴(yán)密，培養(yǎng)學(xué)生良好的邏輯思維能力和嚴(yán)謹(jǐn)規(guī)范的科學(xué)方法。
無論是算法的基本概念、算法復(fù)雜性的分析方法，還是算法的實現(xiàn)步驟，都盡可能提供大量實例加以解釋說明，用實例來模擬算法的運行，有助于學(xué)生學(xué)以致用。
算法設(shè)計與分析(第3版 內(nèi)容簡介
《算法設(shè)計與分析（第3版）》系統(tǒng)地介紹了算法設(shè)計與分析的概念和方法，共4篇內(nèi)容。第1篇介紹算法設(shè)計與分析的基本概念，結(jié)合窮舉法、排序問題及其他一些算法，對算法的時間復(fù)雜性的概念及復(fù)雜性的分析方法作了較為詳細(xì)的敘述；第2篇以算法設(shè)計技術(shù)為綱，從合并排序、堆排序、離散集合的umon和find操作開始，進而介紹遞歸技術(shù)、分治法、貪婪法、動態(tài)規(guī)劃、回溯法、分支與限界法和隨機算法等算法設(shè)計技術(shù)及其復(fù)雜性分析；第3篇介紹計算機應(yīng)用領(lǐng)域里的一些算法，如圖和網(wǎng)絡(luò)流，以及計算幾何中的一些問題；第4篇介紹算法設(shè)計與分析中的一些理論問題，如NP完全問題、計算復(fù)雜性問題、下界理論問題，后介紹近似算法及其性能分析。 《算法設(shè)計與分析（第3版）》內(nèi)容選材適當(dāng)、編排合理、由淺入深、循序漸進、互相銜接、逐步展開，并附有大量實例，既注重算法的思想方法、推導(dǎo)過程和正確性的證明技術(shù)，也注重算法所涉及的數(shù)據(jù)結(jié)構(gòu)、算法的具體實現(xiàn)和算法的工作過程。 《算法設(shè)計與分析（第3版）》可作為高等院校計算機專業(yè)本科生和研究生的教材，也可作為計算機科學(xué)與應(yīng)用的科學(xué)技術(shù)人員的參考資料。 《算法設(shè)計與分析（第3版）》特色： 選材適當(dāng)、編排合理、由淺入深、循序漸進、互相銜接、逐步展開。
算法設(shè)計與分析(第3版 目錄
第1篇 算法設(shè)計與分析的基本概念
第1章 算法的基本概念 2
1.1 引言 2
1.1.1算法的定義和特征 2
1.1.2算法設(shè)計的例子——窮舉法 4
1.1.3算法的復(fù)雜性分析 7
1.2 算法的時間復(fù)雜性 8
1.2.1算法的輸入規(guī)模和運行時間的階 8
1.2.2運行時間的上界——O記號 11
1.2.3運行時間的下界——Ω記號 12
1.2.4運行時間的準(zhǔn)確界——Θ記號 13
1.2.5O記號、Ω記號、Θ記號的性質(zhì) 17
1.2.6復(fù)雜性類型和o記號 18
習(xí)題 19
參考文獻(xiàn) 20
第2章 算法的復(fù)雜性分析 21
2.1 常用的函數(shù)和公式 21
2.1.1整數(shù)函數(shù) 21
2.1.2對數(shù)函數(shù) 22
2.1.3排列、組合和二項式系數(shù) 23
2.1.4級數(shù)求和 24
2.2 算法的時間復(fù)雜性分析 25
2.2.1循環(huán)次數(shù)的統(tǒng)計 26
2.2.2基本操作頻率的統(tǒng)計 29
2.2.3計算步的統(tǒng)計 32
2.3 情況、 壞情況和平均情況分析 33
2.3.1情況、 壞情況和平均情況 33
2.3.2情況和 壞情況分析 34
2.3.3平均情況分析 37
2.4 用生成函數(shù)求解遞歸方程40
2.4.1生成函數(shù)及其性質(zhì) 40
2.4.2用生成函數(shù)求解遞歸方程 43
2.5 用特征方程求解遞歸方程46
2.5.1k階常系數(shù)線性齊次遞歸方程 47
2.5.2k階常系數(shù)線性非齊次遞歸方程 49
2.6 用遞推方法求解遞歸方程51
2.6.1遞推 52
2.6.2用遞推法求解變系數(shù)遞歸方程 52
2.6.3換名 54
2.7 算法的空間復(fù)雜性 56
2.8 算法 57
習(xí)題 58
參考文獻(xiàn) 60
第2篇 算法設(shè)計的基本技術(shù)
第3章 排序問題和離散集合的操作62
3.1 合并排序 62
3.1.1合并排序算法的實現(xiàn) 62
3.1.2合并排序算法的分析 64
3.2 基于堆的排序 65
3.2.1堆 66
3.2.2堆的操作 67
3.2.3堆的建立 70
3.2.4堆的排序 73
3.3 基數(shù)排序 74
3.3.1基數(shù)排序算法的思想方法 74
3.3.2基數(shù)排序算法的實現(xiàn) 76
3.3.3基數(shù)排序算法的分析 78
3.4 離散集合的Union_Find操作 79
3.4.1用于Union_Find操作的數(shù)據(jù)結(jié)構(gòu) 79
3.4.2union、find操作及路徑壓縮 81
習(xí)題 84
參考文獻(xiàn) 85
第4章 遞歸和分治 86
4.1 基于歸納的遞歸算法 86
4.1.1基于歸納的遞歸算法的思想方法 86
4.1.2遞歸算法的例子 87
4.1.3排列問題的遞歸算法 91
4.1.4求數(shù)組主元素的遞歸算法 95
4.1.5整數(shù)劃分問題的遞歸算法 98
4.2 分治法 100
4.2.1分治法的例子 100
4.2.2分治法的設(shè)計原理 104
4.2.3快速排序 111
4.2.4多項式乘積和大整數(shù)乘法 116
4.2.5平面點集 接近點對問題 123
4.2.6選擇問題 130
4.2.7殘缺棋盤問題 136
習(xí)題 141
參考文獻(xiàn) 143
第5章 貪婪法 145
5.1 貪婪法概述 146
5.1.1貪婪法的設(shè)計思想 146
5.1.2貪婪法的例子——貨郎擔(dān)問題 147
5.2 背包問題 148
5.2.1背包問題貪婪算法的實現(xiàn) 148
5.2.2背包問題貪婪算法的分析 150
5.3 單源 短路徑問題 151
5.3.1解 短路徑的狄斯奎諾算法 151
5.3.2狄斯奎諾算法的實現(xiàn) 153
5.3.3狄斯奎諾算法的分析 155
5.4 花費生成樹問題 156
5.4.1花費生成樹概述 156
5.4.2克魯斯卡爾算法 157
5.4.3普里姆算法 161
5.5 霍夫曼編碼問題 165
5.5.1前綴碼和二叉樹 165
5.5.2霍夫曼編碼的實現(xiàn) 169
習(xí)題 171
參考文獻(xiàn) 173
第6章 動態(tài)規(guī)劃 174
6.1 動態(tài)規(guī)劃的思想方法 174
6.1.1動態(tài)規(guī)劃的決策原理 174
6.1.2動態(tài)規(guī)劃實例——貨郎擔(dān)問題 175
6.2 多段圖的 短路徑問題177
6.2.1多段圖的決策過程 178
6.2.2多段圖動態(tài)規(guī)劃算法的實現(xiàn) 180
6.3 資源分配問題 181
6.3.1資源分配的決策過程 182
6.3.2資源分配算法的實現(xiàn) 184
6.4 設(shè)備更新問題 187
6.4.1設(shè)備更新問題的決策過程 187
6.4.2設(shè)備更新算法的實現(xiàn) 190
6.5 公共子序列問題 192
6.5.1公共子序列的搜索過程 192
6.5.2公共子序列算法的實現(xiàn) 195
6.60/1背包問題 196
6.6.10/1背包問題的求解過程 196
6.6.20/1背包問題的實現(xiàn) 198
6.7RNA堿基對匹配問題 199
6.7.1RNA堿基對匹配的搜索過程 200
6.7.2RNA堿基對匹配算法的實現(xiàn) 203
習(xí)題 205
參考文獻(xiàn) 207
第7章 回溯 208
7.1 回溯法的思想方法 208
7.1.1問題的解空間和狀態(tài)空間樹 208
7.1.2狀態(tài)空間樹的動態(tài)搜索 209
7.1.3回溯法的一般性描述 211
7.2n皇后問題 213
7.2.1n皇后問題的求解過程 213
7.2.2n皇后問題算法的實現(xiàn) 215
7.3 圖的著色問題 217
7.3.1圖著色問題的求解過程 218
7.3.2圖的m著色問題算法的實現(xiàn) 220
7.4 哈密爾頓回路問題 222
7.4.1哈密爾頓回路的求解過程 222
7.4.2哈密爾頓回路算法的實現(xiàn) 224
7.50/1背包問題 225
7.5.1回溯法解0/1背包問題的求解過程 226
7.5.2回溯法解0/1背包問題算法的實現(xiàn) 229
7.6 回溯法的效率分析 231
習(xí)題 234
參考文獻(xiàn) 235
第8章 分支與限界 236
8.1 分支與限界法的基本思想236
8.2 作業(yè)分配問題 238
8.2.1分支限界法解作業(yè)分配問題的思想方法 238
8.2.2分支限界法解作業(yè)分配問題算法的實現(xiàn) 241
8.3 單源 短路徑問題 244
8.3.1分支限界法解單源 短路徑問題的思想方法 244
8.3.2分支限界法解單源 短路徑問題算法的實現(xiàn) 246
8.40/1背包問題 248
8.4.1分支限界法解0/1背包問題的思想方法和求解過程 249
8.4.20/1背包問題分支限界算法的實現(xiàn) 251
8.5 貨郎擔(dān)問題 254
8.5.1費用矩陣的特性及歸約 254
8.5.2界限的確定和分支的選擇 256
8.5.3貨郎擔(dān)問題的求解過程 259
8.5.4幾個輔助函數(shù)的實現(xiàn) 262
8.5.5貨郎擔(dān)問題分支限界算法的實現(xiàn) 268
習(xí)題 271
參考文獻(xiàn) 272
第9章 算法 273
9.1 算法概述 273
9.1.1算法的類型 273
9.1.2數(shù)發(fā)生器 274
9.2 舍伍德算法 275
9.2.1快速排序算法 275
9.2.2選擇算法 277
9.3 拉斯維加斯算法 280
9.3.1字符串匹配 280
9.3.2整數(shù)因子 284
9.4 蒙特卡羅算法 285
9.4.1數(shù)組的主元素問題 285
9.4.2素數(shù)測試 287
習(xí)題 290
參考文獻(xiàn) 291
第3篇 計算機應(yīng)用領(lǐng)域的一些基法
0章 圖和網(wǎng)絡(luò)問題 294
10.1圖的遍歷 294
10.1.1圖的深度優(yōu)先搜索遍歷 294
10.1.2圖的廣度優(yōu)先搜索遍歷 299
10.1.3無向圖的接合點 301
10.1.4有向圖的強連通分支 305
10.2網(wǎng)絡(luò)流 308
10.2.1網(wǎng)絡(luò)流的概念 308
10.2.2Ford_Fulkerson方法和容量增廣 312
10.2.3 短路徑增廣 315
10.3二分圖的匹配問題 320
10.3.1預(yù)備知識 321
10.3.2二分圖匹配的匈牙利樹方法 323
習(xí)題 329
參考文獻(xiàn) 331
1章 計算幾何問題 332
11.1引言 332
11.2平面線段的交點問題 334
11.2.1尋找平面線段交點的思想方法 335
11.2.2尋找平面線段交點的實現(xiàn) 337
11.3凸殼問題 342
11.3.1凸殼問題的格雷厄姆掃描法 343
11.3.2格雷厄姆掃描法的實現(xiàn) 344
11.4平面點集的直徑問題 346
11.4.1求取平面點集直徑的思想方法 346
11.4.2平面點集直徑的求取 348
習(xí)題 350
參考文獻(xiàn) 351
第4篇 算法設(shè)計與分析的一些理論問題
2章 NP完全問題 354
12.1P類和NP類問題 355
12.1.1P類問題 355
12.1.2NP類問題 356
12.2NP完全問題 358
12.2.1NP完全問題的定義 358
12.2.2幾個典型的NP完全問題 360
12.2.3其他NP完全問題 366
12.3co_NP類和NPI類問題 366
習(xí)題 369
參考文獻(xiàn) 370
3章 計算復(fù)雜性 371
13.1計算模型 371
13.1.1圖靈機的基本模型 371
13.1.2k帶圖靈機和時間復(fù)雜性 374
13.1.3離線圖靈機和空間復(fù)雜性 376
13.1.4可滿足性問題和Cook定理 379
13.2復(fù)雜性類型之間的關(guān)系 381
13.2.1時間復(fù)雜性和空間復(fù)雜性的關(guān)系 382
13.2.2時間譜系定理和空間譜系定理 384
13.2.3填充變元 389
13.3歸約性關(guān)系 391
13.4完備性 394
13.4.1NLOGSPACE完全問題 394
13.4.2PSPACE完全問題和P完全問題 396
習(xí)題 397
參考文獻(xiàn) 398
4章 下界 399
14.1平凡下界 399
14.2判定樹模型 399
14.2.1檢索問題 400
14.2.2排序問題 401
14.3代數(shù)判定樹模型 402
14.3.1代數(shù)判定樹模型及下界定理 402
14.3.2極點問題 404
14.4線性時間歸約 405
14.4.1凸殼問題 406
14.4.2多項式插值問題 406
習(xí)題 408
參考文獻(xiàn) 408
5章 近似算法 409
15.1近似算法的性能 409
15.2裝箱問題 410
15.2.1首次適宜算法 411
15.2.2 適宜算法及其他算法 412
15.3頂點覆蓋問題 414
15.4貨郎擔(dān)問題 416
15.4.1歐幾里得貨郎擔(dān)問題 417
15.4.2一般的貨郎擔(dān)問題 419
15.5多項式近似方案 419
15.5.10/1背包問題的多項式近似方案 420
15.5.2子集求和問題的完全多項式近似方案 423
習(xí)題 425
參考文獻(xiàn) 426
參考文獻(xiàn) 427
1.1 引言 2
1.1.1算法的定義和特征 2
1.1.2算法設(shè)計的例子——窮舉法 4
1.1.3算法的復(fù)雜性分析 7
1.2 算法的時間復(fù)雜性 8
1.2.1算法的輸入規(guī)模和運行時間的階 8
1.2.2運行時間的上界——O記號 11
1.2.3運行時間的下界——Ω記號 12
1.2.4運行時間的準(zhǔn)確界——Θ記號 13
1.2.5O記號、Ω記號、Θ記號的性質(zhì) 17
1.2.6復(fù)雜性類型和o記號 18
習(xí)題 19
參考文獻(xiàn) 20
第2章 算法的復(fù)雜性分析 21
2.1 常用的函數(shù)和公式 21
2.1.1整數(shù)函數(shù) 21
2.1.2對數(shù)函數(shù) 22
2.1.3排列、組合和二項式系數(shù) 23
2.1.4級數(shù)求和 24
2.2 算法的時間復(fù)雜性分析 25
2.2.1循環(huán)次數(shù)的統(tǒng)計 26
2.2.2基本操作頻率的統(tǒng)計 29
2.2.3計算步的統(tǒng)計 32
2.3 情況、 壞情況和平均情況分析 33
2.3.1情況、 壞情況和平均情況 33
2.3.2情況和 壞情況分析 34
2.3.3平均情況分析 37
2.4 用生成函數(shù)求解遞歸方程40
2.4.1生成函數(shù)及其性質(zhì) 40
2.4.2用生成函數(shù)求解遞歸方程 43
2.5 用特征方程求解遞歸方程46
2.5.1k階常系數(shù)線性齊次遞歸方程 47
2.5.2k階常系數(shù)線性非齊次遞歸方程 49
2.6 用遞推方法求解遞歸方程51
2.6.1遞推 52
2.6.2用遞推法求解變系數(shù)遞歸方程 52
2.6.3換名 54
2.7 算法的空間復(fù)雜性 56
2.8 算法 57
習(xí)題 58
參考文獻(xiàn) 60
第2篇 算法設(shè)計的基本技術(shù)
第3章 排序問題和離散集合的操作62
3.1 合并排序 62
3.1.1合并排序算法的實現(xiàn) 62
3.1.2合并排序算法的分析 64
3.2 基于堆的排序 65
3.2.1堆 66
3.2.2堆的操作 67
3.2.3堆的建立 70
3.2.4堆的排序 73
3.3 基數(shù)排序 74
3.3.1基數(shù)排序算法的思想方法 74
3.3.2基數(shù)排序算法的實現(xiàn) 76
3.3.3基數(shù)排序算法的分析 78
3.4 離散集合的Union_Find操作 79
3.4.1用于Union_Find操作的數(shù)據(jù)結(jié)構(gòu) 79
3.4.2union、find操作及路徑壓縮 81
習(xí)題 84
參考文獻(xiàn) 85
第4章 遞歸和分治 86
4.1 基于歸納的遞歸算法 86
4.1.1基于歸納的遞歸算法的思想方法 86
4.1.2遞歸算法的例子 87
4.1.3排列問題的遞歸算法 91
4.1.4求數(shù)組主元素的遞歸算法 95
4.1.5整數(shù)劃分問題的遞歸算法 98
4.2 分治法 100
4.2.1分治法的例子 100
4.2.2分治法的設(shè)計原理 104
4.2.3快速排序 111
4.2.4多項式乘積和大整數(shù)乘法 116
4.2.5平面點集 接近點對問題 123
4.2.6選擇問題 130
4.2.7殘缺棋盤問題 136
習(xí)題 141
參考文獻(xiàn) 143
第5章 貪婪法 145
5.1 貪婪法概述 146
5.1.1貪婪法的設(shè)計思想 146
5.1.2貪婪法的例子——貨郎擔(dān)問題 147
5.2 背包問題 148
5.2.1背包問題貪婪算法的實現(xiàn) 148
5.2.2背包問題貪婪算法的分析 150
5.3 單源 短路徑問題 151
5.3.1解 短路徑的狄斯奎諾算法 151
5.3.2狄斯奎諾算法的實現(xiàn) 153
5.3.3狄斯奎諾算法的分析 155
5.4 花費生成樹問題 156
5.4.1花費生成樹概述 156
5.4.2克魯斯卡爾算法 157
5.4.3普里姆算法 161
5.5 霍夫曼編碼問題 165
5.5.1前綴碼和二叉樹 165
5.5.2霍夫曼編碼的實現(xiàn) 169
習(xí)題 171
參考文獻(xiàn) 173
第6章 動態(tài)規(guī)劃 174
6.1 動態(tài)規(guī)劃的思想方法 174
6.1.1動態(tài)規(guī)劃的決策原理 174
6.1.2動態(tài)規(guī)劃實例——貨郎擔(dān)問題 175
6.2 多段圖的 短路徑問題177
6.2.1多段圖的決策過程 178
6.2.2多段圖動態(tài)規(guī)劃算法的實現(xiàn) 180
6.3 資源分配問題 181
6.3.1資源分配的決策過程 182
6.3.2資源分配算法的實現(xiàn) 184
6.4 設(shè)備更新問題 187
6.4.1設(shè)備更新問題的決策過程 187
6.4.2設(shè)備更新算法的實現(xiàn) 190
6.5 公共子序列問題 192
6.5.1公共子序列的搜索過程 192
6.5.2公共子序列算法的實現(xiàn) 195
6.60/1背包問題 196
6.6.10/1背包問題的求解過程 196
6.6.20/1背包問題的實現(xiàn) 198
6.7RNA堿基對匹配問題 199
6.7.1RNA堿基對匹配的搜索過程 200
6.7.2RNA堿基對匹配算法的實現(xiàn) 203
習(xí)題 205
參考文獻(xiàn) 207
第7章 回溯 208
7.1 回溯法的思想方法 208
7.1.1問題的解空間和狀態(tài)空間樹 208
7.1.2狀態(tài)空間樹的動態(tài)搜索 209
7.1.3回溯法的一般性描述 211
7.2n皇后問題 213
7.2.1n皇后問題的求解過程 213
7.2.2n皇后問題算法的實現(xiàn) 215
7.3 圖的著色問題 217
7.3.1圖著色問題的求解過程 218
7.3.2圖的m著色問題算法的實現(xiàn) 220
7.4 哈密爾頓回路問題 222
7.4.1哈密爾頓回路的求解過程 222
7.4.2哈密爾頓回路算法的實現(xiàn) 224
7.50/1背包問題 225
7.5.1回溯法解0/1背包問題的求解過程 226
7.5.2回溯法解0/1背包問題算法的實現(xiàn) 229
7.6 回溯法的效率分析 231
習(xí)題 234
參考文獻(xiàn) 235
第8章 分支與限界 236
8.1 分支與限界法的基本思想236
8.2 作業(yè)分配問題 238
8.2.1分支限界法解作業(yè)分配問題的思想方法 238
8.2.2分支限界法解作業(yè)分配問題算法的實現(xiàn) 241
8.3 單源 短路徑問題 244
8.3.1分支限界法解單源 短路徑問題的思想方法 244
8.3.2分支限界法解單源 短路徑問題算法的實現(xiàn) 246
8.40/1背包問題 248
8.4.1分支限界法解0/1背包問題的思想方法和求解過程 249
8.4.20/1背包問題分支限界算法的實現(xiàn) 251
8.5 貨郎擔(dān)問題 254
8.5.1費用矩陣的特性及歸約 254
8.5.2界限的確定和分支的選擇 256
8.5.3貨郎擔(dān)問題的求解過程 259
8.5.4幾個輔助函數(shù)的實現(xiàn) 262
8.5.5貨郎擔(dān)問題分支限界算法的實現(xiàn) 268
習(xí)題 271
參考文獻(xiàn) 272
第9章 算法 273
9.1 算法概述 273
9.1.1算法的類型 273
9.1.2數(shù)發(fā)生器 274
9.2 舍伍德算法 275
9.2.1快速排序算法 275
9.2.2選擇算法 277
9.3 拉斯維加斯算法 280
9.3.1字符串匹配 280
9.3.2整數(shù)因子 284
9.4 蒙特卡羅算法 285
9.4.1數(shù)組的主元素問題 285
9.4.2素數(shù)測試 287
習(xí)題 290
參考文獻(xiàn) 291
第3篇 計算機應(yīng)用領(lǐng)域的一些基法
0章 圖和網(wǎng)絡(luò)問題 294
10.1圖的遍歷 294
10.1.1圖的深度優(yōu)先搜索遍歷 294
10.1.2圖的廣度優(yōu)先搜索遍歷 299
10.1.3無向圖的接合點 301
10.1.4有向圖的強連通分支 305
10.2網(wǎng)絡(luò)流 308
10.2.1網(wǎng)絡(luò)流的概念 308
10.2.2Ford_Fulkerson方法和容量增廣 312
10.2.3 短路徑增廣 315
10.3二分圖的匹配問題 320
10.3.1預(yù)備知識 321
10.3.2二分圖匹配的匈牙利樹方法 323
習(xí)題 329
參考文獻(xiàn) 331
1章 計算幾何問題 332
11.1引言 332
11.2平面線段的交點問題 334
11.2.1尋找平面線段交點的思想方法 335
11.2.2尋找平面線段交點的實現(xiàn) 337
11.3凸殼問題 342
11.3.1凸殼問題的格雷厄姆掃描法 343
11.3.2格雷厄姆掃描法的實現(xiàn) 344
11.4平面點集的直徑問題 346
11.4.1求取平面點集直徑的思想方法 346
11.4.2平面點集直徑的求取 348
習(xí)題 350
參考文獻(xiàn) 351
第4篇 算法設(shè)計與分析的一些理論問題
2章 NP完全問題 354
12.1P類和NP類問題 355
12.1.1P類問題 355
12.1.2NP類問題 356
12.2NP完全問題 358
12.2.1NP完全問題的定義 358
12.2.2幾個典型的NP完全問題 360
12.2.3其他NP完全問題 366
12.3co_NP類和NPI類問題 366
習(xí)題 369
參考文獻(xiàn) 370
3章 計算復(fù)雜性 371
13.1計算模型 371
13.1.1圖靈機的基本模型 371
13.1.2k帶圖靈機和時間復(fù)雜性 374
13.1.3離線圖靈機和空間復(fù)雜性 376
13.1.4可滿足性問題和Cook定理 379
13.2復(fù)雜性類型之間的關(guān)系 381
13.2.1時間復(fù)雜性和空間復(fù)雜性的關(guān)系 382
13.2.2時間譜系定理和空間譜系定理 384
13.2.3填充變元 389
13.3歸約性關(guān)系 391
13.4完備性 394
13.4.1NLOGSPACE完全問題 394
13.4.2PSPACE完全問題和P完全問題 396
習(xí)題 397
參考文獻(xiàn) 398
4章 下界 399
14.1平凡下界 399
14.2判定樹模型 399
14.2.1檢索問題 400
14.2.2排序問題 401
14.3代數(shù)判定樹模型 402
14.3.1代數(shù)判定樹模型及下界定理 402
14.3.2極點問題 404
14.4線性時間歸約 405
14.4.1凸殼問題 406
14.4.2多項式插值問題 406
習(xí)題 408
參考文獻(xiàn) 408
5章 近似算法 409
15.1近似算法的性能 409
15.2裝箱問題 410
15.2.1首次適宜算法 411
15.2.2 適宜算法及其他算法 412
15.3頂點覆蓋問題 414
15.4貨郎擔(dān)問題 416
15.4.1歐幾里得貨郎擔(dān)問題 417
15.4.2一般的貨郎擔(dān)問題 419
15.5多項式近似方案 419
15.5.10/1背包問題的多項式近似方案 420
15.5.2子集求和問題的完全多項式近似方案 423
習(xí)題 425
參考文獻(xiàn) 426
參考文獻(xiàn) 427
展開全部
書友推薦
- >
二體千字文
- >
莉莉和章魚
- >
龍榆生：詞曲概論/大家小書
- >
羅曼·羅蘭讀書隨筆-精裝
- >
新文學(xué)天穹兩巨星--魯迅與胡適/紅燭學(xué)術(shù)叢書(紅燭學(xué)術(shù)叢書)
- >
上帝之肋:男人的真實旅程
- >
中國歷史的瞬間
- >
人文閱讀與收藏·良友文學(xué)叢書:一天的工作
本類暢銷
