计算机日常运用的卓越思想

算法是一张精确的处方，他按顺序详细列出了解决一个问题所需要的具体步骤。每步都必须绝对精确，没有任何人类意图或推测掺杂其中。不管输入什么算法总能运行。

伟大的算法由什么构成：要被普通计算机用户每天用到；能处理具体的现实问题；算法主要和计算机科学理论相关。

本书的目的：让你更加珍视每天在所有计算设备上不停使用的思想的美。就像知道的一点点天文学知识能够增强我在仰望星空时满足感、惊奇感的感受。

搜索引擎索引

搜索引擎的两大主要任务时匹配和排名。

通过索引机制、词位把戏、元词把戏等解决了匹配的问题。

PageRank

PageRank是拉里佩奇发明的网页排名算法。通过超链接把戏、权重把戏将网页的得分计算出来。

由于超链接有可能会形成循环，所以需要使用随机访问者把戏计算出网页的得分。随机访问者模型能同时和超链接把戏、权重把戏结合，每个网页链入链接的质量和数量都会被纳入考虑范围。

公钥加密

一种精巧的安全传递公钥的算法，迪菲赫尔曼密钥交换（颜料混合把戏）。步骤：

你和对方各选择一种私人颜色。

选择一种新的不同颜色并公开宣布，称为“公开颜色”。

你和对方各用一桶公开颜色和一桶私人颜色制造一种混合颜色。这就是你的“公开-私人混合颜色”。

双方都选择对方的“公开-私人混合颜色”与自己的私人颜色混合，双方得到了相同的颜色。

如何将颜色混合把戏转换为数字：（通过离散指数、离散对数的概念，钟算）

你和对方各选择一个私人数字。

双方就两个数字达成一致，基础（例如2）与钟大小（例如11）。

通过求幂后再钟算，将私人数字与公开数字混合起来得到公开-私人数字。

双方将对方的公开-私人数字与自己的私人数字再做一次求幂后的钟算，双方都得到了相同的结果。

纠错码

重复把戏：要确保一些信息被正确的传输，需要重复几次该信息，选取概率高的作为传输结果。

冗余把戏：除了原始信息外，还需要添加一些额外的有效冗余信息。可以将原始消息转换成一条更长的冗余消息，即便这条冗余消息部分损坏，也能判断出来原始信息。

校验和把戏：把精力放在侦错上，侦测到至少一个错误时，请求再发一份数据即可。

简单校验和：将消息中所有数字相加，保留结果的最后一位数字。

定位把戏（二维奇偶校验码）：假如将每16个数字作为一个块，四行四列分别计算校验和，这样在发现存在校验和不一致时，就能通过行列判断出具体是哪个数字不准了。甚至可以通过校验和修正它。

图形识别

图形识别是人工智能的一部分，包括面部识别、物体识别、语音识别和笔迹识别等任务。图形识别任务分为两个阶段：训练阶段，计算机基于一些标记训练数据学习类，其次是分类阶段，计算机对新的未标记数据样本进行分类。

最近邻分类把戏：当你获得一个未分类的数据样本时，首先在训练数据中寻找该样本的最近邻，其次将最近邻所属的类作为你的预测。（稍微更成熟一点的把戏是K个最近邻）

神经网络：神经网络的学习阶段相当耗费精力，需要所有权重和阈值的反复调整，直到网络在训练样本上运行良好。

数据压缩

无损压缩：基本思想是发现数中彼此相通的部分，并运用某种把戏更高效地描述这些部分。（同前把戏/更短符号把戏等）

有损压缩：不是免费午餐，但也是一笔好买卖。抛弃把戏：比如可以简单的将图片没两行或两列像素忽略或抛弃其中一行一列。还原时用相邻像素填充。

JPEG抛弃战略：将整个图片划分为8*8的小方块，每个小方块单独压缩。如果方块恰好是一种颜色，就抛弃63个，如果置有少数像素颜色略有不同，计算机也可以用单个数字代表方块，让方块得到好的压缩结果。如果是从一种颜色渐变到另一种，那么64个数字能被压缩到只有2个。

数据库

事务是数据库中最重要的思想。因为计算程序可能会崩溃，崩溃时丢掉所有正在处理的东西；硬盘和闪存条等计算机存储设备一次只能写少量数据（500个字符左右）。基本上数据库更新两行数据需要两次单独的磁盘操作。

可通过待办日志、预提交、加锁、第二阶段确认提交的方式实现分布式一致性。

数字签名

RSA既是一种公钥加密机制，又是一种数字签名机制。一个数值可通过先跟私钥（挂锁值）进行钟算，再跟公钥（钥匙）进行钟算，得到最开始的数值。知道了挂锁值，能很轻易的计算出合适的钥匙值，反之则不能。

RSA跟一个名为整数分解的古老数学问题之间的联系。没有一种机制被证明时安全的。每一种机制都依赖于一些很复杂、解题时间很长的数学难题。

RSA跟量子计算机的联系。搭建一台规模合适的量子计算机可以暴力破解挂锁值。

任何数字的东西都能被拷贝，而签名不能被拷贝，这一悖论解决的答案是：一个数字签名同时依赖一个置有签名者知道的密码和被签署的消息。对由某一特别实体签署的所有消息，秘密都相同。所以copy的事实无关紧要。

并非万能的算法

有些问题根本不可能同通过计算机解决，我们再大部分时间里都能很好地解决不可判定问题。