《算法之道》介紹

send_linux

為了方便C/C++版面CUer對(duì)新技術(shù)和新知識(shí)的追求，我們會(huì)不定期的提供一些大家喜歡的和版本相關(guān)的技術(shù)類圖書，采取拍賣的方式進(jìn)行，歡迎本討論區(qū)愛好技術(shù)的各位CUer參與競拍。

    同時(shí),也歡迎大家提議更多大家喜好的技術(shù)圖書,我們后期會(huì)盡量的去提供，給大家更多更好的選擇。

    本次的書籍是提供給本版的技術(shù)愛好者和相關(guān)從業(yè)人員的(至少本版發(fā)帖20貼以上)，所以非本版人員請(qǐng)勿擾亂拍賣活動(dòng)，歡迎大家監(jiān)督！

算法之道

• 作者：鄒恒明
• 出版社：機(jī)械工業(yè)出版社
• ISBN：9787111294948
• 上架時(shí)間：2010-1-29
• 出版日期：2010 年2月
• 開本：16開
• 頁碼：292
• 版次：1-1

圖書簡介：

本書追求的目標(biāo)是算法背后的邏輯，是一本啟示書，而不是一本包羅萬象的算法大全。因此，本書甄選了那些最能夠展現(xiàn)算法思想、戰(zhàn)略和精華，并能夠有效訓(xùn)練算法思維的內(nèi)容。本書將算法的討論分為五大部分：算法基礎(chǔ)篇、算法設(shè)計(jì)篇、算法分析篇、經(jīng)典算法篇、難解與無解篇。每一個(gè)部分分別討論算法的一大方面：基礎(chǔ)、設(shè)計(jì)、分析、經(jīng)典和難解問題。
    本書既可以作為大學(xué)本科或研究生的算法教材或參考書，也可以作為對(duì)算法有興趣的讀者提升認(rèn)知深度的讀物。

圖書目錄：

前言
    第一篇  算法基礎(chǔ)篇
    第1章  從無有到無窮        2
    1.1  意念與現(xiàn)實(shí)        3
    1.2  什么是算法        4
    1.3  算法的表示        6
    1.4  算法之魂        7
    1.5  如何比較速度        8
    1.6  算法與計(jì)算機(jī)的關(guān)系        9
    1.7  算法的范疇        10
    1.8  為什么學(xué)習(xí)算法        10
    思考題        11
    第2章  計(jì)數(shù)與漸近        12
    2.1  算法的分析        12
    2.1.1  正確性分析        13
    2.1.2  時(shí)空效率分析        14
    2.1.3  時(shí)空特性分析        14
    2.2  計(jì)數(shù)：算法分析的核心        14
    2.3  算法設(shè)計(jì)        15
    2.4  算法效率表示        16
            .2.5  漸近分析        17
    2.6  O、(、(表示        18
    2.7  最好、最壞、平均        19
    2.8  O、(、(的另一類定義        21
    2.9  O、(、(的性質(zhì)        22
    2.10  要更快的計(jì)算機(jī)還是要更快的算法        22
    思考題        23
    第3章  分治與遞歸        25
    3.1  分而治之為上策        26
    3.2  分治策略        28
    3.3  遞歸表達(dá)式求解        29
    3.3.1  遞歸樹法        29
    3.3.2  替換解法        30
    3.3.3  大師解法        32
    3.4  分治策略舉例1：乘方運(yùn)算        35
    3.5  生命不能承受之重：矩陣乘法        36
    3.6  魔鬼序列：斐波那契序列        38
    3.7  VLSI 布線        41
    3.8  多項(xiàng)式乘法        43
    3.9  分治就在潛意識(shí)深處        43
    思考題        43
    第二篇  算法設(shè)計(jì)篇
    第4章  動(dòng)態(tài)規(guī)劃思想        46
    4.1  什么是動(dòng)態(tài)規(guī)劃        47
    4.2  流水裝配線問題        48
    4.3  最長公共子序列        52
    4.3.1  第一種解法：蠻力策略        52
    4.3.2  第二種解法：動(dòng)態(tài)規(guī)劃        53
    4.4  最長公共子序列變種        55
    4.5  記憶遞歸法        55
    4.6  空間效率改善        56
    4.7  最優(yōu)二叉搜索樹        56
    4.7.1  遞歸解法        59
    4.7.2  計(jì)算最優(yōu)答案        59
    4.8  最優(yōu)子結(jié)構(gòu)與重疊子問題        62
    4.8.1  最優(yōu)子結(jié)構(gòu)        62
    4.8.2  重疊子問題        63
    4.9  動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系        63
    4.10  動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的相互轉(zhuǎn)換        64
    思考題        65
    第5章  貪婪選擇思想        67
    5.1  僅有動(dòng)態(tài)規(guī)劃是不夠的        67
    5.2  什么是貪婪        68
    5.3  背包問題        68
    5.4  貪婪選擇屬性        71
    5.5  教室規(guī)劃問題        72
    5.6  最小生成樹        76
    5.6.1  Kruskal算法的正確性        79
    5.6.2  Kruskal算法的時(shí)間分析        80
    5.7  Prim算法        80
    5.8  霍夫曼樹和霍夫曼編碼        83
    5.8.1  霍夫曼樹        85
    5.8.2  霍夫曼編碼        86
    5.8.3  霍夫曼編碼的無前綴編碼性質(zhì)        87
    5.9  貪婪選擇屬性        88
    5.10  標(biāo)準(zhǔn)分治、動(dòng)態(tài)規(guī)劃和貪婪選擇的比較        89
    思考題        90
    第6章  隨機(jī)化思想        92
    6.1  為什么要隨機(jī)化        93
    6.2  隨機(jī)的平方        94
    6.3  什么是隨機(jī)化算法        95
    6.4  拉斯維加斯算法        96
    6.5  蒙特卡羅算法        97
    6.6  素性測試        97
    6.7  矩陣乘積驗(yàn)證器        100
    6.8  隨機(jī)化最小生成樹算法        102
    6.8.1  Karger-Klein-Tarjan算法        103
    6.8.2  節(jié)點(diǎn)降低算法        103
    6.8.3  線性時(shí)間最小生成樹算法        104
    6.8.4  線性時(shí)間最小生成樹算法的時(shí)間成本分析        104
    6.9  隨機(jī)數(shù)的生成        105
    6.10  隨機(jī)化算法的應(yīng)用        105
    思考題        106
    第三篇  算法分析篇
    第7章  概率分析        108
    7.1  一切都在概率中        109
    7.2  什么是概率分析        109
    7.3  夢幻情人的代價(jià)        110
    7.3.1  直接分析        112
    7.3.2  最壞情況分析        113
    7.3.3  最好情況分析        113
    7.3.4  平均情況分析        113
    7.3.5  平均情況下成本的概率分析        113
    7.4  概率分析結(jié)果的有效性        114
    7.5  正確概率分析的保障        115
    7.6  夢幻情人的概率        115
    7.7  隨機(jī)排列問題        117
    7.8  南柯一夢：從無窮到無有        119
    7.9  概率分析的其他應(yīng)用        120
    思考題        121
    第8章  攤銷分析        122
    8.1  什么是攤銷分析        123
    8.2  攤銷分析與數(shù)據(jù)結(jié)構(gòu)        124
    8.3  攤銷分析的幾種方法        124
    8.4  聚類分析        125
    8.4.1  棧操作的聚類分析        125
    8.4.2  二進(jìn)制計(jì)數(shù)器的聚類分析        126
    8.5  會(huì)計(jì)分析        128
    8.6  勢能分析        130
    8.6.1  棧操作的勢能分析        130
    8.6.2  二進(jìn)制計(jì)數(shù)器的勢能分析        131
    8.7  攤銷分析應(yīng)用：表格擴(kuò)展的代價(jià)        131
    8.7.1  動(dòng)態(tài)表插入操作的聚類分析        134
    8.7.2  動(dòng)態(tài)表插入操作的會(huì)計(jì)分析        134
    8.7.3  動(dòng)態(tài)表插入操作的勢能分析        136
    8.8  運(yùn)氣不好就攤銷        137
    思考題        138
    第9章  競爭分析        139
    9.1  什么是競爭分析        139
    9.2  在線算法和離線算法        141
    9.3  競爭力        142
    9.4  健忘對(duì)手和優(yōu)良對(duì)手        142
    9.5  線性表更新問題        143
    9.6  前置移動(dòng)算法的競爭分析        145
    9.7  聚類問題        147
    9.7.1  聚類問題的次優(yōu)解算法        148
    9.7.2  CLUSTERING-ALGORITHM算法的競爭分析        148
    9.8  競爭分析與普通算法分析        149
    思考題        149
    第四篇  經(jīng)典算法篇
    第10章  排序和次序        152
    10.1  排序無處不在        152
    10.2  插入排序        153
    10.2.1  插入排序的效率分析        154
    10.2.2  折半插入排序        155
    10.3  歸并排序        156
    10.4  快速排序        158
    10.4.1  快速排序的過程        158
    10.4.2  快速排序的時(shí)間復(fù)雜性分析        159
    10.4.3  最壞情況分析        160
    10.4.4  最好情況分析        160
    10.4.5  平均情況分析        161
    10.5  隨機(jī)化快速排序        162
    10.6  排序的下限        164
    10.7  線性排序        165
    10.8  計(jì)數(shù)排序        166
    10.9  基數(shù)排序        168
    10.9.1  基數(shù)排序的正確性        169
    10.9.2  基數(shù)排序的時(shí)間效率分析        170
    10.10  桶排序        171
    10.10.1  桶排序的定義        172
    10.10.2  桶排序的正確性        173
    10.10.3  桶排序的時(shí)間復(fù)雜性分析        173
    10.11  次序選擇        175
    10.12  快速次序選擇算法        176
    10.13  隨機(jī)快速次序選擇算法        178
    10.14  最壞情況下的線性選擇算法        179
    10.14.1  杠桿點(diǎn)好壞分析        180
    10.14.2  算法的時(shí)間復(fù)雜性分析        181
    思考題        181
    第11章  搜索與哈希        183
    11.1  搜索問題        184
    11.2  順序搜索        184
    11.3  折半搜索        185
    11.4  常數(shù)搜索        186
    11.5  哈希搜索        187
    11.6  哈希函數(shù)選擇        189
    11.6.1  直接哈希        189
    11.6.2  除法（模除法）哈希        190
    11.6.3  乘法哈希        191
    11.6.4  乘法哈希的賭徒原理        192
    11.6.5  乘方取中法        193
    11.7  哈希算法的碰撞問題        193
    11.7.1  開放尋址哈希        193
    11.7.2  開放尋址哈希的時(shí)間成本        194
    11.7.3  開放尋址下成功搜索的時(shí)間成本        195
    11.7.4  封閉尋址哈希        196
    11.7.5  探尋序列的設(shè)計(jì)        197
    11.7.6  封閉尋址哈希的效率分析        199
    11.7.7  搜索不成功的時(shí)間成本        199
    11.7.8  成功搜索的效率分析        201
    11.8  哈希表元素刪除        201
    11.9  隨機(jī)化哈希        202
    11.10  全域哈希        203
    11.11  全域哈希構(gòu)造        204
    11.12  完美哈希        206
    思考題        208
    第12章  最短路徑        211
    12.1  劍指羅馬        211
    12.2  最短路徑問題        213
    12.3  單源單點(diǎn)最短路徑問題        215
    12.3.1  深度優(yōu)先搜索與廣度優(yōu)先搜索        215
    12.3.2  深度優(yōu)先解法        217
    12.4  單源多點(diǎn)最短路徑問題        218
    12.4.1  最短路徑的性質(zhì)        219
    12.4.2  Dijkstra最短路徑算法        220
    12.4.3  Dijkstra算法舉例        221
    12.4.4  Dijkstra算法與洪水泛濫        222
    12.4.5  Dijkstra算法的正確性        223
    12.4.6  Dijkstra算法的時(shí)間復(fù)雜性        224
    12.5  Bellman-Ford算法        226
    12.5.1  負(fù)權(quán)重的應(yīng)對(duì)方式        227
    12.5.2  Bellman-Ford算法的正確性        230
    12.5.3  負(fù)循環(huán)檢查問題        231
    12.5.4  Bellman-Ford算法的時(shí)間復(fù)雜性        231
    12.6  多源多點(diǎn)最短路徑問題        232
    12.6.1  多源多點(diǎn)最短路徑問題解決思路        232
    12.6.2  直接動(dòng)態(tài)規(guī)劃解法        233
    12.6.3  矩陣乘法解法        234
    12.6.4  Floyd-Warshall 算法        235
    12.6.5  Johnson 算法        236
    12.6.6  Johnson等效變換        237
    12.6.7  差限問題解決        238
    12.7  天意難違        240
    思考題        240
    第五篇  難解與無解篇
    第13章  可解與不可解        244
    13.1  我們戰(zhàn)無不勝嗎        245
    13.2  易解與難解        245
    13.3  決策問題和優(yōu)化問題        246
    13.4  決策問題        247
    13.5  P類問題        247
    13.6  NP類問題        248
    13.7 （確定性）圖靈機(jī)        249
    13.8  非確定性圖靈機(jī)        249
    13.9  非確定性算法        250
    13.10  回到NP類問題        251
    13.11  P和NP        252
    13.12  搜索問題、決策問題和優(yōu)化問題        253
    13.13  有沒有解和是否可決定        253
    思考題        254
    第14章  NP完全問題        256
    14.1  玉龍雪山下的審判        256
    14.2  NP完全問題的定義        257
    14.3  NP完全的重要性        258
    14.4  多項(xiàng)式時(shí)間規(guī)約        259
    14.5  如何證明一個(gè)問題S是NP完全        259
    14.6  第1個(gè)NP完全問題的證明        260
    14.7  庫克定理        260
    14.8  3-SAT問題        263
    14.9  證明NP難的技巧        264
    14.10  整數(shù)規(guī)劃        265
    14.11  獨(dú)立集問題        266
    14.12  漢密爾頓回路問題        268
    14.13  討論：弱NP完全、強(qiáng)NP完全和中NP完全        271
    思考題        272
    第15章  無解與近似        273
    15.1  難解問題        274
    15.2  不可決定問題        274
    15.3  程序終結(jié)的判斷        275
    15.4  難解之題的求解        276
    15.5  智能窮舉、近似算法和本地搜索        277
    15.6  智能窮舉之回溯策略        279
    15.7  智能窮舉之分支限界        280
    15.8  貪婪近似策略        280
    15.9  啟發(fā)式搜索策略        281
    15.10  模擬淬火算法        282
    15.10.1  模擬淬火算法的思想        284
    15.10.2  模擬淬火算法的基本循環(huán)        284
    15.10.3  淬火算法描述        284
    思考題        286
    結(jié)語  算法之道        288
    附錄  算法隨想        290
    參考文獻(xiàn)        293