算法設(shè)計(jì)

定　價(jià)：￥119.00

作　者：	喬恩·克萊因伯格（Jon Kleinberg）著，王海鵬譯
出版社：	人民郵電出版社
叢編項(xiàng)：
標(biāo)　簽：	暫缺

購(gòu)買(mǎi)這本書(shū)可以去

ISBN：	9787115546647	出版時(shí)間：	2021-03-01	包裝：	平裝
開(kāi)本：	16開(kāi)	頁(yè)數(shù)：	503	字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

　　這是一本關(guān)于算法設(shè)計(jì)和分析的經(jīng)典教材。本書(shū)圍繞算法設(shè)計(jì)進(jìn)行組織，對(duì)每種算法技術(shù)用多個(gè)典型范例進(jìn)行分析，把算法的理論跟實(shí)際問(wèn)題結(jié)合起來(lái)，具有很大的啟發(fā)性。本書(shū)側(cè)重算法設(shè)計(jì)思路，每章都從實(shí)際問(wèn)題出發(fā)，經(jīng)過(guò)深入具體的分析引出相應(yīng)算法的設(shè)計(jì)思想，并對(duì)算法的正確性和復(fù)雜性進(jìn)行合理的分析和論證。本書(shū)覆蓋面廣，且含有200多道精彩的習(xí)題，最后還擴(kuò)展了PSPACE問(wèn)題、參數(shù)復(fù)雜性等內(nèi)容。

作者簡(jiǎn)介

　　作者簡(jiǎn)介喬恩·克萊因伯格（Jon Kleinberg），康奈爾大學(xué)計(jì)算機(jī)科學(xué)教授。他于1996年從麻省理工學(xué)院獲得博士學(xué)位。他榮獲過(guò)美國(guó)國(guó)家科學(xué)基金會(huì)事業(yè)獎(jiǎng)、海軍研究局青年研究員獎(jiǎng)、IBM 杰出創(chuàng)新獎(jiǎng)和美國(guó)國(guó)家科學(xué)院創(chuàng)新研究獎(jiǎng)等眾多獎(jiǎng)項(xiàng)。他的研究集中在算法上，特別是與網(wǎng)絡(luò)結(jié)構(gòu)和信息相關(guān)的算法，以及這些算法在信息科學(xué)、優(yōu)化、數(shù)據(jù)挖掘以及計(jì)算生物學(xué)等方面的應(yīng)用。伊娃·塔多斯（éva Tardos），康奈爾大學(xué)計(jì)算機(jī)科學(xué)教授。她是美國(guó)藝術(shù)與科學(xué)學(xué)院院士、ACM會(huì)士。她榮獲過(guò)美國(guó)國(guó)家科學(xué)基金會(huì)總統(tǒng)青年研究員獎(jiǎng)和富爾克森獎(jiǎng)等眾多獎(jiǎng)項(xiàng)。她的研究興趣主要集中在圖和網(wǎng)絡(luò)問(wèn)題的算法設(shè)計(jì)和分析上。她因在網(wǎng)絡(luò)流算法和網(wǎng)絡(luò)問(wèn)題的近似算法方面的工作而聞名。她最近的工作重點(diǎn)是算法博弈論。譯者簡(jiǎn)介王海鵬，軟件開(kāi)發(fā)者、譯者、培訓(xùn)講師。他擁有二十余年 IT 行業(yè)經(jīng)驗(yàn)，翻譯了二十余本軟件開(kāi)發(fā)相關(guān)圖書(shū)，為行業(yè)內(nèi)多家知名公司提供過(guò)培訓(xùn)。他使用的開(kāi)發(fā)語(yǔ)言主要有 C/C++、Java和 Lua。他專(zhuān)注于提高軟件開(kāi)發(fā)的效率和品質(zhì)，并在量化交易領(lǐng)域擁有豐富的經(jīng)驗(yàn)。

圖書(shū)目錄

目　錄
第 1章　引言：一些典型問(wèn)題　1
1．1　第一個(gè)問(wèn)題：穩(wěn)定匹配　1
1．2　5個(gè)典型問(wèn)題　8
帶解答的練習(xí)　12
練習(xí)　14
注釋和進(jìn)一步閱讀　17
第 2章　算法分析基礎(chǔ)　18
2．1 計(jì)算可解性　18
2．2 增長(zhǎng)的漸近階　21
2．3 用列表和數(shù)組實(shí)現(xiàn)穩(wěn)定匹配算法　26
2．4 常見(jiàn)運(yùn)行時(shí)間綜述　29
2．5 更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)：優(yōu)先隊(duì)列　35
帶解答的練習(xí)　40
練習(xí)　41
注釋和進(jìn)一步閱讀　44
第3章　圖　45
3．1 基本定義和應(yīng)用　45
3．2 圖連通性和圖遍歷　48
3．3 用隊(duì)列和棧實(shí)現(xiàn)圖遍歷　53
3．4 二分性測(cè)試：廣度優(yōu)先搜索的應(yīng)用　58
3．5 有向圖中的連通性　59
3．6 有向無(wú)環(huán)圖和拓?fù)渑判颉?1
帶解答的練習(xí)　64
練習(xí)　66
注釋和進(jìn)一步閱讀　69
第4章　貪心算法　70
4．1 區(qū)間調(diào)度：貪心算法保持領(lǐng)先　70
4．2 最小化延遲的調(diào)度：交換論證　76
4．3 最優(yōu)緩存：更復(fù)雜的交換論證　80
4．4 圖的最短路徑　83
4．5 最小生成樹(shù)問(wèn)題　87
4．6 實(shí)現(xiàn)Kruskal算法：Union-Find數(shù)據(jù)結(jié)構(gòu)　92
4．7 聚類(lèi)　97
4．8 哈夫曼碼和數(shù)據(jù)壓縮　99
*4．9 最小開(kāi)銷(xiāo)樹(shù)形圖：多階段貪心算法　109
帶解答的練習(xí)　113
練習(xí)　116
注釋和進(jìn)一步閱讀　125
第5章　分治　127
5．1 第一個(gè)遞推式：歸并排序算法　127
5．2 進(jìn)一步的遞推關(guān)系　130
5．3 計(jì)數(shù)逆序　134
5．4 尋找最近點(diǎn)對(duì)　137
5．5 整數(shù)乘法　141
5．6 卷積和快速傅里葉變換　142
帶解答的練習(xí)　148
練習(xí)　150
注釋和進(jìn)一步閱讀　152
第6章　動(dòng)態(tài)規(guī)劃　153
6．1 加權(quán)區(qū)間調(diào)度：遞歸過(guò)程　153
6．2 動(dòng)態(tài)規(guī)劃原理：備忘錄或子問(wèn)題迭代　157
6．3 分段最小二乘：多重選擇　159
6．4 子集和與背包：加一個(gè)變量　162
6．5 RNA二級(jí)結(jié)構(gòu)：區(qū)間上的動(dòng)態(tài)規(guī)劃　166
6．6 序列比對(duì)　169
6．7 通過(guò)分治在線(xiàn)性空間中序列比對(duì)　173
6．8 圖中的最短路徑　177
6．9 最短路徑和距離向量協(xié)議　182
*6．10 圖中的負(fù)環(huán)　184
帶解答的練習(xí)　187
練習(xí)　190
注釋和進(jìn)一步閱讀　204
第7章　網(wǎng)絡(luò)流　205
7．1 最大流問(wèn)題和Ford-Fulkerson算法　205
7．2 網(wǎng)絡(luò)中的最大流和最小割　211
7．3 選擇好的增廣路徑　214
*7．4 預(yù)流推進(jìn)最大流算法　218
7．5 第一個(gè)應(yīng)用：二分匹配問(wèn)題　225
7．6 有向圖和無(wú)向圖中的不相交路徑　228
7．7 最大流問(wèn)題的擴(kuò)展　232
7．8 調(diào)查設(shè)計(jì)　236
7．9 航空公司調(diào)度　237
7．10 圖像分割　240
7．11 項(xiàng)目選擇　243
7．12 棒球排除　246
*7．13 進(jìn)一步的方向：為匹配問(wèn)題增加開(kāi)銷(xiāo)　249
帶解答的練習(xí)　253
練習(xí)　255
注釋和進(jìn)一步閱讀　274
第8章　NP和計(jì)算難解性　276
8．1 多項(xiàng)式時(shí)間歸約　276
8．2 通過(guò)“小配件”歸約：可滿(mǎn)足性問(wèn)題　280
8．3 有效證書(shū)和NP的定義　283
8．4 NP完全問(wèn)題　285
8．5 排序問(wèn)題　289
8．6 劃分問(wèn)題　294
8．7 圖著色　297
8．8 數(shù)值問(wèn)題　300
8．9 co-NP和NP的不對(duì)稱(chēng)性　303
8．10 困難問(wèn)題的部分分類(lèi)　305
帶解答的練習(xí)　307
練習(xí)　309
注釋和進(jìn)一步閱讀　323
第9章　PSPACE：NP之外的一類(lèi)問(wèn)題　324
9．1 PSPACE　324
9．2 PSPACE中的一些難題　325
9．3 在多項(xiàng)式空間中求解量化問(wèn)題和博弈　327
9．4 在多項(xiàng)式空間中求解規(guī)劃問(wèn)題　328
9．5 證明問(wèn)題是PSPACE完全的　331
帶解答的練習(xí)　334
練習(xí)　335
注釋和進(jìn)一步閱讀　336
第 10章　擴(kuò)展易解性的界限　337
10．1 尋找小的頂點(diǎn)覆蓋　338
10．2 求解樹(shù)上的NP困難問(wèn)題　340
10．3 圓弧集著色　343
*10．4 圖的樹(shù)分解　349
*10．5 構(gòu)造樹(shù)分解　356
帶解答的練習(xí)　361
練習(xí)　363
注釋和進(jìn)一步閱讀　365
第 11章　近似算法　366
11．1 貪心算法和最優(yōu)值的界限：負(fù)載均衡問(wèn)題　366
11．2 中心選址問(wèn)題　370
11．3 集合覆蓋：一般貪心啟發(fā)式　374
11．4 定價(jià)方法：頂點(diǎn)覆蓋　378
11．5 用定價(jià)方法最大化：不相交路徑問(wèn)題　382
11．6 線(xiàn)性規(guī)劃和舍入：頂點(diǎn)覆蓋的應(yīng)用　386
*11．7 再論負(fù)載均衡：更高級(jí)的LP應(yīng)用　390
11．8 任意好的近似：背包問(wèn)題　394
帶解答的練習(xí)　398
練習(xí)　399
注釋和進(jìn)一步閱讀　404
第 12章　局部搜索　406
12．1 優(yōu)化問(wèn)題的地形　406
12．2 Metropolis算法和模擬退火算法　409
12．3 局部搜索在Hopfield神經(jīng)網(wǎng)絡(luò)中的應(yīng)用　412
12．4 通過(guò)局部搜索的最大割近似　415
12．5 選擇鄰居關(guān)系　417
*12．6 用局部搜索分類(lèi)　418
12．7 最優(yōu)響應(yīng)動(dòng)態(tài)和納什均衡　423
帶解答的練習(xí)　430
練習(xí)　431
注釋和進(jìn)一步閱讀　433
第 13章　隨機(jī)算法　434
13．1 第一個(gè)應(yīng)用：消除爭(zhēng)用　435
13．2 尋找全局最小割　438
13．3 隨機(jī)變量及其期望　442
13．4 MAX 3-SAT的隨機(jī)近似算法　445
13．5 隨機(jī)分治：找中位數(shù)和Quicksort　447
13．6 哈希：字典的隨機(jī)實(shí)現(xiàn)　452
13．7 尋找最近點(diǎn)對(duì)：隨機(jī)方法　457
13．8 隨機(jī)緩存　462
13．9 切爾諾夫界　467
13．10 負(fù)載均衡　468
13．11 分組路由　470
13．12 背景知識(shí)：一些基本概率定義　474
帶解答的練習(xí)　479
練習(xí)　483
注釋和進(jìn)一步閱讀　489
后記：永遠(yuǎn)運(yùn)行的算法　491
參考文獻(xiàn)　497