MIT 6.006 Lecture 1-a 笔记

MIT 6.006 Lecture 1-a 笔记

这是6.006课程的概述部分,主要是对课程的介绍。第一模块的问题讲解从Lecture 1-b开始。

课程概述

一句话概括这门课程:

  • Efficient procedures for solving problems on large inputs.

The world is moving faster, things get bigger, where have the capability of computing on large inputs. But that doesn’t mean that efficiency isn’t of primary concern.

(世界迅速发展,计算机处理大型输入的能力也在变强,但是这不意味着“高效”就变得不重要了。)

  • Scalability

世界会继续发展,输入会继续变大,“large”的意义会继续变迁。所以扩展能力很重要,当输入变大,依然可以“高效”的解决。

We want be able to track how our procedure will gonna to do as input get larger and larger.
(当问题输入变得越来越大时,我们希望依然知道程序会如何执行。)

  • Classic data structure and elementary algorithms

Classic data structures were invented many decades ago, but they stood the test of time, and they continue to be useful

经典数据结构是那些被发明了许多年,经受住了时间的考验依旧有用的数据结构。

  • Real implementaions in Python

课程中会要求用Python来实现这些经典数据结构。所以需要有一定的Python基础。

  • Fun problem set

有趣不是指简单,而是有挑战性而且有价值的问题。这样你解决这些问题后会觉得学到了一些东西,并且会有成就感。

课程内容

课程分为8个模块,每个模块都跟随一些问题:

  1. Algorithmic thinking: Peak finding
  2. Sorting&Trees: Event simulation
  3. Hashing: Genome comparison
  4. Numerics: RSA encrythion
  5. Graphs: Rubik’s cube
  6. Shortest paths
  7. Dynamic programming: Image compression
  8. Advanced topics