資料介紹

相關專題學習資料：

• 計算機網絡技術

資料錄入:allanyang

更新時間:2010-09-07 02:18:00

文件大小:3.5 GB

語言要求:英文

資料類型:視頻資料

下載方式:電驢(eMule)下載
 

 

 

這是麻省理工學院2001年秋季課程《算法導論》的所有課程資料，包括有：課本(含有習題，chm格式)，課堂講稿(ppt轉pdf格式)，作業及其答案(pdf格式)，測驗及其答案(pdf格式)，教師參考(含習題答案，很難得，pdf格式)，課堂錄像(rmvb格式)。

其中的課堂錄像共有24個，將以每周兩個文件的速度提供上網。

關於課本的介紹如下：

本書自第一版出版以來，已經成為世界范圍內廣泛使用的大學教材和專業人員的標准參考手冊。本書全面論述了算法的內容，從一定深度上涵蓋了算法的諸多方面，同時其講授和分析方法又兼顧了各個層次讀者的接受能力。各章內容自成體系，可作為獨立單元學習。所有算法都用英文和偽碼描述，使具備初步編程經驗的人也可讀懂。全書講解通俗易懂，且不失深度和數學上的嚴謹性。第二版增加了新的章節，如算法作用、概率分析與隨機算法、線性編程等，幾乎對第一版的各個部分都作了大量修訂。

學過計算機的都知道，這本書是全世界最權威的算法課程的大學課本了，基本上全世界的名牌大學用的教材都是它。這本書一共四位作者，Thomas H. Cormen，Charles E. Leiserson和Ronald L. Rivest是來自MIT的教授，Clifford Stein是MIT出來的博士，現在哥倫比亞大學做教授，四人姓氏的首字母聯在一起即是此書的英文簡稱(CLRS 2e)，其中的第三作者Ronald L. Rivest是RSA算法的老大(算法名字裡面的R即是指他)，四個超級大牛出的一本書，此書不看人生不能算完整。 

再介紹一下課堂錄像裡面授課的兩位MIT的老師，第一位，外表“絕頂聰明”的，是本書的第二作者Charles E. Leiserson，以邏輯嚴密，風趣幽默享譽MIT。第二位，留著金黃色的絡腮胡子和馬尾發的酷哥是Erik Demaine，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...5Fencoding=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...eHome/index.htm
該課程在MIT的英文網址：http://ocw.mit.edu/OcwWeb/Electrical-Engin...eHome/index.htm

--

課程重點

算法導論是麻省理工學院電機工程與計算機科學系“理論計算機科學”集中選修課程的先導科目。課程幾乎將所有資料放到線上，包括了完整的課堂講義和習題。課本“算法導論，第二版”，是由 Charles Leiserson 教授副筆。

課程描述

本課程教授高效率算法的設計及分析技巧，並著重在有實用價值的方法上。課程主題包含了：排序、搜尋樹、堆積及散列；各個擊破法、動態編程、償還分析、圖論算法、最短路徑、網絡流、計算幾何、數字理論性算法；多項式及矩陣的運算；高速緩存技術及並行運算。

一般資訊

講師：
Erik Demaine
Charles E. Leiserson

SMA 講師：
Lee Wee Sun

課程目標與成果

課程目標

這門課程對學生們簡單介紹計算機算法的分析與設計。完成這門課程後，學生應當能做到以下幾項：

分析算法的漸進效率。

演示對各種主要的算法及數據結構的熟悉性。

對重要算法設計范例及分析方法的應用。

在一般的工程設計狀況上運用有效的算法。

課程成果

完成本課程的學生將會展現做到以下幾項的能力

用歸納法及回路不變量來證明算法的正確性。

用漸進法分析算法在最壞情況下的執行時間。比較由多項式，指數及對數函數初步組合之函數的漸進行為。形容最壞，平均及最好情況分析的相對優點。

分析算法平均執行時間的概率。使用指標隨機值與預期直線性來做分析。練習（這裡的Recite是否是演示或是復習之意，換句話說，原句應該為：練習使用這一類分析的算法。後面出現Recite處皆同）用這一類分析法的算法分析。

解釋隨機化算法的基本性質和分析的方法。練習使用隨機性的算法。解釋隨機化算法與隨機輸入的算法之間的差異。

在適當的時機使用償還法分析算法。練習用此方法對簡單算法的分析。敘述償還分析法的不同策略，包括計數法及可能法。

敘述各個擊破法的模式和解釋當什麼情況算法設計會需要它。練習使用此模式的算法。實作各個擊破算法。推導出各個破算法的遞歸描述。

敘述動態編程的模式和解釋當什麼情況算法設計會需要它。練習使用此模式的算法。實作及分析動態編程算法。

敘述貪婪算法的模式和解釋當什麼情況算法設計會需要它。練習使用此模式的算法。實作及分析貪婪算法。

解釋各主要的排序算法。練習這些算法的分析及它們所包含的設計策略。實作將排序做為子程序的算法。推算比較排序法執行時間的下限，和解釋怎樣可以克服這些界限。

解釋實作動態集合的各大基本數據結構及對其動作的分析。練習使用數據結構的算法和了解它們的效率是如何依賴於所使用的數據結構。用增強已有數據結構的方法來實作新數據結構。實作將數據結構為重要成分的算法。

解釋各大圖論算法及對它們的分析。適時使用圖來模擬工程問題。實作新的圖論算法和使用圖論計算為關鍵的算法，及分析它們。

舉例說明在各個領域中所使用到的熟悉的數個重要算法，展現對應用算法安置的熟悉度 - 如計算幾何，作業研究，安全與加密，並行與分散計算，操作系統，及計算機體系結構。

遠距離教學

這們課程會在美國麻省理工學院教授，同時也是新加坡SMA (Singapore-MIT Alliance) 課程的一部分。無論是授課，演示課，習題或測驗，這兩個國家的課程在各個方面來說都是相同的。在麻省理工學院所有的講義都將是現場教授，這些都會被錄下，數位化，由本課程的網頁提供給新加坡的學生們。這些數位化的課程也會提供給麻省理工學院的學生。李教授會參加本課程的管理，與 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 第一課 課程細節；序論：算法分析，插入排序法(Insertion Sort)，合並排序(Merge Sort) 閱讀：1-2章
發測驗 0

2 演示課 1 算法的正確性
發《作業 1》

3 第二課 漸進表示（Asymptotic Notation）。遞歸公式（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 演示課 7 2-3樹， B-樹
閱讀：18 章 1 到 2 節

20 第十一課 增強數據結構，間距樹
閱讀：14 章
收《作業 5》發《作業 6》

21 第十二課 計算幾何，區間查詢
閱讀：33 章 1 到 2 節

22 演示課 8 凸多邊形
閱讀：33 章 3 節

23 第十三課 van Emde Boas，優先隊列
閱讀：van Emde Boas 的講義
收《作業 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》解答

相關閱讀資料

以下是對本課程有用的參考書。

1 Aho, Alfred V., John E. Hopcroft, 與 Jeffrey D. Ullman. 《計算機算法之設計與分析》（The Design and Analysis of Computer Algorithms） Addison-Wesley， 1974. 經典作品，但是在網絡流，線性規劃和近代算法方面較缺少。 Aho, Alfred V., John E.

2 Aho， Alfred V.， John E. Hopcroft， 與 Jeffrey D. Ullman. 《數據結構與算法》（Data Structures and Algorithms） Addison-Wesley， 1983. 重新改版過後是以前作《計算機算法之設計與分析》（The Design and Analysis of Computer Algorithms ）前六章所改版的較基本版本。

3 Baase， Sara. 《計算機算法：設計與分析導論，第二版》（Computer Algorithms: Introduction to Design and Analysis. 2nd ed） Addison-Wesley， 1988. 普通參考，盡管它的說明有時是潦草扼要的。

4 Bentley， Jon. 《程序設計明珠》（Programming Pearls） Addison-Wesley， 1986. 算法設計在軟件工程中的實用。（Programming Pearls 繁體中文版, 譯者：許鳴程，出版商：基峰，出版日期：2001-11-22，ISBN：9575668804）

5 Bentley， Jon. 《更多的程序設計明珠》（More Programming Pearls） Addison-Wesley， 1988. 更多算法設計在軟件工程中的實用。

6 Bentley， Jon Louis. 《編寫有效率的程序》（Writing Efficient Programs） Prentice-Hall， 1982. 非常傑出的效能精進調整。

7 Brassard， Gilles 與 Paul Bratley. 《算法：理論與實踐》，Prentice-Hall， 1988. 很好的范例及習題，著重於方法而不是個別的問題。

8 Chung， Kai Lai. 《基礎概率理論與隨機過程》，Springer-Verlag， 1974. 對概率直覺性的演示課。

9 Even， Shimon. 《圖形算法》，Computer Science Press， 1979. 對圖形算法有廣泛的論述，包含了網絡流及平面性。

10 Feller， William. 《概率理論導論與應用》，John Wiley & Sons， Vol 1. 1968， Vol 2. 1971. 對概率很好的參考。

11 Garey， Michael R. 與David S. Johnson. 《計算機與難駕馭性：對NP完整性理論的指南》，San Francisco: W. H. Freeman & Co， 1979. 專注於NP完整性的參考書。在後半部含有一份NP完整問題集的列表及在書中出現過，針對多項式時間特別情況的算法的參考。

12 Gonnet， G. H. 《算法與數據結構手冊》，Addison-Wesley， 1984. Pascal 及 C 碼， 真正執行時間的比較，和對研究報告中分析的指示。

13 Gusfield， Dan. 《字串，樹，與序列的算法》， Cambridge University Press， 1997. 操作字符字串及序列的算法的大概論述。

14 Horowitz， Ellis 與Sartaj Sahni. 《計算機算法基礎》，Computer Science Press， 1978. 擇重介紹了數據結構，動態編程，以及分支與界限法。

15 Kingston， Jeffrey H. 《算法與數據結構：設計，正確性，分析》，Addison-Wesley Publishing Co.， 1991. 一本優良的數據結構導入書，關於算法正確性有一篇不錯的章節。

16 Knuth， Donald E. 《計算機程序設計藝術》，Addison-Wesley. 三卷如百科全書般的作品：(1) 基礎算法， (2) 半數值算法， 與 (3) 排序與搜尋。

17 Lawler， Eugene L. 《組合式優選》，Holt， Rinehart， and Winston， 1976. 圖算法（密集圖)，網絡流，與線型規劃。開始幾章是很優秀的。

18 Liu， C. L. 《組合數學導論》，McGraw-Hill， 1968. 與計算機科學有關的組合數學。有優秀的習題.

19 Manber， Udi. 《算法導論》，Addison-Wesley， 1989. 著重於創造力的初級文章。

20 Mehlhorn， Kurt. 《數據結構與算法》，Springer-Verlag， 1984. 三卷： (1) 排序與搜尋， (2) 圖算法和NP－完整性， 與 (3) 多維度查詢與計算幾何。基本及高階論題的講義。

21 Niven， Ivan 與Herbert S. Zuckerman. 《數論導論》，John Wiley & Sons， 1980. 有閱讀價值的的數論入門介紹。

22 Papadimitriou， Christos H. 與Kenneth Steiglitz. 《組合式優選：算法與復雜性》，Prentice-Hall， 1982. 線性規劃和它的變體。

23 Press， William P.， Brian P. Flannery， Saul A. Teukolsky， 與 William T. Vetterling. 《C的數值處方：科學計算的藝術》，Cambridge: Cambridge University Press， 1988. 數值算法的程序碼.

24 Reingold， E. M.， J. Nievergelt， 與N. Deo. 《組合算法：理論與應用》，Prentice-Hall， 1977. 在遞歸關系和二元樹方面的內容不錯。

25 Sedgewick， Robert . 《算法，第二版》，Addison-Wesley， 1988. 有著優秀論題廣度的初階文章。不重於分析，但是有很多圖。

26 Sipser， Michael. 《運算理論導論》，PWS Publishing Co.， 1997. 對可計算性及復雜性理論很好的文章。

27 Tarjan， Robert Endre. 《數據結構與網絡算法》，Society for Industrial and Applied Mathematics， 1983. 有一堆好東西的高階書。

課堂講稿

這裡有本課完整的課堂講稿。

——請下載相應文件查看。

作業

在習題集裡所引用的閱讀材料和習題是由課本《算法導論》，第二版內取得的，( 詳細的資訊請參考 http://mitpress.mit.edu/algorithms/  )。

——請下載相應文件查看。

測驗

這裡提供了本課的一些實際題目和練習考試。

——請下載相應文件查看。

字幕是pdf的，可以在這裡下載，我沒有下載下來打包，一來是我感覺我還聽的懂，用不著，沒有下載，另一全原因是，就是我希望大家都還能去MIT貢獻點點擊量，別人好不容易整理出來的東西，也許也想知道有多少人有興趣看吧
版權歸麻省理工學院所有，請勿轉載