这学期选的一门水课，以下来整理一下这门课的主要内容。
1 二进制
2 编码与压缩
3 错误检测与纠正
主要讲了奇偶校验，用了棋盘作为例子，在左侧和下侧增加一行，保证每行、每列的白色棋子（0）的数量为偶数。
基于奇偶校验的 RAID5 等。注意此方法只能纠正一个错误。
另一种错误检测的例子为 ISBN 码，原理很简单，即对于每位数字赋予一个权重，最终得到一个校验位，来确保某一位数字出现出错的时候能够被发现。身份证的末位也是此原理。注意，此方法只能检测而不能纠正错误。
还讲了纠错编码。汉明距离为在一个编码系统中，一个字符的编码与另一个字符的编码之间的最小编辑距离（需要修改多少位）。一个汉明距离为 3 的编码，可纠正一个错误，发现 2 个错误。（那么问题来了，如何判断是错误了 1 位还是 2 位呢？）
4 搜索
简单的搜索算法：线性搜索；二分搜索；哈希搜索。
5 排序
排序分了两章讲。只讲了基于比较的排序。包括三种很傻的排序算法：选择排序；插入排序；冒泡排序。以及进阶的两类算法：快速排序和归并排序。
在前一类算法中，时间复杂度均为 $O(n^2)$。
- 选择排序每次选最小的拿出来，因此相对其他的排序优势在于交换的次数少。
- 插入排序就像抓扑克的过程，但是在插入过程中需要一定的交换操作。当然，这里还可以在插入过程使用二分查找的方式加速算法。
- 冒泡排序，优势在于若原本的队列已排好序，则仅需要扫描一次（当然，这只是偶然情况，劣势也很多）；而事实上这种排序的效率最低，因为涉及到大量的交换操作。
现实中一般会选择更快的排序算法，时间复杂度为 $O(nlog(n))$。
- 快速排序，想法是每次选择一个「基准」，将整个数组分成两类，在这两个子数组中递归求解。
- 归并排序，从 2 个数字的排序开始，每次对于排好序的子数组做归并操作。
均体现除了分治的思想，快速排序是「先治后分」，而归并排序是「先分后治」。
另外，注意，在上述算法中，选择排序和快速排序不能保证稳定性（即相同数字按照出现顺序排列）。
7 有限状态机
【笔记】计算思维-期末提纲
原文：https://www.cnblogs.com/easonshi/p/12085210.html
