日韩偷拍一区二区,国产香蕉久久精品综合网,亚洲激情五月婷婷,欧美日韩国产不卡

"一個人接受科技教育時所能獲得的最珍貴的收獲，是那些能夠受用終身的通用智能工具[1]。"

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

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

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

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

算法設計技術的新分類法

傳統算法設計技術分類法的缺陷令我感到失望，它激發我開發一套新的分類法[Lev99]，這套分類法就是本書的基礎。以下是這套新分類法的幾個主要優勢。

新分類法比傳統分類法更容易理解。它包含的某些設計策略，例如蠻力法、減治法、變治法、時空權衡和迭代改進，幾乎從不曾被看作重要的設計范例。

新分類法很自然地覆蓋了許多傳統方法無法分類的經典算法(歐幾里得算法、堆排序、查找樹、散列法、拓撲排序、高斯消去法、霍納法則等，不勝枚舉)。所以，新分類法能夠以一種連貫的、一致的方式表達這些經典算法的標準內容。

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

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

設計技術作為問題求解的一般性策略

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

雖然我并不建議將算法設計和分析課程變成一門教授一般性問題求解方法的課程，但我的確認為，我們不應錯過算法設計和分析課程提供的這樣一個的機會。為了這個目標，本書包含了一些和謎題相關的應用。雖然利用謎題來教授算法課程絕不是我的創新，但本書打算通過引進一些全新的謎題來系統地實現這個思路。

如何使用本書

我的目標是寫一本既不泛泛而談，又可供學生們獨立閱讀的教材。為了實現這個目標，本書做了如下努力。

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

第2章主要分析算法的效率，該章將分析非遞歸算法的方法和分析遞歸算法的典型方法區別開來。這一章還花了一些篇幅介紹算法經驗分析和算法可視化。

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

每一章結束時都會對本章最重要的概念和結論做一個總結。

本書包含600多道習題。有些習題是為了給大家練習，另外一些則是為了指出書中正文部分所涉及內容的重要意義，或是為了介紹一些書中沒有涉及的算法。有一些習題利用了因特網上的資源。較難的習題數量不多，會在教師用書中用一種特殊的記號標注出來(因為有些學生可能沒有勇氣做那些標有難度的習題，所以本書沒有對習題標注難度)。謎題類的習題用一種特殊的圖標做標注。

本書所有的習題都附有提示。除了編程練習，習題的詳細解法都能夠在教師用書中找到，符合條件的教師可以填寫書后的教師證明表，發傳真到010-62791865或者發郵件到coo@netease.com，以獲得教學資源的訪問權限，也可聯系培生公司的當地銷售代表，或者訪問www. pearsonhighered.com/irc。本書的任何讀者都可以在CS支持網站cssupport.pearsoncmg.com上找到PowerPoint格式的幻燈片文件。

第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節，它們分別介紹了經驗分析和算法可視化，這兩小節的內容可以結合練習[2]布置給學生。

下面給出了一種針對一個學期課程的教學計劃，這是按照40課時的集中教學來設計的。

……