MIT 计算机科学导论结课小结

August 02, 2017

今天完成了 MITx: 6.00.1x Introduction to Computer Science and Programming Using Python,是这个暑假「完成」的第一门 MOOC,给「完成」加了引号,是因为是跳过了 Problem Set,我当然知道练习很重要,但对于基础的 Python 编程作业实在上不了心,用时30小时,11天,中间有几天偷懒,有两天做 BearCity 3 的中文字幕,所以说,这个速度我可相当满意了。

上这门课的原因也很简单,我意识到对 Python 的理解有短板,为什么要 OOP?Python 中 method 和 function 有何区别?怎么写?上完课后,这些问题也得到了解答。

课程我给 4.5/5,课程内容、视频制作剪辑、课后资料都完美,每一段视频的时间很短,10分钟左右,并且都配有课后练习。最不满的就是 edX 的证书有时间规定的,我上课的时候已经不能领证书,也就作罢。

回想起今年寒假,我看了几节生成器(generator)和递归的内容,看得头晕目眩眼花缭乱,这次老老实实从头开始上,很顺利地掌握了。我可以清晰地看到自己在 11 天里的进步,因此我也推荐给任何有一定基础的初学者。

为什么说要有一定基础?因为我大一的时候上过几节,讲得太过深入,什么是机器?什么是算法?图灵机解决的可计算性问题是什么?听不懂,因为这门课不仅教你编程,还教你什么是计算思维(computational thinking)。这门课也很「枯燥」,他假定了你对计算机足够有兴趣了。如果把这门课和 CS50 比,就是天差地别:CS50 讲课注重趣味性,然后你发现老师满头大汗讲了一个半小时就为了演示编码的意义;6.00.1x 讲究知识面和思维训练,把每个坑和用法演示得清清楚楚,还有海量的作业让你慢慢领悟。我写的 十进制与二进制:为什么浮点数不准? 就是从 6.00.1x 里学来的,6.00.1x 用10分钟的视频讲完了原理和演示,CS 50 花了半个小时。

这门课的核心是计算思维,计算思维听起来很玄乎,但就是程序员最擅长的那一套:抽象分解、自动化、算法。把一个大问题层层剥离,选择合适的算法,编写合适的程序,逐个击破,最终解决问题。我把这门课的内容分成 Python 抽象分解、递归、错误处理、算法这四个部分,随便聊聊。

Python 抽象分解

对象和类型

Everything in Python is an object. 所有能被程序操作的东西,都叫对象。每个对象都有一个类型(type),类型决定了这个对象可以做什么,Python 中的类型包括 int、float、string、list 等等。

变量

变量是最简单的抽象,用变量名指代一个变量,你就不用管这个变量怎么实现的。

数据结构

把数据比作水,数据结构就是杯子,我们需要不同的数据结构来装数据。Python 中的数据结构包括 tuple、list、dictionary。这里比较 tricky 的部分是 list 和 dictionary 是可变的,当我们让多个变量指向同一个 list 或者 dictionary 的时候,任何一个变量变化,其他变量也会变化。演示如下:

a = [1, 2, 4]
b = a
a[0] = 0
print(b)
# [0, 2, 4]

所以,在复制 list 或者 dictionary 的时,务必使用 b = a[:] 或者 c = aDict.copy()

函数

函数把一系列动作抽象,这样就不用老是复制同样的代码,把这一系列动作抽象,我不需要关心代码如何实现,以后只要用这个函数就可以了。值得一提的是,在 Python 中,函数也是个对象,你可以把函数名作为参数传递到另一个函数里。演示如下:

def sampleF(x):
    return x ** 2

def Y(f, a):
    return f(a)

aInt = 9
Y(sampleF, aInt)

生成器

range() 就是个生成器,当我们用 for i in range(1000) 的时候,range() 不是一下子就生成了1000个整数,而是每次要用到的时候,生成1个整数,下次用到的时候,再生成一个,以节省内存开支。

把函数里的 return 换成 yield 即可创造一个生成器。

如果我们需要抽象一套新的数据结构(你也可以理解为定义新的类型),就需要用到类(class)。类定义了这个数据结构里有哪些 attribute,有哪些 method,怎么 print,怎么加减乘除,怎么比较大小。类可以继承,把父类的 attribute 和 method 继承的子类里。

递归

递归把一个大问题分解成一个小问题,把小问题解决,就把大问题解决了,一个例子就是汉诺塔问题。递归的理论基础是数学归纳法,如果函数在 n 的条件下成立可以推导出在 n+1 的条件下也成立,这时候只要证明 n = 1 时函数成立,就能证明 n > 1 的情况下也成立。归纳法是个在数学证明里非常有用的方法,这里不展开了。

错误处理

有时候程序会出错,这里有两个思路:一个是如果出错了,那我执行这么一段代码,也就是 try: except: else: finally: ;另一个思路是如果出错了,就报错,有两个方法 raiseassert

算法

算法就是给计算机解决问题的一套指令,这里我想说一下怎么比较算法的好坏。计算机理论用大 O 记号表示算法的复杂度,即算法在最坏情况下所需操作步数随输入增长的情况,如果是线性增长,则为 O(n),如果是 log 增长,例如二分法,就计为 O(log n)。