麻省理工学院-算法导论

麻省理工学院算法导论关于课本的介绍如下本书自第一版出版以来已经成为世界范围内广泛使用的大学教材和专业人员的标准参考手册本书全面论述了算法的内容从一定深度上涵盖了算法的诸多方面同时其讲授和分析方法又兼顾了各个层次读者的接受能力各章内容自成体系可作为独立单元学习所有算法都用英文和伪码描述使具备初步编程经验的人也可读懂全书讲解通俗易懂且不失深度和数学上的严谨性第二版增加了新的章节如算法作用概率分析与随机算法线性编程等几乎对第一版的各个部分都作了大量修订学过计算机的都知道这本书是全世界最权威的算法课程的大学课本了基本上全世界的名牌大学用的教材都是它这本书一共四位作者和是来自的教授是出来的博士现在哥伦比亚大学做教授四人姓氏的首字母联在一起即是此书的英文简称其中的第三作者是算法的老大算法名字里面的即是指他四个超级大牛出的一本书此书不看人生不能算完整再介绍一下课堂录像里面授课的两位的老师第一位外表绝顶聪明的是本书的第二作者以逻辑严密风趣幽默享誉第二位留着金黄色的络腮胡子和马尾发的酷哥是岁即取得教授资格的天才出生今年才岁业余爱好是俄罗斯方块演戏琉璃折纸杂耍魔术和结绳游戏另外附上该书的中文电子版转格式中文版翻译自该书的第一版中文书名没有使用算法导论而使用的是现代计算机常用数据结构和算法年出版时没有得到国外的授权属于私自翻译出版译者是南京大学计算机系的潘金贵课程重点算法导论是麻省理工学院电机工程与计算机科学系理论计算机科学集中选修课程的先导科目课程几乎将所有资料放到线上包括了完整的课堂讲义和习题课本算法导论第二版是由教授副笔课程描述本课程教授高效率算法的设计及分析技巧并着重在有实用价值的方法上课程主题包含了排序搜寻树堆积及散列各个击破法动态编程偿还分析图论算法最短路径网络流计算几何数字理论性算法多项式及矩阵的运算高速缓存技术及并行运算一般资讯讲师讲师课程目标这门课程对学生们简单介绍计算机算法的分析与设计完成这门课程后学生应当能做到以下几项分析算法的渐进效率演示对各种主要的算法及数据结构的熟悉性对重要算法设计范例及分析方法的应用在一般的工程设计状况上运用有效的算法课程成果完成本课程的学生将会展现做到以下几项的能力用归纳法及回路不变量来证明算法的正确性用渐进法分析算法在最坏情况下的执行时间比较由多项式指数及对数函数初步组合之函数的渐进行为形容最坏平均及最好情况分析的相对优点分析算法平均执行时间的概率使用指标随机值与预期直线性来做分析练习这里的是否是演示或是复习之意换句话说原句应该为练习使用这一类分析的算法后面出现处皆同用这一类分析法的算法分析解释随机化算法的基本性质和分析的方法练习使用随机性的算法解释随机化算法与随机输入的算法之间的差异在适当的时机使用偿还法分析算法练习用此方法对简单算法的分析叙述偿还分析法的不同策略包括计数法及可能法叙述各个击破法的模式和解释当什么情况算法设计会需要它练习使用此模式的算法实作各个击破算法推导出各个破算法的递归描述叙述动态编程的模式和解释当什么情况算法设计会需要它练习使用此模式的算法实作及分析动态编程算法叙述贪婪算法的模式和解释当什么情况算法设计会需要它练习使用此模式的算法实作及分析贪婪算法解释各主要的排序算法练习这些算法的分析及它们所包含的设计策略实作将排序做为子程序的算法推算比较排序法执行时间的下限和解释怎样可以克服这些界限解释实作动态集合的各大基本数据结构及对其动作的分析练习使用数据结构的算法和了解它们的效率是如何依赖于所使用的数据结构用增强已有数据结构的方法来实作新数据结构实作将数据结构为重要成分的算法解释各大图论算法及对它们的分析适时使用图来模拟工程问题实作新的图论算法和使用图论计算为关键的算法及分析它们举例说明在各个领域中所使用到的熟悉的数个重要算法展现对应用算法安置的熟悉度如计算几何作业研究安全与加密并行与分散计算操作系统及计算机体系结构远距离教学这们课程会在美国麻省理工学院教授同时也是新加坡课程的一部分无论是授课演示课习题或测验这两个国家的课程在各个方面来说都是相同的在麻省理工学院所有的讲义都将是现场教授这些都会被录下数位化由本课程的网页提供给新加坡的学生们这些数位化的课程也会提供给麻省理工学院的学生李教授会参加本课程的管理与及两位教授一起写课程相关资料及带领的学生的演示课先修条件对程序设计有很好的理解度及在离散数学包括概率学有扎实的背景是本课程的先有条件麻省理工学院学生本课程是麻省理工学院电机资讯工程资讯理论之集中选修课程的先导科目在选修这门课程前我们认为你应该先选修计算机程序的架构与解译和计算机科学数学及在这两门课得到或更高的成绩如果你还没有达到这些要求你一定要在注册本课程之前与助教沟通授课每周节每节小时课程内所提供的资料包括讲师们口述的讲解是你的责任演示课学生每个星期要参加一小时的演示课课程人员将会排演示课的时程你要负责演示课时所报告的内容演示课的出席率一直以来跟考试的成绩有紧密的关系演示课也是给你一个更直接的机会来发问和与课程人员互动麻省理工学院的学生们麻省理工学院的演示课会在每星期的最后一天由助教来教讲义请你在本课网页中的报名纸上填上你所选择的演示课分组课务办公室出的演示课作业是无效的讲义多数的讲义会使用方便打印的格式放在本科的网页上学生们应该由网页上下载并打印这些讲义当有讲义上线时你将会收到提醒你的内容会告知哪里以及什么时候那些少数没有放在网页上的讲义可以被找到教科书本课程主要的书面参考是由及教授写的教科书算法导论第二版在之前的学期本课程是用了这本书的第一版第二版彻底修订了前一版这已使得第一版不再适合作为一个替代品麻省理工学院的学生们这本教科书可以在各个线上或附近的书店购得习题在学期中将会指定次习题在课目时程表及讲义里分别有暂时的作业时程和截止日期但是真正的截止日期会写在习题上通常来说迟缴的作业不会被接受如果有能令人谅解的情况你应该提前跟你的演示课指导者做出安排麻省理工学院的学生们如果先前的安排发生了变化那么将由院长办公室作出解释因为每题可能被分别评分所以每一题应该要写在单独的纸上在每张纸的顶端写上以下你的名字该堂课讲师的名字习题号码一起解题的人参考段或合作者无如果你是完全一个人解答的话麻省理工学院的学生们你必须要将你的答案写在三孔活页纸上教科人员会将它们装订起来以免散落此外你可以很简单的将那些被评过分的作业加到你的活页笔记本内在你写答案的时候应该要尽量清楚和精确我们希望你的答案容易理解与正确因为技术性资料的沟通是一项重要的才能一个直接简单的回答比迂回的解答值更多分因为它更简洁易懂同时也不易于犯错较懒散的答案就算是正确的也会得较少分所以确定你的笔迹清晰易读将你的答案抄写一份再交是一个不错的主意这不但能让你的作业更加工整也让你有机会能够检查及修正错误习题中有包括一些应该要解答但是不用交的练习题这些问题是用来帮助你更掌握课程内容以及在解答指定习题将会有用习题范围内的材料会在考试中被测到算法的描述你经常会被指定用一个算法来解决某个问题你的写作应该是以一个短文的型态应该有一个标题段落概述你现在要解决的问题和你的解果你的本文应该提供以下部分算法的英文描述如有帮助的话用伪代码最少以一个工作例子或图表来更明确的显示你的算法是怎样工作的算法正确性的一个证明或表示算法执行时间的分析记住你的目的是沟通评分者会被指示对迂回愚钝的描述扣分评分规定最终的评分会基于习题一个随堂考一个家庭作业和期末考习题全部总值是分左右随堂考也是分左右携卷回家测验是分左右而期末考是分左右虽然习题只占你最终分数中的分你必须要做它们下表列出了不做习题对分数的影响跳过习题的影响无百分之一个整级分十分之一个整级分五分之一个整级分四分之一个整级分三分之一个整级分二分之一个整级分一个整级分两个整级分或更多不及格请注意这张表是列出了跳过的习题数而不是整次的习题具体的评分规定会依当时的需求而变动合作规定家庭作业的目的是让你有练习掌握课堂内容的机会因此我们鼓励你合作解题事实上通常组成学习小组的学生会比那些独自读书的学生考的更好但是如果你选择加入学习小组你要靠你自己和你的小组来负责准备小组聚会更具体的说在这之前你应该花到分钟试着自己解每一题如果你的小组不能解答某一题试着跟其他小组交流或问导师虽然你跟他人合作解答题目但是你一定要不受任何帮助而独自的写下你的答案我们要求在你的习题上写下你合作者们的名字如果你没有跟任何人合作你应该写下合作者无如果你的答案是由研究而来例如互联网注明你的资料来源但依你自己的方法写下答案在考试中不允许任何的合作本课程的第二项考试是一个可以带回家的测验虽然你将被允许以几天的时间来完成但它必须是完全由你独自完成关于回家测验的合作规定的一些细节将会安排在第三十五次讲课上请注意这课将会是考试的一部份是强制性参加抄袭和其它反知识性的行为在任何一个以个人成就而自豪的学术环境内是不能被允许的如果你对于合作规定有任何问题或者你觉得你可能违反了规定请与课程人员联系虽然课程人员有义务适当的处理作弊情况但如果是违反者本人提出而不是第三者检举我们会较通情达理及宽大教学时程这份时间表提供了授课演示课题目作业测验的日期及指定要从课本算法导论第二版内阅读的课文第一课课程细节序论算法分析插入排序法合并排序阅读章发测验演示课算法的正确性发作业第二课渐进表示递归公式置换法迭代法主方式阅读章除了第三课各个击破法算法费氏数列多项式乘法阅读章第节章第节演示课递归公式松散性阅读的讲义第四课快速排序法随机化算法阅读章到节章收作业发作业演示课排序法堆积排序法动态集合优先队列阅读章第五课线性时间的排序法下限计数排序法基数排序法阅读章第到节收作业发作业第六课序列统计中位数阅读章演示课中位数的应用桶式排序阅读章第节第七课散列通用散列阅读章到节收作业发作业第八课散列函数完美散列阅读章第节演示课测验复习收作业评分后的作业可以在中午拿到测验演示课二元搜寻树树的追踪阅读章到节第九课二元搜寻树和快速排序法之间的关系随机二元搜寻树的分析阅读章节发作业第十课红黑树循环插入删除阅读章演示课树树阅读章到节第十一课增强数据结构间距树阅读章收作业发作业第十二课计算几何区间查询阅读章到节演示课凸多边形阅读章节第十三课优先队列阅读的讲义收作业发作业第十四课偿还算法表的复制可能法阅读章演示课竞争分析自我排序列第十五课动态编程最长共同子序列最优二元搜寻树阅读章收作业发作业第十六课贪婪算法最小生成树阅读章到节章演示课贪婪算法和动态编程的范例第十七课最短路径算法广度优先搜寻法阅读章节第页章节收作业发作业演示课深度优先搜寻法边的分类阅读章到节第十八课最短路径内的最短路径差异局限阅读章节第十九课全成对最短路径动态编程的算法阅读章收作业第二十课零散集合的数据结构阅读章评分后的作业可以在中午拿到第二十一课带回家发下测验道德解决问题强制参加发测验没有演示课解答测验没有课算法程序比赛开始非强制参加收测验第二十二课网络流最大流量最小切割论阅读章节发作业选答演示课求对集注最大二分图求对集阅读章节第二十三课网络流算法参赛答案截止第二十四课随堂测验比赛颁奖后续课程的讨论作业解答相关阅读资料以下是对本课程有用的参考书与计算机算法之设计与分析经典作品但是在网络流线性规划和近代算法方面较缺少与数据结构与算法重新改版过后是以前作计算机算法之设计与分析前六章所改版的较基本版本计算机算法设计与分析导论第二版普通参考尽管它的说明有时是潦草扼要的程序设计明珠算法设计在软件工程中的实用繁体中文版译者许鸣程出版商基峰出版日期更多的程序设计明珠更多算法设计在软件工程中的实用编写有效率的程序非常杰出的效能精进调整与算法理论与实践很好的范例及习题着重于方法而不是个别的问题基础概率理论与随机过程对概率直觉性的演示课图形算法对图形算法有广泛的论述包含了网络流及平面性概率理论导论与应用对概率很好的参考与计算机与难驾驭性对完整性理论的指南专注于完整性的参考书在后半部含有一份完整问题集的列表及在书中出现过针对多项式时间特别情况的算法的参考算法与数据结构手册及码真正执行时间的比较和对研究报告中分析的指示字串树与序列的算法操作字符字串及序列的算法的大概论述与计算机算法基础择重介绍了数据结构动态编程以及分支与界限法算法与数据结构设计正确性分析一本优良的数据结构导入书关于算法正确性有一篇不错的章节计算机程序设计艺术三卷如百科全书般的作品基础算法半数值算法与排序与搜寻组合式优选图算法密集图网络流与线型规划开始几章是很优秀的组合数学导论与计算机科学有关的组合数学有优秀的习题算法导论着重于创造力的初级文章数据结构与算法三卷排序与搜寻图算法和完整性与多维度查询与计算几何基本及高阶论题的讲义与数论导论有阅读价值的的数论入门介绍与组合式优选算法与复杂性线性规划和它的变体与的数值处方科学计算的艺术数值算法的程序码与组合算法理论与应用在递归关系和二元树方面的内容不错算法第二版有着优秀论题广度的初阶文章不重于分析但是有很多图运算理论导论对可计算性及复杂性理论很好的文章数据结构与网络算法有一堆好东西的高阶书课堂讲稿这里有本课完整的课堂讲稿请下载相应文件查看作业在习题集里所引用的阅读材料和习题是由课本算法导论第二版内取得的详细的资讯请参考请下载相应文件查看测验这里提供了本课的一些实际题目和练习考试请下载相应文件查看