算法概論
出版時間：2009-1 出版社：機(jī)械工業(yè)出版社 作者：Sanjoy Dasgupta,Christos Papadimitriou,Umesh Vazirani 頁數(shù)：376 譯者：錢楓 注,鄒恒明 注
Tag標(biāo)簽：無
前言
《算法概論》的前身是加州大學(xué)伯克利分校和加州大學(xué)圣迭戈分校本科生的算法課講義。經(jīng)過十年課堂教學(xué)的檢驗(yàn)，這本書以其生動有趣的風(fēng)格、精心挑選的內(nèi)容和精確嚴(yán)謹(jǐn)?shù)臄⑹鍪艿搅藢W(xué)術(shù)界和讀者的一致好評。到目前為止，它是Amazon上獲得五星的兩本算法教材中的一本（另一本是《算法導(dǎo)論》，中文版已由機(jī)械工業(yè)出版社出版）。算法是計算機(jī)科學(xué)的靈魂，其復(fù)雜與抽象讓許多學(xué)生望而卻步。這本書最顯著的特點(diǎn)是生動的寫作風(fēng)格：作者貫穿一條主線，以講故事的形式將概念娓娓道來，非常易于理解和消化。
內(nèi)容概要
本書源自加州大學(xué)伯克利分校和加州大學(xué)圣迭戈分校本科生的算法課講義，以獨(dú)特的視角展現(xiàn)了算法設(shè)計的精巧技術(shù)及魅力。在表達(dá)每一種技術(shù)時，強(qiáng)調(diào)每個算法背后的簡潔數(shù)學(xué)思想，分析其時間和空間效率，運(yùn)用與其他技術(shù)類比的方法來說明特征，并提供了大量實(shí)例?！ ”緯匀祟愖罟爬系乃惴ǎㄋ阈g(shù)運(yùn)算）為起點(diǎn)，將各種算法中優(yōu)美而有代表性的內(nèi)容囊括書中，并以最前沿的理論（量子算法）結(jié)束，構(gòu)成了較為完整的算法知識體系?！ ”緯饕攸c(diǎn) ●生動的寫作風(fēng)格：作者貫穿一條主線，以講故事的形式將概念娓娓道來，非常易于理解和消化。 ●優(yōu)美地兼顧語言的生動和嚴(yán)謹(jǐn)性：本書中看不到很多數(shù)學(xué)公式，取而代之的是精確的文字?jǐn)⑹觥！ 窈侠淼靥暨x主題：用300多頁的篇幅使讀者對這門博大精深的科學(xué)有深刻的認(rèn)識。 ●穿插注解框：內(nèi)容包括人文歷史背景、對復(fù)雜概念的進(jìn)一步闡述、算法的擴(kuò)展與重要應(yīng)用等，對正文的敘述進(jìn)行補(bǔ)充。
作者簡介
Sanjoy Dasgupta，擁有加州大學(xué)伯克利分校計算機(jī)科學(xué)博士學(xué)位，現(xiàn)為加州大學(xué)圣迭戈分校教授，主要研究領(lǐng)域是多維數(shù)據(jù)的統(tǒng)計分析。他曾是AT&T實(shí)驗(yàn)室的高級技術(shù)人員。
書籍目錄
出版者的話序言Preface方框目錄0 Prologue（序論） 0.1 Books and algorithms（書和算法） 0.2 Enter Fibonacci（斐波那契數(shù)列） 0.3 Big-O notation（大O記號） Exercises（習(xí)題）1 Algorithms with numbers（數(shù)的算法） 1.1 Basic arithmetic（基本算術(shù)） 1.2 Modular arithmetic（模運(yùn)算） 1.3 Primality testing（素性測試） 1.4 Cryptography（密碼學(xué)） 1.5 Universal hashing（全域散列） Exercises（習(xí)題） Randomized algorithms：a virtual chapter（虛擬章：隨機(jī)化算法）2 Divide-and-conquer algorithms（分而治之算法） 2.1 Multiplication（乘法） 2.2 Recurrence relations（遞歸關(guān)系） 2.3 Mergesort（合并排序） 2.4 Medians（中位數(shù)） 2.5 Matrix multiplication（矩陣乘法） 2.6 The fast Fourier transform（快速傅里葉變換） Exercises（習(xí)題）3 Decompositions of graphs（圖的分解） 3.1 Why graphs?（圖論） 3.2 Depth-first search in undirected graphs（無向圖中的深度優(yōu)先搜索） 3.3 Depth-first search in directed graphs（有向圖中的深度優(yōu)先搜索） 3.4 Strongly connected components（強(qiáng)連通分量） Exercises（習(xí)題）4 Paths in graphs（圖的路徑） 4.1 Distances（距離） 4.2 Breadth-first search（廣度優(yōu)先搜索） 4.3 Lengths on edges（邊的長度） 4.4 Dijkstra’s algorithm（Dijkstra算法） 4.5 Priority queue implementations（實(shí)現(xiàn)優(yōu)先隊(duì)列） 4.6 Shortest paths in the presence of negative edges（帶負(fù)權(quán)的邊的圖中的最短路徑） 4.7 Shortest paths in dags（有向無環(huán)圖中的最短路徑） Exercises（習(xí)題）5 Greedy algorithms（貪婪算法） 5.1 Minimum spanning trees（最小生成樹） 5.2 Huffman encoding（赫夫曼編碼） 5.3 Horn formulas（Horn公式） 5.4 Set cover（集合覆蓋） Exercises（習(xí)題）6 Dynamic programming（動態(tài)規(guī)劃） 6.1 Shortest paths in dags，revisited（回顧：有向無環(huán)圖中的最短路徑） ……7 Linear programming and reductions（線性規(guī)劃與歸約）8 NP-complete problems（NP完全問題）9 Coping with NP-completeness（處理NP完全問題）10 Quantum algorithms（量子算法）Historical notes and further reading（歷史注記與擴(kuò)展閱讀）索引注釋
章節(jié)摘錄
插圖：
圖書封面
圖書標(biāo)簽Tags
無
評論、評分、閱讀與下載
- 還沒讀過(53)
- 勉強(qiáng)可看(387)
- 一般般(661)
- 內(nèi)容豐富(2741)
- 強(qiáng)力推薦(224)
用戶評論 (總計38條)
- 書含有原版的全英文，其中在一些段落加入了注釋，這本書也是幾個大牛的杰作，適合算法比較好的人學(xué)習(xí)來看，注釋版挺好的，這樣能讓讀者讀到幾個人的理解，又因?yàn)橛性牡拇嬖诓粫屪x者陷入迷途
- 此書比較深入淺出。。適合看《算法導(dǎo)論》感到吃力的哥們們，我對這本書的編排很喜歡，不是按枯燥的數(shù)據(jù)結(jié)構(gòu)一章章的排，而是就一類問題緩緩展開著敘述，很適合我不足就在于機(jī)械工業(yè)出版社的紙張，太薄，無法做筆記，很容易穿。。
- 這本書是我的第一本算法書，對于了解算法，開始研究算法問題很有幫助。
- 收到就發(fā)現(xiàn)書角折了好多頁，真心疼……書還是不錯的！
- 很不錯的一本書，內(nèi)容詳細(xì)，細(xì)節(jié)比較多。
- 很推薦 雖然是英文的 但看的時候并不吃力。。講的很細(xì)。。
- 太給力了，書也不錯，哈哈
- 強(qiáng)烈推薦，超級好書
- 沒損壞，感謝零下20度送貨的阿姨~
- 一直想看原版，終于買到了。翻了翻，發(fā)現(xiàn)質(zhì)量還不錯！
- 講解非常精辟
- 速度很快，書籍很好。
- sf! fantastic!
- 很難的啊，我是不太懂的啊
- 挺好的，差不多看完了
- 本來想學(xué)習(xí)英文的，買了之后太難了，也沒看
- 這是一本適合入門的書，但卻不失深度以及廣度，讀來讓人興趣盎然。我認(rèn)為，認(rèn)真讀完這本書，并且思考每章后面的習(xí)題后，會對算法有一個很好的大局觀。當(dāng)然要掌握算法，只靠這一本書是不夠的，不過算作最佳入門是當(dāng)之無愧的。有一位網(wǎng)友的書評寫比我的好得太多，由于字?jǐn)?shù)限制，轉(zhuǎn)載其中的大部分如下：＝＝＝＝＝＝＝＝＝轉(zhuǎn)自豆瓣中 etone師兄的評論：很經(jīng)典 這是本很新的書，06年末發(fā)行，07年才慢慢出現(xiàn)于人們的視野。我在08年初得知這本書，那會我還很奇怪：都什么年月了，怎么還有人寫算法教材——這么“經(jīng)典”的工作，不是上個世紀(jì)就被人做完了嗎?！ ∽x了這本Algorithms，我才知道：這才是我心中的算法書，我等待這樣一本書已經(jīng)很多年了。它的確當(dāng)?shù)闷疬@個名字?！ 娜蛔髡撸篠anjoy Dasgupta, Papadimitrijou, Umesh Vazirani?！ ∑渲?，Umesh堪稱計算機(jī)理論界的第二名師（第一名師是他自己的導(dǎo)師Manuel Blum），他帶過的學(xué)生們猶如一個理論計算機(jī)科學(xué)新生代的全明星隊(duì)。另一個作者Papadimitriou可算是理論界的第二名筆（第一非Knuth莫屬），他的書Computational Complexity和Combinator...ial optimization堪稱理論計算機(jī)科學(xué)最好讀的專業(yè)書，他業(yè)余還寫了本小說"Turing"。第三個作者Dasgupta是個算法方向的研究者，他最年輕，本身就是Umesh的學(xué)生，相比前面二位也沒什么噱頭——可他注定要因這本Algorithms而被載入計算機(jī)科學(xué)的史冊?！ ≡谶@本書之前，算法的經(jīng)典教材首推CLRS的算法導(dǎo)論。算法導(dǎo)論讓人印象深刻的，是它內(nèi)容的全面翔實(shí)，還有它一千兩百頁的厚度?！ 《姷竭@本Algorithms時，你會震驚于它的薄。我從亞馬遜收到這本書時，還以為拿錯了包裹?！ 】勺x過之后，你就會折服于它的美?！ ∵@是一本可以給人帶來巨大閱讀樂趣的專業(yè)書籍。作者娓娓道來，又惜墨如金。用極精煉的語言，為我們指明了一條通向那些美麗算法的線索。我要由衷地說：這本書不僅僅是一些結(jié)果的集合，更是一段美好的旅程。我對書中涉及的內(nèi)容已然熟悉，但讀過之后仍感收獲良多，對算法這門學(xué)問又多了些認(rèn)識。真的是，寫書當(dāng)如是。這本Algorithms，在短短的篇幅內(nèi)，做到了?！ ∪蛔髡呖芍^野心勃勃，幾乎是膽大妄為。他們對傳統(tǒng)算法教學(xué)思路的顛覆和背叛可謂前所未有。剛拿到目錄的時候，我就替他們捏了一把汗，覺得這哪里像一本“正經(jīng)”的算法書。可讀下來，卻不由得佩服——算法書早該這么寫了。 他們并沒有要全面的收錄各種各樣的算法，他們做的事情是理清了一條算法這門學(xué)問的線索。因此填鴨式的內(nèi)容灌輸不是這本書的目的；對結(jié)構(gòu)的精心安排，對問 題的數(shù)學(xué)結(jié)構(gòu)的剖析、從而推出一個算法的過程的講解，都體現(xiàn)除了這本書真正的用心：它要讓學(xué)生獲得最大程度的啟發(fā)，要訓(xùn)練學(xué)生獨(dú)立解決問題的能力。 我覺得這才是教育的真正目的，也是算法課應(yīng)該追求的目標(biāo)。 說完了種種溢美之詞，也來補(bǔ)充一下這本書的不足。這樣一本精煉的算法書，為了它道理的清晰、為了它的美，必然會放棄一點(diǎn)對面面俱到的追求。如果我用這本書來教一門算法課的話，我會增加一點(diǎn)以下的內(nèi)容： 1. 數(shù)據(jù)結(jié)構(gòu)?！? 這本書對數(shù)據(jù)結(jié)構(gòu)沒有單獨(dú)的章節(jié)，都是在某個數(shù)據(jù)結(jié)構(gòu)被一個算法用到的時候講一下，例如priority queue之于Dijkstra's algorithm。這種做法體現(xiàn)了作者的觀點(diǎn)：這門課完全就是關(guān)于algorithms，數(shù)據(jù)結(jié)構(gòu)對于算法而言就只是個工具。如果同一個系還能開出一門 很強(qiáng)的data structures課，這么做當(dāng)然很好，各有側(cè)重。但若是我來上課，肯定會提一下數(shù)據(jù)結(jié)構(gòu)的一些重要思想，例如hashing，和他們的數(shù)學(xué)背景。因?yàn)?對于一些實(shí)際問題，數(shù)據(jù)結(jié)構(gòu)已不再是個工具，可能就是問題本身?！ ?. 幾個沒有被此書涉及到的算法設(shè)計和分析的工具：對手論證(adversarial argument)，matroid，平攤分析(amortized analysis)。 3. 書中每個算法問題目前最好的上下界(upper bounds, lower bounds)。 4. 講一點(diǎn)比貪婪、動態(tài)規(guī)劃等等更加“現(xiàn)代”的算法設(shè)計的思想，例如 5. 除了這本Algorithms作為教材，補(bǔ)充讀物可以在CLRS算法導(dǎo)論和Kleinberg和 閱讀更多 ›
- 亞馬遜上面顯示中文版的 結(jié)果確實(shí)英文版的
- 派送速度快，杭州特能（名字很囧）久聞大名的書，內(nèi)容尚不多言，單從印刷排版來講，十分不錯，可以閱讀暢快。拿到手的時候發(fā)現(xiàn)寫注釋的正是《算法之道》的作者，曾隨手翻閱過，讀完這本再決定是否要再仔細(xì)閱之。如果硬要挑些不滿，字號略小...
- 英文內(nèi)容，加上適當(dāng)?shù)闹形淖⒔猓鬃x，經(jīng)典
- 英文版的理解起來還是有難度的，同時注釋的地方并不是很全面，需要配合其他的書籍一起來理解。
- 但是 激勵我要好好看下去。哪怕一個一個查單詞我也會看下去的。
- 非常好！給力。贊一個
- 太深奧了，建議買中文版
- 與算法導(dǎo)論的風(fēng)格完全不同，原來算法還可以寫的這么有趣！
- 書的內(nèi)容很好，符合演算法之重點(diǎn)主題。
- 大師的杰作，沒得說，好好讀就是了
- 強(qiáng)烈推薦，內(nèi)容很好，并且主要是看原版英文，意思無差別。
- 個人感覺這個版本不是很好
- 讀了這本書，讓我對算法有了新的認(rèn)識。并不是只有一般算法書中有的那些經(jīng)典算法能稱得上是算法，我們從小學(xué)開始學(xué)的加減乘除何嘗不是算法呢？作者想講述的是真真正正的算法的思想，并不是簡單機(jī)械的算法分析。注釋也非常好，并不是對原文的贅述，而是簡單說明后的延伸，既能幫助你理解為能看懂的部分，又可以是你對這個算法有一些原著中沒有提及的認(rèn)識。... 閱讀更多
- 這本書是比較偏理論的算法研究的，amazon能夠非?？焖偎拓浀郊?，讓我直接就可以閱讀，不再像去書店購買那么麻煩，非常感謝！
- 經(jīng)典的算法書籍
- 原版好書
- 上課用的，買來基本上沒看過
- 喜歡英文版的
- 去掉注釋
- 是算法方面的好書
- 英文原版+注釋，很強(qiáng)大