算法设计与分析 1

Algorithms: Design and Analysis, Part 1

这门课中,你将学到算法设计的多种基本原理:分治法、图算法、实用数据结构(堆、哈希表、搜索树)、随机化算法等。 …

斯坦福大学

分享

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

这门课中,你将学到算法设计的多种基本原理:分治法、图算法、实用数据结构(堆、哈希表、搜索树)、随机化算法等。

课程简介

这门课中,你将学到算法设计的多种基本原理。你将学到分治法设计范式,了解它在快速排序、搜索及乘法中的应用。你将学到多种在图上极快速进行计算的基本方法,例如计算连通性信息和最短路径。最后,我们将学习,让电脑“抛硬币”如何引出优雅而实用的算法和数据结构。我们要探讨的问题包括:堆、哈希表、布隆过滤器和平衡搜索树这样的数据结构是如何工作的?为什么快速排序能运行得这么快?关于网络结构和社交网络,图算法能告诉我们一些什么知识?三年级老师所教的乘法算法只是次优算法吗?

课程大纲

第一周: 导论。 渐进分析,包括大O表示法。 用于排序、计算逆序数、矩阵乘法和最近对的分治法。
第二周: 分治法的运行时间分析。 主方法。 随机化算法简介,带有概率复习。 快速排序法。
第三周: 随机化算法和概率的进一步讲解。 线性时间内计算中位数。 图最小割问题的随机化算法。
第四周: 图元。 深度优先和宽度优先搜索。 无向图的连通分支。 有向非循环图的拓扑排序。 有向图中的强连通分支。
第五周: 迪杰斯特拉最短路径算法。 数据结构简介。 堆和应用。
第六周: 数据结构的进一步讲解。 哈希表和应用。 平衡二分搜索树。

背景知识

至少知道如何使用一种语言进行编程(如C语言、Java或Python);熟悉证明方法,包括归纳法和反证法证明。 在斯坦福大学,这门课的另一版本被提供给计算机科学专业大二、大三、大四水平的同学学习。

参考资料

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

授课形式

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

常见问题

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

这门课的授课形式是怎样的?
这门课包含一些课程视频,视频都被分成小段,每一段通常是8到12分钟。其中一些视频中会包含测试问题。课程还有一些单独存在、不属于视频中的测试。每周的视频内容时间大致是2小时。

要学这门课,我需要哪些先修知识?
至少知道如何使用一种语言进行编程(如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 慕课改变你,你改变世界