麻省理工高级数据结构课程

img img 讲座视频中的样本框架(L02

数据结构在现代计算机科学中发挥着核心作用。与算法相比,您更频繁地与数据结构进行交互(想想Google,您的邮件服务器,甚至您的网络路由器)。此外,数据结构是获得有效算法的基本构建块。本课程涵盖数据结构的主要成果和当前研究方向:

时间旅行 我们可以有效地记住过去(一种称为持久性的技术),但总的来说,很难改变过去并看到现在的结果(追溯性)。唉,回归未来真的不可能。
几何 当数据有多个维度时(例如地图,数据库表)。
动态最优 是否有一个二元搜索树与其他搜索树一样好?我们仍然不知道,但我们很接近。
记忆层次 真正的计算机有多级缓存。我们可以优化缓存未命中数,通常甚至不知道缓存的大小。
HASHING 哈希是计算机科学中最常用的数据结构。它仍然是一个活跃的研究领域。
INTEGERS 对数时间太容易了。通过仔细分析您正在处理的信息,您通常可以大幅减少操作时间,有时甚至可以减少操作时间。我们还将介绍说明何时无法实现的下限。
动态图 网络链接已关闭,或者您刚刚添加或删除了社交网络中的朋友。我们仍然可以在变化时保持有关连接的基本信息。
STRINGS 搜索巨型文本中的短语(想想Google或DNA)。
简洁 您知道的大多数“线性大小”数据结构比它们需要的大得多,通常是一个数量级。一些数据结构几乎不需要原始数据之外的空间,但仍然很快(想想堆,但更冷)。

倒置讲座

今年,我们正在尝试倒置讲座:大多数材料都包含在 2012年录制的视频讲座中(已经有超过10万人观看),您可以方便地以比实时更快的速度播放。课堂时间将分为问题答案, 教授和/或客座讲师提供的新材料,以及课堂问题解决,重点是解决问题。特别不同的是,我们将在小组中解决的问题将包括 已知解决方案的问题集风格问题,编码 问题和开放研究问题没有人知道答案,目的是发表关于我们发现的任何内容的论文。(6.851的过去产品已经发表了十多篇论文。)你可以处理你最感兴趣的任何类型的问题。为了促进协作,我们将使用一个 名为Coauthor的新 开源软件平台,以及用于(可选)编码的Github

细节

  • 讲座时间:周三7:00-9:30
  • 第一讲: 2017年9月6日星期三
  • 演讲室: 32 -082 - 除了9月27日在32-155
  • 单位: 3-0-9,G-level和TCS AAGS学分
  • 联系方式:电邮 6851-staff#at#csail.mit.edu
  • 先决条件: 6.046(算法的设计和分析),或来自另一所学校的等效彻底的本科算法课程(例如,涵盖大部分 CLRS)。

推荐阅读

这门课没有完美的教科书,但有一些相关的书:

参与

我们欢迎所有大学的本科生和研究生,虽然这是一个研究生课程。

如果您有兴趣参加课程,学分或作为听众,请执行以下操作:

  1. 加入 6851-学生邮件列表
  2. 注册Coauthor帐户
  3. 填写此注册表格

等级

有四个要求:

  • 观看讲座视频。请务必填写相关的反馈表单。
  • 参加面对面的课程(除非你有一个有效的借口,你需要告诉课程的工作人员)。特别是,您必须每周通过在Coauthor的帖子中发帖或被提及来参与。
  • 轻量级(每周一页)问题集。问题集将每周发布一次,并遵循“一页一页,一页”规则。
  • 根据您自己的改进灵感和同学反馈,修改一个讲座(或两个)的现有抄写员。该课程的整个日历已发布,因此您可以选择您感兴趣的讲座。我们将在第二周发布一份注册表。Scribe笔记通常在相应的课程后的星期二中午(但可以扩展)。
  • 以研究为导向的最终项目 (论文和演示文稿)。我们允许理论,实验,调查和维基百科的最终项目。

过去和未来

该课程每两年提供一次。它在2003春季2005 春季 为6.897,在 2007春季,2010春季,2012春季,2014 春季为6.851。

来了,老弟
-------------    本文结束  感谢您的阅读    -------------
0%