xxxx欧美丰满大屁股/性欧美极品xxxx欧美一区二区/男插女的下面免费视频夜色/美女视频在线一区二区三区

                                                                                                                                                    內(nèi)容簡介

          本書在講述算法設(shè)計(jì)技術(shù)時(shí)采用了新的分類方法，在討論分析方法時(shí)條分縷析，形成了連貫有序、耳目一新的風(fēng)格。為便于學(xué)生掌握，本書涵蓋算法入門課程的全部內(nèi)容，更注重對概念(而非形式)的理解。書中通過一些流行的謎題來激發(fā)學(xué)生的興趣，幫助他們加強(qiáng)和提高解決算法問題的能力。每章小結(jié)、習(xí)題提示和詳細(xì)解答，形成了非常鮮明的教學(xué)特色。

 

編輯推薦：

歷經(jīng)十年數(shù)百所高校教學(xué)實(shí)踐的算法入門經(jīng)典

算法是思維的藝術(shù)，是數(shù)學(xué)之美的完美體現(xiàn)，是計(jì)算機(jī)和信息科學(xué)的靈魂，更是優(yōu)秀程序員的安身立命之本。本書將算法視為解決問題的工具，通過作者獨(dú)創(chuàng)的、具有里程碑意義的新型分類法彌補(bǔ)了傳統(tǒng)算法設(shè)計(jì)技術(shù)分類法的缺陷，用深入淺出的語言和新穎的實(shí)例與謎題，詮釋了何為算法、算法的分類、算法幕后的思想、算法的效率，抽絲剝繭、條分縷析地探索了算法設(shè)計(jì)與分析過程。

本書用全新的方式通過謎題和游戲來開拓算法思維，既適合本科生和研究生教學(xué)，又適合程序員參考，是幫助他們享受算法的樂趣，領(lǐng)悟思維訓(xùn)練之美，提升編程能力的理想讀物。

    （1)從科學(xué)性和專業(yè)性來講，作者將原來不受重視的一些算法設(shè)計(jì)策略（如蠻力法、減治法、變治法、時(shí)空權(quán)衡和迭代改進(jìn)）等納入其中，覆蓋了更多傳統(tǒng)方法無法分類的經(jīng)典算法（如歐幾里得算法、堆排序、查找樹、散列法、拓?fù)渑判颉⒏咚瓜�去法、霍鈉法則等），甚至還納入了一些重要算法設(shè)計(jì)方法的變種。

   （2)從系統(tǒng)性來講，有趣的是，本書采用的正是算法的經(jīng)典模式，首先說明什么是算法，然后經(jīng)過思維訓(xùn)練和實(shí)踐，解決如何分析與設(shè)計(jì)算法。這一點(diǎn)而言，對學(xué)生的真正意義在于，學(xué)會(huì)用思維能力和創(chuàng)新能力來解決問題，為日后的職業(yè)生涯打下堅(jiān)實(shí)的基礎(chǔ)。

    （3)從適用性來講，本書跳出了傳統(tǒng)教材的框架，用一種新穎的方式來呈現(xiàn)主題，既照顧了本科學(xué)生課堂教學(xué)的需求，也兼顧了讓他們課后拓展學(xué)習(xí)，進(jìn)一步探索算法奧秘的愿望，具有廣泛的普適性。

    （4)從創(chuàng)新性來講，本書的分類框架條理清晰，符合計(jì)算機(jī)教育的原理，非常適合算法教學(xué)，大量的流行謎題和游戲，讓人流連忘返，手不釋卷。

經(jīng)過近5年的教學(xué)實(shí)踐，本書第1版和第2版被證明是算法課程中具有較高價(jià)值的經(jīng)典教材，據(jù)不完全統(tǒng)計(jì)，選用本書的學(xué)校包括清華大學(xué)、復(fù)旦大學(xué)、中國礦業(yè)大學(xué)、上海交通大學(xué)、解放軍理工大學(xué)、廣西大學(xué)、華南理工大學(xué)、安徽工業(yè)大學(xué)、廣東工業(yè)大學(xué)、西安建筑科技大學(xué)，廣東理工大學(xué)，齊齊哈爾大學(xué)、南昌航空工業(yè)學(xué)院軟件學(xué)院、解放軍炮兵學(xué)院、綿陽師范學(xué)院、湘潭大學(xué)、徐州工程學(xué)院、廣東工業(yè)大學(xué)、廣東工業(yè)大學(xué)、沈陽工業(yè)大學(xué)、西南科技大學(xué)、上海工程技術(shù)大學(xué)、湖南商學(xué)院、炮兵學(xué)院基礎(chǔ)部、江西財(cái)經(jīng)大學(xué)、華北科技學(xué)院、中南民族大學(xué)、沈陽建筑大學(xué)、北京第二外國語學(xué)院教育技術(shù)中心、濰坊學(xué)院、西華大學(xué)、武漢理工大學(xué)、河南師范大學(xué)、無錫科技職業(yè)學(xué)院、安徽理工大學(xué)、浙江工商大學(xué)、肇慶學(xué)院等。

媒體評論：

l   知名IT雜志《Dr. Dobb Journal》 發(fā)表了一篇題為“算法設(shè)計(jì)技術(shù)新藍(lán)圖”（A New Roadmap of Algorithm Design Techniques）的文章，對Anany Levitin給予高度評價(jià)。

全文鏈接：http://www.drdobbs.com/a-new-road-map-ofalgorithm-design-techni/184404059

l   SIGCSE 2002主題報(bào)告：“謎題在算法教學(xué)過程中的巧用”（Using Puzzles in Teaching Algorithms），作者Anany Levitin和Mary-Angela Papalaskari。

全文鏈接：http://www.csc.villanova.edu/~map/puzzles.pdf

幻燈片：http://www.csc.villanova.edu/~map/sigcse02/sld001.htm

l   -UNLV：“本書以全新的角度另辟蹊徑，按照算法設(shè)計(jì)來對各種算法進(jìn)行分類，這樣做大大激發(fā)了學(xué)生學(xué)習(xí)算法的興趣，提高了他們的學(xué)習(xí)積極性。”

l   -密西根大學(xué)：“本書以引人入勝的獨(dú)到方式描述了算法的結(jié)構(gòu)（英語描述，偽代碼）和行為（英語描述，執(zhí)行樹）”

l   -阿拉巴馬大學(xué): “書中的練習(xí)題很好地綜合了算法跟蹤、算法設(shè)計(jì)、數(shù)學(xué)證明和程序?qū)崿F(xiàn)這幾大重要環(huán)節(jié)。”

 

本書特色：

l 獨(dú)辟蹊徑，采用一種更全面的算法設(shè)計(jì)技術(shù)分類方法

l 涵蓋遞歸與非遞歸算法的數(shù)學(xué)分析，也涉及經(jīng)驗(yàn)分析和算法可視化

l 探討算法的局限性及解決方法

l 將算法視為解決問題的工具，通過謎題和游戲來開拓算法思維

l   為學(xué)生提供600多道習(xí)題(含提示)，為教師提供有詳細(xì)解答的教師手冊

本書適用于以下課程：

l 算法(計(jì)算機(jī)科學(xué))

l C++算法(計(jì)算機(jī)科學(xué))

l Java—算法(計(jì)算機(jī)科學(xué))

l C算法(計(jì)算機(jī)科學(xué))

l C算法/數(shù)據(jù)結(jié)構(gòu)高級(jí)課程(計(jì)算機(jī)科學(xué))

l Java-算法/數(shù)據(jù)結(jié)構(gòu)高級(jí)課程(計(jì)算機(jī)科學(xué))

l C++--算法/數(shù)據(jù)結(jié)構(gòu)高級(jí)課程(計(jì)算機(jī)科學(xué))

 

作者簡介： Anany Levitin教授，維拉諾瓦大學(xué)

畢業(yè)于莫斯科國立大學(xué)并獲得數(shù)學(xué)碩士學(xué)位。他擁有耶路撒冷希伯來大學(xué)數(shù)學(xué)博士學(xué)位和美國肯塔基大學(xué)計(jì)算機(jī)科學(xué)碩士學(xué)位。他的著作《算法設(shè)計(jì)與分析基礎(chǔ)》已經(jīng)被翻譯為中文、俄文、希臘文和韓文，并被全球數(shù)百所高校廣泛用作教材。目前，Levitin博士在美國維拉諾瓦大學(xué)講授“算法設(shè)計(jì)與分析”課程。他的另一本著作《算法謎題》已經(jīng)于2011年秋出版。

 

Anany Levitin，美籍猶太人，維拉諾瓦大學(xué)（Villanova）計(jì)算機(jī)科學(xué)系教授。他的論文“算法設(shè)計(jì)技術(shù)新途徑：彌補(bǔ)傳統(tǒng)分類法的缺憾”(A New Road Mpa of Algorithm Design Techniques: Picking Up Where the Traditional Classfication Leaves Off)深受業(yè)內(nèi)好評，并享有廣泛的聲譽(yù)。他提出的這種新分類方法涵蓋眾多經(jīng)典算法，開創(chuàng)了傳統(tǒng)分類無法以一致方式介紹這些算法的先河。作為通用的問題解決工具，算法設(shè)計(jì)技術(shù)的應(yīng)用很廣，尤其適用于解決“狼，羊，白菜”問題和旅行商問題之類的流行謎題。

 

因?yàn)樗麑λ惴ń逃�所做出的杰出貢獻(xiàn)，Levitin教授曾多次受邀在SIGCSE(Computer Science Education，計(jì)算機(jī)教育) 全球大會(huì)上發(fā)表演講，此大會(huì)每三年才舉行一次。

 

Anany Levitin教授目前的研究課題為“Do We Teach the Right Algorithm Design Techniques ?”

 

目錄：Table of Contents

New to the Third Edition xvii
Preface xix
1Introduction 1
1.1 What Is an Algorithm? 3
Exercises 1.1 7
1.2 Fundamentals of Algorithmic Problem Solving 9
Understanding the Problem 9
Ascertaining the Capabilities of the Computational Device 9
Choosing between Exact and Approximate Problem Solving 11
Algorithm Design Techniques 11
Designing an Algorithm and Data Structures 12
Methods of Specifying an Algorithm 12
Proving an Algorithm’s Correctness 13
Analyzing an Algorithm 14
Coding an Algorithm 15
Exercises 1.2 17
1.3 Important Problem Types 18
Sorting 19
Searching 20
String Processing 20
Graph Problems 21
Combinatorial Problems 21
Geometric Problems 22
Numerical Problems 22
Exercises 1.3 23
1.4 Fundamental Data Structures 25
Linear Data Structures 25
Graphs 28
Trees 31
Sets and Dictionaries 35
Exercises 1.4 37
Summary 38

2 Fundamentals of the Analysis of Algorithm Efficiency 41
2.1 The Analysis Framework 42
Measuring an Input’s Size 43
Units for Measuring Running Time 44
Orders of Growth 45
Worst-Case, Best-Case, and Average-Case Efficiencies 47
Recapitulation of the Analysis Framework 50
Exercises 2.1 50
2.2 Asymptotic Notations and Basic Efficiency Classes 52
Informal Introduction 52
O-notation 53
-notation 54
-notation 55
Useful Property Involving the Asymptotic Notations 55
Using Limits for Comparing Orders of Growth 56
Basic Efficiency Classes 58
Exercises 2.2 58
2.3 Mathematical Analysis of Nonrecursive Algorithms 61
Exercises 2.3 67
2.4 Mathematical Analysis of Recursive Algorithms 70
Exercises 2.4 76
2.5 Example: Computing the nth Fibonacci Number 80
Exercises 2.5 83
2.6 Empirical Analysis of Algorithms 84
Exercises 2.6 89
2.7 Algorithm Visualization 91
Summary 94

3 Brute Force and Exhaustive Search 97
3.1 Selection Sort and Bubble Sort 98
Selection Sort 98
Bubble Sort 100
Exercises 3.1 102
3.2 Sequential Search and Brute-Force String Matching 104
Sequential Search 104
Brute-Force String Matching 105
Exercises 3.2 106
3.3 Closest-Pair and Convex-Hull Problems by Brute Force 108
Closest-Pair Problem 108
Convex-Hull Problem 109
Exercises 3.3 113
3.4 Exhaustive Search 115
Traveling Salesman Problem 116
Knapsack Problem 116
Assignment Problem 119
Exercises 3.4 120
3.5 Depth-First Search and Breadth-First Search 122
Depth-First Search 122
Breadth-First Search 125
Exercises 3.5 128
Summary 130

4 Decrease-and-Conquer 131
4.1 Insertion Sort 134
Exercises 4.1 136
4.2 Topological Sorting 138
Exercises 4.2 142
4.3 Algorithms for Generating Combinatorial Objects 144
Generating Permutations 144
Generating Subsets 146
Exercises 4.3 148
4.4 Decrease-by-a-Constant-Factor Algorithms 150
Binary Search 150
Fake-Coin Problem 152
Russian Peasant Multiplication 153
Josephus Problem 154
Exercises 4.4 156
4.5 Variable-Size-Decrease Algorithms 157
Computing a Median and the Selection Problem 158
Interpolation Search 161
Searching and Insertion in a Binary Search Tree 163
The Game of Nim 164
Exercises 4.5 166
Summary 167

5 Divide-and-Conquer 169
5.1 Mergesort 172
Exercises 5.1 174
5.2 Quicksort 176
Exercises 5.2 181
5.3 Binary Tree Traversals and Related Properties 182
Exercises 5.3 185
5.4 Multiplication of Large Integers and
Strassen’s Matrix Multiplication 186
Multiplication of Large Integers 187
Strassen’s Matrix Multiplication 189
Exercises 5.4 191
5.5 The Closest-Pair and Convex-Hull Problems
by Divide-and-Conquer 192
The Closest-Pair Problem 192
Convex-Hull Problem 195
Exercises 5.5 197
Summary 198

6 Transform-and-Conquer 201
6.1 Presorting 202
Exercises 6.1 205
6.2 Gaussian Elimination 208
LU Decomposition 212
Computing a Matrix Inverse 214
Computing a Determinant 215
Exercises 6.2 216
6.3 Balanced Search Trees 218
AVL Trees 218
2-3 Trees 223
Exercises 6.3 225
6.4 Heaps and Heapsort 226
Notion of the Heap 227
Heapsort 231
Exercises 6.4 233
6.5 Horner’s Rule and Binary Exponentiation 234
Horner’s Rule 234
Binary Exponentiation 236
Exercises 6.5 239
6.6 Problem Reduction 240
Computing the Least Common Multiple 241
Counting Paths in a Graph 242
Reduction of Optimization Problems 243
Linear Programming 244
Reduction to Graph Problems 246
Exercises 6.6 248
Summary 250

7 Space and Time Trade-Offs 253
7.1 Sorting by Counting 254
Exercises 7.1 257
7.2 Input Enhancement in String Matching 258
Horspool’s Algorithm 259
Boyer-Moore Algorithm 263
Exercises 7.2 267
7.3 Hashing 269
Open Hashing (Separate Chaining) 270
Closed Hashing (Open Addressing) 272
Exercises 7.3 274
7.4 B-Trees 276
Exercises 7.4 279
Summary 280

8 Dynamic Programming 283
8.1 Three Basic Examples 285
Exercises 8.1 290
8.2 The Knapsack Problem and Memory Functions 292
Memory Functions 294
Exercises 8.2 296
8.3 Optimal Binary Search Trees 297
Exercises 8.3 303
8.4 Warshall’s and Floyd’s Algorithms 304
Warshall’s Algorithm 304
Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem 308
Exercises 8.4 311
Summary 312

9 Greedy Technique 315
9.1 Prim’s Algorithm 318
Exercises 9.1 322
9.2 Kruskal’s Algorithm 325
Disjoint Subsets and Union-Find Algorithms 327
Exercises 9.2 331
9.3 Dijkstra’s Algorithm 333
Exercises 9.3 337
9.4 Huffman Trees and Codes 338
Exercises 9.4 342
Summary 344

10 Iterative Improvement 345
10.1 The Simplex Method 346
Geometric Interpretation of Linear Programming 347
An Outline of the Simplex Method 351
Further Notes on the Simplex Method 357
Exercises 10.1 359
10.2 The Maximum-Flow Problem 361
Exercises 10.2 371
10.3 Maximum Matching in Bipartite Graphs 372
Exercises 10.3 378
10.4 The Stable Marriage Problem 380
Exercises 10.4 383
Summary 384

11 Limitations of Algorithm Power 387
11.1 Lower-Bound Arguments 388
Trivial Lower Bounds 389
Information-Theoretic Arguments 390
Adversary Arguments 390
Problem Reduction 391
Exercises 11.1 393
11.2 Decision Trees 394
Decision Trees for Sorting 395
Decision Trees for Searching a Sorted Array 397
Exercises 11.2 399
11.3 P, NP, and NP-Complete Problems 401
P and NP Problems 402
NP-Complete Problems 406
Exercises 11.3 409
11.4 Challenges of Numerical Algorithms 412
Exercises 11.4 419
Summary 420

12 Coping with the Limitations of Algorithm Power 423
12.1 Backtracking 424
n-Queens Problem 425
Hamiltonian Circuit Problem 426
Subset-Sum Problem 427
General Remarks 428
Exercises 12.1 430
12.2 Branch-and-Bound 432
Assignment Problem 433
Knapsack Problem 436
Traveling Salesman Problem 438
Exercises 12.2 440
12.3 Approximation Algorithms for NP-Hard Problems 441
Approximation Algorithms for the Traveling Salesman Problem 443
Approximation Algorithms for the Knapsack Problem 453
Exercises 12.3 457
12.4 Algorithms for Solving Nonlinear Equations 459
Bisection Method 460
Method of False Position 464
Newton’s Method 464
Exercises 12.4 467
Summary 468
Epilogue 471

APPENDIX A
Useful Formulas for the Analysis of Algorithms 475
Properties of Logarithms 475
Combinatorics 475
Important Summation Formulas 476
Sum Manipulation Rules 476
Approximation of a Sum by a Definite Integral 477
Floor and Ceiling Formulas 477
Miscellaneous 477

APPENDIX B
Short Tutorial on Recurrence Relations 479
Sequences and Recurrence Relations 479
Methods for Solving Recurrence Relations 480
Common Recurrence Types in Algorithm Analysis 485
References 493
Hints to Exercises 503
Index 547

 

書摘：前　　言

“一個(gè)人接受科技教育時(shí)所能獲得的最珍貴的收獲，是那些能夠受用終身的通用智能工具[1]。”

——George Forsythe，What to do till the computer scientist comes，1968

無論是計(jì)算科學(xué)還是計(jì)算實(shí)踐，算法都在其中扮演著重要角色。因此，這門學(xué)科中出現(xiàn)了大量的教材。它們在介紹算法的時(shí)候，基本上都選擇了以下兩種方案中的一種。第一種方案是按照問題的類型對算法分類。這類教材安排了不同的章節(jié)分別討論排序、查找、圖等算法。這種做法的優(yōu)點(diǎn)是，對于解決同一問題的不同算法，它能夠立即比較這些算法的效率。其缺點(diǎn)在于，由于過于強(qiáng)調(diào)問題的類型，它忽略了對算法設(shè)計(jì)技術(shù)的討論。

第二種方案圍繞著算法設(shè)計(jì)技術(shù)來組織章節(jié)。在這種結(jié)構(gòu)中，即使算法來自于不同的計(jì)算領(lǐng)域，如果它們采用了相同的設(shè)計(jì)技術(shù)，就會(huì)被編成一組。從各方(例如[BaY95])獲得的信心使我相信，這種結(jié)構(gòu)更適合于算法設(shè)計(jì)與分析的基礎(chǔ)課程。強(qiáng)調(diào)算法設(shè)計(jì)技術(shù)有三個(gè)主要原因。第一，學(xué)生們在解決新問題時(shí)，可以運(yùn)用這些技術(shù)設(shè)計(jì)出新的算法。從實(shí)用的角度看，這使得學(xué)習(xí)算法設(shè)計(jì)技術(shù)頗有價(jià)值。第二，學(xué)生們會(huì)試圖按照算法的內(nèi)在設(shè)計(jì)方法對已知的眾多算法進(jìn)行分類。計(jì)算機(jī)科學(xué)教育的一個(gè)主要目的，就是讓學(xué)生們知道如何發(fā)掘不同應(yīng)用領(lǐng)域的算法間的共性。畢竟，每門學(xué)科都會(huì)傾向于把它的重要主題歸納為幾個(gè)甚至一個(gè)規(guī)則。第三，依我看來，算法設(shè)計(jì)技術(shù)作為問題求解的一般性策略，在解決計(jì)算機(jī)領(lǐng)域以外的問題時(shí)，也能發(fā)揮相當(dāng)大的作用。

遺憾的是，無論是從理論還是從教學(xué)的角度，傳統(tǒng)的算法設(shè)計(jì)技術(shù)分類法都存在一些嚴(yán)重的缺陷。其中最顯著的缺陷就是無法對許多重要的算法進(jìn)行分類。由于這種局限性，這些書的作者不得不在按照設(shè)計(jì)技術(shù)進(jìn)行分類的同時(shí)，另外增加一些章節(jié)來討論特殊的問題類型。但這種改變將導(dǎo)致課程缺乏一致性，而且很可能會(huì)使學(xué)生感到迷惑。

算法設(shè)計(jì)技術(shù)的新分類法

傳統(tǒng)算法設(shè)計(jì)技術(shù)分類法的缺陷令我感到失望，它激發(fā)我開發(fā)一套新的分類法[Lev99]，這套分類法就是本書的基礎(chǔ)。以下是這套新分類法的幾個(gè)主要優(yōu)勢。

l   新分類法比傳統(tǒng)分類法更容易理解。它包含的某些設(shè)計(jì)策略，例如蠻力法、減治法、變治法、時(shí)空權(quán)衡和迭代改進(jìn)，幾乎從不曾被看作重要的設(shè)計(jì)范例。

l   新分類法很自然地覆蓋了許多傳統(tǒng)方法無法分類的經(jīng)典算法(歐幾里得算法、堆排序、查找樹、散列法、拓?fù)渑判颉⒏咚瓜�去法、霍納法則等，不勝枚舉)。所以，新分類法能夠以一種連貫的、一致的方式表達(dá)這些經(jīng)典算法的標(biāo)準(zhǔn)內(nèi)容。

l   新分類法很自然地容納了某些設(shè)計(jì)技術(shù)的重要變種(例如，它能涵蓋減治法的3個(gè)變種和變治法的3個(gè)變種)。

l   在分析算法效率時(shí)，新分類法與分析方法結(jié)合得更好(參見附錄B)。

設(shè)計(jì)技術(shù)作為問題求解的一般性策略

在本書中，主要將設(shè)計(jì)技術(shù)應(yīng)用于計(jì)算機(jī)科學(xué)中的經(jīng)典問題(這里唯一的創(chuàng)新是引入了一些數(shù)值算法的內(nèi)容，我們也是用同樣的通用框架來表述這些算法的)。但把這些設(shè)計(jì)技術(shù)看作問題求解的一般性工具時(shí)，它們的應(yīng)用就不僅限于傳統(tǒng)的計(jì)算問題和數(shù)學(xué)問題了。有兩個(gè)因素令這一點(diǎn)變得尤其重要。第一，越來越多的計(jì)算類應(yīng)用超越了它們的傳統(tǒng)領(lǐng)域，并且有足夠的理由使人相信，這種趨勢會(huì)愈演愈烈。第二，人們漸漸認(rèn)識(shí)到，提高學(xué)生們的問題求解能力是高等教育的一個(gè)主要目標(biāo)。為了滿足這個(gè)目標(biāo)，在計(jì)算機(jī)科學(xué)課程體系中安排一門算法設(shè)計(jì)和分析課程是非常合適的，因?yàn)樗鼤?huì)告訴學(xué)生如何應(yīng)用一些特定的策略來解決問題。

雖然我并不建議將算法設(shè)計(jì)和分析課程變成一門教授一般性問題求解方法的課程，但我的確認(rèn)為，我們不應(yīng)錯(cuò)過算法設(shè)計(jì)和分析課程提供的這樣一個(gè)獨(dú)一無二的機(jī)會(huì)。為了這個(gè)目標(biāo)，本書包含了一些和謎題相關(guān)的應(yīng)用。雖然利用謎題來教授算法課程絕不是我的創(chuàng)新，但本書打算通過引進(jìn)一些全新的謎題來系統(tǒng)地實(shí)現(xiàn)這個(gè)思路。

如何使用本書

我的目標(biāo)是寫一本既不泛泛而談，又可供學(xué)生們獨(dú)立閱讀的教材。為了實(shí)現(xiàn)這個(gè)目標(biāo)，本書做了如下努力。

l   根據(jù)George Forsythe的觀點(diǎn)(參見引言)，我試圖著重強(qiáng)調(diào)那些隱藏在算法設(shè)計(jì)和分析背后的主要思想。在選擇特定的算法來闡述這些思想的時(shí)候，我并不傾向于涉及大量的算法，而是選擇那些最能揭示其內(nèi)在設(shè)計(jì)技術(shù)或分析方法的算法。幸運(yùn)的是，大多數(shù)經(jīng)典算法滿足了這個(gè)要求。

l   第2章主要分析算法的效率，該章將分析非遞歸算法的方法和分析遞歸算法的典型方法區(qū)別開來。這一章還花了一些篇幅介紹算法經(jīng)驗(yàn)分析和算法可視化。

l   書中系統(tǒng)地穿插著一些面向讀者的提問。其中有些問題是經(jīng)過精心設(shè)計(jì)的，而且答案緊隨其后，目的是引起讀者的注意或引發(fā)疑問。其余問題的用意是防止讀者走馬觀花，不能充分理解本書的內(nèi)容。

l   每一章結(jié)束時(shí)都會(huì)對本章最重要的概念和結(jié)論做一個(gè)總結(jié)。

l   本書包含600多道習(xí)題。有些習(xí)題是為了給大家練習(xí)，另外一些則是為了指出書中正文部分所涉及內(nèi)容的重要意義，或是為了介紹一些書中沒有涉及的算法。有一些習(xí)題利用了因特網(wǎng)上的資源。較難的習(xí)題數(shù)量不多，會(huì)在教師用書中用一種特殊的記號(hào)標(biāo)注出來(因?yàn)橛行�學(xué)生可能沒有勇氣做那些標(biāo)有難度的習(xí)題，所以本書沒有對習(xí)題標(biāo)注難度)。謎題類的習(xí)題用一種特殊的圖標(biāo)做標(biāo)注。

l   本書所有的習(xí)題都附有提示。除了編程練習(xí)，習(xí)題的詳細(xì)解法都能夠在教師用書中找到，符合條件的教師可以填寫書后的教師證明表，發(fā)傳真到010-62791865或者發(fā)郵件到coo@netease.com，以獲得教學(xué)資源的訪問權(quán)限，也可聯(lián)系培生公司的當(dāng)?shù)劁N售代表，或者訪問www. pearsonhighered.com/irc。本書的任何讀者都可以在CS支持網(wǎng)站http://cssupport.pearsoncmg.com上找到PowerPoint格式的幻燈片文件。

第3版的變化

第3版有若干變化。其中最重要的變化是介紹減治法和分治法的先后順序。第3版會(huì)先介紹減治法，后介紹分治法，這樣做有以下幾個(gè)優(yōu)點(diǎn)。

l   較之分治法，減治法更簡單。

l   在求解問題方面，減治法應(yīng)用更廣。

l   這樣的編排順序便于先介紹插入排序，后介紹合并排序和快速排序。

l   數(shù)組劃分的概念通過選擇性問題引入，這次利用Lomuto算法的單向掃描來實(shí)現(xiàn)，而將Hoare劃分方法的雙向掃描留至后文與快速排序一并介紹。

l   折半查找歸入介紹減常量算法的章節(jié)。

另一重要變化是重新編排第8章關(guān)于動(dòng)態(tài)規(guī)劃的內(nèi)容，具體如下所述。

l   導(dǎo)述部分的內(nèi)容是全新的。在前兩版中用計(jì)算二項(xiàng)式系數(shù)的例子來引入動(dòng)態(tài)規(guī)劃這一重要技術(shù)，但在第3版中會(huì)介紹3個(gè)基礎(chǔ)性示例，這樣介紹的效果更好。

l   8.1節(jié)的習(xí)題是全新的，包括一些在前兩版中沒有涉及的流行的應(yīng)用。

l   第8章其他小節(jié)的順序也做了調(diào)整，以便達(dá)到由淺入深、循序漸進(jìn)的效果。

此外，還有其他一些變化。增加了不少與本書所述算法相關(guān)的應(yīng)用。遍歷圖算法不再隨減治法介紹，而是納入蠻力算法和窮舉查找的范疇，我認(rèn)為這樣更合理。在介紹生成組合對象的算法時(shí)，會(huì)新增格雷碼算法。對求解最近對問題的分治法會(huì)有更深入的探討。改進(jìn)的內(nèi)容包括算法可視化和求解旅行商問題的近似算法，當(dāng)然參考文獻(xiàn)也相應(yīng)更新。

第3版新增約70道習(xí)題，其中涉及算法謎題和面試問題。

讀者所需的知識(shí)背景

本書假定讀者已經(jīng)學(xué)習(xí)了離散數(shù)學(xué)的標(biāo)準(zhǔn)課程和一門基礎(chǔ)性的編程課程。有了這樣的知識(shí)背景，讀者應(yīng)該能夠掌握本書的內(nèi)容而不會(huì)遇到太大的困難。盡管如此，1.4節(jié)、附錄A和附錄B仍然對基本的數(shù)據(jù)結(jié)構(gòu)，必須用到的求和公式和遞推關(guān)系分別進(jìn)行了復(fù)習(xí)和回顧。只有3個(gè)小節(jié)(2.2節(jié)、11.4節(jié)和12.4節(jié))會(huì)用到一些簡單的微積分知識(shí)，如果讀者缺少必要的微積分知識(shí)，完全可以跳過這3個(gè)涉及微積分的小節(jié)，這并不會(huì)妨礙對本書其余部分的理解。

---

         [1] 譯注：George Forsythe認(rèn)為，在這些工具當(dāng)中，最重要的三項(xiàng)依次是自然語言、數(shù)學(xué)和計(jì)算機(jī)科學(xué)。

 

進(jìn)度安排

如果打算開設(shè)一門圍繞算法設(shè)計(jì)技術(shù)來講解算法設(shè)計(jì)和分析理論的基礎(chǔ)課程，可以采用本書作為教材。但要想在一個(gè)學(xué)期內(nèi)完成該課程，本書涵蓋的內(nèi)容可能過于豐富了。大體上來說，跳過第3～12章的部分內(nèi)容不會(huì)影響讀者對后面部分的理解。本書的任何一個(gè)部分都可以安排學(xué)生自學(xué)。尤其是2.6節(jié)和2.7節(jié)，它們分別介紹了經(jīng)驗(yàn)分析和算法可視化，這兩小節(jié)的內(nèi)容可以結(jié)合練習(xí)布置給學(xué)生。

下面給出了一種針對一個(gè)學(xué)期課程的教學(xué)計(jì)劃，這是按照40課時(shí)的集中教學(xué)來設(shè)計(jì)的。

 

<style id="czqlj"></style>

<li id="czqlj"><dl id="czqlj"></dl></li>

課  次	主  題	小  節(jié)
1	課程簡介	1.1～1.3
2，3	分析框架；、和符號(hào)	2.1，2.2
4	非遞歸算法的數(shù)學(xué)分析	2.3
5，6	遞歸算法的數(shù)學(xué)分析	2.4，2.5(+附錄B)
7	蠻力算法	3.1，3.2(+3.3)
8	窮舉查找	3.4
9	深度優(yōu)先查找和廣度優(yōu)先查找	3.5
10～11	減一算法：插入排序、拓?fù)渑判?/font>	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	實(shí)例化簡：預(yù)排序、高斯消去法、平衡查找樹	6.1～6.3
20	改變表現(xiàn)：堆和堆排序	6.4或
	或者霍納法則和二進(jìn)制冪	6.5
21	問題化簡	6.6
22～24	時(shí)空權(quán)衡：串匹配、散列法、B樹	7.2～7.4
25～27	動(dòng)態(tài)規(guī)劃算法	8.1～8.4(選3節(jié))
28～30	貪婪算法：Prim算法、Kruskal算法、Dijkstra算法、哈夫曼算法	9.1～9.4
31～33	迭代改進(jìn)算法	10.1～10.4(選3節(jié))
34	下界的參數(shù)	11.1
35	決策樹	11.2
36	P、NP和NP完全問題	11.3
37	數(shù)值算法< 商品標(biāo)簽 購買記錄(近期成交數(shù)量0) 還沒有人購買過此商品 總計(jì) 0 個(gè)記錄，共 1 頁。 第一頁 上一頁 下一頁 最末頁 用戶評論(共0條評論) 暫時(shí)還沒有任何用戶評論 總計(jì) 0 個(gè)記錄，共 1 頁。 第一頁 上一頁 下一頁 最末頁 用戶名： 匿名用戶 E-mail： 評價(jià)等級(jí)： 評論內(nèi)容： 驗(yàn)證碼： Copyright 2005 www.detikinfo.net All Rights Reserved 地址：清華大學(xué)院內(nèi)清華出版社白樓（清華大學(xué)游泳館東側(cè)） 站長QQ： 124487725(投稿專用) Email:book1402@126.com(投稿專用) 電話：010-62791865 版權(quán)所有：© 2005-2025 文源 版權(quán)所有，并保留所有權(quán)利。

<mark id="czqlj"><optgroup id="czqlj"></optgroup></mark>

<rt id="czqlj"><dd id="czqlj"><sup id="czqlj"></sup></dd></rt>

<var id="czqlj"></var>

<center id="czqlj"><listing id="czqlj"></listing></center>

<var id="czqlj"></var>