跳转至

MIT 6.006 — 算法导论

简介

MIT 6.006 是麻省理工学院的算法入门课程，由 Erik Demaine、Srini Devadas 和 Nancy Lynch 教授主讲。这门课系统地介绍了算法设计和分析的基本方法，涵盖排序、搜索、图算法、动态规划、贪心算法等核心主题。

与 CS61B 侧重"动手实现"不同，MIT 6.006 更侧重"理解和分析"。课程强调数学证明和复杂度分析，要求你不仅知道一个算法怎么用，还要证明它为什么正确、分析它的时间复杂度。这种理论训练对于深入理解算法的本质非常重要。

课程使用 Python 作为教学语言，降低了语法门槛，让你把精力集中在算法本身。

先修要求

  • 编程基础：熟悉 Python 或至少一门编程语言
  • 基础数学：高中数学水平，对对数、指数、求和等概念有基本了解
  • 离散数学基础（推荐）：基本的集合论、逻辑、归纳法

难度

🌟🌟⭐（中等偏上）

课程的理论部分（复杂度证明、动态规划的正确性证明）对没有数学背景的同学有一定挑战。但课程讲解非常清晰，配合视频和笔记可以跟上。

学时

约 80-100 小时

  • lecture：约 30 小时
  • problem sets：约 30-40 小时
  • 复习和考试准备：约 20-30 小时

课程资源

  • 课程主页：MIT OCW 6.006
  • 课程视频：MIT OCW YouTube
  • 课程笔记和作业：课程主页提供完整的 lecture notes 和 problem sets
  • 教材：Introduction to Algorithms (CLRS) 作为参考

自学建议

  1. 一定要做 problem sets。 MIT 的 problem sets 质量极高，每道题都经过精心设计。不做题只看视频，等于没学。

  2. 重视复杂度分析。 这是 MIT 6.006 的核心技能。每学一个算法，都要能写出它的时间复杂度和空间复杂度，并给出证明。

  3. 动态规划是分水岭。 很多同学在动态规划这里卡住。建议先理解"最优子结构"和"重叠子问题"这两个概念，然后从经典的 DP 问题（背包、最长公共子序列、矩阵链乘法）开始练习。

  4. 配合 LeetCode 刷题。 学完一个专题后，去 LeetCode 上找对应的题目练习。理论+实践的组合效果最好。

  5. 如果觉得 CLRS 太难，先看《算法（第4版）》。 Sedgewick 的书更直观，适合作为 MIT 6.006 的补充阅读。

  6. 善用 MIT OCW 的 recitation 视频。 这些习题课视频对理解 problem sets 非常有帮助。