 |
-- 會員 / 註冊 --
|
 |
|
|
|
算法設計與分析基礎(第3版) ( 簡體 字) |
| 作者：（美）Anany Levitin著 | 類別：1. -> 程式設計 -> 演算法 |
| 譯者：潘彥 譯 |
| 出版社：清華大學出版社 |  3dWoo書號： 40577
詢問書籍請說出此書號！【缺書】
NT售價： 345 元 |
| 出版日：12/22/2014 |
| 頁數：422 |
| 光碟數：0 |
|
站長推薦：   |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787302386346 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：一個人在接受科技教育時能得到的最珍貴的收獲是能夠終身受用的通用智能工具。
——喬治?福賽思
無論是計算科學還是計算實踐，算法都在其中扮演著重要角色。因此，這門學科中出現了大量的教材。它們在介紹算法的時候，基本上都選擇了以下兩種方案中的一種。第一種方案是按照問題的類型對算法進行分類。這類教材安排了不同的章節分別討論排序、查找、圖等算法。這種做法的優點是，對于解決同一問題的不同算法，它能夠立即比較這些算法的效率。其缺點在于，由于過于強調問題的類型，它忽略了對算法設計技術的討論。
第二種方案圍繞著算法設計技術來組織章節。在這種結構中，即使算法來自于不同的計算領域，如果它們采用了相同的設計技術，就會被編成一組。從各方(例如[BaY95])獲得的信心使我相信，這種結構更適合于算法設計與分析的基礎課程。強調算法設計技術有三個主要原因。第一，學生們在解決新問題時，可以運用這些技術設計出新的算法。從實用的角度看，這使得學習算法設計技術頗有價值。第二，學生們會試圖按照算法的內在設計方法對已知的眾多算法進行分類。計算機科學教育的一個主要目的，就是讓學生們知道如何發掘不同應用領域的算法間的共性。畢竟，每門學科都會傾向于把它的重要主題歸納為幾個甚至一個規則。第三，依我看來，算法設計技術作為問題求解的一般性策略，在解決計算機領域以外的問題時，也能發揮相當大的作用。
遺憾的是，無論是從理論還是從教學的角度，傳統的算法設計技術分類法都存在一些嚴重的缺陷。其中最顯著的缺陷就是無法對許多重要的算法進行分類。由于這種局限性，這些書的作者不得不在按照設計技術進行分類的同時，另外增加一些章節來討論特殊的問題類型。但這種改變導致課程缺乏一致性，而且很可能會使學生感到迷惑。
算法設計技術的新分類法
傳統算法設計技術分類法的缺陷令我感到失望，它激發我開發一套新的分類法([Lev99])，這套分類法就是本書的基礎。以下是這套新分類法的幾個主要優勢。
新分類法比傳統分類法更容易理解。它包含的某些設計策略，例如蠻力法、減治法、變治法、時空權衡和迭代改進，幾乎從不曾被看作重要的設計范例。
新分類法很自然地覆蓋了許多傳統方法無法分類的經典算法(歐幾里得算法、堆排序、查找樹、散列法、拓撲排序、高斯消去法、霍納法則等，不勝枚舉)。所以，新分類法能夠以一種連貫的、一致的方式表達這些經典算法的標準內容。
新分類法很自然地容納了某些設計技術的重要變種(例如，它能涵蓋減治法的3個變種和變治法的3個變種)。
在分析算法效率時，新分類法與分析方法結合得更好(參見附錄B)。
設計技術作為問題求解的一般性策略
在本書中，主要將設計技術應用于計算機科學中的經典問題(這里唯一的創新是引入了一些數值算法的內容，我們也是用同樣的通用框架來表述這些算法的)。但把這些設計技術看作問題求解的一般性工具時，它們的應用就不僅限于傳統的計算問題和數學問題了。有兩個因素令這一點變得尤其重要。第一，越來越多的計算類應用超越了它們的傳統領域，并且有足夠的理由使人相信，這種趨勢會愈演愈烈。第二，人們漸漸認識到，提高學生們的問題求解能力是高等教育的一個主要目標。為了滿足這個目標，在計算機科學課程體系中安排一門算法設計和分析課程是非常合適的，因為它會告訴學生如何應用一些特定的策略來解決問題。
雖然我并不建議將算法設計和分析課程變成一門教授一般性問題求解方法的課程，但我深信，我們不應錯過算法設計和分析課程提供的這樣一個獨一無二的機會。為了這個目標，本書包含了一些和謎題相關的應用。雖然利用謎題來教授算法課程絕不是我的創新，但本書打算通過引進一些全新的謎題來系統地實現這個思路。
如何使用本書
我的目標是寫一本既不泛泛而談，又可供學生們獨立閱讀的教材。為了實現這個目標，本書做了如下努力。
根據喬治?福賽思的觀點(參見前面的引文)，我試圖著重強調隱藏在算法設計和分析背后的主要思想。在選擇特定的算法來闡述這些思想的時候，我并不傾向于涉及大量的算法，而是選擇那些最能揭示其內在設計技術或分析方法的算法。幸運的是，大多數經典算法滿足這個要求。
第2章主要分析算法的效率，該章將分析非遞歸算法的方法和分析遞歸算法的典型方法區別開來。這一章還花了一些篇幅介紹算法經驗分析和算法可視化。
書中系統地穿插著一些面向讀者的提問。其中有些問題是經過精心設計的，而且答案緊隨其后，目的是引起讀者的注意或引發疑問。其余問題的用意是防止讀者走馬觀花，不能充分理解本書的內容。
每一章結束時都會對本章最重要的概念和結論做一個總結。
本書包含600多道習題。有些習題是為了給大家練習，另外一些則是為了指出書中正文部分所涉及內容的重要意義，或是為了介紹一些書中沒有涉及的算法。有一些習題利用了因特網上的資源。較難的習題數量不多，會在教師用書中用一種特殊的記號標注出來(因為有些學生可能沒有勇氣做那些有難度標注的習題，所以本書沒有對習題標注難度)。謎題類的習題用一種特殊的圖標做標注。
本書所有的習題都附有提示。除了編程練習，習題的詳細解法都能夠在教師資源中找到。請發送郵件到coo@netease.com，申請教師相關資源(也可聯系培生公司的當地銷售代表，或者訪問www.pearsonhighered.com/irc)。本書的任何讀者都可以在CS支持網站http://cssupport.pearsoncmg.com上找到PowerPoint格式的幻燈片文件。如果對算法有興趣，歡迎加入QQ群“算法學習交流”，群號：425283001。
第3版的變化
第3版有若干變化。其中最重要的變化是介紹減治法和分治法的先后順序。第3版會先介紹減治法，后介紹分治法，這樣做有以下幾個優點。
較之分治法，減治法更簡單。
在求解問題方面，減治法應用更廣。
這樣的編排順序便于先介紹插入排序，后介紹合并排序和快速排序。
數組劃分的概念通過選擇性問題引入，這次利用Lomuto算法的單向掃描來實現，而將Hoare劃分方法的雙向掃描留至后文與快速排序一并介紹。
折半查找歸入介紹減常量算法的章節。
另一個重要變化是重新編排第8章關于動態規劃的內容，具體如下所述。
導述部分的內容是全新的。在前兩版中用計算二項式系數的例子來引入動態規劃這一重要技術，但在第3版中會介紹3個基礎性示例，這樣介紹的效果更好。
8.1節的習題是全新的，包括一些在前兩版中沒有涉及的流行的應用。
第8章其他小節的順序也做了調整，以便達到由淺入深、循序漸進的效果。
此外，還有其他一些變化。增加了不少與本書所述算法相關的應用。遍歷圖算法不再隨減治法介紹，而是納入蠻力算法和窮舉查找的范疇，我認為這樣更合理。在介紹生成組合對象的算法時，新增了格雷碼算法。對求解最近對問題的分治法有更深入的探討。改進的內容包括算法可視化和求解旅行商問題的近似算法，當然參考文獻也有相應的更新。
第3版一共新增約70道習題，其中涉及算法謎題和面試問題。
先修課程
本書假定讀者已經學習了離散數學的標準課程和一門基礎性的編程課程。有了這樣的知識背景，讀者應該能夠掌握本書的內容而不會遇到太大的困難。盡管如此，1.4節、附錄A和附錄B仍然對基本的數據結構以及必須用到的求和公式與遞推關系分別進行復習和回顧。只有3個小節(2.2節、11.4節和12.4節)會用到一些簡單的微積分知識，如果讀者缺少必要的微積分知識，完全可以跳過這3個涉及微積分的小節，這并不妨礙對本書其余部分的理解。
課程進度安排
如果打算開設一門圍繞算法設計技術來講解算法設計和分析理論的基礎課程，可以采用本書作為教材。但要想在一個學期內完成該課程，本書涵蓋的內容可能過于豐富了。大體上來說，跳過第3∼12章的部分內容不會影響讀者對后面部分的理解。本書的任何一個部分都可以安排學生自學。尤其是2.6節和2.7節，它們分別介紹了經驗分析和算法可視化，這兩小節的內容可以結合課后練習 布置給學生。
下面給出了針對一個學期課程的教學計劃，這是按照40課時的集中教學來設計的。
課次 主題 小 節
1 課程簡介 1.1∼1.3
2，3 分析框架；常用符號 、 和 2.1，2.2
4 非遞歸算法的數學分析 2.3
5，6 遞歸算法的數學分析 2.4，2.5(+附錄B)
7 蠻力算法 3.1，3.2(+3.3)
8 窮舉查找 3.4
9 深度優先查找和廣度優先查找 3.5
10∼11 減一算法：插入排序、拓撲排序 4.1，4.2
12 折半查找和其他減常量算法 4.4
13 減變量算法 4.5
14∼15 分治法：合并排序、快速排序 5.1∼5.2
16 其他分治法示例 5.3、5.4或5.5
16 減變量算法 5.6
17∼19 實例化簡：預排序、高斯消去法、平衡查找樹 6.1∼6.3
20 改變表現：堆和堆排序或者霍納法則和二進制冪 6.4或6.5
21 問題化簡 6.6
22∼24 時空權衡：串匹配、散列法、B樹 7.2∼7.4
25∼27 動態規劃算法 8.1∼8.4(選3節)
28∼30 貪婪算法：Prim算法、Kruskal算法、Dijkstra算法、哈夫曼算法 9.1∼9.4
31∼33 迭代改進算法 10.1∼10.4(選3節)
34 下界的參數 11.1
35 決策樹 11.2
36 P、NP和NP完全問題 11.3
37 數值算法 11.4(+12.4)
38 回溯法 12.1
39 分支界限法 12.2
40 NP困難問題的近似算法 12.3
致謝
我要向本書的評審表達衷心的感謝，還要感謝本書前兩版的許多讀者，他們提供了許多寶貴的意見和建議，幫助本書得以改進和完善。本書第3版尤其得益于下列人士的評審，包括Andrew Harrington(芝加哥洛約拉大學)、David Levine(圣文德大學)、Stefano Lombardi(加州大學河濱分校)、Daniel McKee(賓州曼斯菲爾德大學)、Susan Brilliant(弗吉尼亞州立聯邦大學)、David Akers(菩及海灣大學)以及兩名匿名評審。
我要感謝培生出版社所有為本書付出不懈努力的工作人員和相關人士。尤其要感謝本書編輯Matt Goldstein、編務助理Chelsea Bell、市場經理Yez Alayan和產品總監Kayla Smith-Tarbox。我還要感謝Richard Camp為本書審稿，Windfall Software的Paul Anagnostopoulos和Jacqui Scarlott為本書排版并提供項目管理支持，以及MaryEllen Oliver為本書進行校對。
最后，我要感謝兩位家人。另一半整天都在寫書比自己本人寫書更讓人崩潰，我的妻子Maria已容忍我多年并任勞任怨地幫助我，本書400多幅插圖以及教師手冊都是憑她一己之力完成的。女兒Miriam是我多年的英語老師，她不但閱讀了本書大量篇幅，還幫我為每章找到了合適的名人名言。
Anany Levitin
anany.levitin@villanova.edu
|
內容簡介： 作者基于豐富的教學經驗，開發了一套全新的算法分類方法。該分類法站在通用問題求解策略的高度，對現有大多數算法準確分類，從而引領讀者沿著一條清晰、一致、連貫的思路來探索算法設計與分析這一迷人領域。本書作為第3版，相對前版調整了多個章節的內容和順序，同時增加了一些算法，并擴展了算法的應用，使得具體算法和通用算法設計技術的對應更加清晰有序；各章累計增加了70道習題，其中包括一些有趣的謎題和面試問題。
本書十分適合用作算法設計和分析的基礎教材，也適合任何有興趣探究算法奧秘的讀者使用，只要讀者具備數據結構和離散數學的知識即可。
Simplified Chinese edition copyright © 2015 by PEARSON EDUCATION ASIA LIMITED and TSINGHUA UNIVERSITY PRESS.
Original English language title: Introduction to the Design and Analysis of Algorithms, 3rd Edition by Anany Levitin, Copyright © 2012
EISBN: 9780132316811
All Rights Reserved.
Published by arrangement with the original publisher, Pearson Education, Inc., publishing as Pearson Education, Inc.
This edition is authorized for sale only in the People’s Republic of China (excluding the Special Administrative Region of Hong Kong and Macao).
本書中文簡體翻譯版由Pearson Education授權給清華大學出版社在中國境內(不包括中國香港、澳門特別行政區)出版發行。
|
目錄：第1章 緒論 1
1.1 什么是算法 2
習題1.1 6
1.2 算法問題求解基礎 7
1.2.1 理解問題 8
1.2.2 了解計算設備的性能 8
1.2.3 在精確解法和近似解法之間做出選擇 9
1.2.4 算法的設計技術 9
1.2.5 確定適當的數據結構 9
1.2.6 算法的描述 10
1.2.7 算法的正確性證明 10
1.2.8 算法的分析 11
1.2.9 為算法寫代碼 12
習題1.2 13
1.3 重要的問題類型 14
1.3.1 排序 15
1.3.2 查找 16
1.3.3 字符串處理 16
1.3.4 圖問題 16
1.3.5 組合問題 17
1.3.6 幾何問題 17
1.3.7 數值問題 18
習題1.3 18
1.4 基本數據結構 20
1.4.1 線性數據結構 20
1.4.2 圖 22
1.4.3 樹 25
1.4.4 集合與字典 28
習題1.4 29
小結 30
第2章 算法效率分析基礎 32
2.1 分析框架 33
2.1.1 輸入規模的度量 33
2.1.2 運行時間的度量單位 34
2.1.3 增長次數 35
2.1.4 算法的最優、最差和平均效率 36
2.1.5 分析框架概要 38
習題2.1 39
2.2 漸近符號和基本效率類型 40
2.2.1 非正式的介紹 40
2.2.2 符號O 41
2.2.3 符號 42
2.2.4 符號 42
2.2.5 漸近符號的有用特性 43
2.2.6 利用極限比較增長次數 44
2.2.7 基本的效率類型 45
習題2.2 46
2.3 非遞歸算法的數學分析 48
習題2.3 52
2.4 遞歸算法的數學分析 54
習題2.4 59
2.5 例題：計算第n個斐波那契數 62
習題2.5 65
2.6 算法的經驗分析 66
習題2.6 69
2.7 算法可視法 70
小結 73
第3章 蠻力法 75
3.1 選擇排序和冒泡排序 76
3.1.1 選擇排序 76
3.1.2 冒泡排序 77
習題3.1 78
3.2 順序查找和蠻力字符串匹配 80
3.2.1 順序查找 80
3.2.2 蠻力字符串匹配 81
習題3.2 82
3.3 最近對和凸包問題的蠻力算法 83
3.3.1 最近對問題 83
3.3.2 凸包問題 84
習題3.3 87
3.4 窮舉查找 89
3.4.1 旅行商問題 89
3.4.2 背包問題 90
3.4.3 分配問題 91
習題3.4 93
3.5 深度優先查找和廣度優先查找 94
3.5.1 深度優先查找 94
3.5.2 廣度優先查找 96
習題3.5 98
小結 100
第4章 減治法 101
4.1 插入排序 103
習題4.1 105
4.2 拓撲排序 106
習題4.2 109
4.3 生成組合對象的算法 111
4.3.1 生成排列 111
4.3.2 生成子集 113
習題4.3 114
4.4 減常因子算法 115
4.4.1 折半查找 116
4.4.2 假幣問題 117
4.4.3 俄式乘法 118
4.4.4 約瑟夫斯問題 119
習題4.4 120
4.5 減可變規模算法 122
4.5.1 計算中值和選擇問題 122
4.5.2 插值查找 125
4.5.3 二叉查找樹的查找和插入 126
4.5.4 拈游戲 127
習題4.5 128
小結 129
第5章 分治法 131
5.1 合并排序 133
習題5.1 135
5.2 快速排序 136
習題5.2 140
5.3 二叉樹遍歷及其相關特性 141
習題5.3 143
5.4 大整數乘法和Strassen矩陣乘法 144
5.4.1 大整數乘法 145
5.4.2 Strassen矩陣乘法 146
習題5.4 148
5.5 用分治法解最近對問題和凸包問題 149
5.5.1 最近對問題 149
5.5.2 凸包問題 151
習題5.5 153
小結 154
第6章 變治法 155
6.1 預排序 156
習題6.1 158
6.2 高斯消去法 160
6.2.1 LU分解 164
6.2.2 計算矩陣的逆 165
6.2.3 計算矩陣的行列式 166
習題6.2 167
6.3 平衡查找樹 168
6.3.1 AVL樹 169
6.3.2 2-3樹 173
習題6.3 174
6.4 堆和堆排序 175
6.4.1 堆的概念 176
6.4.2 堆排序 180
習題6.4 181
6.5 霍納法則和二進制冪 182
6.5.1 霍納法則 182
6.5.2 二進制冪 184
習題6.5 186
6.6 問題化簡 187
6.6.1 求最小公倍數 188
6.6.2 計算圖中的路徑數量 189
6.6.3 優化問題的化簡 189
6.6.4 線性規劃 190
6.6.5 簡化為圖問題 192
習題6.6 193
小結 194
第7章 時空權衡 196
7.1 計數排序 197
習題7.1 199
7.2 字符串匹配中的輸入增強技術 200
7.2.1 Horspool算法 201
7.2.2 Boyer-Moore算法 204
習題7.2 207
7.3 散列法 209
7.3.1 開散列(分離鏈) 210
7.3.2 閉散列(開式尋址) 211
習題7.3 213
7.4 B樹 214
習題7.4 217
小結 218
第8章 動態規劃 219
8.1 三個基本例子 220
習題8.1 224
8.2 背包問題和記憶功能 226
8.2.1 背包問題 226
8.2.2 記憶化 227
習題8.2 229
8.3 最優二叉查找樹 230
習題8.3 234
8.4 Warshall算法和Floyd算法 235
8.4.1 Warshall算法 235
8.4.2 計算完全最短路徑的Floyd算法 238
習題8.4 241
小結 242
第9章 貪婪技術 243
9.1 Prim算法 245
習題9.1 249
9.2 Kruskal算法 250
習題9.2 255
9.3 Dijkstra算法 256
習題9.3 259
9.4 哈夫曼樹及編碼 260
習題9.4 264
小結 265
第10章 迭代改進 266
10.1 單純形法 267
10.1.1 線性規劃的幾何解釋 267
10.1.2 單純形法概述 270
10.1.3 單純形法其他要點 275
習題10.1 276
10.2 最大流量問題 278
習題10.2 285
10.3 二分圖的最大匹配 286
習題10.3 291
10.4 穩定婚姻問題 292
習題10.4 295
小結 296
第11章 算法能力的極限 297
11.1 如何求下界 298
11.1.1 平凡下界 298
11.1.2 信息論下界 299
11.1.3 敵手下界 299
11.1.4 問題化簡 300
習題11.1 302
11.2 決策樹 302
11.2.1 排序的決策樹 303
11.2.2 查找有序數組的決策樹 305
習題11.2 306
11.3 P、NP和NP完全問題 308
11.3.1 P和NP問題 308
11.3.2 NP完全問題 311
習題11.3 314
11.4 數值算法的挑戰 316
習題11.4 322
小結 323
第12章 超越算法能力的極限 325
12.1 回溯法 325
12.1.1 n皇后問題 326
12.1.2 哈密頓回路問題 328
12.1.3 子集和問題 328
12.1.4 一般性說明 329
習題12.1 331
12.2 分支界限法 332
12.2.1 分配問題 332
12.2.2 背包問題 335
12.2.3 旅行商問題 336
習題12.2 338
12.3 NP困難問題的近似算法 339
12.3.1 旅行商問題的近似算法 340
12.3.2 背包問題的近似算法 349
習題12.3 352
12.4 解非線性方程的算法 353
12.4.1 平分法 355
12.4.2 試位法 357
12.4.3 牛頓法 358
習題12.4 360
小結 361
跋 363
附錄A 算法分析的實用公式 366
附錄B 遞推關系簡明指南 369
習題提示 380
參考文獻 414 |
| 序： |
|
