书部落-计算机PDF电子书之家 » 计算机基础理论 » 麻省理工学院算法导论（中英文版包括原版教材、上课笔记、测试、课后作业等）


2007-1-25 22:32 shubulo
麻省理工学院算法导论（中英文版包括原版教材、上课笔记、测试、课后作业等）

[free]
$H|HEt3o'[p"V~
p#J3u d:k 麻省理工学院算法导论（中英文版包括原版教材、上课笔记、测试、课后作业等）'Q*}iZD&v

b;U,Zfx |$yu}   
Ga d:lV5M} 【内容简介】 sAFC7M^(e
本书深入浅出，全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣，并保持了数学严谨性。本书的设计目标全\_sCQHnly

5a O;`A5f(Z1jo 面，适用于多种用途。涵盖的内容有：算法在计算中的作用，概率分析和随机算法的介绍。本书专门讨论了线性规划，介绍了动态规
^M"^g$H }%D 3q7O;ecj
划的两个应用，随机化和线性规划技术的近似算法等，还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算
H"w*yMsEnb
^#GF|9l/E*p\5|-k 法，以及对贪心算法元素的讨论。本书还介绍了对强连通子图算法正确性的证明，对哈密顿回路和子集求和问题的NP完全性的证明等
ac \`DDW5uJ"Q %Q#GQ,a#B$w
内容。全书提供了900多个练习题和思考题以及叙述较为详细的实例研究。.!Mj#r,qV!O'~#{6q)s6J
本书内容丰富，对本科生的数据结构课程和研究生的算法课程都是很实用的教材。本书在读者的职业生涯中，也是一本案头的数学参
Rl o O DR
7e1u&M{1j h2@ 考书或工程实践手册。
hxbl5v `A 在有关算法的书中，有一些叙述非常严谨，但不够全面，另一些涉及了大量的题材，但又缺乏严谨性。《算法导论》将严谨性和全面S;t6TVH~V.[
"})k(INl(@3a,c~1n
性融为一体。..
[0Pe\kAg 本书深入讨论各类算法，并着力使这些算法的设计和分析能为各个层次的读者接受。各章自成体系，可以作为独立的学习单元。算法
mK(Awd(F *cR}IW!SbS;O
以英语和伪代码的形式描述，具备初步程序设计经验的人就能看懂。说明和解释力求浅显易懂，不失深度和数学严谨性。,E;O+sBb"U'a#J
本书自第1版出版以来，已经成为世界范围内广泛使用的大学教材和专业人员的标准参考书。第2版增加了论述算法作用、概率分析与$_*h4] nkR@i

'm9QC6J6jrLq7_ 随机算法、线性规划等几章。同时，对第1版的几乎每一节都作了大量的修订。一项巧妙而又重要的修改是提前引入循环不变式，并在:I#kw3F$K%y

TD;[3B'Agp 全书中用来证明算法的正确性。在不改变数学和分析重点的前提下，作者将许多数学基础知识从第一部分移到了附录中，并在开始部^d#G.NWA|5l
s&R)s:oYLR;Db
分加入了一些富有诱导性的题材。... (L;Em+Z#Tl

yq(C@?*a 【作译者信息】 Vd"Y:s5rHq_

E,@E"Xm5]4obVj 作者:Charles E.Leiserson
+H|3[k$F:F)w ] Charles E.Leiserson 麻省理工学院计算机科学与电气工程系教授。 6N_+B+m$l i P U]

)i9d t%iaWh7|9I E 作者:Clifford Stein/Dc$Ga\b$o
Clifford Stein 哥伦比亚大学工程与运筹学副教授
gMVp#H
lT:l c0z/H 作者:Ronald L.Rivest5H!F3uF8L5m+C4j|D
Ronald L.Rivest 麻省理工学院计算机科学系Andrew与Erna Viterbi具名教授
??8p_(eF)X
m`R5qf9O 作者:Thomas H.Cormen
2l,Ip+X%I5k'I@5z Thomas H.Cormen 达特茅斯学院计算机科学系副教授 8o7K+s+sW \/P)b
[/free]/G$lV;ZcP

s#d J ut+Q6N
w d&B2J ^{ni#^ 解压密码：[color=Red]shubulo.com_al[/color]$K1S Jq&o }9h*[

:gB] _ k"_$IQ [fg]http://book.shubulo.com/book/theory/MIT_Introduction_To_Algorithms_2enE_CHN_EN.rar[/fg]
%@a^5qU,bjZbV
8zs Y@Hr,?t g$\ 网盘下载-请根据你的网络状况选择[color=Red]网通下载[/color]或者[color=Red]电信下载[/color]，
#dw7g+K[;~$G 不支持多线程，打不开网页时多刷新几次。。
+^4y.bqV [url]http://shubulo.com.gbaopan.com/files/78182d8f4a8e4bf1bfa81e89dceb9e24.gbp[/url]
"`-e x ?+Sh 下不了请直接去站务管理处留言，回帖管理员很难看到，谢谢合作
y7Z_j/`(\+tMUh ] ?+nm&KI
[dd]9211884[/dd]

2007-1-25 22:35 shubulo
关于课本的介绍如下：
~*o^cQt'fG@2DW
"s'Y@;c Q1n8ZoG 本书自第一版出版以来，已经成为世界范围内广泛使用的大学教材和专业人员的标准参考手册。本书全面论述了算法的内容，从一定深度上涵盖了算法的诸多方面，同时其讲授和分析方法又兼顾了各个层次读者的接受能力。各章内容自成体系，可作为独立单元学习。所有算法都用英文和伪码描述，使具备初步编程经验的人也可读懂。全书讲解通俗易懂，且不失深度和数学上的严谨性。第二版增加了新的章节，如算法作用、概率分析与随机算法、线性编程等，几乎对第一版的各个部分都作了大量修订。x(ST U!B]

a^/I3t'^&w%cE3V NN 学过计算机的都知道，这本书是全世界最权威的算法课程的大学课本了，基本上全世界的名牌大学用的教材都是它。这本书一共四位作者，Thomas H. Cormen，Charles E. Leiserson和Ronald L. Rivest是来自MIT的教授，Clifford Stein是MIT出来的博士，现在哥伦比亚大学做教授，四人姓氏的首字母联在一起即是此书的英文简称(CLRS 2e)，其中的第三作者Ronald L. Rivest是RSA算法的老大(算法名字里面的R即是指他)，四个超级大牛出的一本书，此书不看人生不能算完整。](YK;X0I)KVe

(aj*PL[7H 再介绍一下课堂录像里面授课的两位MIT的老师，第一位，外表“绝顶聪明”的，是本书的第二作者Charles E. Leiserson，以逻辑严密，风趣幽默享誉MIT。第二位，留着金黄色的络腮胡子和马尾发的酷哥是Erik Demaine，21岁即取得MIT教授资格的天才，1981出生，今年才25岁，业余爱好是俄罗斯方块、演戏、琉璃、折纸、杂耍、魔术和结绳游戏。
sJ,f*|l?VC6t&K -~,b qE*w.x*{F#t
另外，附上该书的中文电子版，pdg转pdf格式，中文版翻译自该书的第一版，中文书名没有使用《算法导论》，而使用的是《现代计算机常用数据结构和算法》，1994年出版时没有得到国外的授权，属于“私自翻译出版”，译者是南京大学计算机系的潘金贵。WDx^Q J0Z
H1Vhh$H,GPr

%oR*OOd"c1Y%y_o 参考网页
8h6rW.y2ni*DlSQ .{ r^c~"Op6K+UQ$r
该书在China-Pub的网址：[url]http://www.china-pub.com/computers/common/info.asp?id=6434[/url]
3jMxj},Yj 该书在Amazon的网址：[url]http://www.amazon.com/gp/product/026203293...5Fencoding=UTF8[/url]_)i9P^ Y1d:u
该书的勘误网址：[url]http://www.cs.dartmouth.edu/~thc/clrs-2e-bugs/bugs.php[/url]
ur#wC U&NZ 该书的一个在线学习中心：[url]http://highered.mcgraw-hill.com/sites/0070131511/[/url]
W*r'V*rL0Ks @n kT\o%M3X7}
该课程在MIT的中文网址：[url]http://www.cocw.net/mit/Electrical-Enginee...eHome/index.htm[/url]
C"@IVGg1a 该课程在MIT的英文网址：[url]http://ocw.mit.edu/OcwWeb/Electrical-Engin...eHome/index.htm[/url]
*h)uw s:R,Z"?
|$}h8[!\!YE&D3oC 5p_-c7\3Puk
--
%|Qb9^t ^xG.v!k1Od/\ b-N
Uv\l AEL
课程重点
:Id/WI/E [$h"f6wt n~0P
算法导论是麻省理工学院电机工程与计算机科学系“理论计算机科学”集中选修课程的先导科目。课程几乎将所有资料放到线上，包括了完整的课堂讲义和习题。课本“算法导论，第二版”，是由 Charles Leiserson 教授副笔。Yo|BP*EQSs
VmB ?%q9Sl%~!ad
Q\+J||
课程描述|4idwH
:A9`0|l Q.V0Ob
本课程教授高效率算法的设计及分析技巧，并着重在有实用价值的方法上。课程主题包含了：排序、搜寻树、堆积及散列；各个击破法、动态编程、偿还分析、图论算法、最短路径、网络流、计算几何、数字理论性算法；多项式及矩阵的运算；高速缓存技术及并行运算。
VD2xt;@ sn
u ]'{(]9Q+pC-M H0Q ;A*^9l'l6TNc1RW+C
一般资讯
Y[bEJ R _X 8UxE"o$Q TV-A
讲师：T?8FS8hJ:@2W Q]Mh\
Erik Demaine
ErQckq?6Qwm Charles E. Leiserson
q!EMk2s$g+N!T D3GB
y'V%@){"Lg-ZFvH SMA 讲师：`~z e,F&k
Lee Wee Sunc8M3sU'`0F9h
1m'`D] Ya

3WW:nb*GcR 课程目标与成果
z Lx [ ulk6w D2E[ GV#ZPldg
课程目标
.x;A!^.C_B#m/| 1v5e4^!ufB_!k
这门课程对学生们简单介绍计算机算法的分析与设计。完成这门课程后，学生应当能做到以下几项：:i?4L8P0@7\N

!Oz+N4i.oX{ 分析算法的渐进效率。
4| p+R0r*|9Ue A B c ?
,kmHw,V 演示对各种主要的算法及数据结构的熟悉性。.NM9K/h\7sZ&x f
5Ut I2kH y LT(_#T*f
对重要算法设计范例及分析方法的应用。
2\0eM~b5]M [Iu PX0B a r2h`
在一般的工程设计状况上运用有效的算法。~Y4Rz'M*p

h]nl"sD1T Rh"f&e q+}.w#gC
课程成果k6JhC%rL4|y!`+l

l[,_c}9qe&v0N 完成本课程的学生将会展现做到以下几项的能力
{R iHy$]C2vaf /]O:Ztm$I1\
用归纳法及回路不变量来证明算法的正确性。!D!B] k y/a

9GYRg2~D\"XuF@[ 用渐进法分析算法在最坏情况下的执行时间。比较由多项式，指数及对数函数初步组合之函数的渐进行为。形容最坏，平均及最好情况分析的相对优点。
|:QQ|F,gVh
hcr,w7{VI/~!Mun} 分析算法平均执行时间的概率。使用指标随机值与预期直线性来做分析。练习（这里的Recite是否是演示或是复习之意，换句话说，原句应该为：练习使用这一类分析的算法。后面出现Recite处皆同）用这一类分析法的算法分析。
F;@7j P]8|b
I(?D9C3M)Iy8h 解释随机化算法的基本性质和分析的方法。练习使用随机性的算法。解释随机化算法与随机输入的算法之间的差异。
Jym5P@8c0I,AH b x7Ng Q5Y ]m|
在适当的时机使用偿还法分析算法。练习用此方法对简单算法的分析。叙述偿还分析法的不同策略，包括计数法及可能法。 e0@ X'Ym3^
'wm*MD\
叙述各个击破法的模式和解释当什么情况算法设计会需要它。练习使用此模式的算法。实作各个击破算法。推导出各个破算法的递归描述。y'{#kw4n
P/Qh$m;M$`y
叙述动态编程的模式和解释当什么情况算法设计会需要它。练习使用此模式的算法。实作及分析动态编程算法。
uU'w H lY\Y
] ~H B.K_Y`'Zf 叙述贪婪算法的模式和解释当什么情况算法设计会需要它。练习使用此模式的算法。实作及分析贪婪算法。
.R^f QS
&U7k/CDs)?4^Npm5q 解释各主要的排序算法。练习这些算法的分析及它们所包含的设计策略。实作将排序做为子程序的算法。推算比较排序法执行时间的下限，和解释怎样可以克服这些界限。
2EbyD H:eC4xe
F1t2] ]G v7i-j| 解释实作动态集合的各大基本数据结构及对其动作的分析。练习使用数据结构的算法和了解它们的效率是如何依赖于所使用的数据结构。用增强已有数据结构的方法来实作新数据结构。实作将数据结构为重要成分的算法。
5~ p1t!^5N#B T DBoV
解释各大图论算法及对它们的分析。适时使用图来模拟工程问题。实作新的图论算法和使用图论计算为关键的算法，及分析它们。
zh!z-g(t+g.ld T I2r;Uf&C9o
举例说明在各个领域中所使用到的熟悉的数个重要算法，展现对应用算法安置的熟悉度 - 如计算几何，作业研究，安全与加密，并行与分散计算，操作系统，及计算机体系结构。
~%|v$M2K0x
Q$Q#Q{KmS7e
+H9U9\c{OA'N/ho 远距离教学/{.Kn*y2Ow$kr
8?+d1s L&l;vd
这们课程会在美国麻省理工学院教授，同时也是新加坡SMA (Singapore-MIT Alliance) 课程的一部分。无论是授课，演示课，习题或测验，这两个国家的课程在各个方面来说都是相同的。在麻省理工学院所有的讲义都将是现场教授，这些都会被录下，数位化，由本课程的网页提供给新加坡的学生们。这些数位化的课程也会提供给麻省理工学院的学生。李教授会参加本课程的管理，与 Demaine 及 Leiserson 两位教授一起写课程相关资料，及带领 SMA 的学生的演示课。7X"A#zAg^]xo

:r PX4z2\ j^q R/_K%nXC4lo)y Bk
先修条件
%~8N)P*Me
[-`O1uC!b 对程序设计有很好的理解度及在离散数学，包括概率学有扎实的背景，是本课程的先有条件。*^X$n zy(os
U:Tj+kG[ G5@
麻省理工学院学生： 本课程是麻省理工学院电机资讯工程资讯理论之集中选修课程的先导科目。在选修这门课程前我们认为你应该先选修 6.001 计算机程序的架构与解译和 6.042J / 18.062J 计算机科学数学，及在这两门课得到 C 或更高的成绩。如果你还没有达到这些要求，你一定要在注册本课程之前与助教沟通。
Tj*X(I;i)]"\h O"J
}Ah k2a6^%c
/qCh6@a6F 授课
Vh'M0CP5I0C9fg3N nXH*pa9b
每周2节
$A y7j:^*K(F 每节1.5小时] u\)\]:s

e t#h"xBH }+xy:s` 课程内所提供的资料，包括讲师们口述的讲解是你的责任。4i$F!z_E8z+lNAQ

iUeAWL$e"u,}6OZ8b#y!i "Py Yim0k%sJ
演示课
#n3hm&t6`1I kp gm A(\)`R;C
学生每个星期要参加一小时的演示课。课程人员将会排演示课的时程。你要负责演示课时所报告的内容。演示课的出席率一直以来跟考试的成绩有紧密的关系。演示课也是给你一个更直接的机会来发问和与课程人员互动。
%Xe(Wm/i2d \ c9l]e!c;[
麻省理工学院的学生们： 麻省理工学院的演示课会在每星期的最后一天由助教来教。讲义 3 请你在本课网页中的报名纸上填上你所选择的演示课分组。课务办公室出的演示课作业是无效的。
0L8V Php`
mW:F.Q&|n"H5[-x
a4J;G-v~{;i` 讲义
D `%{ z.`d]Q xG lqD+XbhkRS
多数的讲义会使用方便打印的格式放在本科的网页上。学生们应该由网页上下载并打印这些讲义。当有讲义上线时你将会收到 e-mail 提醒你。e-mail 的内容会告知哪里以及什么时候那些少数没有放在网页上的讲义可以被找到。]o.c!|%M/y$E7T

P0z*E `&z"^%G%o oe1GP/O,j
教科书2u1K2klo.p5f
i C*z;sY"e
本课程主要的书面参考是由 Corman, Leiserson, Rivest 及 Stein 教授写的教科书《算法导论，第二版》。在之前的学期本课程是用了这本书的第一版。第二版彻底修订了前一版，这已使得第一版不再适合作为一个替代品。
y:j,\!Ru D Ef){Z|
麻省理工学院的学生们： 这本教科书可以在各个线上或附近的书店购得。%UP6Vp1l6Qh GX*M/rL

ueCT0C`};g E&d/|} FkP7e
习题
+zDC~2v(Xa;}c0O
;FW`4^ CD2UD.p_ 在学期中将会指定 9 次习题。在课目时程表及讲义 2 里分别有暂时的作业时程和截止日期，但是真正的截止日期会写在习题上。_1L^_~~I}
Xm%ff-jQ6{g
通常来说迟缴的作业不会被接受。如果有能令人谅解的情况，你应该提前跟你的演示课指导者做出安排。
w Zj{)l {r"_1}$S#}
麻省理工学院的学生们： 如果先前的安排发生了变化，那么将由院长办公室作出解释。+wH:w*Ic\
,t_0Q+c~*U I
因为每题可能被分别评分，所以每一题应该要写在单独的纸上。在每张纸的顶端写上以下：
p.sTF[-x 'v8Y/wZF"jU/n hz
- 你的名字PV `}g}m
- 该堂课讲师的名字R.g N0I:@~6L6sN:Iq
- 习题号码
k]4X9V$f!NS.FD] - 一起解题的人(参考 14 段)，或“合作者：无”如果你是完全一个人解答的话。
&RqtL!ef0y;U1B:`
3Z E7i3lgm 麻省理工学院的学生们：
D0GM,p9gO)b+VG 你必须要将你的答案写在三孔活页纸上，教科人员会将它们装订起来以免散落。此外，你可以很简单的将那些被评过分的作业加到你的活页笔记本内。
0f`HH"Ln/U'V,I v Q6?a/ci
在你写答案的时候应该要尽量清楚和精确。我们希望你的答案容易理解与正确，因为技术性资料的沟通是一项重要的才能。
5zAe+BRE 6d8Kh[? V,^J
一个直接，简单的回答比迂回的解答值更多分，因为它更简洁易懂同时也不易于犯错。较懒散的答案就算是正确的，也会得较少分，所以确定你的笔迹清晰易读。将你的答案抄写一份再交是一个不错的主意，这不但能让你的作业更加工整，也让你有机会能够检查及修正错误。#e!HF7DG@:a'oJ

(tvA!Nj[!A 习题中有包括一些应该要解答但是不用交的练习题，这些问题是用来帮助你更掌握课程内容以及在解答指定习题将会有用。习题范围内的材料会在考试中被测到。ej^*`7y"Jd
q;xS/Ux;Hv(mo

)Xv.E l9}p0D.\ 算法的描述"w^2}xE!b3{A3u

TC Z4nbX2WJ 你经常会被指定“用一个算法”来解决某个问题。你的写作应该是以一个短文的型态。应该有一个标题段落概述你现在要解决的问题和你的解果。你的本文应该提供以下部分：
E _ N$[(Vlgq
)J} s6L6EG-NBN 1. 算法的英文描述，如有帮助的话，用伪代码(pseudocode)。dq}6uR?
2. 最少以一个工作例子或图表来更明确的显示你的算法是怎样工作的。
lL2VH v+m1GK/`4~)k 3. 算法正确性的一个证明（或表示）。 k kW{AYW8\v
4. 算法执行时间的分析。XCq \N&q$Fr3CH.e

u[&B"~}IQ 记住，你的目的是沟通。评分者会被指示对迂回愚钝的描述扣分。%Bo{/ppS \3R
mA"vY'b?T
%u6rR9p W5U
评分规定
)CNJ'y3@n| g ?
cqt.QX,DQ&C+qV 最终的评分会基于习题(P)，一个随堂考(Q1)，一个家庭作业(Q2)和期末考(F)。习题全部总值是80分左右，随堂考也是80分左右，携卷回家测验是150分左右，而期末考是180分左右。4d#HeA$|Z6x N
3PR:`)u@@
虽然习题只占你最终分数中的80分，你必须要做它们。aW8P5}C

)t0^+J'De%} wo 下表列出了不做习题对分数的影响：q ?9PJx]2rQIY

?&_7i zc!r5BvG 跳过习题的影响
i8Pqx&j5P4K$l ;tI#M%?$I p/\
--------------------------------------------------------------------------------
5wl*HK6v3[&C;f+X"IRL 0 无
+Y!K8T:Kx.v/t#^ 1 百分之一个整级分
m9kB.Q6J 2 十分之一个整级分
;puo,c-g 3 五分之一个整级分/bjR&u4zS:|.L
4 四分之一个整级分
4fl|I._ 5 三分之一个整级分VsF2}4u:pckx
6 二分之一个整级分a+e Hn;B&P
7 一个整级分^bvY:]&l
8 两个整级分r KB3Uul-^
9 或更多 不及格
.W'YONL4LU t'p S-_n
c*K*N.sP5U1T 请注意这张表是列出了跳过的习题数，而不是整次的习题。具体的评分规定会依当时的需求而变动。p2_?5J`cS"Uu
\G h)tr6LpBh"r

&V:t5Yvw$A8R,JCH 合作规定
l;g8|"Jl ;Y:vLH0nG
家庭作业的目的是让你有练习掌握课堂内容的机会。因此，我们鼓励你合作解题。事实上，通常组成学习小组的学生会比那些独自读书的学生考的更好。但是，如果你选择加入学习小组，你要靠你自己和你的小组来负责准备小组聚会。更具体的说，在这之前你应该花30到45分钟试着自己解每一题。如果你的小组不能解答某一题，试着跟其他小组交流或问导师。4o`hH/s} e-AV

B$\fig&V!@xn 虽然你跟他人合作解答题目，但是，你一定要不受任何帮助而独自的写下你的答案。我们要求在你的习题上写下你合作者们的名字。如果你没有跟任何人合作，你应该写下“合作者：无”。如果你的答案是由研究而来(例如：互联网)，注明你的资料来源，但依你自己的方法写下答案。 IE4yPt~
+A2s#Y4U:~+A+o
在考试中不允许任何的合作。本课程的第二项考试是一个可以带回家的测验，虽然你将被允许以几天的时间来完成，但它必须是完全由你独自完成。关于回家测验的合作规定的一些细节将会安排在第三十五次讲课上。请注意这课将会是考试的一部份，是强制性参加。
X,}:D3aF5bG ha
*[+{zvte 抄袭和其它反知识性的行为在任何一个以个人成就而自豪的学术环境内是不能被允许的。如果你对于合作规定有任何问题，或者你觉得你可能违反了规定，请与课程人员联系。虽然课程人员有义务适当的处理作弊情况，但如果是违反者本人提出而不是第三者检举，我们会较通情达理及宽大。7Fk2b&Ui q i H
Pc7OG&T%z I,tI

lpcf)kJ [ 教学时程
hvf J#~)A-jN
*ZOa#P8Yn+@kCP 这份时间表提供了授课，演示课题目，作业，测验的日期，及指定要从课本“算法导论，第二版”内阅读的课文。4TaWR#I^6Bs
:PQ B%W,HT
1 第一课 课程细节；序论：算法分析，插入排序法(Insertion Sort)，合并排序(Merge Sort) 阅读：1-2章
*]Gm+ady SRuJ 发测验 0
3r~o'G(B,b7u C
6E2IL(\0iAE 2 演示课 1 算法的正确性
m\2_9[!]?BY 发《作业 1》UlU3m\nB ]t

B;Eb7|'`%s.agw 3 第二课 渐进表示（Asymptotic Notation）。递归公式（Recurrences）：置换法，迭代法，主方式:MFJD:lg
阅读：3-4 章，除了§4.4o/{? |!E

y8?yt4[G2F'u%U(N&Vk 4 第三课 各个击破法： Strassen 算法，费氏数列，多项式乘法。? r#dlAMd
阅读：28 章第 2 节，30章第1节${XYV"T:wh-~ t\@C

]q"`W0c$n5h n Qqp 5 演示课 2 递归公式，松散性/lyU4{7e#v
阅读：Akra-Bazzi 的讲义'lA0@8Y%g!Oi7Y

1B }[:U8| B5\p j 6 第四课 快速排序法，随机化算法
8{.m(ysx.i]r 阅读：5 章 1 到 3 节，7 章/bvO.mFEcHe
收《作业 1》发《作业 2》
bz.|1`\ ZVe{,@*E'w5R KR
7 演示课 3 排序法：堆积排序法，动态集合，优先队列
(T/D&lgDvs 阅读：6 章6Zd'iSQ4Sr+[
q.M2c pdmH9v!J
8 第五课 线性时间的排序法，下限，计数排序法， 基数排序法)b y q1o@(t1z%z
阅读： 8 章第 1 到 3 节
-J2d!Q"^,v'RV TPB 收《作业 2》发《作业 3》
T'|,R-Nu-@XUR
h:IGm5J9n&~ 9 第六课 序列统计，中位数
7q0O Y4A@ 阅读：9 章 _ NW0OXI

[msk;P+D}%_ 10 演示课 4 中位数的应用，桶式排序5C"IH&H@NZ\
阅读：8 章第 4 节
-{/V7}j(T
{Kh3uC,b Db 11 第七课 散列，通用散列#e0dY-f*o5J
阅读： 11 章 1 到 3 节c7S$sh9`
收《作业 3》发《作业 4》
\ g9{k'i3? VS
w8O)Y^:`J` 12 第八课 散列函数，完美散列5bj E'\VtG-e
阅读：11 章第 5 节j#_4w'j4L2Oe.|;I_0^DA
4}9}TJ+Wm2uZ-m}
13 演示课 5 测验 1 复习
7\,C6Sdf+{t 收《作业 4》p1m&i*H N~5ic
s5{!YsNe-_@x]`+w
14 评分后的作业4可以在中午拿到
*f'b6l+~$C K
zFD ]-b!dPbp 15 测验 1
&OaG+\$w2oD+M
:[Yq3RW!JO 16 演示课 6 二元搜寻树，树的追踪 kuM,L(Mc6`#|
阅读：12 章 1 到 3 节K,LbbX/i-M4P9b
`Yx]To!{+J E
17 第九课 二元搜寻树和快速排序法之间的关系；随机二元搜寻树的分析+Vm&]H/t
阅读：12 章 4 节
(MRga8g 发《作业 5》
cmF*Vh1s-G
d@w!zeE U{ 18 第十课 红黑树，循环，插入，删除0Yt5Ch;~5u/K
阅读：13 章 ]/S)iqF9@[ S [ t

mFz o!T @C0YPr 19 演示课 7 2-3树， B-树 K,Cf`S,B
阅读：18 章 1 到 2 节
mM~Q5y5nUk
+W$r6C+C3D)e(s 20 第十一课 增强数据结构，间距树5e_/h3A9D P:?-V A
阅读：14 章
&?8U n2GJc1v^ 收《作业 5》发《作业 6》4@1b-M7H"k5z'}

\wU3H^ 21 第十二课 计算几何，区间查询6Y`M q d)u&]
阅读：33 章 1 到 2 节 HD rz5f.gX\@^
Tg Lp)EE5t/c
22 演示课 8 凸多边形:HE-}Zy
阅读：33 章 3 节
k"bc&Z \.^T0{ I*r$vt!x#KK-s
23 第十三课 van Emde Boas，优先队列
P(v(H%Z0yr 阅读：van Emde Boas 的讲义l7]x-Q&z
收《作业 6》发《作业 7》2uj QIc0ATMx
c!UD)U(d&f|n
24 第十四课 偿还算法，表的复制，可能法
*eXH6e0H%a9rP] o 阅读：17 章K{.S4^:g,W R__U

t,e;ssZ4k 25 演示课 9 竞争分析，自我排序列
@2n |7bw9iw m S*]k-a4t!z
26 第十五课 动态编程，最长共同子序列，最优二元搜寻树
8c:x?:B JHP 阅读：15 章
u3L(b!y2w f7v 收《作业 7》发《作业 8》
&p8w)E7utbn j}X5KzVZu-U
27 第十六课 贪婪算法，最小生成树
$xS7va/rI l;W7C\ 阅读：16 章 1 到 3 节， 23 章
2rpW n\zg J ?)V8vF@x ?
28 演示课 10 贪婪算法和动态编程的范例
QA\F$Uh1f
u`(Cq3r 29 第十七课 最短路径，Dijkstra算法，广度优先搜寻法cSXb:\'w6b;N
阅读：22 章1， 2 节；第 580 - 587 页，24章 3 节Z|J$hC a
收《作业 8》发《作业 9》Fy Kh;A%s)Lz
%w"kQ(s }:vc
30 演示课 11 深度优先搜寻法，边的分类-gCz-K)b+akr x$O5i#@
阅读：22 章 3 到 5 节
,N(},q IA^ @O
AJ.B.NT(uJ~#y"l'p r 31 第十八课 最短路径，Bellman-Ford，DAG内的最短路径，差异局限
&])]:I7T |x | O3l C 阅读：24 章 1, 2, 4, 5 节8ch`.j+eE

7s4zaM6w V eV.T C3? 32 第十九课 全成对最短路径，动态编程，Floyd-Warshall，Johnson 的算法
G0V;t;_M Q&e1n/JT 阅读：25 章
(y#r#E6}!q-j 收《作业 9》 E:[%D%nB'fm2DF*h4f k
y|QA%a6N @ J:X
33 第二十课 零散集合的数据结构
2h6^h%x?k/C 阅读：21 章i%aA#U!P0r2Rc9_
{Q,d-|K&^Dy(h
34 评分后的作业9可以在中午拿到
?*z7|'I-u `'n K wX$Mk!w(Z ?;V
35 第二十一课 带回家 发下 测验 2 ; 道德，解决问题 (强制参加)^ D4n-Ti
发测验 2!\ a+x7~1N
PV0g5H_a6D7D
36 没有演示课 - 解答测验 2!4^!V;OG NPh

G'Qq~ w| tM 37 没有课
SHK3rgIZI 算法程序比赛开始 (非强制参加)
vgB7q,C1q d*Y 收测验 2
;Q3[.mDC~;|c
0^*j(z8v xHx 38 第二十二课 网络流，最大流量最小切割论
7I,D&@7H0`C;Drw"p 阅读：26 章 1 - 2 节
*ud~,I3OIN 发《作业 10》 (选答)&z(l7^(T&lv

{$B5^(_5z&] 39 演示课 12 求对集 (注：最大二分图求对集)
,q)O4Z!C[ `;i O 阅读：26 章 3 节
9_#b c{Y
1w8S&A7y Sh&C 40 第二十三课 网络流，Edmonds-Karp 算法
:Wke4BpUD0C7e 参赛答案截止
0IRllD
+i/O?.d@2bl 41 第二十四课 随堂测验；比赛颁奖；后续课程的讨论sg? ias N2TO
《作业 10》解答Pp_K,X(H8iN

{r cd8}{(Kl
,E1CO I4|^ 相关阅读资料%s0h`_w&R @tY$g0|
np#O4p4?%Yl5p
以下是对本课程有用的参考书。s[N|w+Qhr

#v!i7` e2g SD)D%m 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.
v-k A#Px4gu*|$k u.~
!nwAo0T5^!w4p:p 2 Aho， Alfred V.， John E. Hopcroft， 与 Jeffrey D. Ullman. 《数据结构与算法》（Data Structures and Algorithms） Addison-Wesley， 1983. 重新改版过后是以前作《计算机算法之设计与分析》（The Design and Analysis of Computer Algorithms ）前六章所改版的较基本版本。2]%LW | RUg'K _

c_Ecg 3 Baase， Sara. 《计算机算法：设计与分析导论，第二版》（Computer Algorithms: Introduction to Design and Analysis. 2nd ed） Addison-Wesley， 1988. 普通参考，尽管它的说明有时是潦草扼要的。
5t*pNt4\aB*?:r h6E @!ME R'HO
4 Bentley， Jon. 《程序设计明珠》（Programming Pearls） Addison-Wesley， 1986. 算法设计在软件工程中的实用。（Programming Pearls 繁体中文版, 译者：许鸣程，出版商：基峰，出版日期：2001-11-22，ISBN：9575668804）
\*`"`R`@kY +WObM hb
5 Bentley， Jon. 《更多的程序设计明珠》（More Programming Pearls） Addison-Wesley， 1988. 更多算法设计在软件工程中的实用。{$d _4qz/ZY%Pt~

!L8UK#Aw \7\V x 6 Bentley， Jon Louis. 《编写有效率的程序》（Writing Efficient Programs） Prentice-Hall， 1982. 非常杰出的效能精进调整。_m[Ls

0C4N.h$pi0mT+~^I 7 Brassard， Gilles 与 Paul Bratley. 《算法：理论与实践》，Prentice-Hall， 1988. 很好的范例及习题，着重于方法而不是个别的问题。
QZtv*{0fNg
Y#s!f"w1`r 8 Chung， Kai Lai. 《基础概率理论与随机过程》，Springer-Verlag， 1974. 对概率直觉性的演示课。gxaC!{(v;])@
Sq*P4m@
9 Even， Shimon. 《图形算法》，Computer Science Press， 1979. 对图形算法有广泛的论述，包含了网络流及平面性。;`:M"S-g;M4pR&@

'G5~)eS-c3}"R8z 10 Feller， William. 《概率理论导论与应用》，John Wiley & Sons， Vol 1. 1968， Vol 2. 1971. 对概率很好的参考。
5T1a;s_A#x#n J*H*^
m^)A5L/R A_g-? 11 Garey， Michael R. 与David S. Johnson. 《计算机与难驾驭性：对NP完整性理论的指南》，San Francisco: W. H. Freeman & Co， 1979. 专注于NP完整性的参考书。在后半部含有一份NP完整问题集的列表及在书中出现过，针对多项式时间特别情况的算法的参考。a?&p&o r+E4G

%bk uH&B h&vF 12 Gonnet， G. H. 《算法与数据结构手册》，Addison-Wesley， 1984. Pascal 及 C 码， 真正执行时间的比较，和对研究报告中分析的指示。
p Y(KIz.}![;^
#D+OEG{2{5n5YY2F 13 Gusfield， Dan. 《字串，树，与序列的算法》， Cambridge University Press， 1997. 操作字符字串及序列的算法的大概论述。;K6HLI i$d

D+{6md(@4^ 14 Horowitz， Ellis 与Sartaj Sahni. 《计算机算法基础》，Computer Science Press， 1978. 择重介绍了数据结构，动态编程，以及分支与界限法。
1qt U0{v%Oq
EL wR(\G&d7s)? 15 Kingston， Jeffrey H. 《算法与数据结构：设计，正确性，分析》，Addison-Wesley Publishing Co.， 1991. 一本优良的数据结构导入书，关于算法正确性有一篇不错的章节。
'\0Hk4?9{pb
6j{Z%X9N7N$U.Z 16 Knuth， Donald E. 《计算机程序设计艺术》，Addison-Wesley. 三卷如百科全书般的作品：(1) 基础算法， (2) 半数值算法， 与 (3) 排序与搜寻。:[Kg ]V7FI3MF}2R'X

yN2oN2F'] 17 Lawler， Eugene L. 《组合式优选》，Holt， Rinehart， and Winston， 1976. 图算法（密集图)，网络流，与线型规划。开始几章是很优秀的。EUq;UF,z#j2}'d zb

U(j i1MB(]q2a:| 18 Liu， C. L. 《组合数学导论》，McGraw-Hill， 1968. 与计算机科学有关的组合数学。有优秀的习题.V v;s{/Y9^(]
/_nK(h`4R2XY!S
19 Manber， Udi. 《算法导论》，Addison-Wesley， 1989. 着重于创造力的初级文章。
H Z8T:j6d?A5p&v h~4^E|
20 Mehlhorn， Kurt. 《数据结构与算法》，Springer-Verlag， 1984. 三卷： (1) 排序与搜寻， (2) 图算法和NP－完整性， 与 (3) 多维度查询与计算几何。基本及高阶论题的讲义。F u-TUoV~

;u,Ty/COtR 21 Niven， Ivan 与Herbert S. Zuckerman. 《数论导论》，John Wiley & Sons， 1980. 有阅读价值的的数论入门介绍。 WFA0d!W

L F#VJ-i-A;g!d 22 Papadimitriou， Christos H. 与Kenneth Steiglitz. 《组合式优选：算法与复杂性》，Prentice-Hall， 1982. 线性规划和它的变体。;dDV#e^
%o4EYR3H$x~W
23 Press， William P.， Brian P. Flannery， Saul A. Teukolsky， 与 William T. Vetterling. 《C的数值处方：科学计算的艺术》，Cambridge: Cambridge University Press， 1988. 数值算法的程序码.(IZ5V2z*O,q0d+`
rL0Y[%D
24 Reingold， E. M.， J. Nievergelt， 与N. Deo. 《组合算法：理论与应用》，Prentice-Hall， 1977. 在递归关系和二元树方面的内容不错。3Wi6h9WY2@1]|
F9A'[W y t
25 Sedgewick， Robert . 《算法，第二版》，Addison-Wesley， 1988. 有着优秀论题广度的初阶文章。不重于分析，但是有很多图。1S{/b2c~oQ*m
8o1?6ibg'pV
26 Sipser， Michael. 《运算理论导论》，PWS Publishing Co.， 1997. 对可计算性及复杂性理论很好的文章。
oq#FJ ~:[(?;AI;v4N9o
7jFkW|1L 27 Tarjan， Robert Endre. 《数据结构与网络算法》，Society for Industrial and Applied Mathematics， 1983. 有一堆好东西的高阶书。
!V;jY2t^a p#q?y 4{9R3F!G,ac%p

H%Ut_,Y 课堂讲稿
I W+]n n0J o ^.icP7U C7d
这里有本课完整的课堂讲稿。
,{k(Zw@~
q*dsk8L5|%^ ——请下载相应文件查看。
SoR6AA(}n }
%a6h c(qG'dwp-? r(C1Tw"vHJqn
作业
a7W%IjZ-}Qps )L W'S.W"ZJ2o
在习题集里所引用的阅读材料和习题是由课本《算法导论》，第二版内取得的，( 详细的资讯请参考 [url]http://mitpress.mit.edu/algorithms/[/url] )。
yj&fH,jd h!k |\L|
——请下载相应文件查看。)dW-Ie,v'e8L4F2~%n]
'd3TuBi s

,\$WU]!k(`8| 测验:Rg8I.JK1W6S
Ia@)HXj
这里提供了本课的一些实际题目和练习考试。
q)on0}J]
:W.^wtD ——请下载相应文件查看。

2007-1-25 22:38 shubulo
走进算法——小评《算法导论》.Ay4z\8OO@
SbC,gkrpt
　　 “程序=算法+数据结构”这式子我们都知道，可是却又不是很“知道”。越来越高级的程序设计语言和集成开发环境帮助我们进行快速的软件开发，代码自动生成机制和封装良好的组件技术使得我们可以像搭积木一样构造系统。于是我们开始对数据结构和算法生疏了，转而跟风去学习这样那样的编程语言。很多本科生正是因为这样的原因错过了打好坚实基础的大好时间，在技术的海洋中迷失了方向。于是，多了很多有趣的问题，譬如语言之争、平台之争……甚至还没有开始系统掌握一门语言之前就开始考虑是学习Java还是C++，PHP还是CGI……当然现在又多了c#、Ruby、Python等等等等。舍本逐末的做法明显愚蠢，可我们恰恰是乐此不疲。
:}7d/RA9y N+i N&oj/]'a-c@*G1r"d
E,ek'\2m
直到真正开发项目或者做科研的时候，才意识到自以为了不起的编程技术并不足以应付真正的研发需要。其实很多很多的软件开发恰恰需要扎实的理论基础知识，如何高效地处理并发任务，如何应对高负载和阻塞，如何解决系统瓶颈等等。很多的系统其实需要我们绞尽脑汁，找到一套切实可行的数据结构和运行算法。而IT技术职位之所以还处于高薪之列，正是因为需要更多的基础知识扎实、拥有创造性能力的开发人员。君不见，现有的IT技术职位的笔试和面试涉及越来越多的算法和数据结构方面的知识。我身边也有众多同仁开始意识到自己上学时候的欠缺，纷纷恶补数据结构和算法分析。 uJ.tj:\Cd
1@at*@DF*b2R j,^c
|\#d.\ b)E,g

r aWwK,oa8E 如果有人要我推荐一本系统研习算法的图书，那我会不加思索地选这本《算法导论》。有人说这么多的算法书籍，为何要推荐这本。其实，和介绍各种开发平台和程序设计语言的那些抄来抄去的书相比，算法类的书实在是少的可怜。在如此有限的书籍之中找到一本最好的还是相对比较容易的。我钟情这本书的原因如下：v+Cs&Z0?b)J.E
;]a b,rk
e/n h:N } h3rz
l0w@2i:L x
1．这是一本科班教材。数不清的名牌大学采用了这本书作为计算机专业的算法教材，其中包括卡内基•梅隆、麻省理工、斯坦福三所公认拥有全世界最顶尖的计算机科学专业的学校。所以这本书是可信的、严谨的、科学的、经过检验的。同时，课后习题的存在，可以帮助我们检验自己的学习情况。{ f C#V]/K

rU's9ttW6m ySf3bs/q F f&rW5|
b} tl&n s SejF
2．这本书的涵盖范围相当的广。由易到难，几乎囊括绝大部分主要的算法分支。如果想通过一本书就系统地学习算法分析与设计课程，那么本书显然是最佳选择之一。当然也有《算法导论》一书没有涵盖的方面，但是，确实已经相当广博了。
*iES.D b.`1^
.T N&yi/R
7K#Le&P'Z!h bbcn+L u8f
3．这本书具有一定的深度。不同专题的讨论具有相当的深度，基本上从分析和设计思想方面来传递知识体系和方法论，引导我们建立自己的思考方式。单靠学习到的书本知识肯定是不够的，但是通过有一定深度的训练，我们可以学会如何进行算法的分析与设计，不至于浮在面上。'Tg ~)DBKg
fB6O$F%aN

qecy4S
7DRs |7z \!y 4．综合以上：既有深度又有广度，同时保持科学的严谨性的一本书，以我目前的阅读经历来看，只此一本。当然，有更好的书，即高德纳（Knuth）的《计算机程序设计艺术》。但那是大部头，至今还没有写完，全书七卷才刚刚进行到第四卷。而且就已经出版的四卷书来看，想要读通这部书，没有两、三年功夫还做不到。我表弟是专搞OI和ACM的，以他的投入程度，一样是读了一半《计算机程序设计艺术》就投入了《算法导论》的怀抱。所以我会推荐《算法导论》。至于《计算机程序设计艺术》这套书，等学会了这一本书后再去研究，也还是很大的工程。
#lCNw;uc
9K/AY9cy
#E|O9^k R @u m0|7Mu6I.^
5．适用性好。《算法导论》除了具有教材的系统性外，同时在安排结构的时候也充分把各个章节独立起来，使得读者能够有选择地阅读自己需要的内容。在附录中还提供了必备的数学基础知识介绍。初学者作为教材，程序员作为参考书，应试者用来突击复习，都是不错的选择。同时，全书使用伪代码进行描述，没有语言上的差别，也扩大了本书的适用范围。6}|hS]/C{
g:a*G x+L"h,`

8j!}*l ?]x~u kVB)Oc@O
6．选择一本书当然是为了更好地学习，《算法导论》的另一个优势就是，MIT的开放课程计划为广大求知若渴的青年们提供了与本书配套的视频教程、课堂讲稿、课后作业、测验和教师参考。让我们有机会获得更好的学习效果。（该课程在MIT的中文网址：[url]http://www.myoops.org/cocw/mit/Electrical-Engineering-and-Computer-Science/6-046JIntroduction-to-AlgorithmsFall2001/CourseHome/index.htm[/url]。该课程在MIT的英文网址：[url]http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/CourseHome/index.htm[/url]。VeryCD提供的Emule课程下载网址：[url]http://lib.verycd.com/2006/03/02/0000092463.html[/url]。）
@'`D0y[6UrW
?|8_!}"~ R+@ f$jD ` w&OZ5yrO!U b
v)Yap$QG
当然本书也有一点不足。其一是书后习题没有答案，这其实在算法学习中很恼人，同样的问题会有很多不同的解决算法，初学者无法知道自己是否已经掌握了解决问题的较好办法，好在MIT开放课程中会提供部分答案；其二因为教材的本质，使得阅读的趣味性相对降低，至少不具备畅销书（例如headfirst系列）的幽默感，同时在举例方面也有所欠缺，有时理解起来不是特别顺畅。但是算法研究就是如此，需要专注和投入，同时在目前的图书市场上，这本书已经是不二之选了。我第一次拜读的时候还没有中文版可以阅读，啃英文版的过程对我来说也是充满了乐趣。现在有了中文版，实在是件值得庆祝的事情，应该可以帮助我解决当时对一些句子的困惑。中文版的译者们，其实很早以前就翻译过本书第一版的内容，大家可以查阅《现代计算机常用数据结构和算法》一书。因此我对这次第二版的翻译质量是很信任的，并在第一时间购买了中文版收藏在自己的书柜之中。
8H4l6^:s|u9@&sf 1QW`.o v hFv
k1K H d%]F J|*v

K_Hfx8s!zf s 如果想用2~3个月的时间系统地学习算法分析与设计，如果想要短时间地复习一下算法知识，再次的，郑重向大家推介这本《算法导论》。不仅仅是因为个人的喜爱，同时这本书确确实实是一本不可多得的计算机算法方面的经典教材。最后，要感谢机械工业出版社华章公司和几位译者，感谢他们在计算机技术略显浮躁的今天能够带来这样一本理论巨著的中译本。

2007-1-26 21:45 大唐汉人
hehe 我也开眼界了啊

呵呵
zNMsn+V6R^ 看看啊 学点东西

2007-1-27 16:32 today66
靠！^n1gI)K"H)q;_7SW
付了币下载不了！！
)vM"i|L1F2F1z x0b&C 没信誉！！

2007-1-29 15:05 rabbitbear
骗子
a2GR2eS vLE 根本下不了！！！！

2007-1-29 18:57 shubulo
[font=黑体][color=Red][b][size=4]你好，因为放这本书的服务器出了点问题，请过段时间再下，到时不会再重复收BBVmR2U;M

'f/@;G,B/r*FN;C i,V+o6q&n G cY @
已经恢复~
J*[ L-i'O_1S,sJ [/size][/b][/color][/font]

2007-1-31 17:57 ngloom
回复 #7 shubulo 的帖子

5555555.....:'( :Q

2007-2-2 09:38 baodingwzf
学习

可以下载，只是速度稍慢。

2007-2-5 22:51 sfl80
密码是多少？为什么没法打开？:o

2007-2-6 17:30 shubulo
[quote]原帖由 [i]sfl80[/i] 于 2007-2-5 22:51 发表
,Z2|j'n6MY2X^ 密码是多少？为什么没法打开？:o [/quote]
4N:LOjDbN-[n;E
5U$|!P6p0K_$be7H1XfR 你好，本站默认解压密码是shubulo.com
`]rT~*h_ 压缩包说明上写着的:L

2007-2-7 00:56 kakatokaka
下载成功。多谢多谢！

2007-2-7 17:26 sfl80
谢啦！！！:lol

2007-2-8 15:37 ethan5500
中文的是第一版的啊，有第二版的吗

2007-3-7 09:12 cyjfs
有没有中文版:) :)

2007-3-10 18:52 tecycheng
fhduyrtyrtyttretyry

2007-3-17 11:58 Charliex
楼主介绍了好多资料呢，谢谢楼主

2007-3-17 17:36 roycia
好东西

好东西能够看看长学问

2007-3-18 17:06 tonyli
很好.woxihuan

2007-3-22 21:49 特兰克斯
今年要努力了,准备参加学校的算法设计比赛,这个很有用的,谢过楼主 \/z8?qD
大家共同进步

页: [1] 2 3 4 5
查看完整版本: 麻省理工学院算法导论（中英文版包括原版教材、上课笔记、测试、课后作业等）


Powered by Discuz! Archiver 5.0.0  © 2001-2006 Comsenz Inc.