算法设计与分析,2

Algorithms: Design and Analysis, Part 2

这门课中,你将学到进阶算法设计的多种基本原理:贪婪算法及应用、动态规划及应用、NP完备性及其对算法设计者的意义…

斯坦福大学

分享

算法设计与分析
  • 分类: 计算机
  • 平台: Coursera
  • 语言: 英语

这门课中,你将学到进阶算法设计的多种基本原理:贪婪算法及应用、动态规划及应用、NP完备性及其对算法设计者的意义、启发式的设计和分析等等。

课程简介

这门课中,你将学到进阶算法设计的多种基本原理。你将学到贪婪算法设计范式,及其在计算良好网络主干(亦即生成树)和数据压缩良好代码方面的应用。你将学到较难但用途广泛的动态规划算法设计范式,及其在互联网路由和基因组片段测序方面的应用。你将学到NP完备及算法设计领域中著名的P vs. NP问题。最后,我们将学习多种策略,来处理困难NP完备问题,包括启发式的设计和分析。你将学到:上世纪五十年代阿帕网出现之前发明的最短路径算法如何支配当今互联网通信的路由方式,为什么高效算法对于现代基因组学具有根本重要性,如何通过“仅仅”求解一个数学题来得到上百万美元的奖金。

课程大纲

第一、二周:贪婪算法设计范式 最优缓存和调度中的应用 最小生成树及其在聚类中的应用 并查集数据结构 最优数据压缩

第三、四周:动态规划设计范式 背包问题应用 序列比对、最短路径路由和最优查找树

第五、六周:难解问题以及如何处理 NP完备性及P vs. NP问题 可解特殊情况 具有可证明性能保证的启发式 局部查找 打败蛮力查找的指数时间算法

背景知识

至少知道如何使用一种语言进行编程(如C、Java或Python);熟悉证明方法,包括归纳法和反证法证明。 在斯坦福大学,这门课的另一版本被提供给计算机科学专业大二、大三、大四水平的同学学习。 这门课要求学生对”算法设计与分析,第一部分”课程的内容比较熟悉,尤其是渐近分析、基本数据结构和基本图算法。

参考资料

这门课没有任何指定教材。课程中大多数内容都会在著名算法教材中涉及到,我们鼓励学生使用自己最喜欢的算法教材作为参考资料。

授课形式

这门课将包含一些课程视频,视频长度通常在10到15分钟之间。其中一些视频中间会穿插测试问题。课程还有一些单独存在、不属于视频中的笔头和编程作业,以及一个期末考试。

常见问题

完成这门课后,我能否得到结业证明?
能,成功学完这门课的学生将得到授课老师签发的结业证明。

要学这门课,我需要哪些先修知识?
至少知道如何使用一种语言进行编程(如C、Java或Python);熟悉证明方法,包括归纳法和反证法证明;了解一些离散概率知识,例如会计算扑克牌型得到葫芦的概率。在斯坦福大学,这门课的另一版本被提供给计算机科学专业大二、大三、大四水平的同学学习。

这门算法设计与分析课程同普林斯顿大学的算法课程有何不同?
两门课是互补的。那门课强调实现和测试,而这门课着眼于算法设计范式和用于分析的相关数学模型。在典型计算机科学教学中,这门课是大三大四学生学习的课程,而那门课是大一大二学生学习的课程。

声明:MOOC中国收录之课程均源自下列机构,版权均归他们所有。本站仅作报道并尊重其著作权益,感谢他们对MOOC事业做出的贡献!(排名不分先后)
  • Coursera
  • edX
  • OpenLearning
  • FutureLearn
  • iversity
  • Udacity
  • NovoEd
  • Canvas
  • Open2Study
  • Google
  • ewant
  • FUN
  • IOC-Athlete-MOOC
  • World-Science-U
  • Codecademy
  • CourseSites
  • opencourseworld
  • ShareCourse
  • gacco
  • MiriadaX
  • JANUX
  • openhpi
  • Stanford-Open-Edx
  • 网易云课堂
  • 中国大学MOOC
  • 学堂在线
  • 顶你学堂
  • 华文慕课
  • 好大学在线CnMooc

Copyright © 2008-2015 MOOC.CN 慕课改变你,你改变世界