最优秀的课程之一

https://t.co/QmUpWFPcKw https://t.co/Ta2IV7YcsB

高级数据结构（6.851）

来源：https://courses.csail.mit.edu/6.851/spring21/

教授：Erik Demaine (http://erikdemaine.org/)

助教：Josh Brunner、Jenny Diomidova、Della Hendrickson

[首页] [讲座 (https://courses.csail.mit.edu/6.851/spring21/lectures/)] [习题集 (https://courses.csail.mit.edu/6.851/spring21/psets/)] [项目 (https://courses.csail.mit.edu/6.851/spring21/project/)] [Coauthor (https://coauthor.csail.mit.edu/6.851-2021/)] [GitHub (https://github.com/6851-2021)] [无障碍 (https://accessibility.mit.edu/)]

数据结构在现代计算机科学中扮演着核心角色。你与数据结构交互的频率甚至超过算法（想想谷歌、你的邮件服务器，甚至你的网络路由器）。此外，数据结构是获得高效算法的重要构建模块。本课程涵盖数据结构领域的主要成果和当前研究方向：

时间旅行我们可以高效地记住过去（一种称为持久化的技术），但通常很难改变过去并观察对现在的影响（回溯性）。所以可惜的是，《回到未来》实际上并不可行。

几何当数据具有多个维度时（例如地图、数据库表）。

动态最优性是否存在一棵二叉搜索树与所有其他树一样好？我们仍不知道，但已经很接近了。

内存层次结构真正的计算机有多级缓存。我们可以优化缓存未命中次数，通常甚至不需要知道缓存的大小。

哈希哈希是计算机科学中使用最广泛的数据结构，并且仍然是一个活跃的研究领域。

整数对数时间太容易了。通过仔细分析你处理的信息，你通常可以大幅减少操作时间，有时甚至减少到常数。我们还将涵盖下界，说明何时这是不可能的。

动态图网络链路断开，或者你在社交网络中刚添加或删除一个好友。我们仍然可以在连通性变化时维护关于连通性的关键信息。

字符串在大型文本中搜索短语（想想谷歌或DNA）。

简洁你所知道的大多数“线性规模”的数据结构都比实际需求大得多，通常大一个数量级。有些数据结构除了原始数据外几乎不需要额外空间，但依然很快（想想堆，但酷得多）。

全在线格式

大部分课程内容涵盖在视频讲座 (https://courses.csail.mit.edu/6.851/spring21/lectures/)中（录制于2010年，已有超过35万人观看），你可以方便地以快于实时的速度播放。可能还有一些由教授和/或客座讲师呈现的新内容，这些内容会被录制供异步观看。

但同步会议时间（也在线上）将重点放在协作解决问题上，与你的同学和课程工作人员一起。特别不寻常的是，我们将分组解决的问题包括习题集风格的问题（有已知解法）、编程问题（适合热爱编程的人）以及开放研究问题（无人知道答案），目标是将我们的发现发表成论文。（本课程过往几期已经产出了若干篇已发表的论文。）你可以选择你最感兴趣的问题类型。为了促进协作，我们将使用我们的开源软件平台 (https://github.com/edemaine/coauthor/)——称为Coauthor (https://coauthor.csail.mit.edu/6.851-2021)，同时结合GitHub (https://github.com/6851-2021)进行（可选）编程。

同步会议的时间将根据学生的日程和时区进行安排。如果你可能对这门课感兴趣，请注册6851-students邮件列表 (http://lists.csail.mit.edu/mailman/listinfo/6851-students)，以便你能帮助决定时间表。

我们建议为在线协作配备一个绘图板，如果你没有，请务必申请一个。我们将使用一系列定制的、前沿的开源软件工具进行在线协作，包括我们自己的Coauthor (https://github.com/edemaine/coauthor/)、Cocreate (https://github.com/edemaine/cocreate/)和Comingle (https://github.com/edemaine/comingle/)，旨在尽可能好地复现线下体验。加入我们，让这一切成为可能！

具体信息

同步课堂时间：美国东部时间周一 4:00pm–5:30pm 和/或 美国东部时间周四 7:00–8:30pm 强烈建议参加两个时段；需要学分的学生必须至少参加一个。 同步课堂地点：线上，通过Comingle （填写报名表格并加入邮件列表（见下文）以获取班级的私人链接。） 第一次课：美国东部时间2021年2月18日周四 7:00–8:30pm 第二次课：美国东部时间2021年2月22日周一 4:00–5:30pm 办公时间：美国东部时间周一中午12:00 美国东部时间周二晚上7:00 美国东部时间周三晚上10:00 教授：Erik Demaine (http://erikdemaine.org/)，edemaineatmit.edu 助教：Josh Brunner，brunnerjatmit.edu Jenny Diomidova，diomidovaatmit.edu Della Hendrickson，dellaatmit.edu 工作人员邮箱：6851-staffatcsail.mit.edu 学分：3-0-9 先修课程：6.046或同等离散数学和算法背景。 或者获得导师许可。 学分等级：H-level 和 TCS AAGS 学分

推荐阅读

本课程没有完美的教材，但有一些相关的书籍：

• 《数据结构与网络算法 (http://epubs.siam.org/doi/book/10.1137/1.9781611970265)》，作者 Robert E. Tarjan（涵盖二叉搜索树、伸展树、链接-切割树）
• 《开放数据结构 (http://opendatastructures.org/)》，作者 Pat Morin（涵盖二叉搜索树、B树、哈希以及一些整数数据结构）

参与方式

我们欢迎来自麻省理工学院及其附属大学以及波士顿地区所有大学的本科生和研究生。通常我们从所有大学招收学生，但在线模式下，我们需要确保规模不会超出容量，因此所有此类学生需要向教授请求许可。如果你有兴趣参加这门课（无论是否修学分或旁听），请执行以下操作：

1. 如果你是麻省理工/哈佛的学生，请提前注册。
2. 如果你不是麻省理工/哈佛的学生，请给 Erik 发送邮件请求许可。
3. 加入6851-students邮件列表 (http://lists.csail.mit.edu/mailman/listinfo/6851-students)。
4. 在Coauthor (https://coauthor.csail.mit.edu/6.851-2021)上注册账号。
5. 如果你还没有GitHub (https://github.com/)账号，请注册一个（这与github.mit.edu不同）。
6. 填写此报名表格 (https://forms.gle/CrgKy99gpWuTGcwb8)。

要求与评分

本课程包含六个部分，其中一些是必需的： 必需：观看所有视频讲座 (https://courses.csail.mit.edu/6.851/spring21/lectures/)，通过在 Coauthor 上点赞完成问题 (https://coauthor.csail.mit.edu/6.851-2021/search/tag%3Acompletion)来衡量。 必需：观看你未参加的同步课堂的录制部分。 必需：参加同步课堂，每周至少一次（如有例外请发送邮件至6851-staff） 必需：参与课堂讨论，以每周至少在 Coauthor 上发文一次（非平庸帖子）来衡量。请查看你的统计视图 (https://coauthor.csail.mit.edu/6.851-2021/stats/me) 以检查是否有零周的周次。（对于已解决问题，平庸帖子的例子：“用一棵树。”非平庸帖子的例子：描述你尝试过但失败的技术。已删除和未发布的帖子不计入，但私人帖子计入。） 选择：习题集 (https://courses.csail.mit.edu/6.851/spring21/psets/)。习题集每周发布，遵循“一进一出”规则。 选择：项目 (https://courses.csail.mit.edu/6.851/spring21/project/)：基于课堂工作的书面报告和演示。

本学期我们正在尝试灵活的评分方案：

• 20%：观看讲座 [必需]
• 40%：课堂参与 [必需]
• 40%：习题集
• 40%：项目

每个部分按100分制评分，然后根据上述百分比加权，最后求和得到你的总分。你的字母等级（A、B等）将根据此分数分配（90+ = A，80+ = B，70+ = C，60+ = D，<60 = F）。然而，我们保留在分配标注（+、- 或直接字母）时的灵活性，根据其他因素如参与度是否超出预期或刚刚及格。

百分比权重总和为140%，因此你可以跳过项目（40%）或习题集（40%），仍然达到100%的总工作量。或者，你可以通过在其他部分努力来弥补任何部分的失分。目的是让项目成为可选，但通过减少习题集数量来奖励做项目的人。

一条额外的规则是，如果你没有观看大部分讲座并且大部分周没有参与课堂（根据上述最低要求），你就不能通过这门课，这也是“必需”的含义。

过去与未来

本课程大约每两年开设一次。曾在2003年春季 (http://courses.csail.mit.edu/6.897/spring03/)和2005年春季 (http://courses.csail.mit.edu/6.897/spring05/)以6.897的编号开设，并在2007年春季 (http://courses.csail.mit.edu/6.851/spring07/)、2010年春季 (http://courses.csail.mit.edu/6.851/spring10/)、2012年春季 (http://courses.csail.mit.edu/6.851/spring12/)、2014年春季 (http://courses.csail.mit.edu/6.851/spring14/)和2017年秋季 (http://courses.csail.mit.edu/6.851/fall17/)以6.851的编号开设。