麻省理工學院-算法導論MIT Introduction to Algorithms 英文版 DVD 只於電腦播放 課程類型：電機工程與計算機科學 導師： Prof.CharlesLeiserson Prof.ErikDemaine Prof.CharlesLeiserson 查爾斯Leiserson工程教授是麻省理工學院的電氣工程和計算機科學教職研究員。他是麻省理工學院的計算機科學和人工智能實驗室（CSAIL）成員，是ACM研究員。 Prof.ErikDemaine 他的童年是和他的父親去北美旅行，他的父親是馬丁德曼，一位藝術家和雕塑家，他是在家中接受教育的。沒過12歲，埃里克就進入了加拿大達爾豪西大學，完成他的學士學位時，他只有14歲。 關於課本的介紹如下： 本書自第一版出版以來，已經成為世界範圍內廣泛使用的大學教材和專業人員的標準參考手冊。本書全面論述了算法的內容，從一定深度上涵蓋了算法的諸多方面，同時其講授和分析方法又兼顧了各個層次讀者的接受能力。各章內容自成體系，可作為獨立單元學習。所有算法都用英文和偽碼描述，使具備初步編程經驗的人也可讀懂。全書講解通俗易懂，且不失深度和數學上的嚴謹性。第二版增加了新的章節，如算法作用、概率分析與隨機算法、線性編程等，幾乎對第一版的各個部分都作了大量修訂。 學過計算機的都知道，這本書是全世界最權威的算法課程的大學課本了，基本上全世界的名牌大學用的教材都是它。這本書一共四位作者，ThomasH.Cormen，CharlesE.Leiserson和RonaldL.Rivest是來自MIT的教授，CliffordStein是MIT出來的博士，現在哥倫比亞大學做教授，四人姓氏的首字母聯在一起即是此書的英文簡稱(CLRS2e)，其中的第三作者RonaldL.Rivest是RSA算法的老大(算法名字裡面的R即是指他)，四個超級大牛出的一本書，此書不看人生不能算完整。 再介紹一下課堂錄像裡面授課的兩位MIT的老師，第一位，外表“絕頂聰明”的，是本書的第二作者CharlesE.Leiserson，以邏輯嚴密，風趣幽默享譽MIT。第二位，留著金黃色的絡腮鬍子和馬尾發的酷哥是ErikDemaine，21歲即取得MIT教授資格的天才，1981出生，今年才25歲，業餘愛好是俄羅斯方塊、演戲、琉璃、摺紙、雜耍、魔術和結繩遊戲。 另外，附上該書的中文電子版，pdg轉pdf格式，中文版翻譯自該書的第一版，中文書名沒有使用《算法導論》，而使用的是《現代計算機常用數據結構和算法》，1994年出版時沒有得到國外的授權，屬於“私自翻譯出版”，譯者是南京大學計算機系的潘金貴。 參考網頁 該書在China-Pub的網址：http://www.china-pub.com/computers/common/info.asp?id=6434 該書在Amazon的網址：http://www.amazon.com/gp/product/026203293...ing=UTF8 該書的勘誤網址：http://www.cs.dartmouth.edu/~thc/clrs-2e-bugs/bugs.php 該書的一個在線學習中心：http://highered.mcgraw-hill.com/sites/0070131511/ 該課程在MIT的中文網址：http://www.cocw.net/mit/Electrical-Enginee...ndex.htm 該課程在MIT的英文網址：http://ocw.mit.edu/OcwWeb/Electrical-Engin...ndex.htm -- 課程重點 算法導論是麻省理工學院電機工程與計算機科學系“理論計算機科學”集中選修課程的先導科目。課程幾乎將所有資料放到線上，包括了完整的課堂講義和習題。課本“算法導論，第二版”，是由CharlesLeiserson教授副筆。 課程描述 本課程教授高效率算法的設計及分析技巧，並著重在有實用價值的方法上。課程主題包含了：排序、搜尋樹、堆積及散列；各個擊破法、動態編程、償還分析、圖論算法、最短路徑、網絡流、計算幾何、數字理論性算法；多項式及矩陣的運算；高速緩存技術及並行運算。 一般資訊 講師： ErikDemaine CharlesE.Leiserson SMA講師： LeeWeeSun 課程目標與成果 課程目標 這門課程對學生們簡單介紹計算機算法的分析與設計。完成這門課程後，學生應當能做到以下幾項： 分析算法的漸進效率。 演示對各種主要的算法及數據結構的熟悉性。 對重要算法設計範例及分析方法的應用。 在一般的工程設計狀況上運用有效的算法。 課程成果 完成本課程的學生將會展現做到以下幾項的能力 用歸納法及迴路不變量來證明算法的正確性。 用漸進法分析算法在最壞情況下的執行時間。比較由多項式，指數及對數函數初步組合之函數的漸進行為。形容最壞，平均及最好情況分析的相對優點。 分析算法平均執行時間的概率。使用指標隨機值與預期直線性來做分析。練習（這裡的Recite是否是演示或是複習之意，換句話說，原句應該為：練習使用這一類分析的算法。後面出現Recite處皆同）用這一類分析法的算法分析。 解釋隨機化算法的基本性質和分析的方法。練習使用隨機性的算法。解釋隨機化算法與隨機輸入的算法之間的差異。 在適當的時機使用償還法分析算法。練習用此方法對簡單算法的分析。敘述償還分析法的不同策略，包括計數法及可能法。 敘述各個擊破法的模式和解釋當什麼情況算法設計會需要它。練習使用此模式的算法。實作各個擊破算法。推導出各個破算法的遞歸描述。 敘述動態編程的模式和解釋當什麼情況算法設計會需要它。練習使用此模式的算法。實作及分析動態編程算法。 敘述貪婪算法的模式和解釋當什麼情況算法設計會需要它。練習使用此模式的算法。實作及分析貪婪算法。 解釋各主要的排序算法。練習這些算法的分析及它們所包含的設計策略。實作將排序做為子程序的算法。推算比較排序法執行時間的下限，和解釋怎樣可以克服這些界限。 解釋實作動態集合的各大基本數據結構及對其動作的分析。練習使用數據結構的算法和了解它們的效率是如何依賴於所使用的數據結構。用增強已有數據結構的方法來實作新數據結構。實作將數據結構為重要成分的算法。 解釋各大圖論算法及對它們的分析。適時使用圖來模擬工程問題。實作新的圖論算法和使用圖論計算為關鍵的算法，及分析它們。 舉例說明在各個領域中所使用到的熟悉的數個重要算法，展現對應用算法安置的熟悉度-如計算幾何，作業研究，安全與加密，並行與分散計算，操作系統，及計算機體系結構。 遠距離教學 這們課程會在美國麻省理工學院教授，同時也是新加坡SMA(Singapore-MITAlliance)課程的一部分。無論是授課，演示課，習題或測驗，這兩個國家的課程在各個方面來說都是相同的。在麻省理工學院所有的講義都將是現場教授，這些都會被錄下，數位化，由本課程的網頁提供給新加坡的學生們。這些數位化的課程也會提供給麻省理工學院的學生。李教授會參加本課程的管理，與Demaine及Leiserson兩位教授一起寫課程相關資料，及帶領SMA的學生的演示課。 先修條件 對程序設計有很好的理解度及在離散數學，包括概率學有紮實的背景，是本課程的先有條件。 麻省理工學院學生：本課程是麻省理工學院電機資訊工程資訊理論之集中選修課程的先導科目。在選修這門課程前我們認為你應該先選修6.001計算機程序的架構與解譯和6.042J/18.062J計算機科學數學，及在這兩門課得到C或更高的成績。如果你還沒有達到這些要求，你一定要在註冊本課程之前與助教溝通。 授課 每週2節 每節1.5小時 課程內所提供的資料，包括講師們口述的講解是你的責任。 演示課 學生每個星期要參加一小時的演示課。課程人員將會排演示課的時程。你要負責演示課時所報告的內容。演示課的出席率一直以來跟考試的成績有緊密的關係。演示課也是給你一個更直接的機會來發問和與課程人員互動。 麻省理工學院的學生們：麻省理工學院的演示課會在每星期的最後一天由助教來教。講義3請你在本課網頁中的報名紙上填上你所選擇的演示課分組。課務辦公室出的演示課作業是無效的。 講義 多數的講義會使用方便打印的格式放在本科的網頁上。學生們應該由網頁上下載並打印這些講義。當有講義上線時你將會收到e-mail提醒你。e-mail的內容會告知哪里以及什麼時候那些少數沒有放在網頁上的講義可以被找到。 教科書 本課程主要的書面參考是由Corman,Leiserson,Rivest及Stein教授寫的教科書《算法導論，第二版》。在之前的學期本課程是用了這本書的第一版。第二版徹底修訂了前一版，這已使得第一版不再適合作為一個替代品。 麻省理工學院的學生們：這本教科書可以在各個線上或附近的書店購得。 習題 在學期中將會指定9次習題。在課目時程表及講義2里分別有暫時的作業時程和截止日期，但是真正的截止日期會寫在習題上。 通常來說遲繳的作業不會被接受。如果有能令人諒解的情況，你應該提前跟你的演示課指導者做出安排。 麻省理工學院的學生們：如果先前的安排發生了變化，那麼將由院長辦公室作出解釋。 因為每題可能被分別評分，所以每一題應該要寫在單獨的紙上。在每張紙的頂端寫上以下： -你的名字 -該堂課講師的名字 -習題號碼 -一起解題的人(參考14段)，或“合作者：無”如果你是完全一個人解答的話。 麻省理工學院的學生們： 你必須要將你的答案寫在三孔活頁紙上，教科人員會將它們裝訂起來以免散落。此外，你可以很簡單的將那些被評過分的作業加到你的活頁筆記本內。 在你寫答案的時候應該要盡量清楚和精確。我們希望你的答案容易理解與正確，因為技術性資料的溝通是一項重要的才能。 一個直接，簡單的回答比迂迴的解答值更多分，因為它更簡潔易懂同時也不易於犯錯。較懶散的答案就算是正確的，也會得較少分，所以確定你的筆跡清晰易讀。將你的答案抄寫一份再交是一個不錯的主意，這不但能讓你的作業更加工整，也讓你有機會能夠檢查及修正錯誤。 習題中有包括一些應該要解答但是不用交的練習題，這些問題是用來幫助你更掌握課程內容以及在解答指定習題將會有用。習題範圍內的材料會在考試中被測到。 算法的描述 你經常會被指定“用一個算法”來解決某個問題。你的寫作應該是以一個短文的型態。應該有一個標題段落概述你現在要解決的問題和你的解果。你的本文應該提供以下部分： 1.算法的英文描述，如有幫助的話，用偽代碼(pseudocode)。 2.最少以一個工作例子或圖表來更明確的顯示你的算法是怎樣工作的。 3.算法正確性的一個證明（或表示）。 4.算法執行時間的分析。 記住，你的目的是溝通。評分者會被指示對迂迴愚鈍的描述扣分。 評分規定 最終的評分會基於習題(P)，一個隨堂考(Q1)，一個家庭作業(Q2)和期末考(F)。習題全部總值是80分左右，隨堂考也是80分左右，攜卷回家測驗是150分左右，而期末考是180分左右。 雖然習題只佔你最終分數中的80分，你必須要做它們。 下表列出了不做習題對分數的影響： 跳過習題的影響 -------------------------------------------------------------------------------- 0無 1百分之一個整級分 2十分之一個整級分 3五分之一個整級分 4四分之一個整級分 5三分之一個整級分 6二分之一個整級分 7一個整級分 8兩個整級分 9或更多不及格 請注意這張表是列出了跳過的習題數，而不是整次的習題。具體的評分規定會依當時的需求而變動。 合作規定 家庭作業的目的是讓你有練習掌握課堂內容的機會。因此，我們鼓勵你合作解題。事實上，通常組成學習小組的學生會比那些獨自讀書的學生考的更好。但是，如果你選擇加入學習小組，你要靠你自己和你的小組來負責準備小組聚會。更具體的說，在這之前你應該花30到45分鐘試著自己解每一題。如果你的小組不能解答某一題，試著跟其他小組交流或問導師。 雖然你跟他人合作解答題目，但是，你一定要不受任何幫助而獨自的寫下你的答案。我們要求在你的習題上寫下你合作者們的名字。如果你沒有跟任何人合作，你應該寫下“合作者：無”。如果你的答案是由研究而來(例如：互聯網)，註明你的資料來源，但依你自己的方法寫下答案。 在考試中不允許任何的合作。本課程的第二項考試是一個可以帶回家的測驗，雖然你將被允許以幾天的時間來完成，但它必須是完全由你獨自完成。關於回家測驗的合作規定的一些細節將會安排在第三十五次講課上。請注意這課將會是考試的一部份，是強制性參加。 抄襲和其它反知識性的行為在任何一個以個人成就而自豪的學術環境內是不能被允許的。如果你對於合作規定有任何問題，或者你覺得你可能違反了規定，請與課程人員聯繫。雖然課程人員有義務適當的處理作弊情況，但如果是違反者本人提出而不是第三者檢舉，我們會較通情達理及寬大。 教學時程 這份時間表提供了授課，演示課題目，作業，測驗的日期，及指定要從課本“算法導論，第二版”內閱讀的課文。 1第一課課程細節；序論：算法分析，插入排序法(InsertionSort)，合併排序(MergeSort)閱讀：1-2章 發測驗0 2演示課1算法的正確性 發《作業1》 3第二課漸進表示（AsymptoticNotation）。遞歸公式（Recurrences）：置換法，迭代法，主方式 閱讀：3-4章，除了§4.4 4第三課各個擊破法：Strassen算法，費氏數列，多項式乘法。 閱讀：28章第2節，30章第1節 5演示課2遞歸公式，鬆散性 閱讀：Akra-Bazzi的講義 6第四課快速排序法，隨機化算法 閱讀：5章1到3節，7章 收《作業1》發《作業2》 7演示課3排序法：堆積排序法，動態集合，優先隊列 閱讀：6章 8第五課線性時間的排序法，下限，計數排序法，基數排序法 閱讀：8章第1到3節 收《作業2》發《作業3》 9第六課序列統計，中位數 閱讀：9章 10演示課4中位數的應用，桶式排序 閱讀：8章第4節 11第七課散列，通用散列 閱讀：11章1到3節 收《作業3》發《作業4》 12第八課散列函數，完美散列 閱讀：11章第5節 13演示課5測驗1複習 收《作業4》 14評分後的作業4可以在中午拿到 15測驗1 16演示課6二元搜尋樹，樹的追踪 閱讀：12章1到3節 17第九課二元搜尋樹和快速排序法之間的關係；隨機二元搜尋樹的分析 閱讀：12章4節 發《作業5》 18第十課紅黑樹，循環，插入，刪除 閱讀：13章 19演示課72-3樹，B-樹 閱讀：18章1到2節 20第十一課增強數據結構，間距樹 閱讀：14章 收《作業5》發《作業6》 21第十二課計算幾何，區間查詢 閱讀：33章1到2節 22演示課8凸多邊形 閱讀：33章3節 23第十三課vanEmdeBoas，優先隊列 閱讀：vanEmdeBoas的講義 收《作業6》發《作業7》 24第十四課償還算法，表的複制，可能法 閱讀：17章 25演示課9競爭分析，自我排序列 26第十五課動態編程，最長共同子序列，最優二元搜尋樹 閱讀：15章 收《作業7》發《作業8》 27第十六課貪婪算法，最小生成樹 閱讀：16章1到3節，23章 28演示課10貪婪算法和動態編程的範例 29第十七課最短路徑，Dijkstra算法，廣度優先搜尋法 閱讀：22章1，2節；第580-587頁，24章3節 收《作業8》發《作業9》 30演示課11深度優先搜尋法，邊的分類 閱讀：22章3到5節 31第十八課最短路徑，Bellman-Ford，DAG內的最短路徑，差異局限 閱讀：24章1,2,4,5節 32第十九課全成對最短路徑，動態編程，Floyd-Warshall，Johnson的算法 閱讀：25章 收《作業9》 33第二十課零散集合的數據結構 閱讀：21章 34評分後的作業9可以在中午拿到 35第二十一課帶回家發下測驗2;道德，解決問題(強制參加) 發測驗2 36沒有演示課-解答測驗2! 37沒有課 算法程序比賽開始(非強制參加) 收測驗2 38第二十二課網絡流，最大流量最小切割論 閱讀：26章1-2節 發《作業10》(選答) 39演示課12求對集(注：最大二分圖求對集) 閱讀：26章3節 40第二十三課網絡流，Edmonds-Karp算法 參賽答案截止 41第二十四課隨堂測驗；比賽頒獎；後續課程的討論 《作業10》解答 相關閱讀資料 以下是對本課程有用的參考書。 1Aho,AlfredV.,JohnE.Hopcroft,與JeffreyD.Ullman.《計算機算法之設計與分析》（TheDesignandAnalysisofComputerAlgorithms）Addison-Wesley，1974.經典作品，但是在網絡流，線性規劃和近代算法方面較缺少。Aho,AlfredV.,JohnE. 2Aho，AlfredV.，JohnE.Hopcroft，與JeffreyD.Ullman.《數據結構與算法》（DataStructuresandAlgorithms）Addison-Wesley，1983.重新改版過後是以前作《計算機算法之設計與分析》（TheDesignandAnalysisofComputerAlgorithms）前六章所改版的較基本版本。 3Baase，Sara.《計算機算法：設計與分析導論，第二版》（ComputerAlgorithms:IntroductiontoDesignandAnalysis.2nded）Addison-Wesley，1988.普通參考，儘管它的說明有時是潦草扼要的。 4Bentley，Jon.《程序設計明珠》（ProgrammingPearls）Addison-Wesley，1986.算法設計在軟件工程中的實用。（ProgrammingPearls繁體中文版,譯者：許鳴程，出版商：基峰，出版日期：2001-11-22，ISBN：9575668804） 5Bentley，Jon.《更多的程序設計明珠》（MoreProgrammingPearls）Addison-Wesley，1988.更多算法設計在軟件工程中的實用。 6Bentley，JonLouis.《編寫有效率的程序》（WritingEfficientPrograms）Prentice-Hall，1982.非常傑出的效能精進調整。 7Brassard，Gilles與PaulBratley.《算法：理論與實踐》，Prentice-Hall，1988.很好的範例及習題，著重於方法而不是個別的問題。 8Chung，KaiLai.《基礎概率理論與隨機過程》，Springer-Verlag，1974.對概率直覺性的演示課。 9Even，Shimon.《圖形算法》，ComputerSciencePress，1979.對圖形算法有廣泛的論述，包含了網絡流及平面性。 10Feller，William.《概率理論導論與應用》，JohnWiley&Sons，Vol1.1968，Vol2.1971.對概率很好的參考。 11Garey，MichaelR.與DavidS.Johnson.《計算機與難駕馭性：對NP完整性理論的指南》，SanFrancisco:WHFreeman&Co，1979.專注於NP完整性的參考書。在後半部含有一份NP完整問題集的列表及在書中出現過，針對多項式時間特別情況的算法的參考。 12Gonnet，GH《算法與數據結構手冊》，Addison-Wesley，1984.Pascal及C碼，真正執行時間的比較，和對研究報告中分析的指示。 13Gusfield，Dan.《字串，樹，與序列的算法》，CambridgeUniversityPress，1997.操作字符字串及序列的算法的大概論述。 14Horowitz，Ellis與SartajSahni.《計算機算法基礎》，ComputerSciencePress，1978.擇重介紹了數據結構，動態編程，以及分支與界限法。 15Kingston，JeffreyH.《算法與數據結構：設計，正確性，分析》，Addison-WesleyPublishingCo.，1991.一本優良的數據結構導入書，關於算法正確性有一篇不錯的章節。 16Knuth，DonaldE.《計算機程序設計藝術》，Addison-Wesley.三卷如百科全書般的作品：(1)基礎算法，(2)半數值算法，與(3)排序與搜尋。 17Lawler，EugeneL.《組合式優選》，Holt，Rinehart，andWinston，1976.圖算法（密集圖)，網絡流，與線型規劃。開始幾章是很優秀的。 18Liu，CL《組合數學導論》，McGraw-Hill，1968.與計算機科學有關的組合數學。有優秀的習題. 19Manber，Udi.《算法導論》，Addison-Wesley，1989.著重於創造力的初級文章。 20Mehlhorn，Kurt.《數據結構與算法》，Springer-Verlag，1984.三卷：(1)排序與搜尋，(2)圖算法和NP－完整性，與(3)多維度查詢與計算幾何。基本及高階論題的講義。 21Niven，Ivan與HerbertS.Zuckerman.《數論導論》，JohnWiley&Sons，1980.有閱讀價值的的數論入門介紹。 22Papadimitriou，ChristosH.與KennethSteiglitz.《組合式優選：算法與復雜性》，Prentice-Hall，1982.線性規劃和它的變體。 23Press，WilliamP.，BrianP.Flannery，SaulA.Teukolsky，與WilliamT.Vetterling.《C的數值處方：科學計算的藝術》，Cambridge:CambridgeUniversityPress，1988.數值算法的程序碼. 24Reingold，EM，J.Nievergelt，與N.Deo.《組合算法：理論與應用》，Prentice-Hall，1977.在遞歸關係和二元樹方面的內容不錯。 25Sedgewick，Robert.《算法，第二版》，Addison-Wesley，1988.有著優秀論題廣度的初階文章。不重於分析，但是有很多圖。 26Sipser，Michael.《運算理論導論》，PWSPublishingCo.，1997.對可計算性及復雜性理論很好的文章。 27Tarjan，RobertEndre.《數據結構與網絡算法》，SocietyforIndustrialandAppliedMathematics，1983.有一堆好東西的高階書。 課堂講稿 這裡有本課完整的課堂講稿。 ——請下載相應文件查看。 作業 在習題集裡所引用的閱讀材料和習題是由課本《算法導論》，第二版內取得的，(詳細的資訊請參考http://mitpress.mit.edu/algorithms/)。 ——請下載相應文件查看。 測驗 這裡提供了本課的一些實際題目和練習考試。 ——請下載相應文件查看。 版權歸麻省理工學院所有，請勿轉載 學校介紹 麻省理工學院（MassachusettsInstituteofTechnology，縮寫：MIT）是美國一所綜合性私立大學，有“世界理工大學之最”的美名。位於麻薩諸塞州的波士頓，查爾斯河（CharlesRiver）將其與波士頓的後灣區（BackBay）隔開。今天MIT無論是在美國還是全世界都有非常重要的影響力，培養了眾多對世界產生重大影響的人士，是全球高科技和高等研究的先驅領導大學，也是世界理工科菁英的所在地。麻省理工是當今世界上最富盛名的理工科大學，《紐約時報》筆下“全美最有聲望的學校”。入選中國世界紀錄協會世界綜合實力最強的大學候選世界紀錄。