算法導(dǎo)論（原書(shū)第3版）/計(jì)算機(jī)科學(xué)叢書(shū)

[美] Thomas H.Cormen，[美] Charles E.Leiserson，[美] Ronald L.Rivest，[美] Clifford Stein 著，殷建平，徐云，王剛 等 譯

• 出版社： 機(jī)械工業(yè)出版社
• ISBN：9787111407010
• 版次：3
• 商品編碼：11144230
• 品牌：機(jī)工出版
• 包裝：平裝
• 叢書(shū)名： 計(jì)算機(jī)科學(xué)叢書(shū)
• 外文名稱(chēng)：Introduction to Algorithms, third edition
• 開(kāi)本：16開(kāi)
• 出版時(shí)間：2012-12-01
• 用紙：膠版紙
• 頁(yè)數(shù)：796
• 正文語(yǔ)種：中文

點(diǎn)此購(gòu)買(mǎi)

編輯推薦

　　MIT四大名師聯(lián)手鑄就，影響全球千萬(wàn)程序員的“算法shengjing”！國(guó)內(nèi)外千余所高校采用！

內(nèi)容簡(jiǎn)介

　　在有關(guān)算法的書(shū)中，有一些敘述非常嚴(yán)謹(jǐn)，但不夠全面；另一些涉及了大量的題材，但又缺乏嚴(yán)謹(jǐn)性?！端惴▽?dǎo)論（原書(shū)第3版）/計(jì)算機(jī)科學(xué)叢書(shū)》將嚴(yán)謹(jǐn)性和全面性融為一體，深入討論各類(lèi)算法，并著力使這些算法的設(shè)計(jì)和分析能為各個(gè)層次的讀者接受。全書(shū)各章自成體系，可以作為獨(dú)立的學(xué)習(xí)單元；算法以英語(yǔ)和偽代碼的形式描述，具備初步程序設(shè)計(jì)經(jīng)驗(yàn)的人就能看懂；說(shuō)明和解釋力求淺顯易懂，不失深度和數(shù)學(xué)嚴(yán)謹(jǐn)性。

　　《算法導(dǎo)論（原書(shū)第3版）/計(jì)算機(jī)科學(xué)叢書(shū)》全書(shū)選材經(jīng)典、內(nèi)容豐富、結(jié)構(gòu)合理、邏輯清晰，對(duì)本科生的數(shù)據(jù)結(jié)構(gòu)課程和研究生的算法課程都是非常實(shí)用的教材，在IT專(zhuān)業(yè)人員的職業(yè)生涯中，《算法導(dǎo)論（原書(shū)第3版）/計(jì)算機(jī)科學(xué)叢書(shū)》也是一本案頭必備的參考書(shū)或工程實(shí)踐手冊(cè)。

　　第3版的主要變化：

　　·新增了van Emde Boas樹(shù)和多線程算法，并且將矩陣基礎(chǔ)移至附錄。

　　·修訂了遞歸式（現(xiàn)在稱(chēng)為“分治策略”）那一章的內(nèi)容，更廣泛地覆蓋分治法。

　　·移除兩章很少講授的內(nèi)容：二項(xiàng)堆和排序網(wǎng)絡(luò)。

　　·修訂了動(dòng)態(tài)規(guī)劃和貪心算法相關(guān)內(nèi)容。

　　·流網(wǎng)絡(luò)相關(guān)材料現(xiàn)在基于邊上的全部流。

　　·由于關(guān)于矩陣基礎(chǔ)和Strassen算法的材料移到了其他章，矩陣運(yùn)算這一章的內(nèi)容所占篇幅更小。

　　·修改了對(duì)Knuth-Morris-Pratt字符串匹配算法的討論。

　　·新增100道練習(xí)和28道思考題，還更新并補(bǔ)充了參考文獻(xiàn)。

作者簡(jiǎn)介

　　Thomas H. Cormen （托馬斯·科爾曼），達(dá)特茅斯學(xué)院計(jì)算機(jī)科學(xué)系教授、系主任。目前的研究興趣包括：算法工程、并行計(jì)算、具有高延遲的加速計(jì)算。他分別于1993年、1986年獲得麻省理工學(xué)院電子工程和計(jì)算機(jī)科學(xué)博士、碩士學(xué)位，師從Charles E. Leiserson教授。由于他在計(jì)算機(jī)教育領(lǐng)域的突出貢獻(xiàn)，Cormen教授榮獲2009年ACM杰出教員獎(jiǎng)。

　　Charles E. Leiserson（查爾斯·雷瑟爾森），麻省理工學(xué)院計(jì)算機(jī)科學(xué)與電氣工程系教授，Margaret MacVicar Faculty Fellow。他目前主持MIT超級(jí)計(jì)算技術(shù)研究組，并是MIT計(jì)算機(jī)科學(xué)和人工智能實(shí)驗(yàn)室計(jì)算理論研究組的成員。他的研究興趣集中在并行和分布式計(jì)算的理論原理，尤其是與工程現(xiàn)實(shí)相關(guān)的技術(shù)研究。Leiserson教授擁有卡內(nèi)基·梅隆大學(xué)計(jì)算機(jī)科學(xué)博士學(xué)位，還是ACM、IEEE和SIAM的會(huì)士。

　　Ronald L. Rivest （羅納德·李維斯特），現(xiàn)任麻省理工學(xué)院電子工程和計(jì)算機(jī)科學(xué)系安德魯與厄納·維特爾比（Andrew and Erna Viterbi）教授。他是MIT計(jì)算機(jī)科學(xué)和人工智能實(shí)驗(yàn)室的成員，并領(lǐng)導(dǎo)著其中的信息安全和隱私中心。他1977年從斯坦福大學(xué)獲得計(jì)算機(jī)博士學(xué)位，主要從事密碼安全、計(jì)算機(jī)安全算法的研究。他和Adi Shamir和Len Adleman一起發(fā)明了RSA公鑰算法，這個(gè)算法在信息安全中獲得大的突破，這一成果也使他和Shamir、Adleman一起得到2002年ACM圖靈獎(jiǎng)。他現(xiàn)在擔(dān)任國(guó)家密碼學(xué)會(huì)的負(fù)責(zé)人。

　　Clifford Stein（克利福德·斯坦），哥倫比亞大學(xué)計(jì)算機(jī)科學(xué)系和工業(yè)工程與運(yùn)籌學(xué)系教授，他還是工業(yè)工程與運(yùn)籌學(xué)系的系主任。在加入哥倫比亞大學(xué)大學(xué)之前，他在達(dá)特茅斯學(xué)院計(jì)算機(jī)科學(xué)系任教9年。Stein教授擁有MIT碩士和博士學(xué)位。他的研究興趣包括：算法的設(shè)計(jì)與分析，組合優(yōu)化、運(yùn)籌學(xué)、網(wǎng)絡(luò)算法、調(diào)度、算法工程和生物計(jì)算。

精彩書(shū)評(píng)

　　★“鑒于數(shù)據(jù)量的爆炸性增長(zhǎng)，和計(jì)算應(yīng)用的多樣性，現(xiàn)在比以往更需要有效算法。這本書(shū)條理清晰，是一本非常好的算法設(shè)計(jì)與分析方面的導(dǎo)論性書(shū)籍。每章前半部分介紹了講授和學(xué)習(xí)算法的有效方法，后半部分為更專(zhuān)業(yè)的讀者和求知欲強(qiáng)的學(xué)生提供了更引人入勝的資料來(lái)討論這個(gè)迷人領(lǐng)域的各種可能性和挑戰(zhàn)?！?/p>

　　——Shang-Hua Teng（騰尚華），南加州大學(xué)維特比工學(xué)院計(jì)算機(jī)系Seeley G. Mudd 教授

　　★“本書(shū)是算法領(lǐng)域的一部經(jīng)典著作，書(shū)中系統(tǒng)、全面地介紹了現(xiàn)代算法：從較快算法和數(shù)據(jù)結(jié)構(gòu)到用于看似難以解決問(wèn)題的多項(xiàng)式時(shí)間算法；從圖論中的經(jīng)典算法到用于字符匹配、計(jì)算集合和數(shù)論的特殊算法。本書(shū)第3版尤其增加了兩章專(zhuān)門(mén)討論van Emde Boas樹(shù)（有用的數(shù)據(jù)結(jié)構(gòu)之一）和多線程算法（日益重要的一個(gè)主題）?！?/p>

　　——Daniel Spielman，耶魯大學(xué)計(jì)算機(jī)科學(xué)和應(yīng)用數(shù)學(xué)Henry Ford II教授

目錄

精彩書(shū)摘

　　證明 每個(gè)結(jié)點(diǎn)的秩從0開(kāi)始，并且只有執(zhí)行了LINK操作，它才會(huì)增加。因?yàn)樽疃嘤衝—1個(gè)UNION操作，所以同樣最多有n—1個(gè)LINK操作。因?yàn)槊總€(gè)LINK操作或者不改變?nèi)魏蔚闹?，或者將某結(jié)點(diǎn)的秩加1，所以所有的秩最大為n—1。

　　引理21.6提供了一個(gè)關(guān)于結(jié)點(diǎn)秩的較弱的界。事實(shí)上，每個(gè)結(jié)點(diǎn)的秩最大為（lgn）（見(jiàn)練習(xí)21.4—2）。然而，引理21.6的這個(gè)較松的界已足夠滿足我們的要求。

　　時(shí)間界的證明 我們將利用攤還分析中的勢(shì)方法（見(jiàn)17.3節(jié)）來(lái)證明O（ma（n））的時(shí)間界。在進(jìn)行攤還分析時(shí)，為了方便起見(jiàn)，我們假設(shè)不調(diào)用UNION操作，而是調(diào)用LINK操作。也就是說(shuō)，因?yàn)長(zhǎng)INK過(guò)程的參數(shù)是指向兩個(gè)根的指針，故我們獨(dú)立使用相應(yīng)的FIND—SET操作。下面的引理說(shuō)明即使因調(diào)用UNION而導(dǎo)致額外的FIND—SET操作，其漸近運(yùn)行時(shí)間仍然保持不變。

　　……

前言/序言

　　在計(jì)算機(jī)出現(xiàn)之前，就有了算法?，F(xiàn)在有了計(jì)算機(jī)，就需要更多的算法，算法是計(jì)算的核心。

　　本書(shū)提供了對(duì)當(dāng)代計(jì)算機(jī)算法研究的一個(gè)全面、綜合的介紹。書(shū)中給出了多個(gè)算法，并對(duì)它們進(jìn)行了較為深入的分析，使得這些算法的設(shè)計(jì)和分析易于被各個(gè)層次的讀者所理解。我們力求在不犧牲分析的深度和數(shù)學(xué)嚴(yán)密性的前提下，給出深入淺出的說(shuō)明。

　　書(shū)中每一章都給出了一個(gè)算法、一種算法設(shè)計(jì)技術(shù)、一個(gè)應(yīng)用領(lǐng)域或一個(gè)相關(guān)的主題。算法是用英語(yǔ)和一種“偽代碼”來(lái)描述的，任何有一點(diǎn)程序設(shè)計(jì)經(jīng)驗(yàn)的人都能看得懂。書(shū)中給出了244幅圖，說(shuō)明各個(gè)算法的工作過(guò)程。我們強(qiáng)調(diào)將算法的效率作為一種設(shè)計(jì)標(biāo)準(zhǔn)，對(duì)書(shū)中的所有算法，都給出了關(guān)于其運(yùn)行時(shí)間的詳細(xì)分析。

　　本書(shū)主要供本科生和研究生的算法或數(shù)據(jù)結(jié)構(gòu)課程使用。因?yàn)闀?shū)中討論了算法設(shè)計(jì)中的工程問(wèn)題及其數(shù)學(xué)性質(zhì)，所以，本書(shū)也可以供專(zhuān)業(yè)技術(shù)人員自學(xué)之用。

　　本書(shū)是第3版。在這個(gè)版本里，我們對(duì)全書(shū)進(jìn)行了更新，包括新增了若干章、修訂了偽代碼等。

　　致使用本書(shū)的教師

　　本書(shū)的設(shè)計(jì)目標(biāo)是全面、適用于多種用途。它可用于若干課程，從本科生的數(shù)據(jù)結(jié)構(gòu)課程到研究生的算法課程。由于書(shū)中給出的內(nèi)容比較多，只講一學(xué)期一般講不完，因此，教師們應(yīng)該將本書(shū)看成是一種“緩存區(qū)”或“瑞典式自助餐”，從中挑選出能最好地支持自己希望教授的課程的內(nèi)容。

　　教師們會(huì)發(fā)現(xiàn)，要圍繞自己所需的各個(gè)章節(jié)來(lái)組織課程是比較容易的。書(shū)中的各章都是相對(duì)獨(dú)立的，因此，你不必?fù)?dān)心意想不到的或不必要的各章之間的依賴(lài)關(guān)系。每一章都是以節(jié)為單位，內(nèi)容由易到難。如果將本書(shū)用于本科生的課程，可以選用每一章的前面幾節(jié)內(nèi)容；用于研究生的課程中，則可以完整地講授每一章。

　　全書(shū)包含957道練習(xí)和158道思考題。每一節(jié)結(jié)束時(shí)給出練習(xí)，每一章結(jié)束時(shí)給出思考題。練習(xí)一般比較短，用于檢查學(xué)生對(duì)書(shū)中內(nèi)容的基本掌握情況。有一些是簡(jiǎn)單的自查性練習(xí)，有一些則要更充實(shí)，可以作為家庭作業(yè)布置給學(xué)生。每一章后的思考題都是一些敘述較為詳細(xì)的實(shí)例研究，它們常常會(huì)介紹一些新的知識(shí)。一般來(lái)說(shuō)，這些思考題都會(huì)包含幾個(gè)小問(wèn)題，引導(dǎo)學(xué)生逐步得到問(wèn)題的解。

　　鑒于本書(shū)前幾版使用的反饋，我們?cè)诒緯?shū)配套網(wǎng)站上公布了其中一些練習(xí)和思考題的答案（但不是全部）。我們會(huì)定期更新這些答案，因此需要教師每次授課前都到這個(gè)網(wǎng)站上來(lái)查看?！　≡谀切┎惶m合本科生、更適合研究生的章節(jié)和練習(xí)前面，都加上了星號(hào)（）。帶星號(hào)的章節(jié)也不一定就比不帶星號(hào)的更難，但可能要求了解更多的數(shù)學(xué)知識(shí)。類(lèi)似地，帶星號(hào)的練習(xí)可能要求有更好的數(shù)學(xué)背景或創(chuàng)造力。

　　致使用本書(shū)的學(xué)生

　　希望本教材能為學(xué)生們提供關(guān)于算法這一領(lǐng)域的有趣介紹。我們力求使書(shū)中給出的每一個(gè)算法都易于理解和有趣。為了在同學(xué)們遇到不熟悉或比較困難的算法時(shí)提供幫助，我們逐個(gè)步驟地描述每一個(gè)算法。此外，為了便于大家理解書(shū)中對(duì)算法的分析，對(duì)于其中所需的數(shù)學(xué)知識(shí)，我們給出了詳細(xì)的解釋。如果對(duì)某一主題已經(jīng)有所了解，會(huì)發(fā)現(xiàn)根據(jù)書(shū)中各章的編排順序，可以跳過(guò)一些介紹性的小節(jié)，直接閱讀更高級(jí)的內(nèi)容。

　　本書(shū)是一本大部頭著作，讀者所修的課程可能只講授其中的一部分。我們?cè)噲D使它能成為一本現(xiàn)在對(duì)讀者有用的教材，將來(lái)在讀者的職業(yè)生涯中，也能成為一本案頭的數(shù)學(xué)參考書(shū)或工程實(shí)踐手冊(cè)。

　　閱讀本書(shū)需要哪些預(yù)備知識(shí)呢·

　　讀者需要有一些程序設(shè)計(jì)方面的經(jīng)驗(yàn)，尤其需要理解遞歸過(guò)程和簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，如數(shù)組和鏈表。

　　讀者應(yīng)該能較為熟練地利用數(shù)學(xué)歸納法進(jìn)行證明。書(shū)中有一些內(nèi)容要求讀者具備初等微積分方面的知識(shí)。除此之外，本書(shū)的第一部分和第八部分將介紹讀者需要用到的所有數(shù)學(xué)技巧。

　　我們收到讀者的反饋，他們強(qiáng)烈希望提供練習(xí)和思考題的答案，為此，我們?cè)谡旧辖o出了少數(shù)練習(xí)和思考題的答案，讀者可以根據(jù)我們的答案來(lái)檢驗(yàn)自己的解答?！　≈率褂帽緯?shū)的專(zhuān)業(yè)技術(shù)人員

　　本書(shū)涉及的主題非常廣泛，因而是一本很好的算法參考手冊(cè)。因?yàn)槊恳徽露际窍鄬?duì)獨(dú)立的，所以讀者可以重點(diǎn)查閱自己感興趣的主題?！　≡谖覀兯懻摰乃惴ㄖ?，多數(shù)都有著極大的實(shí)用價(jià)值。因此，我們?cè)跁?shū)中涉及了算法實(shí)現(xiàn)方面的考慮和其他工程方面的問(wèn)題。對(duì)于那些為數(shù)不多的、主要具有理論研究?jī)r(jià)值的算法，通常還給出其實(shí)用的替代算法?！　∪绻Ｍ麑?shí)現(xiàn)這些算法中的任何一個(gè)，你會(huì)發(fā)現(xiàn)將書(shū)中的偽代碼翻譯成你熟悉的某種程序設(shè)計(jì)語(yǔ)言是一件相當(dāng)直接的事。偽代碼被設(shè)計(jì)成能夠清晰、簡(jiǎn)明地描述每一個(gè)算法。因此，我們不考慮錯(cuò)誤處理和其他需要對(duì)讀者所用編程環(huán)境有特定假設(shè)的軟件工程問(wèn)題。我們力求簡(jiǎn)單而直接地給出每一個(gè)算法，而不會(huì)讓某種特定程序設(shè)計(jì)語(yǔ)言的特殊性掩蓋算法的本質(zhì)內(nèi)容。

　　如果你是在課堂外使用本書(shū)，那么可能無(wú)法從教師那里得到答案來(lái)驗(yàn)證自己的解答，因此，我們?cè)诰W(wǎng)站上給出了部分練習(xí)和思考題的答案，讀者可以免費(fèi)下載參考。

　　致我們的同事

　　我們?cè)诒緯?shū)中給出了詳盡的參考文獻(xiàn)。每一章在結(jié)束時(shí)都給出了“本章注記”，介紹一些歷史性的細(xì)節(jié)和參考文獻(xiàn)。但是，各章的注記并沒(méi)有提供整個(gè)算法領(lǐng)域的全部參考文獻(xiàn)。有一點(diǎn)可能是讓人難以置信的，就是在本書(shū)這樣一本大部頭中，由于篇幅的原因，很多有趣的算法都沒(méi)能包括進(jìn)來(lái)。

　　盡管學(xué)生們發(fā)來(lái)了大量的請(qǐng)求，希望我們提供思考題和練習(xí)的解答，但我們還是決定基本上不提供思考題和練習(xí)的參考答案（少數(shù)除外），以打消學(xué)生們?cè)噲D查閱答案，而不是自己動(dòng)手得出答案的念頭。

　　第3版中所做的修改

　　在本書(shū)的第2版和第3版之間有哪些變化呢·這兩版之間的變化量和第2版與第1版之間的變化量相當(dāng)，正如在第2版的變化中所說(shuō)，這些變化可以說(shuō)不太大，也可以說(shuō)很大，具體要看讀者怎么看待這些變化了。

　　快速地瀏覽一遍目錄，你就會(huì)發(fā)現(xiàn)，第2版中的多數(shù)章節(jié)在第3版中都出現(xiàn)了。在第3版中，去掉了兩章和一節(jié)的內(nèi)容，新增加了三章以及兩節(jié)的內(nèi)容。如果單從目錄來(lái)判斷第3版中改動(dòng)的范圍，得出的結(jié)論很可能是改動(dòng)不大。

　　我們依然保持前兩版的組織結(jié)構(gòu)，既按照問(wèn)題領(lǐng)域又根據(jù)技術(shù)來(lái)組織章節(jié)內(nèi)容。書(shū)中既包含基于技術(shù)的章，如分治法、動(dòng)態(tài)規(guī)劃、貪心算法、攤還分析、NP完全性和近似算法，也包含關(guān)于排序、動(dòng)態(tài)集的數(shù)據(jù)結(jié)構(gòu)和圖問(wèn)題算法的完整部分。我們發(fā)現(xiàn)雖然讀者需要了解如何應(yīng)用這些技術(shù)來(lái)設(shè)計(jì)和分析算法，但是思考題中很少提示應(yīng)用哪個(gè)技術(shù)來(lái)解決這些問(wèn)題。

　　下面總結(jié)了第3版的主要變化：

　　新增了討論van Emde Boas樹(shù)和多線程算法的章節(jié)，并且將矩陣基礎(chǔ)移至附錄。

　　修訂了遞歸式那一章的內(nèi)容，更廣泛地覆蓋分治法，并且前兩節(jié)介紹了應(yīng)用分治法解決兩個(gè)問(wèn)題。4.2節(jié)介紹了用于矩陣乘法的Strassen算法，關(guān)于矩陣運(yùn)算的內(nèi)容已從本章移除。

　　移除兩章很少講授的內(nèi)容：二項(xiàng)堆和排序網(wǎng)絡(luò)。排序網(wǎng)絡(luò)中的關(guān)鍵思想——0-1原理，在本版的思考題8-7中作為比較交換算法的0-1排序引理進(jìn)行介紹。斐波那契堆的處理不再依賴(lài)二項(xiàng)堆。

　　修訂了動(dòng)態(tài)規(guī)劃和貪心算法相關(guān)內(nèi)容。與第2版中的裝配線調(diào)度問(wèn)題相比，本版用一個(gè)更有趣的問(wèn)題——鋼條切割來(lái)引入動(dòng)態(tài)規(guī)劃。而且，我們比在第2版中更強(qiáng)調(diào)助記性，并且引入子問(wèn)題圖這一概念來(lái)闡釋動(dòng)態(tài)規(guī)劃算法的運(yùn)行時(shí)間。在我們給出的貪心算法例子（活動(dòng)選擇問(wèn)題）中，我們以更直接的方式給出貪心算法?！　∥覀儚亩嫠阉鳂?shù)（包括紅黑樹(shù)）刪除一個(gè)結(jié)點(diǎn)的方式，現(xiàn)在保證實(shí)際所刪除的結(jié)點(diǎn)就是請(qǐng)求刪除的結(jié)點(diǎn)（在前兩版中，有些情況下某個(gè)其他結(jié)點(diǎn)可能被刪除）。用這種新的方式刪除結(jié)點(diǎn)，如果程序的其他部分保持指針指向樹(shù)中的結(jié)點(diǎn)，那么終止時(shí)就不會(huì)錯(cuò)誤地將指針指向已刪去的結(jié)點(diǎn)。

　　流網(wǎng)絡(luò)相關(guān)材料現(xiàn)在基于邊上的全部流。這種方法比前兩版中使用的凈流更直觀。

　　由于關(guān)于矩陣基礎(chǔ)和Strassen算法的材料移到了其他章，矩陣運(yùn)算這一章的內(nèi)容比第2版中所占的篇幅更小。

　　修改了對(duì)Knuth-Morris-Pratt字符串匹配算法的討論。

　　修正了上一版中的一些錯(cuò)誤。在網(wǎng)站上，這些錯(cuò)誤大多數(shù)都已在第2版的勘誤中給出，但是有些沒(méi)有給出。

　　根據(jù)許多讀者的要求，我們改變了書(shū)中偽代碼的語(yǔ)法，現(xiàn)在用“=”表示賦值，用“==”表示檢驗(yàn)相等，正如C、C++、Java和Python所用的。同樣，我們不再使用關(guān)鍵字do和then而是使用“//”作為程序行末尾的注釋符號(hào)。我們現(xiàn)在還使用點(diǎn)標(biāo)記法表明對(duì)象屬性。書(shū)中的偽代碼仍是過(guò)程化的，而不是面向?qū)ο蟮?。換句話說(shuō)，我們只是簡(jiǎn)單地調(diào)用過(guò)程，將對(duì)象作為參數(shù)傳遞，而不是關(guān)于對(duì)象的運(yùn)行方法。

　　新增100道練習(xí)和28道思考題，還更新并補(bǔ)充了參考文獻(xiàn)。

　　最后，我們對(duì)書(shū)中的語(yǔ)句、段落和小節(jié)進(jìn)行了一些調(diào)整，以使本書(shū)條理更清晰。

　　網(wǎng)站

　　讀者可以通過(guò)網(wǎng)站來(lái)獲取補(bǔ)充資料，以及與我們聯(lián)系。這個(gè)網(wǎng)站上給出了已知錯(cuò)誤的清單、部分練習(xí)和思考題的答案等。此外，網(wǎng)站上還告訴讀者如何報(bào)告錯(cuò)誤或者提出建議。

　　第3版致謝

　　我們已經(jīng)與MIT Press合作20多年，建立了很好的合作關(guān)系！感謝Ellen Faran、Bob Prior、Ada Brunstein和Mary Reilly的幫助和支持。

　　在出版第3版時(shí)，我們?cè)谶_(dá)特茅斯學(xué)院計(jì)算機(jī)科學(xué)系、MIT計(jì)算機(jī)科學(xué)與人工智能實(shí)驗(yàn)室、哥倫比亞大學(xué)工業(yè)工程與運(yùn)籌學(xué)系從事教學(xué)和科研工作。感謝這些學(xué)校和同事為我們提供的支持和實(shí)驗(yàn)環(huán)境。

　　Julie Sussman，P.P.A擔(dān)當(dāng)本書(shū)第3版的技術(shù)編輯，再次拯救了我們。每次審閱，我們都覺(jué)得已經(jīng)消除了錯(cuò)誤，但是Julie還是發(fā)現(xiàn)了許多錯(cuò)誤。她還幫我們改進(jìn)了幾處文字表述。如果有技術(shù)編輯名人堂，Julie一定第一輪就可以入選。Julie是非凡的，我們?cè)趺锤兄x都是不夠的。Priya Natarajan也發(fā)現(xiàn)了一些錯(cuò)誤，使得我們可以在將本書(shū)交給出版社前修正這些錯(cuò)誤。書(shū)中的任何錯(cuò)誤（毫無(wú)疑問(wèn)，一定存在一些錯(cuò)誤）都由作者負(fù)責(zé)（或許這些錯(cuò)誤有些是Julie審閱材料后引入的）。

　　對(duì)于van Emde Boas樹(shù)的處理出自于Erik Demaine的筆記，轉(zhuǎn)而也受到Michael Bender的影響。此外，我還將Javed Aslam、Bradley Kuszmaul和Hui Zha的思想也整合到這一版。

　　多線程算法這一章是基于與Harald Prokop一起撰寫(xiě)的筆記，其他在MIT從事Cilk項(xiàng)目的同事也對(duì)本部分內(nèi)容有所貢獻(xiàn)，包括Bradley Kuszmaul和Matteo Frigo。多線程偽代碼的設(shè)計(jì)靈感來(lái)自MIT Cilk擴(kuò)展到C，以及由Cilk Arts的Cilk++擴(kuò)展到C++。

　　我們還要感謝許多第1版和第2版的讀者，他們報(bào)告了所發(fā)現(xiàn)的錯(cuò)誤，或者提出了改進(jìn)本書(shū)的建議。我們修正了全部報(bào)告來(lái)的真實(shí)錯(cuò)誤，并且盡可能多地采納了讀者的建議。我們很高興有這么多的人為本書(shū)做出貢獻(xiàn)，但是很遺憾我們無(wú)法全部列出這些貢獻(xiàn)者。

　　最后，非常感謝我們各自的妻子Nicole Cormen、Wendy Leiserson、Gail Rivest和Rebecca Ivry，還有我們的孩子Ricky、Will、Debby和Katie Leiserson，Alex和Christopher Rivest，以及Molly、Noah和Benjamin Stein。感謝他們?cè)谖覀儗?xiě)作本書(shū)過(guò)程中給予的愛(ài)和支持。正是由于有了來(lái)自家庭的耐心和鼓勵(lì)，本書(shū)的寫(xiě)作工作才得以完成。謹(jǐn)將此書(shū)獻(xiàn)給他們。

　　Thomas H.Cormen，新罕布什爾州黎巴嫩市

　　Charles E.Leiserson，馬薩諸塞州劍橋市

　　Ronald L.Rivest，馬薩諸塞州劍橋市

　　Clifford Stein，紐約州紐約市

　　譯者序

　　我從1994年開(kāi)始每年都為本科生講授《算法設(shè)計(jì)與分析》課程，粗略地統(tǒng)計(jì)一下發(fā)現(xiàn)至今已有5000余名各類(lèi)學(xué)生聽(tīng)過(guò)該課。算法的重要性不言而喻，因?yàn)椴还苄赂拍?、新方法、新理論如何引人注目，信息的表示與處理總是計(jì)算技術(shù)（含軟件、硬件、應(yīng)用、網(wǎng)絡(luò)、安全、智能等）永恒的主題。信息處理的核心是算法，在大數(shù)據(jù)時(shí)代，設(shè)計(jì)高效的算法顯得格外重要。

　　當(dāng)初，為了教好這門(mén)基礎(chǔ)必修課，提高教學(xué)質(zhì)量，我覺(jué)得應(yīng)該從教學(xué)內(nèi)容的改革入手，具體來(lái)說(shuō)，采用的教材應(yīng)該與國(guó)際一流大學(xué)接軌。1997年訪美期間，在Stanford大學(xué)了解到他們采用的教材是Thomas H. Cormen等編著的《Introduction to Algorithms》，于是從Stanford書(shū)店買(mǎi)了一本帶回來(lái)，從第二年開(kāi)始便改用該書(shū)作教材。至今，15年過(guò)去了，我們一直追隨其變遷，從第二版到第三版。教學(xué)實(shí)踐證明它確實(shí)是一本好教材，難怪世界范圍內(nèi)包括MIT、CMU、Stanford、UCB、Cornell、UIUC等國(guó)際國(guó)內(nèi)名校在內(nèi)的1000余所大學(xué)都一直用它作為教材或教學(xué)參考書(shū)，也難怪它印數(shù)巨大且在《高引用計(jì)算機(jī)科學(xué)文獻(xiàn)》（《Most Cited Computer Science Citations》）一覽表中名列前茅。

　　這是一本有1200多頁(yè)的厚書(shū)，教學(xué)內(nèi)容非常豐富，不但涵蓋了典型算法、算法分析、算法設(shè)計(jì)方法和NP完全等內(nèi)容，而且還包括數(shù)據(jù)結(jié)構(gòu)，甚至高級(jí)數(shù)據(jù)結(jié)構(gòu)的介紹。后者可作為國(guó)內(nèi)《數(shù)據(jù)結(jié)構(gòu)》課程的教材或教學(xué)參考資料。在學(xué)時(shí)有限的情況下，要在本科階段教完前者的所有內(nèi)容也是困難的，故要做取舍。好在該書(shū)的各個(gè)章節(jié)相對(duì)獨(dú)立且難度由淺入深，我們的做法是將相對(duì)容易的一般的入門(mén)性內(nèi)容留在本科階段，而將相對(duì)難的專(zhuān)門(mén)的較深入的內(nèi)容并入研究生課程《算法及復(fù)雜性》或《計(jì)算復(fù)雜性》。除本校外，本人就曾多次應(yīng)邀在蘭州大學(xué)、湖南大學(xué)和浙江師范大學(xué)等院校為研究生講授過(guò)這些內(nèi)容。其實(shí)該書(shū)也適合希望增強(qiáng)自身程序設(shè)計(jì)能力和程序評(píng)判能力的廣大應(yīng)用計(jì)算技術(shù)的社會(huì)公眾，特別是參加信息學(xué)奧林匹克競(jìng)賽和ACM程序設(shè)計(jì)競(jìng)賽的選手及其教練員。

　　教學(xué)過(guò)程中我們發(fā)現(xiàn)該書(shū)具有以下特點(diǎn)：

（1）選材與時(shí)俱進(jìn)，具有實(shí)用性且能引起讀者的興趣。該書(shū)中研究的許多問(wèn)題都是當(dāng)前現(xiàn)實(shí)應(yīng)用中的關(guān)鍵技術(shù)問(wèn)題。

（2）采用偽碼描述算法，既簡(jiǎn)潔易懂又便于抓住本質(zhì)，再配上豐富的插圖來(lái)描述和解釋算法的執(zhí)行過(guò)程使得教學(xué)內(nèi)容更加通俗，便于自學(xué)。

（3）對(duì)算法正確性和復(fù)雜性的分析比較全面，既有嚴(yán)密的論證，又有直觀的解釋。

（4）既有結(jié)論性知識(shí)的介紹，也有逐步導(dǎo)出結(jié)論的研究過(guò)程的展示。

（5）豐富的練習(xí)題和思考題使得及時(shí)檢驗(yàn)所學(xué)知識(shí)掌握情況和進(jìn)一步拓展學(xué)習(xí)內(nèi)容成為可能。

　　同時(shí)，我們也注意到：學(xué)生們總是反映看英文版教材速度太慢，所以他們總是想方設(shè)法再找一本中譯版來(lái)閱讀。正是這樣的背景，在第三版的《Introduction to Algorithms》出版后，我們應(yīng)機(jī)械工業(yè)出版社編輯的邀請(qǐng)，啟動(dòng)了長(zhǎng)久的翻譯工程，先后參加翻譯工作的老師有：國(guó)防科學(xué)技術(shù)大學(xué)的殷建平教授（翻譯第1~3章）、中國(guó)科學(xué)技術(shù)大學(xué)的徐云教授（翻譯第10~14章、第18~21章和第27章）、南開(kāi)大學(xué)的王剛教授（翻譯第4章和第15~17章）、南開(kāi)大學(xué)的劉曉光教授（翻譯第6~9章）、南開(kāi)大學(xué)的蘇明副研究員（翻譯第5章和第28~30章）、上海交通大學(xué)的鄒恒明教授（翻譯第22~26章）、哈爾濱工業(yè)大學(xué)的王宏志副教授（翻譯第31~35章和附錄部分）。由于水平有限且工作量巨大，譯文中一定存在許多不足，在此敬請(qǐng)各位同行專(zhuān)家學(xué)者和廣大讀者批評(píng)指正，歡迎大家將發(fā)現(xiàn)的錯(cuò)誤或提出的意見(jiàn)與建議發(fā)送到郵箱。在整個(gè)工程即將完成之際，我們特別要感謝機(jī)械工業(yè)出版社的溫莉芳老師和王春華老師，沒(méi)有你們的信任、耐心和支持整個(gè)翻譯工作不可能完成。

　　殷建平

　　2012年11月于長(zhǎng)沙

點(diǎn)此購(gòu)買(mǎi)