 |
-- 會員 / 註冊 --
|
 |
|
|
|
從算法到程序 ( 簡體 字) |
| 作者：徐子珊 | 類別：1. -> 程式設計 -> 演算法 |
| 譯者： |
| 出版社：清華大學出版社 |  3dWoo書號： 35086
詢問書籍請說出此書號！【缺書】
NT售價： 295 元 |
| 出版日：2/19/2013 |
| 頁數：556 |
| 光碟數：1 |
|
站長推薦：   |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787302304746 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：學科的基本問題和基本方法是學科方法論的基本內容。計算機能解決的僅僅是計算問題而已。什么是計算問題？有哪些典型的計算問題？如何描述計算問題是計算學科的基本問題之一，也是計算機應用的前提。將問題與數據加以形式化表示，并設計解決計算問題的算法，評價算法的運行效率是計算學科的基本方法。本書的每一章節都圍繞著一類或一個計算問題的形式化描述和算法及其分析展開。在開卷之前，先粗線條地向讀者描述一下本書。
計算問題來自現實世界，現實世界五彩繽紛，計算問題多種多樣。本書按典型計算問題的分類來組織各章內容，包括計數問題、代數計算問題、計算幾何問題、數論問題、組合優化問題和圖的搜索問題。
計數問題是最古老的但也是人類生活須臾不能離開的計算問題，特別是在現代科技與工業領域存在大量的計數問題。用計算機快速解決計數問題是實至名歸。第1章討論解決計數問題的基礎是加法原理和乘法原理的應用。
為了讓讀者清醒地看到數據組織方式對算法設計方法及算法運行效率的影響，在第2章中濃縮了關于線性表、二叉樹、散列表等最基礎的幾個數據結構。
數學中的計算問題更是比比皆是。數學問題的算法，如解線性方程組、計算多項式的變換、線段之間的位置關系等也是很多信息處理應用問題中經常要用的基本操作。本書用第4∼6章的篇幅討論代數、幾何及數論中的典型計算問題的算法，所用的方法是第3章中介紹的漸增性策略和分治策略。
在多個可能解中尋求最優解的組合優化問題是計算學科面對的最典型的問題，因為人類的活動幾乎都涉及資源的競爭，而有資源競爭就會產生組合優化問題。本書用第7∼9章的內容來討論組合優化問題的解決方法。討論是按從大到小收縮解空間的線索展開。從無約束的回溯策略開始，到加上最優子結構性質及子問題重疊性質后的動態規劃策略，解空間越小，算法效率越高。筆者試圖以這樣的全方位地討論組合優化問題解決方法的形式，引導讀者深入理解啟發式解題思想方法。
在第10章討論一個描述應用問題的重要數學模型--圖。重點討論圖中頂點的搜索算法。利用搜索算法，討論了諸如拓撲排序、關節點計算、網絡流等幾個經典的關于圖的應用問題。
算法研究歷史悠久。然而今天，算法理論研究落腳點在于指導計算機程序設計實踐。本書討論的每一個經典算法，均用C語言寫成了通用的功能函數，并用這些函數解決了一系列有趣的應用問題。第11章匯總了這些函數的原型聲明及數據結構的定義。
本書寫作上除了上述的內容組織形式上的特點外，還用心于以下幾點。
1. 理論嚴謹，語言規范
對每一個問題的算法，從問題的分析開始，包括思路的發展，算法的描述，正確性證明，運行時間的計算都加以詳盡討論，讓讀者能體驗到計算學科的科學嚴謹性。算法設計與分析以理論繁復著稱。筆者試圖以樸實的文字和平和的闡述展示對問題的分析，算法步驟的思考和運行時間估算。在確保科學性、正確性的前提下盡量使用與生活語言相近的詞語而避免使用過多生僻的專用術語，讓讀者在閱讀中感受本書的自然親切。
2. 理論與實踐互動
筆者對每一個理論算法都給出現有技術的程序實現，用以驗證理論算法的正確性。雖然此前已經在理論上證明了算法的正確性，但通過實現了的程序的正確運行進一步證明理論是可行的。并且，算法的程序實現及對測試數據的調試運行能使讀者深入理解算法的思想及其中細節微妙之處。對書中的每一個經典算法， 均精選了1∼2個應用問題，或說明如何直接調用算法解決該問題，或說明如何運用算法設計的思想解決問題。問題均選自ACM/ICPC的賽題或北京大學的網站http://poj.org/problemlist.
3. 小步推進，深入淺出
要設計一個算法來解決計算問題往往是比較復雜的。對復雜問題分析以及設計解決問題的算法并對其進行分析，進而實現為程序難免行文比較冗長。為減輕讀者閱讀疲勞，在保證內容完整性的前提下，適當地將問題分析、算法設計分析以及程序實現復雜過程按一定的內部邏輯分解成若干部分，一步一個小標題。讀者可依次一步一步連續閱讀，也可分多次，每次閱讀一個部分。閱讀時可通過小標題明確自己在整個過程中的那一部分，又不失對全局的掌控。
4. 圖文并茂，生動形象
算法的基礎是數學，數學講的是邏輯思維。然而，邏輯思維并不排斥形象思維，形象思維有時可為邏輯思維深入推進助力。為幫助讀者快速且正確地理解抽象概念，或思想方法，或微妙的技術細節，書中在適宜的地方插入很多精心繪制的插圖。通過這些插圖讀者可對書中相應的文字或符號表述的理論、方法或技術內容有生動、形象的認識。
5. 通用代碼，便于引用
本書中對所有算法的程序實現并非簡單的代碼堆砌。筆者對所實現的每一個C函數參數與返回值，數據與變量的設置及關鍵代碼都進行了詳盡的解析。并且將大多數算法和數據結構寫成通用的代碼，以光盤的形式向讀者提供類似于C++的STL或Java的Collection Framework的通用庫，便于讀者在工作中或生活中需要時引用。本書算法中的偽代碼的編寫規范參照“Introduction to Algorithm”一書中的體例。
為方便選用本作為算法課程教材的教師朋友使用，隨書光盤中提供了PPT格式的課件。
徐子珊 記于山城重慶
2012年10月 |
內容簡介：本書第1章討論算法設計、分析的基本概念。第2章討論算法設計中最常用的幾個數據結構，包括鏈表、棧、隊列、二叉搜索數、散列表等。第3章討論算法設計的兩個基本策略：漸增策略與分支策略。這3章的內容為閱讀本書以后的內容奠定了基礎。第4章討論幾個代數計算的基本問題及其算法，包括矩陣運算、解線性方程組、多項式運算等。第5章討論幾個關于計算幾何的基本問題及其算法，包括線段的相交判斷、平面點集的凸包計算、最鄰近點對問題等。第6章討論關于整數運算的基本問題，包括大整數的表示與運算、最大公約數計算、模運算、素數判定及整數因數分解等。這3章內容為讀者深入學習解決各種復雜問題奠定了基礎。第7~9章分別用回溯策略、動態規劃策略及貪婪策略研究、解決計算機應用面臨的最普遍最典型的問題組合優化問題。第10章討論圖的搜索算法及其應用，包括深度優先搜索、拓撲排序、有向圖的強連通分支計算、關節點計算、廣度優先搜索、網絡最大流及二部圖的最大匹配等問題。對所有的經典算法及數據結構，書中給出C語言的實現函數，形成一個通用的函數庫，并詳盡地加以解析。伴隨各種算法的設計、分析及程序實現，書中給出了豐富多彩的應用問題及其解決方案的討論，并給出了完整的程序代碼。所有程序代碼都經過反復調試，第11章介紹這些代碼的使用方法。
所有代碼都以隨書光盤的方式提供給讀者，以便使用。本書無論是對初學算法及程序設計入門的大學生還是對已經在職場打拼多年的程序員，以及希望提高自身理論修養和技術水平的讀者都比較適合。
|
目錄：第1章 計算問題1
1.1 計算問題及其算法1
1.1.1 計算問題及其描述1
1.1.2 算法及其描述2
1.1.3 偽代碼的使用約定3
1.1.4 算法分析4
1.1.5 算法運行時間的漸近表示5
1.2 數據結構6
1.2.1 什么是數據結構6
1.2.2 數據結構對算法效率的影響7
1.2.3 字典與字典操作8
1.3 程序設計10
1.3.1 算法與程序10
1.3.2 數據類型的抽象與代碼通用性11
1.4 數據的輸入輸出13
1.4.1 應用問題13
1.4.2 標準輸入輸出15
1.4.3 文件輸入輸出20
1.5 計數問題22
1.5.1 簡單模擬23
1.5.2 加法原理和乘法原理25
1.5.3 整數序列31第2章 數據結構基礎37
2.1 線性表38
2.1.1 線性表的鏈表表示38
2.1.2 對鏈表的操作39
2.1.3 鏈表的程序實現42
2.1.4 鏈表應用47
2.2 棧53
2.2.1 棧的概念及其鏈表實現53
2.2.2 棧的程序實現54
2.2.3 棧的應用56
2.3 隊列62
2.3.1 隊列的概念及其鏈表實現62
2.3.2 隊列的程序實現63
2.3.3 隊列的應用64
2.4 二叉搜索樹68
2.4.1 二叉樹及其在計算機中的表示68
2.4.2 二叉搜索樹76
2.4.3 二叉搜索樹的查詢操作76
2.4.4 二叉搜索樹中元素的增刪78
2.4.5 紅-黑樹及其性質80
2.4.6 紅-黑樹的操作83
2.4.7 紅-黑樹的程序實現92
2.4.8 二叉搜索樹的應用102
2.5 散列表102
2.5.1 直接尋址表與散列表102
2.5.2 用拉鏈解決沖突104
2.5.3 散列表的程序實現106
2.5.4 散列表的應用109第3章 基本算法設計策略112
3.1 漸增型算法112
3.1.1 有序序列的合并問題112
3.1.2 序列的劃分問題117
3.2 分治算法121
3.2.1 歸并排序算法122
3.2.2 快速排序算法126
3.2.3 序統計與選擇問題130
3.3 排序問題的討論132
3.3.1 排序的性質132
3.3.2 比較型排序算法的時間復雜度133
3.3.3 應用136
3.4 堆與基于堆的優先隊列141
3.4.1 堆的概念及其創建141
3.4.2 基于二叉堆的優先隊列149
3.4.3 應用153第4章 代數計算169
4.1 矩陣及其計算169
4.1.1 矩陣與向量169
4.1.2 矩陣的運算171
4.1.3 矩陣的性質173
4.1.4 矩陣的程序實現174
4.2 矩陣的LUP分解176
4.2.1 LUP分解法概述177
4.2.2 LU分解178
4.2.3 計算LUP分解179
4.2.4 程序實現182
4.3 解線性方程組183
4.3.1 前代法和回代法183
4.3.2 用LUP分解計算矩陣的逆185
4.3.3 程序實現186
4.4 多項式及其計算188
4.4.1 多項式及其表示188
4.4.2 多項式的運算190
4.4.3 FFT191
4.4.4 程序實現199
4.5 應用204
4.5.1 多項式的泰勒展開式204
4.5.2 完善序列208
4.5.3 函數的有理式逼近211第5章 計算幾何218
5.1 線段的性質218
5.1.1 叉積及其應用219
5.1.2 向量的極角222
5.1.3 程序實現223
5.2 判斷是否存在線段相交226
5.2.1 算法描述與分析227
5.2.2 程序實現230
5.3 求凸殼234
5.3.1 Graham掃描235
5.3.2 程序實現239
5.4 求最鄰近點對242
5.4.1 算法描述與分析242
5.4.2 程序實現245
5.5 應用248
5.5.1 光導管248
5.5.2 最小邊界矩形255
5.5.3 德克薩斯一日游260第6章 數論算法264
6.1 整數的表示264
6.1.1 整數的表示264
6.1.2 整數的算術運算264
6.1.3 程序實現269
6.1.4 應用275
6.2 初等數論的概念277
6.3 最大公約數283
6.3.1 Euclid算法284
6.3.2 EUCLID算法的運行時間284
6.3.3 Euclid算法的迭代版本286
6.3.4 程序實現287
6.3.5 應用289
6.4 模運算294
6.4.1 模加法和乘法295
6.4.2 解模線性方程296
6.4.3 元素的冪299
6.4.4 應用303
6.5 素數檢測305
6.5.1 偽素數檢測305
6.5.2 Miller-Rabin的隨機素數檢測308
6.5.3 Miller-Rabin素數檢測的錯誤率310
6.5.4 程序實現310
6.6 整數分解313
6.6.1 Pollard的ρ探索法313
6.6.2 程序實現317
6.6.3 應用320第7章 回溯策略323
7.1 組合問題323
7.1.1 組合問題的例子323
7.1.2 組合問題的形式化描述325
7.2 組合問題的回溯算法326
7.2.1 解空間的樹狀結構326
7.2.2 解決組合問題的回溯算法328
7.2.3 回溯算法的框架333
7.3 子集樹和排列樹339
7.3.1 子集樹問題339
7.3.2 排列樹問題343
7.3.3 應用349
7.4 用回溯算法解決組合優化問題360
7.4.1 組合優化問題360
7.4.2 用回溯策略解決組合優化問題362
7.4.3 應用365第8章 動態規劃策略375
8.1 組裝線調度問題376
8.1.1 問題描述376
8.1.2 算法設計與分析378
8.1.3 應用--牛牛玩牌381
8.2 最長公共子序列386
8.2.1 問題描述386
8.2.2 算法設計與分析386
8.2.3 程序實現389
8.2.4 應用390
8.3 0-1背包問題398
8.3.1 問題描述398
8.3.2 算法設計與分析398
8.3.3 程序實現401
8.3.4 應用402
8.4 帶權有向圖中任意兩點間的最短路徑409
8.4.1 問題描述409
8.4.2 算法設計與分析410
8.4.3 程序實現413
8.4.4 應用--牛牛聚會415第9章 貪婪策略419
9.1 活動選擇問題419
9.1.1 算法描述與分析419
9.1.2 程序實現423
9.1.3 貪婪算法與動態規劃424
9.1.4 應用--海岸雷達425
9.2 Huffman編碼428
9.2.1 算法描述與分析428
9.2.2 應用--𨧤R𨧤叉Huffman樹433
9.2.3 程序實現437
9.3 最小生成樹443
9.3.1 算法描述與分析443
9.3.2 程序實現446
9.3.3 應用--北方通信網448
9.4 單源最短路徑問題453
9.4.1 算法描述與分析453
9.4.2 程序實現456
9.4.3 應用--西氣東送458第10章 圖的搜索算法465
10.1 深度優先搜索466
10.1.1 算法描述與分析466
10.1.2 程序實現469
10.1.3 有向無圈圖的拓撲排序472
10.1.4 應用--全排序478
10.2 有向圖的強連通分支482
10.2.1 算法描述與分析482
10.2.2 程序實現486
10.2.3 應用--親情號489
10.3 無向圖的雙連通分支494
10.3.1 算法描述與分析494
10.3.2 程序實現497
10.3.3 應用--雌雄大盜498
10.4 廣度優先搜索504
10.4.1 算法描述與分析504
10.4.2 程序實現507
10.4.3 應用--攻城掠地508
10.5 流網絡與最大流問題512
10.5.1 算法描述與分析512
10.5.2 程序實現521
10.5.3 應用523第11章 代碼實驗528
11.1 頭文件清單528
11.1.1 基本應用類函數528
11.1.2 數據結構類531
11.1.3 代數記算類函數534
11.1.4 計算幾何類函數536
11.1.5 數論計算類函數537
11.1.6 回溯搜索類函數539
11.1.7 動態規劃類函數540
11.1.8 貪婪策略類函數540
11.1.9 圖的搜索類函數541
11.2 實驗平臺的搭建542
11.2.1 集成開發環境的安裝542
11.2.2 實驗項目的建立542
11.3 應用問題程序的運行實例544
11.3.1 加載程序文件544
11.3.2 調試程序545
11.3.3 各應用問題加載文件清單546
11.4 函數庫的擴展554
11.4.1 向已有的源文件中添加新函數554
11.4.2 創建新的源文件555
參考文獻557 |
| 序： |
|
