算法導(dǎo)論

前言

前言Introduction to Algorithms，Third Edition在計算機(jī)出現(xiàn)之前，就有了算法?，F(xiàn)在有了計算機(jī)，就需要更多的算法，算法是計算的核心。本書提供了對當(dāng)代計算機(jī)算法研究的一個全面、綜合的介紹。書中給出了多個算法，并對它們進(jìn)行了較為深入的分析，使得這些算法的設(shè)計和分析易于被各個層次的讀者所理解。我們力求在不犧牲分析的深度和數(shù)學(xué)嚴(yán)密性的前提下，給出深入淺出的說明。書中每一章都給出了一個算法、一種算法設(shè)計技術(shù)、一個應(yīng)用領(lǐng)域或一個相關(guān)的主題。算法是用英語和一種“偽代碼”來描述的，任何有一點程序設(shè)計經(jīng)驗的人都能看得懂。書中給出了244幅圖，說明各個算法的工作過程。我們強(qiáng)調(diào)將算法的效率作為一種設(shè)計標(biāo)準(zhǔn)，對書中的所有算法，都給出了關(guān)于其運行時間的詳細(xì)分析。本書主要供本科生和研究生的算法或數(shù)據(jù)結(jié)構(gòu)課程使用。因為書中討論了算法設(shè)計中的工程問題及其數(shù)學(xué)性質(zhì)，所以，本書也可以供專業(yè)技術(shù)人員自學(xué)之用。本書是第3版。在這個版本里，我們對全書進(jìn)行了更新，包括新增了若干章、修訂了偽代碼等。致使用本書的教師本書的設(shè)計目標(biāo)是全面、適用于多種用途。它可用于若干課程，從本科生的數(shù)據(jù)結(jié)構(gòu)課程到研究生的算法課程。由于書中給出的內(nèi)容比較多，只講一學(xué)期一般講不完，因此，教師們應(yīng)該將本書看成是一種“緩存區(qū)”或“瑞典式自助餐”，從中挑選出能最好地支持自己希望教授的課程的內(nèi)容。教師們會發(fā)現(xiàn)，要圍繞自己所需的各個章節(jié)來組織課程是比較容易的。書中的各章都是相對獨立的，因此，你不必?fù)?dān)心意想不到的或不必要的各章之間的依賴關(guān)系。每一章都是以節(jié)為單位，內(nèi)容由易到難。如果將本書用于本科生的課程，可以選用每一章的前面幾節(jié)內(nèi)容；用于研究生的課程中，則可以完整地講授每一章。全書包含957道練習(xí)和158道思考題。每一節(jié)結(jié)束時給出練習(xí)，每一章結(jié)束時給出思考題。練習(xí)一般比較短，用于檢查學(xué)生對書中內(nèi)容的基本掌握情況。有一些是簡單的自查性練習(xí)，有一些則要更充實，可以作為家庭作業(yè)布置給學(xué)生。每一章后的思考題都是一些敘述較為詳細(xì)的實例研究，它們常常會介紹一些新的知識。一般來說，這些思考題都會包含幾個小問題，引導(dǎo)學(xué)生逐步得到問題的解。鑒于本書前幾版使用的反饋，我們在本書配套網(wǎng)站上公布了其中一些練習(xí)和思考題的答案（但不是全部），網(wǎng)址為http://mitpress.mit.edu/algorithms/。我們會定期更新這些答案，因此需要教師每次授課前都到這個網(wǎng)站上來查看。在那些不太適合本科生、更適合研究生的章節(jié)和練習(xí)前面，都加上了星號()。帶星號的章節(jié)也不一定就比不帶星號的更難，但可能要求了解更多的數(shù)學(xué)知識。類似地，帶星號的練習(xí)可能要求有更好的數(shù)學(xué)背景或創(chuàng)造力。致使用本書的學(xué)生希望本教材能為學(xué)生們提供關(guān)于算法這一領(lǐng)域的有趣介紹。我們力求使書中給出的每一個算法都易于理解和有趣。為了在同學(xué)們遇到不熟悉或比較困難的算法時提供幫助，我們逐個步驟地描述每一個算法。此外，為了便于大家理解書中對算法的分析，對于其中所需的數(shù)學(xué)知識，我們給出了詳細(xì)的解釋。如果對某一主題已經(jīng)有所了解，會發(fā)現(xiàn)根據(jù)書中各章的編排順序，可以跳過一些介紹性的小節(jié)，直接閱讀更高級的內(nèi)容。本書是一本大部頭著作，讀者所修的課程可能只講授其中的一部分。我們試圖使它能成為一本現(xiàn)在對讀者有用的教材，將來在讀者的職業(yè)生涯中，也能成為一本案頭的數(shù)學(xué)參考書或工程實踐手冊。閱讀本書需要哪些預(yù)備知識呢?讀者需要有一些程序設(shè)計方面的經(jīng)驗，尤其需要理解遞歸過程和簡單的數(shù)據(jù)結(jié)構(gòu)，如數(shù)組和鏈表。  讀者應(yīng)該能較為熟練地利用數(shù)學(xué)歸納法進(jìn)行證明。書中有一些內(nèi)容要求讀者具備初等微積分方面的知識。除此之外，本書的第一部分和第八部分將介紹讀者需要用到的所有數(shù)學(xué)技巧。我們收到讀者的反饋，他們強(qiáng)烈希望提供練習(xí)和思考題的答案，為此，我們在http://mitpress.mit.edu/algorithms/這個網(wǎng)站上給出了少數(shù)練習(xí)和思考題的答案，讀者可以根據(jù)我們的答案來檢驗自己的解答。致使用本書的專業(yè)技術(shù)人員本書涉及的主題非常廣泛，因而是一本很好的算法參考手冊。因為每一章都是相對獨立的，所以讀者可以重點查閱自己感興趣的主題。在我們所討論的算法中，多數(shù)都有著極大的實用價值。因此，我們在書中涉及了算法實現(xiàn)方面的考慮和其他工程方面的問題。對于那些為數(shù)不多的、主要具有理論研究價值的算法，通常還給出其實用的替代算法。如果希望實現(xiàn)這些算法中的任何一個，你會發(fā)現(xiàn)將書中的偽代碼翻譯成你熟悉的某種程序設(shè)計語言是一件相當(dāng)直接的事。偽代碼被設(shè)計成能夠清晰、簡明地描述每一個算法。因此，我們不考慮錯誤處理和其他需要對讀者所用編程環(huán)境有特定假設(shè)的軟件工程問題。我們力求簡單而直接地給出每一個算法，而不會讓某種特定程序設(shè)計語言的特殊性掩蓋算法的本質(zhì)內(nèi)容。如果你是在課堂外使用本書，那么可能無法從教師那里得到答案來驗證自己的解答，因此，我們在http://mitpress.mit.edu/algorithms/這個網(wǎng)站上給出了部分練習(xí)和思考題的答案，讀者可以免費下載參考。致我們的同事我們在本書中給出了詳盡的參考文獻(xiàn)。每一章在結(jié)束時都給出了“本章注記”，介紹一些歷史性的細(xì)節(jié)和參考文獻(xiàn)。但是，各章的注記并沒有提供整個算法領(lǐng)域的全部參考文獻(xiàn)。有一點可能是讓人難以置信的，就是在本書這樣一本大部頭中，由于篇幅的原因，很多有趣的算法都沒能包括進(jìn)來。盡管學(xué)生們發(fā)來了大量的請求，希望我們提供思考題和練習(xí)的解答，但我們還是決定基本上不提供思考題和練習(xí)的參考答案（少數(shù)除外），以打消學(xué)生們試圖查閱答案，而不是自己動手得出答案的念頭。第3版中所做的修改在本書的第2版和第3版之間有哪些變化呢?這兩版之間的變化量和第2版與第1版之間的變化量相當(dāng)，正如在第2版的變化中所說，這些變化可以說不太大，也可以說很大，具體要看讀者怎么看待這些變化了?？焖俚貫g覽一遍目錄，你就會發(fā)現(xiàn)，第2版中的多數(shù)章節(jié)在第3版中都出現(xiàn)了。在第3版中，去掉了兩章和一節(jié)的內(nèi)容，新增加了三章以及兩節(jié)的內(nèi)容。如果單從目錄來判斷第3版中改動的范圍，得出的結(jié)論很可能是改動不大。我們依然保持前兩版的組織結(jié)構(gòu)，既按照問題領(lǐng)域又根據(jù)技術(shù)來組織章節(jié)內(nèi)容。書中既包含基于技術(shù)的章，如分治法、動態(tài)規(guī)劃、貪心算法、攤還分析、NP完全性和近似算法，也包含關(guān)于排序、動態(tài)集的數(shù)據(jù)結(jié)構(gòu)和圖問題算法的完整部分。我們發(fā)現(xiàn)雖然讀者需要了解如何應(yīng)用這些技術(shù)來設(shè)計和分析算法，但是思考題中很少提示應(yīng)用哪個技術(shù)來解決這些問題。下面總結(jié)了第3版的主要變化：新增了討論van Emde Boas樹和多線程算法的章節(jié)，并且將矩陣基礎(chǔ)移至附錄。修訂了遞歸式那一章的內(nèi)容，更廣泛地覆蓋分治法，并且前兩節(jié)介紹了應(yīng)用分治法解決兩個問題。4.2節(jié)介紹了用于矩陣乘法的Strassen算法，關(guān)于矩陣運算的內(nèi)容已從本章移除。移除兩章很少講授的內(nèi)容：二項堆和排序網(wǎng)絡(luò)。排序網(wǎng)絡(luò)中的關(guān)鍵思想——01原理，在本版的思考題87中作為比較交換算法的01排序引理進(jìn)行介紹。斐波那契堆的處理不再依賴二項堆。修訂了動態(tài)規(guī)劃和貪心算法相關(guān)內(nèi)容。與第2版中的裝配線調(diào)度問題相比，本版用一個更有趣的問題——鋼條切割來引入動態(tài)規(guī)劃。而且，我們比在第2版中更強(qiáng)調(diào)助記性，并且引入子問題圖這一概念來闡釋動態(tài)規(guī)劃算法的運行時間。在我們給出的貪心算法例子（活動選擇問題）中，我們以更直接的方式給出貪心算法。我們從二叉搜索樹（包括紅黑樹）刪除一個結(jié)點的方式，現(xiàn)在保證實際所刪除的結(jié)點就是請求刪除的結(jié)點（在前兩版中，有些情況下某個其他結(jié)點可能被刪除）。用這種新的方式刪除結(jié)點，如果程序的其他部分保持指針指向樹中的結(jié)點，那么終止時就不會錯誤地將指針指向已刪去的結(jié)點。流網(wǎng)絡(luò)相關(guān)材料現(xiàn)在基于邊上的全部流。這種方法比前兩版中使用的凈流更直觀。由于關(guān)于矩陣基礎(chǔ)和Strassen算法的材料移到了其他章，矩陣運算這一章的內(nèi)容比第2版中所占的篇幅更小。修改了對KnuthMorrisPratt字符串匹配算法的討論。修正了上一版中的一些錯誤。在網(wǎng)站上，這些錯誤大多數(shù)都已在第2版的勘誤中給出，但是有些沒有給出。根據(jù)許多讀者的要求，我們改變了書中偽代碼的語法，現(xiàn)在用“=”表示賦值，用“==”表示檢驗相等，正如C、C++、Java和Python所用的。同樣，我們不再使用關(guān)鍵字do和then而是使用“//”作為程序行末尾的注釋符號。我們現(xiàn)在還使用點標(biāo)記法表明對象屬性。書中的偽代碼仍是過程化的，而不是面向?qū)ο蟮摹Q句話說，我們只是簡單地調(diào)用過程，將對象作為參數(shù)傳遞，而不是關(guān)于對象的運行方法。新增100道練習(xí)和28道思考題，還更新并補(bǔ)充了參考文獻(xiàn)。最后，我們對書中的語句、段落和小節(jié)進(jìn)行了一些調(diào)整，以使本書條理更清晰。網(wǎng)站讀者可以通過http://mitpress.mit.edu/algorithms/這個網(wǎng)站來獲取補(bǔ)充資料，以及與我們聯(lián)系。這個網(wǎng)站上給出了已知錯誤的清單、部分練習(xí)和思考題的答案等。此外，網(wǎng)站上還告訴讀者如何報告錯誤或者提出建議。第3版致謝我們已經(jīng)與MIT Press合作20多年，建立了很好的合作關(guān)系！感謝Ellen Faran、Bob Prior、Ada Brunstein和Mary Reilly的幫助和支持。在出版第3版時，我們在達(dá)特茅斯學(xué)院計算機(jī)科學(xué)系、MIT計算機(jī)科學(xué)與人工智能實驗室、哥倫比亞大學(xué)工業(yè)工程與運籌學(xué)系從事教學(xué)和科研工作。感謝這些學(xué)校和同事為我們提供的支持和實驗環(huán)境。Julie Sussman，P.P.A擔(dān)當(dāng)本書第3版的技術(shù)編輯，再次拯救了我們。每次審閱，我們都覺得已經(jīng)消除了錯誤，但是Julie還是發(fā)現(xiàn)了許多錯誤。她還幫我們改進(jìn)了幾處文字表述。如果有技術(shù)編輯名人堂，Julie一定第一輪就可以入選。Julie是非凡的，我們怎么感謝都是不夠的。Priya Natarajan也發(fā)現(xiàn)了一些錯誤，使得我們可以在將本書交給出版社前修正這些錯誤。書中的任何錯誤（毫無疑問，一定存在一些錯誤）都由作者負(fù)責(zé)（或許這些錯誤有些是Julie審閱材料后引入的）。對于van Emde Boas樹的處理出自于Erik Demaine的筆記，轉(zhuǎn)而也受到Michael Bender的影響。此外，我還將Javed Aslam、Bradley Kuszmaul和Hui Zha的思想也整合到這一版。多線程算法這一章是基于與Harald Prokop一起撰寫的筆記，其他在MIT從事Cilk項目的同事也對本部分內(nèi)容有所貢獻(xiàn)，包括Bradley Kuszmaul和Matteo Frigo。多線程偽代碼的設(shè)計靈感來自MIT Cilk擴(kuò)展到C，以及由Cilk Arts的Cilk++擴(kuò)展到C++。我們還要感謝許多第1版和第2版的讀者，他們報告了所發(fā)現(xiàn)的錯誤，或者提出了改進(jìn)本書的建議。我們修正了全部報告來的真實錯誤，并且盡可能多地采納了讀者的建議。我們很高興有這么多的人為本書做出貢獻(xiàn)，但是很遺憾我們無法全部列出這些貢獻(xiàn)者。最后，非常感謝我們各自的妻子Nicole Cormen、Wendy Leiserson、Gail Rivest和Rebecca Ivry，還有我們的孩子Ricky、Will、Debby和Katie Leiserson，Alex和Christopher Rivest，以及Molly、Noah和Benjamin Stein。感謝他們在我們寫作本書過程中給予的愛和支持。正是由于有了來自家庭的耐心和鼓勵，本書的寫作工作才得以完成。謹(jǐn)將此書獻(xiàn)給他們。Thomas H.Cormen，新罕布什爾州黎巴嫩市Charles E.Leiserson，馬薩諸塞州劍橋市Ronald L.Rivest，馬薩諸塞州劍橋市Clifford Stein，紐約州紐約市譯者序我從1994年開始每年都為本科生講授《算法設(shè)計與分析》課程，粗略地統(tǒng)計一下發(fā)現(xiàn)至今已有5000余名各類學(xué)生聽過該課。算法的重要性不言而喻，因為不管新概念、新方法、新理論如何引人注目，信息的表示與處理總是計算技術(shù)（含軟件、硬件、應(yīng)用、網(wǎng)絡(luò)、安全、智能等）永恒的主題。信息處理的核心是算法，在大數(shù)據(jù)時代，設(shè)計高效的算法顯得格外重要。當(dāng)初，為了教好這門基礎(chǔ)必修課，提高教學(xué)質(zhì)量，我覺得應(yīng)該從教學(xué)內(nèi)容的改革入手，具體來說，采用的教材應(yīng)該與國際一流大學(xué)接軌。1997年訪美期間，在Stanford大學(xué)了解到他們采用的教材是Thomas H. Cormen等編著的《Introduction to Algorithms》，于是從Stanford書店買了一本帶回來，從第二年開始便改用該書作教材。至今，15年過去了，我們一直追隨其變遷，從第二版到第三版。教學(xué)實踐證明它確實是一本好教材，難怪世界范圍內(nèi)包括MIT、CMU、Stanford、UCB、Cornell、UIUC等國際國內(nèi)名校在內(nèi)的1000余所大學(xué)都一直用它作為教材或教學(xué)參考書，也難怪它印數(shù)巨大且在《高引用計算機(jī)科學(xué)文獻(xiàn)》（《Most Cited Computer Science Citations》）一覽表中名列前茅。這是一本有1200多頁的厚書，教學(xué)內(nèi)容非常豐富，不但涵蓋了典型算法、算法分析、算法設(shè)計方法和NP完全等內(nèi)容，而且還包括數(shù)據(jù)結(jié)構(gòu)，甚至高級數(shù)據(jù)結(jié)構(gòu)的介紹。后者可作為國內(nèi)《數(shù)據(jù)結(jié)構(gòu)》課程的教材或教學(xué)參考資料。在學(xué)時有限的情況下，要在本科階段教完前者的所有內(nèi)容也是困難的，故要做取舍。好在該書的各個章節(jié)相對獨立且難度由淺入深，我們的做法是將相對容易的一般的入門性內(nèi)容留在本科階段，而將相對難的專門的較深入的內(nèi)容并入研究生課程《算法及復(fù)雜性》或《計算復(fù)雜性》。除本校外，本人就曾多次應(yīng)邀在蘭州大學(xué)、湖南大學(xué)和浙江師范大學(xué)等院校為研究生講授過這些內(nèi)容。其實該書也適合希望增強(qiáng)自身程序設(shè)計能力和程序評判能力的廣大應(yīng)用計算技術(shù)的社會公眾，特別是參加信息學(xué)奧林匹克競賽和ACM程序設(shè)計競賽的選手及其教練員。教學(xué)過程中我們發(fā)現(xiàn)該書具有以下特點：（1）選材與時俱進(jìn)，具有實用性且能引起讀者的興趣。該書中研究的許多問題都是當(dāng)前現(xiàn)實應(yīng)用中的關(guān)鍵技術(shù)問題。（2）采用偽碼描述算法，既簡潔易懂又便于抓住本質(zhì)，再配上豐富的插圖來描述和解釋算法的執(zhí)行過程使得教學(xué)內(nèi)容更加通俗，便于自學(xué)。（3）對算法正確性和復(fù)雜性的分析比較全面，既有嚴(yán)密的論證，又有直觀的解釋。（4）既有結(jié)論性知識的介紹，也有逐步導(dǎo)出結(jié)論的研究過程的展示。（5）豐富的練習(xí)題和思考題使得及時檢驗所學(xué)知識掌握情況和進(jìn)一步拓展學(xué)習(xí)內(nèi)容成為可能。同時，我們也注意到：學(xué)生們總是反映看英文版教材速度太慢，所以他們總是想方設(shè)法再找一本中譯版來閱讀。正是這樣的背景，在第三版的《Introduction to Algorithms》出版后，我們應(yīng)機(jī)械工業(yè)出版社編輯的邀請，啟動了長久的翻譯工程，先后參加翻譯工作的老師有：國防科學(xué)技術(shù)大學(xué)的殷建平教授（翻譯第1~3章）、中國科學(xué)技術(shù)大學(xué)的徐云教授（翻譯第10~14章、第18~21章和第27章）、南開大學(xué)的王剛教授（翻譯第4章和第15~17章）、南開大學(xué)的劉曉光教授（翻譯第6~9章）、南開大學(xué)的蘇明副研究員（翻譯第5章和第28~30章）、上海交通大學(xué)的鄒恒明教授（翻譯第22~26章）、哈爾濱工業(yè)大學(xué)的王宏志副教授（翻譯第31~35章和附錄部分）。由于水平有限且工作量巨大，譯文中一定存在許多不足，在此敬請各位同行專家學(xué)者和廣大讀者批評指正，歡迎大家將發(fā)現(xiàn)的錯誤或提出的意見與建議。在整個工程即將完成之際，我們特別要感謝機(jī)械工業(yè)出版社的溫莉芳老師和王春華老師，沒有你們的信任、耐心和支持整個翻譯工作不可能完成。殷建平2012年11月于長沙

內(nèi)容概要

　　在有關(guān)算法的書中，有一些敘述非常嚴(yán)謹(jǐn)，但不夠全面；另一些涉及了大量的題材，但又缺乏嚴(yán)謹(jǐn)性。本書將嚴(yán)謹(jǐn)性和全面性融為一體，深入討論各類算法，并著力使這些算法的設(shè)計和分析能為各個層次的讀者接受。全書各章自成體系，可以作為獨立的學(xué)習(xí)單元；算法以英語和偽代碼的形式描述，具備初步程序設(shè)計經(jīng)驗的人就能看懂；說明和解釋力求淺顯易懂，不失深度和數(shù)學(xué)嚴(yán)謹(jǐn)性。
　　全書選材經(jīng)典、內(nèi)容豐富、結(jié)構(gòu)合理、邏輯清晰，對本科生的數(shù)據(jù)結(jié)構(gòu)課程和研究生的算法課程都是非常實用的教材，在IT專業(yè)人員的職業(yè)生涯中，本書也是一本案頭必備的參考書或工程實踐手冊。
　　第3版的主要變化：
　　·新增了van Emde Boas樹和多線程算法，并且將矩陣基礎(chǔ)移至附錄。
　　·修訂了遞歸式（現(xiàn)在稱為“分治策略”）那一章的內(nèi)容，更廣泛地覆蓋分治法。
　　·移除兩章很少講授的內(nèi)容：二項堆和排序網(wǎng)絡(luò)。
　　·修訂了動態(tài)規(guī)劃和貪心算法相關(guān)內(nèi)容。
　　·流網(wǎng)絡(luò)相關(guān)材料現(xiàn)在基于邊上的全部流。
　　·由于關(guān)于矩陣基礎(chǔ)和Strassen算法的材料移到了其他章，矩陣運算這一章的內(nèi)容所占篇幅更小。
　　·修改了對Knuth-Morris-Pratt字符串匹配算法的討論。
　　·新增100道練習(xí)和28道思考題，還更新并補(bǔ)充了參考文獻(xiàn)。

作者簡介

Thomas H. Cormen
（托馬斯?科爾曼）達(dá)特茅斯學(xué)院計算機(jī)科學(xué)系教授、系主任。目前的研究興趣包括：算法工程、并行計算、具有高延遲的加速計算。他分別于1993年、1986年獲得麻省理工學(xué)院電子工程和計算機(jī)科學(xué)博士、碩士學(xué)位，師從Charles
E. Leiserson教授。由于他在計算機(jī)教育領(lǐng)域的突出貢獻(xiàn)，Cormen教授榮獲2009年ACM杰出教員獎。
 Charles E.
Leiserson（查爾斯?雷瑟爾森）麻省理工學(xué)院計算機(jī)科學(xué)與電氣工程系教授，Margaret MacVicar Faculty
Fellow。他目前主持MIT超級計算技術(shù)研究組，并是MIT計算機(jī)科學(xué)和人工智能實驗室計算理論研究組的成員。他的研究興趣集中在并行和分布式計算的理論原理，尤其是與工程現(xiàn)實相關(guān)的技術(shù)研究。Leiserson教授擁有卡內(nèi)基?梅隆大學(xué)計算機(jī)科學(xué)博士學(xué)位，還是ACM、IEEE和SIAM的會士。
 Ronald L. Rivest
（羅納德?李維斯特）現(xiàn)任麻省理工學(xué)院電子工程和計算機(jī)科學(xué)系安德魯與厄納?維特爾比（Andrew and Erna
Viterbi）教授。他是MIT計算機(jī)科學(xué)和人工智能實驗室的成員，并領(lǐng)導(dǎo)著其中的信息安全和隱私中心。他1977年從斯坦福大學(xué)獲得計算機(jī)博士學(xué)位，主要從事密碼安全、計算機(jī)安全算法的研究。他和Adi
Shamir和Len
Adleman一起發(fā)明了RSA公鑰算法，這個算法在信息安全中獲得最大的突破，這一成果也使他和Shamir、Adleman一起得到2002年ACM圖靈獎。他現(xiàn)在擔(dān)任國家密碼學(xué)會的負(fù)責(zé)人。
 Clifford
Stein（克利福德?斯坦）哥倫比亞大學(xué)計算機(jī)科學(xué)系和工業(yè)工程與運籌學(xué)系教授，他還是工業(yè)工程與運籌學(xué)系的系主任。在加入哥倫比亞大學(xué)大學(xué)之前，他在達(dá)特茅斯學(xué)院計算機(jī)科學(xué)系任教9年。Stein教授擁有MIT碩士和博士學(xué)位。他的研究興趣包括：算法的設(shè)計與分析，組合優(yōu)化、運籌學(xué)、網(wǎng)絡(luò)算法、調(diào)度、算法工程和生物計算。

書籍目錄

Introduction to Algorithms, Third Edition
出版者的話
譯者序
前言
第一部分　基礎(chǔ)知識
第1章　算法在計算中的作用
　1.1　算法
　1.2　作為一種技術(shù)的算法
　思考題
　本章注記
第2章　算法基礎(chǔ)
　2.1　插入排序
　2.2　分析算法
　2.3　設(shè)計算法
　　2.3.1　分治法
　　2.3.2　分析分治算法
　思考題
　本章注記
第3章　函數(shù)的增長
　3.1　漸近記號
　3.2　標(biāo)準(zhǔn)記號與常用函數(shù)
　思考題
　本章注記
第4章　分治策略
　4.1　最大子數(shù)組問題
　4.2　矩陣乘法的Strassen算法
　4.3　用代入法求解遞歸式
　4.4　用遞歸樹方法求解遞歸式
　4.5　用主方法求解遞歸式
　4.6　證明主定理
　　4.6.1　對b的冪證明主定理
　　4.6.2　向下取整和向上取整
　思考題
　本章注記
第5章　概率分析和隨機(jī)算法
　5.1　雇用問題
　5.2　指示器隨機(jī)變量
　5.3　隨機(jī)算法
　?5.4　概率分析和指示器隨機(jī)變量的進(jìn)一步使用
　　5.4.1　生日悖論
　　5.4.2　球與箱子
　　5.4.3　特征序列
　　5.4.4　在線雇用問題
　思考題
　本章注記
第二部分　排序和順序統(tǒng)計量
第6章　堆排序
　6.1　堆
　6.2　維護(hù)堆的性質(zhì)
　6.3　建堆
　6.4　堆排序算法
　6.5　優(yōu)先隊列
　思考題
　本章注記
第7章　快速排序
　7.1　快速排序的描述
　7.2　快速排序的性能
　7.3　快速排序的隨機(jī)化版本
　7.4　快速排序分析
　　7.4.1　最壞情況分析
　　7.4.2　期望運行時間
　思考題
　本章注記
第8章　線性時間排序
　8.1　排序算法的下界
　8.2　計數(shù)排序
　8.3　基數(shù)排序
　8.4　桶排序
　思考題
　本章注記
第9章　中位數(shù)和順序統(tǒng)計量
　9.1　最小值和最大值
　9.2　期望為線性時間的選擇算法
　9.3　最壞情況為線性時間的選擇算法
　思考題
　本章注記
第三部分　數(shù)據(jù)結(jié)構(gòu)
第10章　基本數(shù)據(jù)結(jié)構(gòu)
　10.1　棧和隊列
　10.2　鏈表
　10.3　指針和對象的實現(xiàn)
　10.4　有根樹的表示
　思考題
　本章注記
第11章　散列表
　11.1　直接尋址表
　11.2　散列表
　11.3　散列函數(shù)
　　11.3.1　除法散列法
　　11.3.2　乘法散列法
　　11.3.3　全域散列法
　11.4　開放尋址法
　11.5　完全散列
　思考題
　本章注記
第12章　二叉搜索樹
　12.1　什么是二叉搜索樹
　12.2　查詢二叉搜索樹
　12.3　插入和刪除
　12.4　隨機(jī)構(gòu)建二叉搜索樹
　思考題
　本章注記
第13章　紅黑樹
　13.1　紅黑樹的性質(zhì)
　13.2　旋轉(zhuǎn)
　13.3　插入
　13.4　刪除
　思考題
　本章注記
第14章　數(shù)據(jù)結(jié)構(gòu)的擴(kuò)張
　14.1　動態(tài)順序統(tǒng)計
　14.2　如何擴(kuò)張數(shù)據(jù)結(jié)構(gòu)
　14.3　區(qū)間樹
　思考題
　本章注記
第四部分　高級設(shè)計和分析技術(shù)
第15章　動態(tài)規(guī)劃
　15.1　鋼條切割
　15.2　矩陣鏈乘法
　15.3　動態(tài)規(guī)劃原理
　15.4　最長公共子序列
　15.5　最優(yōu)二叉搜索樹
　思考題
　本章注記
第16章　貪心算法
　16.1　活動選擇問題
　16.2　貪心算法原理
　16.3　赫夫曼編碼
　16.4　擬陣和貪心算法
　16.5　用擬陣求解任務(wù)調(diào)度問題
　思考題
　本章注記
第17章　攤還分析
　17.1　聚合分析
　17.2　核算法
　17.3　勢能法
　17.4　動態(tài)表
　　17.4.1　表擴(kuò)張
　　17.4.2　表擴(kuò)張和收縮
　思考題
　本章注記
第五部分　高級數(shù)據(jù)結(jié)構(gòu)
第18章　B樹
　18.1　B樹的定義
　18.2　B樹上的基本操作
　18.3　從B樹中刪除關(guān)鍵字
　思考題
　本章注記
第19章　斐波那契堆
　19.1　斐波那契堆結(jié)構(gòu)
　19.2　可合并堆操作
　19.3　關(guān)鍵字減值和刪除一個結(jié)點
　19.4　最大度數(shù)的界
　思考題
　本章注記
第20章　van Emde Boas樹
　20.1　基本方法
　20.2　遞歸結(jié)構(gòu)
　　20.2.1　原型van Emde Boas結(jié)構(gòu)
　　20.2.2　原型van Emde Boas結(jié)構(gòu)上的操作
　20.3　van Emde Boas樹及其操作
　　20.3.1　van Emde Boas樹
　　20.3.2　van Emde Boas樹的操作
　思考題
　本章注記
第21章　用于不相交集合的數(shù)據(jù)結(jié)構(gòu)
　21.1　不相交集合的操作
　21.2　不相交集合的鏈表表示
　21.3　不相交集合森林
　*21.4　帶路徑壓縮的按秩合并的分析
　思考題
　本章注記
第六部分　圖算法
第22章　基本的圖算法
　22.1　圖的表示
　22.2　廣度優(yōu)先搜索
　22.3　深度優(yōu)先搜索
　22.4　拓?fù)渑判?br />　22.5　強(qiáng)連通分量
　思考題
　本章注記
第23章　最小生成樹
　23.1　最小生成樹的形成
　23.2　Kruskal算法和Prim算法
　思考題
　本章注記
第24章　單源最短路徑
　24.1　Bellman?Ford算法
　24.2　有向無環(huán)圖中的單源最短路徑問題
　24.3　Dijkstra算法
　24.4　差分約束和最短路徑
　24.5　最短路徑性質(zhì)的證明
　思考題
　本章注記
第25章　所有結(jié)點對的最短路徑問題
　25.1　最短路徑和矩陣乘法
　25.2　Floyd?Warshall算法
　25.3　用于稀疏圖的Johnson算法
　思考題
　本章注記
第26章　最大流
　26.1　流網(wǎng)絡(luò)
　26.2　Ford\Fulkerson方法
　26.3　最大二分匹配
　26.4　推送重貼標(biāo)簽算法
　26.5　前置重貼標(biāo)簽算法
　思考題
　本章注記
第七部分　算法問題選編
第27章　多線程算法
　27.1　動態(tài)多線程基礎(chǔ)
　27.2　多線程矩陣乘法
　27.3　多線程歸并排序
　思考題
　本章注記
第28章　矩陣運算
　28.1　求解線性方程組
　28.2　矩陣求逆
　28.3　對稱正定矩陣和最小二乘逼近
　思考題
　本章注記
第29章　線性規(guī)劃
　29.1　標(biāo)準(zhǔn)型和松弛型
　29.2　將問題表達(dá)為線性規(guī)劃
　29.3　單純形算法
　29.4　對偶性
　29.5　初始基本可行解
　思考題
　本章注記
第30章　多項式與快速傅里葉變換
　30.1　多項式的表示
　30.2　DFT與FFT
　30.3　高效FFT實現(xiàn)
　思考題
　本章注記
第31章　數(shù)論算法
　31.1　基礎(chǔ)數(shù)論概念
　31.2　最大公約數(shù)
　31.3　模運算
　31.4　求解模線性方程
　31.5　中國余數(shù)定理
　31.6　元素的冪
　31.7　RSA公鑰加密系統(tǒng)
　31.8　素數(shù)的測試
　31.9　整數(shù)的因子分解
　思考題
　本章注記
第32章　字符串匹配
　32.1　樸素字符串匹配算法
　32.2　Rabin\Karp算法
　32.3　利用有限自動機(jī)進(jìn)行字符串匹配
　32.4　Knuth?Morris?Pratt算法
　思考題
　本章注記
第33章　計算幾何學(xué)
　33.1　線段的性質(zhì)
　33.2　確定任意一對線段是否相交
　33.3　尋找凸包
　33.4　尋找最近點對
　思考題
　本章注記
第34章　NP完全性
　34.1　多項式時間
　34.2　多項式時間的驗證
　34.3　NP完全性與可歸約性
　34.4　NP完全性的證明
　34.5　NP完全問題
　　34.5.1　團(tuán)問題
　　34.5.2　頂點覆蓋問題
　　34.5.3　哈密頓回路問題
　　34.5.4　旅行商問題
　　34.5.5　子集和問題
　思考題
　本章注記
第35章　近似算法
　35.1　頂點覆蓋問題
　35.2　旅行商問題
　35.2.1　滿足三角不等式的旅行商問題
　35.2.2　一般旅行商問題
　35.3　集合覆蓋問題
　35.4　隨機(jī)化和線性規(guī)劃
　35.5　子集和問題
　思考題
　本章注記
第八部分　附錄：數(shù)學(xué)基礎(chǔ)知識
附錄A　求和
　A.1　求和公式及其性質(zhì)
　A.2　確定求和時間的界
　思考題
　附錄注記
附錄B　集合等離散數(shù)學(xué)內(nèi)容
　B.1　集合
　B.2　關(guān)系
　B.3　函數(shù)
　B.4　圖
　B.5　樹
　　B.5.1　自由樹
　　B.5.2　有根樹和有序樹
　　B.5.3　二叉樹和位置樹
　思考題
　附錄注記
附錄C　計數(shù)與概率
　C.1　計數(shù)
　C.2　概率
C.3　離散隨機(jī)變量
　C.4　幾何分布與二項分布
　*C.5　二項分布的尾部
　思考題
　附錄注記
附錄D　矩陣
　D.1　矩陣與矩陣運算
　D.2　矩陣基本性質(zhì)
　思考題
　附錄注記
參考文獻(xiàn)
索引

媒體關(guān)注與評論

“鑒于數(shù)據(jù)量的爆炸性增長，和計算應(yīng)用的多樣性，現(xiàn)在比以往更需要有效算法。這本書條理清晰，是一本非常好的算法設(shè)計與分析方面的導(dǎo)論性書籍。每章前半部分介紹了講授和學(xué)習(xí)算法的有效方法，后半部分為更專業(yè)的讀者和求知欲強(qiáng)的學(xué)生提供了更引人入勝的資料來討論這個迷人領(lǐng)域的各種可能性和挑戰(zhàn)?！薄猄hang-Hua Teng（騰尚華），南加州大學(xué)維特比工學(xué)院計算機(jī)系Seeley G. Mudd 教授   “本書是算法領(lǐng)域的一部經(jīng)典著作，書中系統(tǒng)、全面地介紹了現(xiàn)代算法：從最快算法和數(shù)據(jù)結(jié)構(gòu)到用于看似難以解決問題的多項式時間算法；從圖論中的經(jīng)典算法到用于字符匹配、計算集合和數(shù)論的特殊算法。本書第3版尤其增加了兩章專門討論van Emde Boas樹（最有用的數(shù)據(jù)結(jié)構(gòu)之一）和多線程算法（日益重要的一個主題）?！薄狣aniel Spielman，耶魯大學(xué)計算機(jī)科學(xué)和應(yīng)用數(shù)學(xué)Henry Ford II教授   “作為一個在算法領(lǐng)域有著近30年教育和研究經(jīng)驗的教育者和研究人員，我可以清楚明白地說這本書是我所見到的該領(lǐng)域最好的教材。它對算法給出了清晰透徹、百科全書式的闡述。我們將繼續(xù)使用這本書的新版作為研究生和本科生的教材和可以信賴的研究參考書?！薄狦abriel Robins，弗吉尼亞大學(xué)工程和應(yīng)用科學(xué)學(xué)院計算機(jī)科學(xué)系教授

編輯推薦

《算法導(dǎo)論(原書第3版)》編輯推薦：全球超過50萬人閱讀的算法圣經(jīng)！算法標(biāo)準(zhǔn)教材，國內(nèi)外1000余所高校采用。國內(nèi)知名高校6位教授歷時3年傾心翻譯！

名人推薦

鑒于數(shù)據(jù)量的爆炸性增長，和計算應(yīng)用的多樣性，現(xiàn)在比以往更需要有效算法。這本書條理清晰，是一本非常好的算法設(shè)計與分析方面的導(dǎo)論性書籍。每章前半部分介紹了講授和學(xué)習(xí)算法的有效方法，后半部分為更專業(yè)的讀者和求知欲強(qiáng)的學(xué)生提供了更引人入勝的資料來討論這個迷人領(lǐng)域的各種可能性和挑戰(zhàn)?！猄hang-Hua Teng（騰尚華），南加州大學(xué)維特比工學(xué)院計算機(jī)系Seeley G. Mudd 教授本書是算法領(lǐng)域的一部經(jīng)典著作，書中系統(tǒng)、全面地介紹了現(xiàn)代算法：從最快算法和數(shù)據(jù)結(jié)構(gòu)到用于看似難以解決問題的多項式時間算法；從圖論中的經(jīng)典算法到用于字符匹配、計算集合和數(shù)論的特殊算法。本書第3版尤其增加了兩章專門討論van Emde Boas樹（最有用的數(shù)據(jù)結(jié)構(gòu)之一）和多線程算法（日益重要的一個主題）?！狣aniel Spielman，耶魯大學(xué)計算機(jī)科學(xué)和應(yīng)用數(shù)學(xué)Henry Ford II教授作為一個在算法領(lǐng)域有著近30年教育和研究經(jīng)驗的教育者和研究人員，我可以清楚明白地說這本書是我所見到的該領(lǐng)域最好的教材。它對算法給出了清晰透徹、百科全書式的闡述。我們將繼續(xù)使用這本書的新版作為研究生和本科生的教材和可以信賴的研究參考書?！狦abriel Robins，弗吉尼亞大學(xué)工程和應(yīng)用科學(xué)學(xué)院計算機(jī)科學(xué)系教授

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    算法導(dǎo)論 PDF格式下載

---