eMule资源
中文名称：麻省理工学院-算法导论
英文名称：MIT - Introduction to Algorithms
发行时间：2001年
地区：美国
语言：英语
简介：
申明：该资源已经杀毒
杀毒软件：McAfee VirusScan Enterprise
版本：8.0.0
常驻服务器： DonkeyServer No1 (ed2k://|server|62.241.53.2|4242|/)
开源时间：白天不定期，晚上21:00-早晨7:00
这是麻省理工学院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/ )。
——请下载相应文件查看。
测验
这里提供了本课的一些实际题目和练习考试。