《演算法導論》有什麼好的學習心得?
歡迎交流分享。
2015/08/21更新1. 動手做,動手做,動手做(重要的事情說三遍)我見過好多把CLRS當小說看的,真還有很多人囫圇吞棗給看完了的。但是沒有動手自己去實現這些演算法的話,CLRS看得再熟練,都只停留在紙面上。有些真正性能和實現上面的優點,不寫代碼是感受不出來的。說到動手做的的話,做完題沒有答案對就等於沒有做啊。關於算導的答案部分,目前不是很全,主要有(不保證正確):
- Introduction to Algorithms study group 現在應該有前11章的大部分答案,正確率不保證,僅供參考
- ime.usp.br 的頁面 相當於一個教師指南的冊子,答案講的比較精細,基本上是全部正確的,但是題目覆蓋不是很全
- http://www2.compute.dtu.dk/~phbi/files/teaching/solution.pdf 也是一個教師指南,但是正確率要更低一些好像,很多題目也只有大致思路,僅供參考
- yinyanghu.github.io 的頁面 南大的學長,好像在滑鐵盧讀博吧,這是一個第二版的連接,第三版的答案還在撰寫當中
2. 盡量看英文原版(不是為了裝逼)
很多同學對看英文有排斥心理,這個很正常的。但是看英文原版真的不是為了裝逼,而是中文翻譯版雖說進步不少,但是拗口和錯誤之處還是有很多。你說演算法這個東西吧,稍微理解錯一個加一減一,就會對最後的結果產生很大的不同。我們當年上CLRS的時候,愣是盯著翻譯版的某句話苦思冥想了好久。結果一看英文原版,瞬間豁然開朗,遂中文版丟棄一邊了。我個人建議,中英文混合著看,看不懂中文看英文,看不懂英文看中文。3. 書名真的是大誤
Introduction個鬼哦,大家不要被導論給騙了。這裡的導論我覺得應該是與TAOCP之類的書籍相比,它確實還就算個導論。但如果和什麼《深入理解XXX》《深度探索XXX》《XXX編程指南》之類的相比,它絕對是難度與深度的集合體,學習曲線巨陡峭,基本上自學一兩個月就跟沒學似的。4. 配合別的東西一起學
硬啃書真的是很寂寞,當然不排除有的同學有這樣過人的學力。如果這樣一直吃白飯確實吃不下的話,可以考慮跟一下公開課。coursera/edx/mooc上面的好課都挺多,不出家門上到國外同學們斥巨資拚老命上到的課,還是賺到了的。5. 關於理論證明的取捨
CLRS作為一本嚴謹的科學研究入門教材,理論的證明充斥了這本書的很大一部分。每一章節的很多題目,都是證明某個引理之類的。這一部分的取捨我覺得因人而異吧,有的同學只是為了掌握演算法本身而去學CLRS,那麼證明部分我覺得只要能做到說服自己即可;有的同學將來要讀博發paper的話,CLRS上的證明最好還是弄透徹比較好。雖然自己再造一個什麼新的排序演算法,新的二叉搜索樹什麼的可能性不是很高(大神除外了,Size Balanced Tree人家中學時候造出來),但是嚴謹的數學素養是非常重要的。Postscript:如果說CLRS是一桌理論與思維的盛宴的話,Algorithms Unlocked (豆瓣)就是餐前的開胃小菜。衝到飯店裡直接就上主菜如果吃不消的話,可以考慮來讀一讀這本同樣是作者Cormen寫的小冊子。不過目前還沒有翻譯版,有機會的同學可以嘗試一下。全部讀完,讀過部分的題目完成度在99%左右。。。1.英文版和中文版的差別不大,演算法導論的翻譯絕對是可以的,當然的確有部分明顯的錯誤,不過基本都是非常明顯的列印錯誤,少部分的翻譯錯誤也是很容易判別的,絕對不會影響閱讀。。。如果你中文版看不懂,那麼基本看英文也是一個結果,該不懂的還是不懂,某些人可能是因為中文版沒看懂,然後斷定中文版翻譯有問題,這樣就可以掩蓋自己的水平缺陷,達到自欺欺人的效果。。。少部分的翻譯錯誤可以臨時對照pdf的英文版。。。。。總之,沒有必要特意看英文版。2.沒有演算法基礎的同學,尤其是連數組,堆棧,二叉樹的遍歷,幾個基本排序演算法的代碼都寫不出來的同學,別看這本書。。。雖然這本書也會提這些東西,但是,它基本是做個引子,然後引入更深的東西。。。就好比,小學數學沒學好,直接去學大學數學一樣。。。所以先從小學數學學起(先學一本最基礎的數據結構)。
3.如果瀏覽目錄發現一半以上的東西是完全沒見過的,那麼在第2條的基礎上,去poj練一兩個月,把網路流的基本演算法步驟,凸包,並查集,線段樹,貪心動態規劃,逆序數,以及基本的數論演算法之類的東西給補上。。。不然就好比,高中畢業的你直接看《苔絲》之類的英文小說一樣,一段話裡面有二三十個單詞不認識,臨時去查,去標記,特別痛苦。。根本享受不了小說的氣氛和韻味。
4.在做好2.3的基礎上,如果樂於探究演算法的原理,想知其然並知其所以然,而且又有很多時間(幾百個小時吧),這樣就可以讀這本書了。。我讀這本書的證明部分是有個比較獨特方法:不要把自己當成一個讀者,而是一個交流者,和這本書的作者(大師)交流。。比如,它一般是要在做一個大證明之前會先拋出這個證明結論,你看到結論後,如果比較感興趣,可以先自己試著去探索一下,證明一下,探索幾十分鐘後,哪怕沒有探索出結果,那也是多少有了自己的一點收穫,然後帶著你的收穫再來看這本書的證明,就像你和大師交流一樣。。。5.別把這本書做入門書,說是入門書的人要麼就是特別厲害而且特別不負責任的,要麼就是啥都不懂的人以為看到「導論」兩個字就認為特別基礎的人。6.關於數學,首先必須是大學畢業的,學過高等數學,矩陣和離散數學的,如果沒學過這幾本,那麼裡面的東西也真夠嗆,原因同2。。如果學過但是忘了,那麼書的附錄部分會有複習,看一下就可以了。。。如果看了還是搞不懂書裡面的推理,那麼基本就是你可能不太適合讀這類書的證明部分,不太適合搞研究。。。僅此而已。。。看演算法導論,而不做習題的都是耍流氓 把習題都認真做出來了,那演算法導論也算是學到家了,整本書能教你的,基本都掌握了
資料篇:
- 講義:CS 97SI: Introduction to Competitive Programming Contests
- 數學基礎:Single Variable Calculus --&> Mathematics for Computer Science(別名:離散數學)
- 習題解析:http://mosfet.isu.edu/classes/cs385f10/resources/Introduction%20to%20Algorithms%28Instructor%27s%20Manual%29.pdf(或直接輸題號Google)
心得篇:
- 看英文原版。(話說技術書籍不看英文那絕對會被噁心死吧,當然這只是我個人觀點)
- 遇到複雜度分析,記得自己動手推一遍。
- 做習題。
- 做習題。(因為很重要所以說了兩遍)
最近在學,當自己糾結習題的時候,這個挺管用的:
http://clrs.skanev.com/index.html
推薦一下coursera的課程吧, Robert Sedgewick是《演算法》第四版 的作者哦。。。有意思的是普林斯頓在coursera是不髮結課證書的,任何證明都沒有。。。還有一個月開課,快來吧!
Coursera -- Algorithm Part I
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne
還有就是這個,旅行家問題,嘿嘿。。。
Coursera-- Discrete Optimization
只笑笑,不說話
充足的耐心和紮實的數學基礎是讀懂演算法導論的基礎。
書中每一個定理需要自己推導一下,有些只需要初中的數學知識即可,但是有一些,需要用到泰勒公式和無窮的概念,這要求你必須對高等數學有良好的基礎。不要想走捷徑,演算法從來都和數學離不開關係。如果實在是不想再和數學打交道了,建議不要看演算法導論,看看博客和一些別的演算法書籍就可以了。
----------------------------分割線--------------------------------找出了之前學習演算法導論的筆記,基本上每題都數學討論了,數學真的是很重要啊。當年裝逼買了一本,寫了個名字╮(╯▽╰)╭
貌似不少人都說不要看中文版……其實我覺得中文版翻譯得還可以啊……當然這種東西看英文原版是避不開的就是了。另外算導這種書還是抱著看比看PDF好吧(個人觀點)可以採取 看算導-&>看Wikipedia或者其他能找到的資料-&>看算導 的方法……還有就是,學習數學……
上quora可以直接問作者哦Thomas Cormen"s answer to How should one read Introduction to Algorithms (CLRS) to get the most out of it?
對於這種題,大佬們肯定這麼答
1.必須看原版!原版!原版都看不懂學個鳥編程!
2.要有數學基礎!!不去補基礎!這本書你看不了!!!
3.做題!!做題!!題都做不明白就是你智商有問題!!
----
對於大佬來說,英文很簡單、數學基礎很紮實、智商也高,但不適合我們這種小渣渣
你聽大佬的話,一般都逃不出幾個結局
買來原版書--看了一頁--放棄
給自己定了很嚴格的計劃--高等數學、離散數學狂補基礎--數學沒學好--放棄
題太難--放棄
所以我的建議
1.如果你連一本原版書都沒看過,請買中文版
2.不必等學完數學基礎,現在就開始,一旦開始就別停下來。
3.別想著學會100%,不會跳過或記下來,初期不要只看書!!先找一門課,先把課中學的都記下來。
4.最後有時間來啃書,可以多啃幾遍
---
當然我每看完,我也是剛開始的少年,共勉,不喜勿噴
過硬的數學基礎學起來會事半功倍。
關鍵在做習題,那些習題設計的非常精妙,經常有幾道題連續證明各種推論最後拼在一起的,引人入勝。
另外這本書的學習曲線非常陡峭(至少對於我來說),一開始看起來會非常煩躁,遇到這種情況可以直接看公式和偽代碼,看不懂再看文字描述。個人感覺這本書主要針對的是演算法分析,想刷POJ刷的爽可能還得另找辦法。這本書太理論化 正統化,像蘇聯的教材而不是美國的教材 很多演算法的來龍去脈沒有講清楚也沒有講在什麼情況下應該用哪一種演算法
如果想要知道某個演算法的歷史最好去看knuth的書,如果想知道怎麼用,algorithm in c 其實挺好的跟一門公開課。刷OJ是充分不必要條件,很多時間可能會浪費在格式這種細節上。事實上很多數據結構可以手動模擬足以,真寫程序也是調用別人的輪子,或者到時候來補也為時未晚。
最近快校招了也在補演算法,我屬於IC半路自學轉CS,演算法和數據結構上基本沒什麼基礎。
本著只看最牛逼的書和對智商的莫名自信,加上輪子哥也說這書可以自學,就直接上手了。對於這種大磚頭書,自己有個學習心得,就是按周目來刷,不要硬啃。
初步制定的計劃是這樣的:第一周目:快速瀏覽一遍,忽略數學證明和多數習題,理解演算法思想為主,用拿手的語言去實現一下每節最核心的演算法。目前我是每天看三四章,後面速度會慢下來,這樣下來20天左右能刷完全書。根據自己的時間去調整進度,這一遍儘可能快。第二周目:根據第一周目的經驗,先去補一下相關的數學基礎,然後就像其他回答里說到的,動手刷習題、寫代碼實現。不過對於數學證明我還是持觀望態度,不是專門搞理論的話,理解思想就夠了。等我實踐完第一周目有什麼體會了再更吧。事實上過完第一周目有個基礎我就要去刷面試題了,第二周目應該算有生之年系列。。CS 161 Summer 2016配合斯坦福的note看
去看中文版第一版,然後被噁心到,然後看英文版原著,然後盲聽做一遍MIT演算法導論的課程字幕。保證你比誰都「了解」這個課。。。。但是,不保證你能懂。。。
看到其他回答基本都說得比較詳細了,補充一個:MIT有一門Introduction to Algorithms(6.006)網課,textbook剛好是演算法導論,可以考慮配合課程一起學。
Lecture Videos | Introduction to Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare
這門網課lecture和recitation的視頻都很完整,還包括了兩個部分的筆記,assignments、exams以及對應的solutions。在reading部分還有每個lecture對應書上的章節:
書上習題答案可以參考: CLRS Solutions
推薦閱讀:
※如何解決做筆記對閱讀的「打斷」?
※好的讀書方法是什麼,需要做讀書筆記么?還是一直讀下去就行?
※如何評價肯·福萊特的世紀三部曲?
※怎麼才能寫出一篇精彩的感悟式文章?
※有哪些大神級人物生命結尾說了總結人生的一句話或一首詩?比如李叔同等,?