免费人妻中文不卡无码_日本精品爽爽van在线_久久精品国产99久久丝袜蜜桃_女强人被春药精油按摩bd电影

一個人在接受科技教育時，最有價值的收獲是能使其終身受益的通用智能工具。
喬治福賽斯
（譯注：原文為The most valuable acquisitions in a scientific or technical education are the general-purpose mental tools which remain serviceable for a life-time，出自1968年發(fā)表的What to do till the computer scientist comes。福賽斯(George Forsythe，19171972)1939年在布朗大學(xué)獲得博士學(xué)位，二戰(zhàn)后供職于斯坦福大學(xué)數(shù)學(xué)系，后來在該校創(chuàng)辦計算機系。他先后培養(yǎng)的博士生超過190名。他與MATLAB之父莫勒合著的《線性代數(shù)系統(tǒng)的計算機求解》出版于1967年。）

算法在計算科學(xué)和計算實踐中發(fā)揮著核心作用�；�于這樣的認知，涌現(xiàn)出大量相關(guān)的著述，尤其是教材。它們在介紹算法時基本上選擇遵循兩種方案。一種是根據(jù)問題類型對算法進行分類。這樣的書用單獨的章節(jié)介紹排序、查找以及圖等算法。這種方案的優(yōu)點在于，能立即對比同一問題場景下不同算法的效率。缺點在于，它強調(diào)的是問題類型，忽略了算法設(shè)計技術(shù)。
第二種方案是圍繞算法設(shè)計技術(shù)進行組織。采用這種組織方式，如果來自不同計算領(lǐng)域的算法采用的是相同的設(shè)計方法，就把它們歸為一組。我和許多人一樣(例如[BaY95])，認為這種組織方式更適合算法設(shè)計與分析基礎(chǔ)課程。強調(diào)算法設(shè)計技術(shù)主要有三個原因。第一，這些技術(shù)為學(xué)生提供了工具來為新的問題設(shè)計算法。這使學(xué)習(xí)算法設(shè)計技術(shù)具有實踐意義上的價值。第二，它們根據(jù)基本的設(shè)計理念來對眾多已知的算法進行分類。尋找不同應(yīng)用領(lǐng)域的算法之間的共性，這應(yīng)該是計算機科學(xué)教育的一個主要目標(biāo)。畢竟，每一門學(xué)科都將其主要課題的分類視為其學(xué)科的要點甚至是中心點。第三，在我看來，算法設(shè)計技術(shù)作為一般的問題解決策略具有實用性，適用于計算以外的問題。
遺憾的是，無論從理論還是教育的角度，算法設(shè)計技術(shù)的傳統(tǒng)分類法都有幾個重大的缺陷。最重要的是沒有對許多重要的算法進行分類。這一不足迫使其他教科書的作者背離設(shè)計技術(shù)的組織形式，在書中加入相應(yīng)的章節(jié)來處理具體的問題類型。這樣的轉(zhuǎn)換導(dǎo)致算法課程喪失連貫性，注定會導(dǎo)致學(xué)生覺得亂。
算法設(shè)計技術(shù)的新分類法
傳統(tǒng)算法設(shè)計技術(shù)分類法的缺陷讓人感到失望，所以我開發(fā)了一套新的分類法[Lev99]，這也是本書的基礎(chǔ)。新的分類法主要有下面幾個優(yōu)點。
新的分類法比傳統(tǒng)分類法更全面。新加入的蠻力法、減治法、變治法、時空權(quán)衡和迭代改進等策略很少(甚至從未)被認為是重要的設(shè)計范式(design paradigm)。
新的分類法自然涵蓋傳統(tǒng)分類法無法歸類的許多經(jīng)典算法(歐幾里得算法、堆排序、查找樹、散列法、拓撲排序、高斯消去法和霍納規(guī)則等)，所以，新的分類法使我們能以統(tǒng)一和連貫的方式呈現(xiàn)經(jīng)典算法的標(biāo)準(zhǔn)體系。
它自然適應(yīng)幾種設(shè)計技術(shù)的重要變化形式。例如，它能夠涵蓋減治法的三個變種和變治法的三個變種。
進行效率分析時，新的分類法與分析方法更適合(參見附錄B)。
設(shè)計技術(shù)作為問題求解的一般性策略
本書主要是將算法設(shè)計技術(shù)應(yīng)用于計算機科學(xué)的經(jīng)典問題。唯一的創(chuàng)新是加入了一些關(guān)于數(shù)值算法的內(nèi)容，這些內(nèi)容涵蓋在同一個通用框架內(nèi)。但是，這些設(shè)計技術(shù)可以用作通用問題求解工具，其應(yīng)用并不限于傳統(tǒng)的計算和數(shù)學(xué)問題。有兩個因素使這一點顯得特別重要。首先，越來越多的計算應(yīng)用超越了傳統(tǒng)領(lǐng)域，而且有理由相信這種趨勢在未來會進一步加強。其次，培養(yǎng)學(xué)生解決問題的能力被認為是大學(xué)教育的一個主要目標(biāo)。在計算機科學(xué)課程體系中安排一門算法設(shè)計與分析課程是非常合適的，因為它可以教會學(xué)生如何應(yīng)用一些特定的策略來解決問題。
我并不是說要把算法設(shè)計與分析課程變成一門常規(guī)性的問題求解課程。但我真心覺得不宜錯過研究算法設(shè)計與分析所帶來的獨特機會�；�于此，我在本書中加入了謎題和謎題風(fēng)格類游戲的應(yīng)用。雖然在算法教學(xué)中使用謎題不是什么新鮮事，但本書力求以系統(tǒng)化的方式通過幾個遠遠高于標(biāo)準(zhǔn)的例子來做到這一點。
如何使用本書
我的目標(biāo)是寫一本既不泛泛而談但又可供學(xué)生獨立閱讀的教材。為了實現(xiàn)這個目標(biāo)，本書做了如下努力。
根據(jù)喬治福賽斯的觀點(參見之前的引文)，我試圖著重強調(diào)隱藏于算法設(shè)計和分析背后的主要思想。在選擇特定的算法來闡述這些思想的時候，我并不傾向于涉及大量的算法，而是選擇那些最能揭示其基本設(shè)計技術(shù)或分析方法的算法。值得慶幸的是，大多數(shù)經(jīng)典算法都滿足這個要求。
第2章主要分析算法的效率，該章有意區(qū)分了用于分析非遞歸算法的方法和通常用于分析遞歸算法的方法。這一章還花了一些篇幅來介紹算法經(jīng)驗分析和算法可視化。
書中以系統(tǒng)化的方式穿插了一些面向讀者的提問，其中有些問題是我們精心設(shè)計的，而且答案緊隨其后，其目的是引起讀者的注意或引發(fā)疑問。其余問題的用意是防止讀者走馬觀花而無法充分理解本書的內(nèi)容。
每章結(jié)尾處都會對當(dāng)前這一章中最重要的概念和結(jié)論做一個總結(jié)。
本書包含600多道習(xí)題。有些習(xí)題供大家練習(xí)用，另外一些則是想要指出書中正文部分所涉及內(nèi)容的重要意義，或是想要介紹書中沒有涉及的一些算法。有一些習(xí)題利用了網(wǎng)上的資源。較難的習(xí)題數(shù)量不多，在教參中用一種特殊的記號標(biāo)注出來(有的學(xué)生可能沒有勇氣做那些有難度標(biāo)注的習(xí)題，所以本書沒有為習(xí)題標(biāo)注難度)。謎題類的習(xí)題用一種特殊的圖標(biāo)做標(biāo)注。
本書全部習(xí)題都附有提示。除了編程練習(xí)，習(xí)題的詳細解法都能在教師資源中找到。請發(fā)送郵件到coo@netease.com，申請教師相關(guān)資源(也可聯(lián)系培生的當(dāng)?shù)劁N售代表，或者訪問www.pearsonhighered.com/irc)。
第3版的變化
第3版有若干變化，其中最重要的變化是介紹減治法和分治法的先后順序。第3版先介紹減治法，后介紹分治法，這樣做可以帶來以下優(yōu)勢。
相比分治法，減治法更簡單。
相比分治法，減治法能解決的問題更多。
新的編排順序便于先介紹插入排序，后介紹合并排序和快速排序。
數(shù)組劃分的概念通過選擇問題引入，這次利用Lomuto算法的單向掃描來實現(xiàn)，而將Hoare劃分方法的雙向掃描留到后文與快速排序一并介紹。
折半查找歸入介紹減常量算法的章節(jié)。
另一個重要變化是重新編排了第8章關(guān)于動態(tài)規(guī)劃的內(nèi)容，具體是指導(dǎo)述部分的內(nèi)容是全新的。在前兩版中用計算二項式系數(shù)的例子來引入動態(tài)規(guī)劃這一重要技術(shù)，但第3版介紹了三個基礎(chǔ)性示例，效果更好一些；8.1節(jié)的習(xí)題是全新的，包括前兩版中沒有涉及的一些流行應(yīng)用；第8章其他小節(jié)的順序有調(diào)整，以便達到由淺入深、循序漸進的效果。
此外，還有其他一些變化。增加了不少與本書所述算法相關(guān)的應(yīng)用。遍歷圖算法不再隨減治法介紹，而是納入蠻力算法和窮舉查找的范疇，因為我認為這樣更合理。在介紹生成組合對象的算法時，新增了格雷碼算法。對求解最近對問題的分治法有更深入的探討。改進的內(nèi)容包括算法可視化和求解旅行商問題的近似算法，當(dāng)然參考文獻也有相應(yīng)的更新。
第3版大約新增70道習(xí)題，涉及算法謎題和常見的算法面試題。
先修課程
本書假定讀者已經(jīng)學(xué)過離散數(shù)學(xué)的標(biāo)準(zhǔn)課程和一門基礎(chǔ)性的編程課程。有了這樣的知識背景，讀者應(yīng)該能夠掌握本書的內(nèi)容而不會遇到太大的困難。盡管如此，1.4節(jié)、附錄A和附錄B仍然對基本的數(shù)據(jù)結(jié)構(gòu)以及肯定會用到的求和公式與遞推關(guān)系進行復(fù)習(xí)和回顧。只有3個小節(jié)(2.2節(jié)、11.4節(jié)和12.4節(jié))會用到一些簡單的微積分知識，如果讀者缺少必要的微積分知識，完全可以跳過這3個涉及微積分的小節(jié)，這樣做并不妨礙大家對本書其余部分的理解。
課程進度安排
如果打算開設(shè)一門基礎(chǔ)課來聚焦于算法設(shè)計技術(shù)，講解算法設(shè)計和分析理論，可以采用本書作為教材。但要想在一個學(xué)期內(nèi)完成該課程，本書的內(nèi)容可能就太豐富了。大體上來說，跳過第3章到第12章的部分內(nèi)容不會影響讀者對后面部分的理解。本書的任何一個部分都可以安排學(xué)生自學(xué)。尤其是2.6節(jié)和2.7節(jié)，它們分別介紹經(jīng)驗分析和算法可視化，這兩個小節(jié)可以結(jié)合課后練習(xí)一起布置給學(xué)生，讓他們課后完成。
以下教學(xué)計劃用于一個學(xué)期的課程，按照40課時的全日制教學(xué)計劃來設(shè)計。
課次 主題 小節(jié)
1 課程簡介 1.1～1.3
2，3 分析框架；常用符號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 減一算法：插入排序、拓撲排序 4.1，4.2
12 折半查找和其他減常量算法 4.4
13 減變量算法 4.5
14～15 分治法：合并排序、快速排序 5.1～5.2
16 其他分治法示例 5.3、5.4或5.5
17～19 實例化簡：預(yù)排序、高斯消去法、平衡查找樹 6.1～6.3
20 改進性能：堆和堆排序或者霍納法則和二進制冪 6.4或6.5
21 問題化簡 6.6
22～24 時空權(quán)衡：串匹配、散列法、B樹 7.2～7.4
25～27 動態(tài)規(guī)劃算法 8.1～8.4(選學(xué)3節(jié))
28～30 貪婪算法：Prim算法、Kruskal算法、Dijkstra算法、哈夫曼算法 9.1～9.4
31～33 迭代改進算法 10.1～10.4(選學(xué)3節(jié))
34 下界的參數(shù) 11.1
35 決策樹 11.2
36 P、NP和NP完全問題 11.3
37 數(shù)值算法 11.4( 12.4)
38 回溯法 12.1
39 分支定界法 12.2
40 NP困難問題的近似算法 12.3
致謝
我要向本書的審閱人員表達衷心的感謝，還要感謝本書前面兩個版本的許多讀者，他們提供了許多寶貴的意見和建議來幫助改進和完善本書。本書第3版尤其得益于下列審閱人員：芝加哥洛約拉大學(xué)的Andrew Harrington、圣文德大學(xué)的David Levine、加州大學(xué)河濱分校的Stefano Lombardi、賓州曼斯菲爾德大學(xué)的Daniel McKee、弗吉尼亞州立聯(lián)邦大學(xué)的Susan Brilliant、菩及海灣大學(xué)的David Akers以及兩名匿名評審。
我要感謝培生出版社為本書付出不懈努力的所有工作人員和相關(guān)人員。尤其要感謝本書編輯Matt Goldstein、編務(wù)助理Chelsea Bell、市場經(jīng)理Yez Alayan和產(chǎn)品總監(jiān)Kayla Smith-Tarbox。我還要感謝Richard Camp為本書審稿，感謝Windfall Software的Paul Anagnostopoulos和Jacqui Scarlott為本書排版并提供項目管理支持，感謝MaryEllen Oliver擔(dān)任本書校對。
最后，我要感謝我的兩位家人。相比自己寫書，另一半天天忙著寫書更讓人崩潰，我的妻子Maria包容我多年并任勞任怨地幫助我完成書中400多個公式或插圖以及教師手冊。女兒Miriam是我多年的英語老師，她不但閱讀了本書大部分內(nèi)容，還幫著我為每章找到了恰如其分的名人名言。

阿納尼樂維汀(Anany Levitin)