編輯推薦

　　（1）全麵介紹算法設計思想以及算法分析原理。

　　（2）結構完整，內容從易到難，包含豐富實例與習題。

　　（3）對所涉及算法均提供C++或僞代碼。

內容簡介

　　本書全麵介紹算法設計思想以及算法分析原理。全書共分為四個部分：第一部分是基礎知識，包含第1章與第2章，主要介紹算法的基本概念、算法復雜度分析的基本方法、隨機算法以及理解本書所需掌握的數據結構知識等；第二部分包含第3～9章，介紹各種算法設計思想，包括分治策略、貪心策略、動態規劃、搜索與遍曆、迴溯、分支定界、代數方法等；第三部分包含第10～12章，介紹算法復雜度理論知識，包括下界定理、NP難和NP完全問題以及近似算法等；最後一部分是並行算法，包括第13～15章，介紹PRAM算法、網格算法以及超立方算法。 本書結構完整，內容從易到難，包含豐富實例與習題，對所涉及算法均提供C++或僞代碼，不僅可作為計算機專業本科或研究生的算法課程教材，也可作為算法愛好者的自學參考書。

內頁插圖

目錄

第1章　導論

1.1　什麼是算法

1.2　算法規範

1.2.1　導論

1.2.2　遞歸算法

1.3　性能分析

1.3.1　空間復雜度

1.3.2　時間復雜度

1.3.3　平攤復雜度

1.3.4　漸進符號（O，□，□）

1.3.5　實際復雜度

1.3.6　性能測量

1.4　概率算法

1.4.1　概率論基礎

1.4.2　隨機算法：正規描述

1.4.3　確認重復元素

1.4.4　素數測試

1.4.5　優缺點

1.5　參考文獻及閱讀

第2章　數據結構基礎

2.1　棧與隊列

2.2　樹

2.2.1　術語

2.2.2　二叉樹

2.3　字典

2.3.1　二叉搜索樹

2.4　優先隊列

2.4.1　堆

2.4.2　堆排序

2.5　集閤與不相交集閤的並集

2.5.1　導論

2.5.2　求並集及查找操作

2.6　圖

2.6.1　導論

2.6.2　定義

2.6.3　圖的錶示

2.7　參考文獻及閱讀

第3章　分治策略

3.1　一般方法

3.2　殘缺棋盤

3.3　二分搜索

3.4　找最大值和最小值

3.5　閤並排序

3.6　快速排序

3.6.1　性能測量

3.6.2　隨機排序算法

3.7　選擇

3.7.1　最差情況下的最優算法

3.7.2　Select2的實現

3.8　矩陣相乘

3.9　凸包

3.9.1　幾種幾何基本

3.9.2　QuickHull算法

3.9.3　Graham掃描

3.9.4　O(nlogn)的分治算法

3.10　參考文獻及閱讀

3.11　附加習題

第4章　貪心法

4.1　一般方法

4.2　集裝箱裝船

4.3　背包問題

4.4　樹節點分裂

4.5　有期限的工作序列化

4.6　最小生成樹

4.6.1　Prim算法

4.6.2　Kruskal算法

4.6.3　最優的隨機算法（*）

4.7　磁帶最優存儲

4.8　最優閤並模式

4.9　單源最短路徑

4.10　參考文獻及閱讀

4.11　附加習題

第5章　動態規劃

5.1　一般方法

……

第6章　基本遍曆及搜索技術

第7章　迴溯

第8章　分支定界

第9章　代數問題

第10章　下界理論

第11章　難及完全問題

第12章　近似算法

第13章　PRAM算法

第14章　網格算法

第15章　超立方算法

前言/序言

　　如果我們預挑齣計算機科學中那些影響長久的貢獻，算法（algorithm）一定位列其中。自從人類發明瞭可以執行基本數學運算的機器，什麼是可以計算的以及如何計算就成為人們一直研究的課題。伴隨此項研究，人們發現瞭大量的重要算法以及設計方法。算法成為計算機科學領域中的一項重要組成部分。本書的目的就是對有關算法的內容精心地組織，從而使得使用本書的同學以及實踐者可以設計和分析全新的算法。

　　一本包含所有已發明的算法的書將會異常冗長。傳統的算法書通常隻對很少的幾個問題領域有深入的闡述。對於每個問題，通常會給齣並分析效率最高的算法。這樣的做法有一個主要缺點。盡管同學們瞭解瞭很多很快的算法並且也掌握瞭分析算法的工具，但還是對如何設計一個好的算法信心不足。

　　這裏所欠缺的就是沒有強調設計（design）技術。設計方麵的知識一定可以幫助創造好的算法，沒有分析工具則無法判斷算法的優劣。這樣設計為主分析為輔的關係就自然地延伸為有效的講授之道：我們將圍繞基本的算法設計策略來組織本書。基本的設計策略是相對比較少的。並且大部分讀者想要學習的算法可以劃分到這些分類中；例如歸並排序和快速排序是分治策略的例子，而Kruskal的最小生成樹算法和Dijkstra的單源最短路徑算法是貪心策略的例子。理解這些策略是掌握設計技能的重要的第一步。

　　盡管我們深切地認為強調設計以及分析是組織算法學習的正確之路，這裏還是要給齣一些注意事項。首先，我們並沒有包括所有的設計原理。例如綫性規劃是最成功的技術之一，由於它往往由單獨的課程所講述從而沒有包含到本書中。其次，讀者不應該死闆地學習算法設計，認為每個算法都是由一種技術得到的。事實並不是如此。

　　本書的主要篇幅，第3～9章，描述瞭不同的設計策略。每種策略首先描述一個大概。通常給齣一個“程序抽象”來描述采用該策略所形成的計算模式的大綱。接著給齣一係列的例子來講述該策略的復雜以及變化。這些例子往往是按照由易到難的次序安排。其復雜的程度可以在不同的方麵升高。我們通常先給齣一個非常容易理解的例子，所使用的數據結構也僅僅為一維的數組。對這個例子，所用設計策略顯而易見可以得到正確的解法。後麵的例子可能需要證明基於該設計技術的算法是正確的。也可能是需要更加復雜的數據結構（例如樹或者圖），並且分析更加復雜。這樣組織的主要目的是強調組成和分析算法的藝術。另外還希望能讓讀者體會好的程序結構以及算法正確性的證明。

　　第1～12章中的算法都是用C++或者僞C++代碼給齣。很多是可以直接運行並且已經經過測試的。選擇C++是因為它是麵嚮對象的程序語言。C++在計算機業界被廣泛接受還有其他的很多理由。選擇這種程序語言並不是說不熟悉C++的讀者就不能用這本書。因為本書中大部分的算法都是比較短的，用來描述這些算法的代碼也足夠簡單可以被廣大讀者所理解。第13～15章講述並行計算。並行計算是一個飛速發展的領域，沒有一個被廣泛接受的模型或者程序語言。因此，我們選擇用僞代碼來描述這些算法。第1～12章中也有些簡單的算法是用僞代碼描述的。這是因為我們認為這些算法的核心思想用僞代碼描述更加清晰。如何將這些僞代碼轉換為C++代碼將作為練習留給讀者。

　　另外本書的一大特色是廣泛地討論瞭隨機算法。第13～15章中的很多算法是隨機的。其他章節中也包含瞭一些隨機算法。一門學季製的並行算法導論課程可以包含第13～15章，以及其他少量的補充內容。

　　我們也標齣瞭一些內容（用*號）是適用於高級課程的。這本書的內容可以作為本科高年級學生或者研究生的一門學期製課程，或者兩門學季製的課程。它需要學生具備高級語言的編程能力，其餘的內容都自完備的。實踐上，一門數據結構課也是有幫助的，這樣學生具備更成熟的編程能力。如果是學季製的學校，第一個學季可以講授一些基本的設計技術，例如第3章～第9章中的分治、貪心、動態規劃、搜索和遍曆、迴溯、分治定界以及代數方法（見錶Ⅰ）。第二個學季可以講授第10～15章：下界定理、 D_Dd__________ǒe??_____________

　　如果課程是一個學期的，並且學生之前沒有接觸過數據結構和大O錶示，那麼第1～7章、第11章以及第13章的內容比較閤適（見錶Ⅲ）。

　　如果進度更加緊湊一些可以包含第1～7章、第11章、第13章以及第14章的內容（見錶Ⅳ）。

　　如果學生已經掌握瞭數據結構和大O錶示，可以由第3～11章，以及第13～15章構成一門高級課程（見錶Ⅴ）。

　　每章的最後給齣瞭大量的習題可以作為課程作業。我們發現最受歡迎並且最有啓發性的作業是讓學生在同一個數據集上運行兩個算法並且比較兩個算法的運行時間。本書的絕大多數算法都有實現的細節，供學生們使用。將這些C++程序轉換為其他語言的程序也不睏難。那麼剩餘的就是構造閤適的數據集以及編寫一個main函數來完成上述的運行記時。記時的結果應該與算法的時間復雜度漸進分析的結論相一緻。這項任務並不簡單，是有教育意義並且很有趣的。最重要的是它強調瞭一個往往被人們忽視的方麵，也就是算法在實用過程中還有實踐性的一麵。

　　在這個新版中，我們還加入一些新的例子以及習題，加強瞭平攤復雜度，更新瞭每章最後的參考文獻以及閱讀。

　　緻謝

　　我們要感謝Martin J. Biernat、Jeff Jenness、Saleem Khan、Ming-Yang Kao、Douglas M. Compbell以及Stephen P. Leach的意見和建議。我們要感謝佛羅裏達大學的同學指齣瞭較早版本中的錯誤。我們還要感謝Teo Gonzalez、Danny Krizanc以及David Wei仔細閱讀瞭部分章節。

　　Ellis Horowitz

　　Sartaj Sahni

　　Sanguthevar Rajasekaran

很快

還沒看

還沒看

書還是不錯的！就是略貴！！！！！！！

65353565535537575735.35735

還沒看

65353565535537575735.35735

相當有用的一本書,對學算法很有幫助

相當有用的一本書,對學算法很有幫助