CMU 15-122

这是CMU 15-122的笔记(和翻译). 这个课程的名字是Principles of Imperative Computation, 即命令式计算原理, 实际上就是教如何在C语言中进行编程的课程, 但却是按照编程语言学家所认为的正确方式教授. 从一开始学生就需要学习如何对于命令式程序进行推理.

最开始学生使用一门叫做C0的编程语言进行编程, 大致上它可以算是C语言的一个精心设计的安全子集, 有着良定义的句法和语义. 之后, 学生从C0过渡到真正的C语言. 课程的内容大致上是计算机科学常识, 基本的(命令式)编程常识, 以及(命令式)算法和数据结构.

当然, 在上这门课之前, 还是要把C0语言先安装好. 课程提供了deb格式的安装包.

讲座1

这节课比较简单, 但主要是为了说明基本的风格. 其检视了一个函数的定义, 似乎是一个施行幂运算的函数. 然而, 也有一点小问题. 之后, 引入了循环不变量, 前条件, 后条件来对于程序进行推理, 并最终证明了修改之后的程序的正确性. C0语言支持用某种形式来表达循环不变量, 前条件, 后条件, 其他的断言等内容. 并可进行执行程序时的动态检查. 一方面, 它可以供人阅读. 另一方面, 它也可供机器执行. 当然, 有些东西不可能在其中表达, 比如说终止性. 这必须另外说明并证明. 本课的最后, 还提示了一下关于模算术的一点内容, 即该函数的正确性是在模算术意义下的.

讲座2

讲座2是关于整数的表示的. 首先, 介绍了自然数的二进制表示, 以及进制的转换. 鉴于将二进制表示转换为整数值其实就是多项式求值, 所以介绍了Horner规则, 中国人也将其称为秦九韶算法. 将一个自然数值转换为二进制表示当然就是通过不断做带余除法. 在C0语言中, int的值用32bit来表示, 其实就是two's complement表示的带符号整数, 所以是模$2^{32}$的算术, 取值范围是从$-2^{31}$到$2^{31}-1$. 两个这样的表示相加其实就是小学的竖式加法, 当然实际机器不是这么实现的. 经过简单的思考可知, 加逆 (也就是相反数) 可以是bitwise complement再加上一: $-x=~x+1$. 并且, $-1$的表示不论是多少位的版本, 都会是全为$1$的串. 十六进制表示的话, 不论C0还是C在词法上前面都会加上0x. $2^{10}=1K$. $2^{20}=1M$. $2^{30}=1G$. $2^{40}=1T$.

除法或许是要特别注意的, 不像加法或乘法即便当成无符号数计算也是一样. 鉴于$2$的大于$1$的幂次都不是素数, 所以非零元不一定都有逆, 于是我们考虑带余除法. 我们用$x/y$表示整数除法, $x\%y$表示整数模 (modulus) 运算, 其中$y\ne 0$. 我们希望它们满足$$(x/y)⁎y+(x\%y)=x\text{.}$$当然, 这还不足以刻画两种运算. 另外, 我们希望$0\le |x\%y|<|y|$. 不过, 在$y$不整除$x$的情况下, 这仍然留下了modulus是正是负的不确定性, 所以需要进一步的规定来限制. 一种方式是约定整数除法运算永远向着零的方向截断. 这会导致一个现象, 就是在$x$为负的情况下整数模运算的结果永远都是负的, 而$x$为正的情况下整数模运算的结果永远都是正的. 另一种约定是整数除法永远向下取整. 这会导致整数模运算的正负和$y$的正负是一致的. C0语言使用第一种约定.

我们不仅用整数来进行数字运算, 很多时候整数也用来表示其他种类的数据, 因此所谓的按位运算也是很有用的. 按位与: &. 按位或: |. 按位非: ~. 按位不可兼或 (异或): ^. 除了按位运算, 左移和右移也是常见的运算. x << k代表x左移k位, x >> k代表x右移动k位. 鉴于C0的(带符号)整数是32bit的, 所以$0\le k<32$. 左移的时候, 空出来的位填0, 这相当于乘$2^k$. 右移的时候, 空出来的位填充最高位, 此即所谓算术右移. 这样做之后, 首先我们看出来$x$将保持符号. 其次, 它相当于除以$2^k$, 向下取整. (这个可以通过计算证明.)

作为一个位的例子, 整数可以用来表示颜色. 这是所谓的ARGB表示. 用3个8bit分别表示RGB, 还剩8bit表示不透明度, 顺序就是ARGB. 如果p表示颜色, 那么(p >> 16) & 0xFF可以用来获得红色分量的值. 这其实就是把红色分量移到最右边的位置, 然后用掩码给其他位都填0. 反过来, 如果想修改某个分量的值, 比如绿色, 设g包含了我们所想修改到的值, 那么(p & 0xFFFF00FF) | (g << 8)就是我们所想要的答案.

讲座3

讲座3是关于数组的.

讲座4

讲座4是关于在数组中进行线性搜索的. 在未排序的数组里, 因为没有能够利用的什么信息, 按顺序搜索是一个自然的选择. 当然, 对于已排序的数组, 我们可以使用所谓的二分查找 (binary search). 不过讲座4实际上还没有涉及二分查找, 而是介绍了在已排序的数组中施行线性搜索. 读者可以看到, 即便是线性查找这一看似简单的主题, 也并非那么容易.

bool is_sorted(int[] A, int lo, int hi)
//@requires 0 <= lo && lo <= hi && hi <= \length(A);
{
  for (int i = lo; i < hi-1; i++)
    //@loop_invariant lo <= i;
    if (!(A[i] <= A[i+1])) return false;
  return true;
}

讲座4

讲座5

第1节 大$O$记号

在设计和分析算法的过程中, 我们试图使得函数的运行时间在数学上精确, 这是通过推导所谓的算法的渐进复杂度度量完成的. 除了想要数学上的精确性, 还要两条基本原则指导着我们的数学分析.

1. 我们想要我们的分析实际有用, 这导致了两个结果.
   首先, 我们观察到我们关心的问题总是随着输入的变大而变得更加困难, 因而我们对于大$O$的定义捕获了我们只关心大输入下算法的行为的想法, 即当算法的所用时间很长时. 正是大输入下算法之间的差异变得真正显著起来.
   第二, 还存在着另外一种数学概念, 大$\Theta$, 你们可以自己了解, 并且这实际上经常是我们真正想要在课上讨论的概念. 但是, 计算机科学家肯定是倾向于基于大$O$记号进行思考和交流. 我们教授大$O$的一部分原因是为了帮助你们能够与其他计算机科学家进行交流!

讲座6 二分搜索

计算机科学中一个基础并且反复出现的问题是寻找搜集 (collection) 中的元素, 例如集合中的元素. 这种问题的一个重要算法二分搜索. 我们使用二分搜索以寻找一个已排序的数组中的整数并指出其位置. 之前的讲座中我们已经讨论过了线性搜索, 并给出了这个问题的一些背景. 本讲座清晰地刻画了算法设计中序的力量: 如果一个数组已经排好序了, 那么我们可以非常高效地搜索整个数组, 比无序的状态下要高效得多.

我们也将又一次看到循环不变量在编写正确代码方面的重要性.

讲座7 快速排序

本次讲座我们考虑两个相关的排序算法, 其运行效率要比之前讲座介绍的选择排序要好得多: 归并排序和快速排序. 我们细致地建立了快速排序及其不变量. 和往常一样, 契约和循环不变量将会弥合算法的抽象想法以及其实现之间的差距.

第1节 快速排序算法

快速排序以不同的方式运用了分而治之的技巧. 我们按照以下方式处理:

1. 选择数组中的任意一个元素 (即所谓的主元(pivot)).
2. 将数组分为两段, 其中一段的元素均小于主元, 而另一段则均大于主元, 主元夹在这两段之间 (即所谓的划分阶段).
3. 递归地排序主元左边和右边的两段.

让我们来分析这个算法的划分阶段的渐进复杂度, 例如我们有数组$$3,1,4,4,7,2,8$$并且选取$3$作为我们的主元, 那么我们需要将这个(未排序的!)数组的每个元素与主元进行比较, 然后得到划分, 其中$2,1$是在左侧的, $4,7,8,4$是在右侧的.

第2节 快速排序函数

第3节 划分

快速排序的代码的最厚部分实际上就是在划分步骤. 一个朴素的想法是挑选主元然后将输入数组的其他所有元素复制到一个临时数组的两端, 小于主元的元素自左开始放置, 大于等于主元的元素自右开始放置. 当结束的时候, 临时数组中必定还会留下一个空位, 而那个位置就是我们应该放置主元的地方. 最后, 我们将临时数组的内容复制回输入的数组之中.

译注: 也可以只把大于主元的元素自右开始放置, 然后空下来的位置的元素都应该等于主元. 如果等于主元的元素不止一个, 那么这将减少递归排序左右两侧的工作量.

这种方法需要分配新的数组. 与之相对的是, 选择排序在排序过程中就不需要分配新的数组. 一个算法若是至多只会分配常量空间, 则将其称为原地的(in-place). 选择排序是原地的, 因为它并不需要分配任何临时空间. 若是我们采用以上想法进行划分, 那么快速排序也不是原地算法, 因为每个对于划分的调用都需要分配等于其输入数组长度的新数组.

译注: 原地算法有多种多样的含义. 其实, 如果直接分配一个等于最初输入长度的临时数组, 似乎也可以满足这里的原地的要求. 不过, 另外一点值得注意的是, 快速排序不会是尾递归的, 所以说它其实不太能满足极端严格意义上的原地要求. 随着数组长度的增大, 快速排序有可能使用更多的栈空间.

但是若是有点小聪明, 我们可以写出原地版本的划分算法! 也就是说, 不需要分配额外内存空间的划分算法. 让我们来考虑划分调用时的情况:
或许我们应该首先注意到的事情在于我们并不知道主元在划分完了的数组里的最终位置! 这是因为我们并不知道有多少元素比主元小.

第4节 实现划分

第5节 稳定性

第6节 归并排序

第7节 练习

讲座8 库

讲座9 栈和队列

讲座10 链表

讲座11 无界数组