这学期选的一门模块课,选用教材为 不插电的计算机科学 复习主要过一遍 PPT,这本教材网上有边免费的英文版,不过总体的难度较小,不看也罢。

以下来整理一下这门课的主要内容。

1 二进制

数字,文字编码,图像,色彩的表示。在图像中提到了游程压缩。

2 编码与压缩

主要有霍夫曼编码,LZ 压缩

3 错误检测与纠正

主要讲了奇偶校验,用了棋盘作为例子,在左侧和下侧增加一行,保证每行、每列的白色棋子(0)的数量为偶数。

基于奇偶校验的 RAID5 等。注意此方法只能纠正一个错误。

另一种错误检测的例子为 ISBN 码,原理很简单,即对于每位数字赋予一个权重,最终得到一个校验位,来确保某一位数字出现出错的时候能够被发现。身份证的末位也是此原理。注意,此方法只能检测而不能纠正错误。

还讲了纠错编码。汉明距离为在一个编码系统中,一个字符的编码与另一个字符的编码之间的最小编辑距离(需要修改多少位)。一个汉明距离为 3 的编码,可纠正一个错误,发现 2 个错误。(那么问题来了,如何判断是错误了 1 位还是 2 位呢?)

4 搜索

简单的搜索算法:线性搜索;二分搜索;哈希搜索。

5 排序

排序分了两章讲。只讲了基于比较的排序。包括三种很傻的排序算法:选择排序;插入排序;冒泡排序。以及进阶的两类算法:快速排序和归并排序。

在前一类算法中,时间复杂度均为 \(O(n^2)\)

  • 选择排序每次选最小的拿出来,因此相对其他的排序优势在于交换的次数少。
  • 插入排序就像抓扑克的过程,但是在插入过程中需要一定的交换操作。当然,这里还可以在插入过程使用二分查找的方式加速算法。
  • 冒泡排序,优势在于若原本的队列已排好序,则仅需要扫描一次(当然,这只是偶然情况,劣势也很多);而事实上这种排序的效率最低,因为涉及到大量的交换操作。

现实中一般会选择更快的排序算法,时间复杂度为 \(O(nlog(n))\)

  • 快速排序,想法是每次选择一个「基准」,将整个数组分成两类,在这两个子数组中递归求解。
  • 归并排序,从 2 个数字的排序开始,每次对于排好序的子数组做归并操作。

均体现除了分治的思想,快速排序是「先治后分」,而归并排序是「先分后治」。

另外,注意,在上述算法中,选择排序和快速排序不能保证稳定性(即相同数字按照出现顺序排列)。

7 有限状态机

主要是五元组 \((Q, \Sigma, \sigma, q_0, F)\)

  • \(Q\) 有限状态集
  • \(\Sigma\) 输入字符表,或者说是动作
  • \(\sigma\) 转移函数 \(Q\times \Sigma \rightarrow Q\)
  • \(q_0\) 为初始状态
  • \(F\) 为 Q 的子集,终结状态集

8 递归与分治

递归注意需要:1. 边界条件,即终止条件;2. 递归模式,即如何把大问题转化为小问题。

分治,注意:1. 划分;2. 求子问题;3. 合并。上面的归并排序、快速排序、二分查找都可以看做分治算法。

另外的例子有:棋牌覆盖问题;循环赛日程安排问题。

9 数据结构

讲了线性表和树结构。

线性表中,当然会讲栈和队列。关于 LIFO 栈的应用:1. 在递归函数中,计算机存储的代码即利用了栈结构;2. 括号匹配。而 FIFO 队列,则可用于作业调度(防止计算机活锁)。

树结构中,讲了如何把一般的树转化为二叉树——即「左儿子右兄弟」。还介绍了二叉搜索树,可以:1. 搜索;2. 插入;3. 删除,对于 Delete 操作,难点在于删除节点有两个孩子的情况,这时候需要找到比这个节点大的最小的那个节点,注意到该节点一定是没有左孩子的,将它拿过来代替要删除的节点。

10 图算法

讲了图的表示:邻接表和邻接矩阵。以及 DFS 和 BFS。还有拓扑排序,这里注意到,若为(上)三角阵,则必能拓扑排序。

11 网络,带权图

最小生成树的两个算法:Kraskal 和 Prim 算法。前者,对于所有边按照权重排序,从小到大检查,若不形成环,则加入集合(用到的数据结构为并查集,可在 $ O(|E|)$ 时间内判断结果)——注意,这里在生成过程中可能出现森林。而对于 Prim 算法,则是从一个节点出发,将这个节点和图中其余节点分割,这两个不相交的节点集构成了整个节点集的一个割,在连接这两个不相交节点集的「桥」中,每次选择一条最小边加入——注意此时是从一个较小的树长成最小生成树的。另外,在这里不仅这几涉及边的排序,需要动态的删除和插入,因此不同于 Kraskal 算法中的简单排序,这里用到了二叉搜索树,实现了动态查找。

活动网络,在图算法中,拓扑排序解决了活动网络的先后顺序,下面需要判断哪些活动会对整体的完成时间产生影响,即找到关键路径。

对于网络表示,我们用节点表示「事件」,即在此之前的边全部已完成,可以开展后续活动;而用边表示「活动」,每条边上有该活动所需的时间。另外,整个网络还有一个源 source 和汇 sink 。问题都是找关键路径。

12 并发与死锁

主要讲了数据库的并发操作。若不进行限制,则可能出现三类问题:

  • 丢失修改 lost update,即 \(T_1\)\(T_2\) 同时修改,最终结果出错
  • 不可重复读 nonrepearable read,在 \(T_2\) 修改/删除前后, \(T_1\) 读取结果不一致
  • 读脏数据 dirty read,在 \(T_2\) ROLLBACK 的过程中,\(T_1\) 进行了读取

因此,需要并发控制,主要的策略有:1. 封锁 locking;2. 时间戳 timestamp;3. 乐观控制。主要讲第一种。分为排它锁 exclusive lock(X 锁,也叫写锁)和共享锁 share lock(S 锁,也叫读锁)。

有了这两种锁,还是有可能出现问题:活锁,即由于其他的请求某一程序无限等待,这一问题只需要采取「先来先服务」的有限策略即可。

对于死锁,预防的方法:1. 一次封锁;2. 顺序封锁,都会造成并发程度减少,而且更大的问题在于程序执行之前并不知道要求的数据有哪些。而如何诊断也有:1. 超时法,即粗暴地设定一个阈值;2. 等待图,即画出等待依赖关系,检查是否出现环。如何解决死锁,一般是插销代价最小的那件事务。