從算法到程序：從應(yīng)用問(wèn)題編程實(shí)踐全面體驗(yàn)算法理論

定　價(jià)：￥59.00

作　者：	徐子珊著
出版社：	清華大學(xué)出版社
叢編項(xiàng)：
標(biāo)　簽：	計(jì)算機(jī)/網(wǎng)絡(luò) 計(jì)算機(jī)理論

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

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

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

　　《從算法到程序》第1章討論算法設(shè)計(jì)、分析的基本概念，第2章討論算法設(shè)計(jì)中最常用的幾個(gè)數(shù)據(jù)結(jié)構(gòu)，包括鏈表、棧、隊(duì)列、二叉搜索數(shù)、散列表等。第3章討論了算法設(shè)計(jì)的兩個(gè)基本策略：漸增策略與分支策略。這3章的內(nèi)容，為讀者閱讀本書(shū)以后的內(nèi)容奠定了基礎(chǔ)。第4章討論了幾個(gè)代數(shù)計(jì)算的基本問(wèn)題及其算法，包括矩陣運(yùn)算、解線(xiàn)性方程組、多項(xiàng)式運(yùn)算等。第5章討論了幾個(gè)關(guān)于計(jì)算幾何的基本問(wèn)題及其算法，包括線(xiàn)段的相交判斷、平面點(diǎn)集的凸包計(jì)算、最鄰近點(diǎn)對(duì)問(wèn)題等。第6章討論了關(guān)于整數(shù)運(yùn)算的基本問(wèn)題，包括大整數(shù)的表示與運(yùn)算、最大公約數(shù)計(jì)算、模運(yùn)算、素?cái)?shù)判定及整數(shù)因數(shù)分解等。這3章內(nèi)容為讀者深入學(xué)習(xí)解決各種復(fù)雜問(wèn)題奠定了解決數(shù)學(xué)計(jì)算問(wèn)題的基礎(chǔ)。第7~9章分別用回溯策略、動(dòng)態(tài)規(guī)劃策略及貪婪策略研究、解決計(jì)算機(jī)應(yīng)用面臨的最普遍最典型的問(wèn)題組合優(yōu)化問(wèn)題。第10章討論圖的搜索算法及其應(yīng)用。包括深度優(yōu)先搜索、拓?fù)渑判?、有向圖的強(qiáng)連通分支計(jì)算、關(guān)節(jié)點(diǎn)計(jì)算、廣度優(yōu)先搜索、網(wǎng)絡(luò)最大流及二部圖的最大匹配等問(wèn)題。對(duì)所有的的經(jīng)典算法及數(shù)據(jù)結(jié)構(gòu)，書(shū)中給出C語(yǔ)言的實(shí)現(xiàn)函數(shù)，形成一個(gè)通用的函數(shù)庫(kù)，并詳盡地加以解析。伴隨各種算法的設(shè)計(jì)、分析及程序?qū)崿F(xiàn)，書(shū)中給出了豐富多彩的應(yīng)用問(wèn)題及其解決方案的討論，并給出了完整的程序代碼。所有程序代碼都經(jīng)過(guò)反復(fù)調(diào)試，第十一章介紹這些代碼的使用方法。所有代碼都以隨書(shū)光盤(pán)的方式提供給讀者方便使用。本書(shū)無(wú)論是對(duì)初學(xué)算法及程序設(shè)計(jì)入門(mén)大學(xué)生讀者還是對(duì)已經(jīng)在職場(chǎng)打拼多年的程序員并有著提高自身理論修養(yǎng)及技術(shù)水平愿望的讀者都有著開(kāi)卷有益的意義。

作者簡(jiǎn)介

　　徐子珊男，副教授。數(shù)學(xué)專(zhuān)業(yè)出身，長(zhǎng)期從事高校數(shù)學(xué)、算法和程序設(shè)計(jì)教學(xué)，深受學(xué)生喜愛(ài)。曾擔(dān)任ACM/ICPC競(jìng)賽教練，指導(dǎo)過(guò)多屆ITAT競(jìng)賽。2003年在復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)系做國(guó)內(nèi)訪(fǎng)問(wèn)學(xué)者，師從國(guó)內(nèi)算法界前輩朱洪教授。2010年曾出版《算法設(shè)計(jì)、分析與實(shí)現(xiàn)》一書(shū)，受到讀者好評(píng)。該書(shū)遠(yuǎn)銷(xiāo)中國(guó)臺(tái)灣地區(qū)，曾有多人來(lái)函索要書(shū)中相關(guān)代碼。2012年出版該書(shū)修訂版。

圖書(shū)目錄

第1章計(jì)算問(wèn)題1
1.1計(jì)算問(wèn)題及其算法1
1.1.1計(jì)算問(wèn)題及其描述1
1.1.2算法及其描述2
1.1.3偽代碼的使用約定3
1.1.4算法分析4
1.1.5算法運(yùn)行時(shí)間的漸近表示5
1.2數(shù)據(jù)結(jié)構(gòu)6
1.2.1什么是數(shù)據(jù)結(jié)構(gòu)6
1.2.2數(shù)據(jù)結(jié)構(gòu)對(duì)算法效率的影響7
1.2.3字典與字典操作8
1.3程序設(shè)計(jì)10
1.3.1算法與程序10
1.3.2數(shù)據(jù)類(lèi)型的抽象與代碼通用性11
1.4數(shù)據(jù)的輸入輸出13
1.4.1應(yīng)用問(wèn)題13
1.4.2標(biāo)準(zhǔn)輸入輸出15
1.4.3文件輸入輸出20
1.5計(jì)數(shù)問(wèn)題22
1.5.1簡(jiǎn)單模擬23
1.5.2加法原理和乘法原理25
1.5.3整數(shù)序列31
第2章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)37
2.1線(xiàn)性表38
2.1.1線(xiàn)性表的鏈表表示38
2.1.2對(duì)鏈表的操作39
2.1.3鏈表的程序?qū)崿F(xiàn)42
2.1.4鏈表應(yīng)用47
2.2棧53
2.2.1棧的概念及其鏈表實(shí)現(xiàn)53
2.2.2棧的程序?qū)崿F(xiàn)54
2.2.3棧的應(yīng)用56
2.3隊(duì)列62
2.3.1隊(duì)列的概念及其鏈表實(shí)現(xiàn)62
2.3.2隊(duì)列的程序?qū)崿F(xiàn)63
2.3.3隊(duì)列的應(yīng)用64
2.4二叉搜索樹(shù)68
2.4.1二叉樹(shù)及其在計(jì)算機(jī)中的表示68
2.4.2二叉搜索樹(shù)76
2.4.3二叉搜索樹(shù)的查詢(xún)操作76
2.4.4二叉搜索樹(shù)中元素的增刪78
2.4.5紅?黑樹(shù)及其性質(zhì)80
2.4.6紅?黑樹(shù)的操作83
2.4.7紅?黑樹(shù)的程序?qū)崿F(xiàn)92
2.4.8二叉搜索樹(shù)的應(yīng)用102
2.5散列表102
2.5.1直接尋址表與散列表102
2.5.2用拉鏈解決沖突104
2.5.3散列表的程序?qū)崿F(xiàn)106
2.5.4散列表的應(yīng)用109
第3章基本算法設(shè)計(jì)策略112
3.1漸增型算法112
3.1.1有序序列的合并問(wèn)題112
3.1.2序列的劃分問(wèn)題117
3.2分治算法121
3.2.1歸并排序算法122
3.2.2快速排序算法126
3.2.3序統(tǒng)計(jì)與選擇問(wèn)題130
3.3排序問(wèn)題的討論132
3.3.1排序的性質(zhì)132
3.3.2比較型排序算法的時(shí)間復(fù)雜度133
3.3.3應(yīng)用136
3.4堆與基于堆的優(yōu)先隊(duì)列141
3.4.1堆的概念及其創(chuàng)建141
3.4.2基于二叉堆的優(yōu)先隊(duì)列149
3.4.3應(yīng)用153
第4章代數(shù)計(jì)算169
4.1矩陣及其計(jì)算169
4.1.1矩陣與向量169
4.1.2矩陣的運(yùn)算171
4.1.3矩陣的性質(zhì)173
4.1.4矩陣的程序?qū)崿F(xiàn)174
4.2矩陣的LUP分解176
4.2.1LUP分解法概述177
4.2.2LU分解178
4.2.3計(jì)算LUP分解179
4.2.4程序?qū)崿F(xiàn)182
4.3解線(xiàn)性方程組183
4.3.1前代法和回代法183
4.3.2用LUP分解計(jì)算矩陣的逆185
4.3.3程序?qū)崿F(xiàn)186
4.4多項(xiàng)式及其計(jì)算188
4.4.1多項(xiàng)式及其表示188
4.4.2多項(xiàng)式的運(yùn)算190
4.4.3FFT191
4.4.4程序?qū)崿F(xiàn)199
4.5應(yīng)用204
4.5.1多項(xiàng)式的泰勒展開(kāi)式204
4.5.2完善序列208
4.5.3函數(shù)的有理式逼近211
第5章計(jì)算幾何218
5.1線(xiàn)段的性質(zhì)218
5.1.1叉積及其應(yīng)用219
5.1.2向量的極角222
5.1.3程序?qū)崿F(xiàn)223
5.2判斷是否存在線(xiàn)段相交226
5.2.1算法描述與分析227
5.2.2程序?qū)崿F(xiàn)230
5.3求凸殼234
5.3.1Graham掃描235
5.3.2程序?qū)崿F(xiàn)239
5.4求最鄰近點(diǎn)對(duì)242
5.4.1算法描述與分析242
5.4.2程序?qū)崿F(xiàn)245
5.5應(yīng)用248
5.5.1光導(dǎo)管248
5.5.2最小邊界矩形255
5.5.3德克薩斯一日游260
第6章數(shù)論算法264
6.1整數(shù)的表示264
6.1.1整數(shù)的表示264
6.1.2整數(shù)的算術(shù)運(yùn)算264
6.1.3程序?qū)崿F(xiàn)269
6.1.4應(yīng)用275
6.2初等數(shù)論的概念277
6.3最大公約數(shù)283
6.3.1Euclid算法284
6.3.2EUCLID算法的運(yùn)行時(shí)間284
6.3.3Euclid算法的迭代版本286
6.3.4程序?qū)崿F(xiàn)287
6.3.5應(yīng)用289
6.4模運(yùn)算294
6.4.1模加法和乘法295
6.4.2解模線(xiàn)性方程296
6.4.3元素的冪299
6.4.4應(yīng)用303
6.5素?cái)?shù)檢測(cè)305
6.5.1偽素?cái)?shù)檢測(cè)305
6.5.2Miller?Rabin的隨機(jī)素?cái)?shù)檢測(cè)308
6.5.3Miller?Rabin素?cái)?shù)檢測(cè)的錯(cuò)誤率310
6.5.4程序?qū)崿F(xiàn)310
6.6整數(shù)分解313
6.6.1Pollard的ρ探索法313
6.6.2程序?qū)崿F(xiàn)317
6.6.3應(yīng)用320
第7章回溯策略323
7.1組合問(wèn)題323
7.1.1組合問(wèn)題的例子323
7.1.2組合問(wèn)題的形式化描述325
7.2組合問(wèn)題的回溯算法326
7.2.1解空間的樹(shù)狀結(jié)構(gòu)326
7.2.2解決組合問(wèn)題的回溯算法328
7.2.3回溯算法的框架333
7.3子集樹(shù)和排列樹(shù)339
7.3.1子集樹(shù)問(wèn)題339
7.3.2排列樹(shù)問(wèn)題343
7.3.3應(yīng)用349
7.4用回溯算法解決組合優(yōu)化問(wèn)題360
7.4.1組合優(yōu)化問(wèn)題360
7.4.2用回溯策略解決組合優(yōu)化問(wèn)題362
7.4.3應(yīng)用365
第8章動(dòng)態(tài)規(guī)劃策略37
8.1組裝線(xiàn)調(diào)度問(wèn)題376
8.1.1問(wèn)題描述376
8.1.2算法設(shè)計(jì)與分析378
8.1.3應(yīng)用——牛牛玩牌381
8.2最長(zhǎng)公共子序列386
8.2.1問(wèn)題描述386
8.2.2算法設(shè)計(jì)與分析386
8.2.3程序?qū)崿F(xiàn)389
8.2.4應(yīng)用390
8.30?1背包問(wèn)題398
8.3.1問(wèn)題描述398
8.3.2算法設(shè)計(jì)與分析398
8.3.3程序?qū)崿F(xiàn)401
8.3.4應(yīng)用402
8.4帶權(quán)有向圖中任意兩點(diǎn)間的最短路徑409
8.4.1問(wèn)題描述409
8.4.2算法設(shè)計(jì)與分析410
8.4.3程序?qū)崿F(xiàn)413
8.4.4應(yīng)用——牛牛聚會(huì)415
第9章貪婪策略419
9.1活動(dòng)選擇問(wèn)題419
9.1.1算法描述與分析419
9.1.2程序?qū)崿F(xiàn)423
9.1.3貪婪算法與動(dòng)態(tài)規(guī)劃424
9.1.4應(yīng)用——海岸雷達(dá)425
9.2Huffman編碼428
9.2.1算法描述與分析428
9.2.2應(yīng)用——R叉Huffman樹(shù)433
9.2.3程序?qū)崿F(xiàn)437
9.3最小生成樹(shù)443
9.3.1算法描述與分析443
9.3.2程序?qū)崿F(xiàn)446
9.3.3應(yīng)用——北方通信網(wǎng)448
9.4單源最短路徑問(wèn)題453
9.4.1算法描述與分析453
9.4.2程序?qū)崿F(xiàn)456
9.4.3應(yīng)用——西氣東送458
第10章圖的搜索算法465
10.1深度優(yōu)先搜索466
10.1.1算法描述與分析466
10.1.2程序?qū)崿F(xiàn)469
10.1.3有向無(wú)圈圖的拓?fù)渑判?72
10.1.4應(yīng)用——全排序478
10.2有向圖的強(qiáng)連通分支482
10.2.1算法描述與分析482
10.2.2程序?qū)崿F(xiàn)486
10.2.3應(yīng)用——親情號(hào)489
10.3無(wú)向圖的雙連通分支494
10.3.1算法描述與分析494
10.3.2程序?qū)崿F(xiàn)497
10.3.3應(yīng)用——雌雄大盜498
10.4廣度優(yōu)先搜索504
10.4.1算法描述與分析504
10.4.2程序?qū)崿F(xiàn)507
10.4.3應(yīng)用——攻城掠地508
10.5流網(wǎng)絡(luò)與最大流問(wèn)題512
10.5.1算法描述與分析512
10.5.2程序?qū)崿F(xiàn)521
10.5.3應(yīng)用523
第11章代碼實(shí)驗(yàn)528
11.1頭文件清單528
11.1.1基本應(yīng)用類(lèi)函數(shù)528
11.1.2數(shù)據(jù)結(jié)構(gòu)類(lèi)531
11.1.3代數(shù)記算類(lèi)函數(shù)534
11.1.4計(jì)算幾何類(lèi)函數(shù)536
11.1.5數(shù)論計(jì)算類(lèi)函數(shù)537
11.1.6回溯搜索類(lèi)函數(shù)539
11.1.7動(dòng)態(tài)規(guī)劃類(lèi)函數(shù)540
11.1.8貪婪策略類(lèi)函數(shù)540
11.1.9圖的搜索類(lèi)函數(shù)541
11.2實(shí)驗(yàn)平臺(tái)的搭建542
11.2.1集成開(kāi)發(fā)環(huán)境的安裝542
11.2.2實(shí)驗(yàn)項(xiàng)目的建立542
11.3應(yīng)用問(wèn)題程序的運(yùn)行實(shí)例544
11.3.1加載程序文件544
11.3.2調(diào)試程序545
11.3.3各應(yīng)用問(wèn)題加載文件清單546
11.4函數(shù)庫(kù)的擴(kuò)展554
11.4.1向已有的源文件中添加新函數(shù)554
11.4.2創(chuàng)建新的源文件555
參考文獻(xiàn)557