Lecture 1

1.Basics of computation

计算机所能做的最基本的两件事：

• 计算：什么样的计算呢？首先是计算机内置的一系列基本操作（包括简单的计算、逻辑、测试、对数据的移动），它们是计算机使用的基本单位。当然这是远远不够的，要靠用户自定义高效的计算。
• 存储

排除时间和空间因素，计算机也是有限制的，比如计算太复杂（如预测天气）或者基本不可能被计算出的问题（如图灵停机问题）

2.Types of knowledge

陈述性知识（Declarative knowledge）：事实

程序性知识（Imperative/Procedural knowledge）： “如何去做”的方法。是发现新知识的途径。

3.Basic machine architecture

计算思想（computational thinking）：将待解决的问题分为一系列机械步骤，从而得到问题的解决

为了把解决问题的方法步骤（recipe）变为计算机的机械过程，我们应该做什么呢？

• 为解决某一特殊问题而专门建造一台机器。这类机器被称为“固定程序计算机”，如计算器，专门破解Enigma的bombe机等。
• 建造一台能做我们让它做的任何事的计算机。比如小白鼠斥巨资建造的Deep Thought，今天算一下ultimate answer，明天再算一下ultimate question......这就需要存储与操作指令序列（程序），然后通过翻译器将程序变为基本操作。这类机器被称为“存储程序计算机”，现代电子计算机均按此原理设计。（关于这段历史，推荐阅读《面对面的办公室——纪念艾伦•图灵百年诞辰》）

图灵说仅仅用6种基本操作就可以计算任何可计算的问题（图灵完全性）。事实上现代程序语言有着更方便的基本操作集，也可通过方法抽象（函数）得到新的基本操作。

4.Programming language characteristics

语法（syntax）：定义了格式正确（well-formed）的表达式的构成。语法错误的话机器可以查出来。

语义（semantics）：定义了与表达式相关的意义。

• 静态语义（static semantics）：语法上有效，且有意义。
• 正式语义（formal semantics）：语法正确，无静态语义错误，且只有一个意义（无二义性）。这一步出错的话机器是查不出来的，可能停止运行并报错，或陷入死循环，或输出一个错误结果。

------------------------------------------------------------------------------------

Lecture 2

1.Types of programming languages

低级语言：使用与计算机内部控制单元相似的指令。比如想要算1+2的话，用汇编语言大概是先定义两个数在存储系统的地址，然后将它们MOVE到寄存器，再加......（没学过汇编，请指正）相当费劲，必须对计算机内部结构有一定了解。 wiki

高级语言：是计算机具体细节的抽象化，与低级语言相比，更接近自然语言，方便理解使用。现在只要输入“1+2”就行啦！ wiki

• 编译语言（Compiled language）：抽象的表达通过编译被转化为低等码，再翻译执行。编译的五个阶段：词法分析、语法分析、语义检查和中间代码生成、代码优化、目标代码生成。高级源代码（Source Code）→编译器（Compiler）→低级目标代码（Object Code）。如c语言，就是将源文件（.c/cpp）通过编译预处理→编译（翻译成中间代码表示或汇编代码）→优化→汇编（翻译成目标机器指令）→链接的一系列过程，最终生成可执行文件（.exe）。
• 解释语言（Interpreted language）：由一个特殊程序将源程序转化为内部的数据结构，然后直接将每一步转化为低级的机器指令。也就是一次翻译并执行一条指令。如Java，就是一种先编译再解释的语言，源程序通过编译转化为中间代码（字节码），当程序运行时，虚拟机再根据不同的平台把字节码解释成具体平台上的机器指令执行，也就是所谓的“平台无关性”。

两者的区别：编译语言需要在开始将源代码全部转换为机器语言之后再执行，查错改错不方便，但运行快。解释语言虽然运行慢了点，但由于它是边翻译边执行的，很容易找到出错点。

2.Python objects

object的类型（type）定义了程序能对它做的事情

3.Variables and naming

在变量名和值（储存于计算机中）之间建立联系，并用一个table记下这些联系

4.String

操作符重载（Operator overloading）：使用同一操作符来做不同的事情。如1+2是做加法，‘1‘+‘2‘则是字符串连接。也就是让操作符根据object的不同type来决定自身功能。（又回到上面”类型“的定义了）

------------------------------------------------------------------------------------

Lecture 3

主要就是写循环来各种guess and check，三种方法：

• Exhaustive enumeration（穷举，最常用）
• Bisection search（二分法）：对于浮点型数值，当穷举的step太大可能会跳过正确答案，step太小运行又慢，这时候就要用二分法了，丢一半留一半。
• Newton-Raphson （也叫牛顿迭代法，求近似方程根用）

关于第三个牛顿老爷的方法，为啥这样就能得到一个更优的近似值呢？回到高数的泰勒展开（咳咳）p(x)在g点处的泰勒展开取前两项(后面神马2阶导3阶导n阶导的先统统忽略不计)为：p(x)=（其实是约等于）p(g)+p‘(g)(g-x)，令p(x)=0移项后就得到上图的结果啦。

------------------------------------------------------------------------------------

Lecture 4-函数

1.图灵完全（Turing complete）：一系列操作数据的规则如果具有模拟图灵机的计算能力，就是图灵完全的。详见wiki（扩展：图灵机）简单来说，使用之前学的变量赋值、输入输出、比较、条件分支、循环等工具，任何可计算的问题都能被计算出来。同时，任何可以使用某种语言来计算的问题也可以使用其他语言来计算。

本来想写写图灵机的，后来找到了一篇很风骚的文章：《图灵机与NP》

有兴趣的话还可以搜搜邱奇－图灵论题（The Church-Turing Thesis）

2.Enviroment

和变量赋值一样，函数定义被提交给shell后，在环境（变量-值表）中作为procedure object（过程对象，靠识别器来识别）与函数名绑定在一起

函数调用时，内部参数的操作是在新一层环境中进行的，和原环境的变量无关。

如果觉得这个概念有点抽象，CodeSkulptor有一个很好的功能叫Viz Mode，提供可视化的调试，一步步走下来就能完全理解变量存储与环境了。（要FQ）

总结起来函数的两大特性：

• 分解（Decomposition）：将问题分解成一个个独立的模块（modules），并可重用
• 抽象（Abstract）：函数可以看作一个黑盒，里面细节用户不关心，只需根据函数的详述（specification，也就是说明书）提供合法输入来得到相应结果

------------------------------------------------------------------------------------

Lecture 5-递归

1.Recursive algorithms

• 递归步骤——将一个问题缩小为一个同样版本，但更简单的问题
• 基本事件——持续缩减至一个可以直接解决的简单事件

和数学归纳法的思想是一致的。

2.Using environments to understand recursion

• 每一个递归调用实际上都创造了一个新环境
• 每一层环境中变量与值之间的绑定都是独立的，不会被递归调用所改变
• 当递归调用返回值后，控制流回到上一层环境

3.Global variables

全局变量可在超过函数范围以外的很多地方被看到或修改掉，会破坏代码的本地性

------------------------------------------------------------------------------------

Lecture 6-对象

1.Lists

lists和其他object（如tuple，int，float，str）的不同在于——它是可变的（mutable），内部元素可以修改

2.Functions as objects

第一类对象（First class object）

• 有类型
• 可以是某些数据结构（如lists）的元素
• 可以出现在表达式中（赋值、函数参数）

函数其实也是第一类对象。这个页面或许可以帮你理解。

把函数当做数据结构的元素来使用的方式叫高阶编程（Higher-order programming,HOP） wiki

Python提供的HOP：map（将函数应用于list的每一个元素）

3.Dictionaries

是一般化的lists，元素下标不一定要是整数，可以是任意不可变值（可以是tuple）。下标（index）变成了可查阅的关键字（key），一堆<关键字，值>记录的集合就形成了“字典”。这些记录是无序的。

------------------------------------------------------------------------------------

Lecture 7-调试

1.Test suites

在测试时，我们希望使用一个能有效地揭示bug的输入集合，也就是用尽量少的输入来全面测试出bug的所在。

那么该选择什么样的输入呢？我们可以将输入域划分为子集（每个子集中的输入在正确性上是等同的），然后从每个不同的子集中各挑选一个有代表性的，作为测试用例。可以利用输入域本身的分界来划分出子集，划分时请注意尽量避免额外的、无效的、重复的测试。

2.Black-box testing

黑盒测试：是一种测试应用程序的功能性的软件测试方法。在测试者看来，程序像一个黑盒子一样，只能根据说明书（Specification）知道这个程序是做什么用的，而并不知道其内部的具体细节。好处是可以从一般使用者的角度出发，避免固有偏见。测试时从以下两个角度出发来看：

• 一般情况：根据程序说明书，可能的典型事件有哪些？
• 特别地：可能的极端事件有哪些？

3.Glass-box testing

白盒测试：直译为“玻璃盒子的测试”。和黑盒测试相比，现在测试者完全知道程序的内部结构是啥，因此在设计测试用例时要尽可能走遍每条路径。

测试规则：

4.Test drivers and stubs

单元测试（Unit testing）：测试每个模块。可能产生算法错误。

整体测试（Integration testing）：可能产生模块间的交互错误。

测试驱动（Test drivers）：专门用来做测试的一段程序。建立环境，定义测试集，测试运行并产生报告。如果用到了其他未经调试过的部分，使用Stubs来模拟那部分的行为。

反复进行单元测试与整体测试，直到代码正确后，还需要做回归测试（Regression testing）确保之前运作良好的部分没有因为任何修改而被破坏。

------------------------------------------------------------------------------------

Lecture 8-断言和异常

断言：也就是给程序一些前提条件，使之在安全的范围内运行，最终产生我们所预期的结果。使用断言的好处是简单粗暴，事先将出错情况排除（如果不满足断言，直接产生AssertionError），也就不用考虑如何处理异常的问题。方便调试。缺点是运行中要反复检查是否符合断言，可能会降低效率。

在测试时不应使用断言，还是应当靠异常信息来发现运行不当之处。

断言一般被用于检查数据类型或一些应有的约束。

------------------------------------------------------------------------------------

Lecture 9

当你坑哧坑哧编好了一个程序后，如何来评价它的好坏呢？

首先，这个程序肯定得是正确的吧；其次，它还得有效率（特别是在实时控制中“效率”真的是非常关键的）效率包括两方面：时间和空间。如何在有限的空间内尽快计算出应有结果是我们优化程序和算法的目标，所谓“既让马儿吃得少，又让马儿快快跑”是也。

那么如何度量一个算法的复杂度呢？这里撇开空间复杂度不谈，我们来看看时间复杂度。首先想到的便是“这个程序具体的运行时间是多少呢？”有三方面的影响因素：

1. 机器性能不同
2. Python版本不同
3. 输入不同

前两个因素使用RAM模型（和图灵机一样属于理论模型）可转化为对基本步骤的度量，第三个因素，即根据不同的输入，也分为最好与最坏情况。我们考察最坏情况下的算法执行的基本步骤数。

假设一个算法的问题规模是n，这个算法中的基本操作执行次数是n的函数f(n)（取最坏情况）那么随着n的逐渐增大，可以看出f(n)在总体上是呈现一个增大的趋势的，我们就使用这个f(n)来度量时间复杂度。进一步引入数学中的大O记号，我们定义一个算法的时间复杂度为：

这个大O记号代表什么意思呢？简单来说就是用一个比较简单的函数来表示这个函数的渐进上界，一般取多项式f(n)的最高阶（忽略小阶和常系数）。除了大O符号外，还有大Ω符号（与大O符号正相反，表示渐进下界）和大Θ符号（大O和大Ω取中间）

常见的时间复杂度（越往下越复杂）：

 ------------------------------------------------------------------------------------

Lecture 10

每一个经典算法的产生可能都是创造者耗尽一生心血的成果。对于我们普通程序员来说，虽然创造“新的”有效算法是很难的（天才除外......），但我们可以站在巨人的肩膀上，把每个问题分解为小的子问题，然后利用已有的有效算法求解每部分，最后得到整个问题的解。这一节就主要讲了一些选择、排序算法：

1.查找

包括顺序查找，二分查找（折半查找），哈希表

2.排序

包括选择排序，二路归并排序

常用的排序算法还有很多，像插入排序、冒泡排序（课后有一道习题就是）、快速排序、堆排序、希尔排序等等，有兴趣可以找本数据结构来看，或者去听上面清华的那门课也不错。另外可参考：

• python实现
• 复杂度分析

Python为list提供一个sorted函数，使用的算法叫timsort，后面讲class也会提到。

最后还有两个知识点：

1.RAM模型（随机访问机器模型）

此RAM（Random-access machine）非彼RAM（Random-access memory），属于抽象机器模型 。它最重要的一个特征是：任何存储单元可在单位时间（constant time）内被访问。

python提供一个indirection机制来实现这一特性（使用指针来间接指出元素的存储位置，类似于指令系统的间接寻址）

2.运用辅助空间时，首先分配出一个空间（数组），然后插入元素。当这个空间满了，想再插入数据的话怎么办？采取的方法：重新分配一个新空间，大小是原空间的两倍，再把原来的元素copy到新空间，插入新元素。这样做的效率如何呢？

数据分析证明，每一段的总运行时间与添加新元素所用时间的比值基本<=3，与元素规模n无关（相当于常数时间了）。这里运用的就是“平摊分析（Amortized cost analysis）”的思想，即在一系列操作中即使某一操作的代价很大，但整体的平均代价还是很小的。也就是说，虽然“向已满的空间中插入新元素”这一操作很复杂，但这个更大的新空间是有益于后面的插入的，因此平均代价也没那么高了。

edx6.00 笔记