《改变未来的九大算法》
刚刚读完一本书， 《改变未来的九大算法》。属于经济学读物，并不是给计算机专业的学生读的。但是读的过程还是很爽，介绍了伟大的计算机、人类指尖的精灵的构建算法。国外的教授讲东西真是举重若轻，轻车熟路，可以看出人家对问题的研究以及对事物的热爱。John MacCormick，并不算很特殊很著名的教授，但是能写出这种书，国内要多久才能出现有这样的情操和理想的教授呢。
简介
这是一本科普书，重点在于向一点儿都不懂计算机的人讲述计算机科学的美妙。我们每天都在使用着计算机带来的便利，包括互联网，但是真正能感受到它的美的人却极少。在国内，我只能说极极少。作者将算法比作人类指尖精灵的构建，并解释了为什么我们要关注那些伟大的算法，有一个很好的比喻：
我肯定不是一位天文学专家…… 但每当我注视夜空，我知道的少量天文学知识增强了我对这一经验的享受。希望在读完本书后，你在使用计算机时也能经常获得同样的满足和惊奇之感，这也是我殷切的希望。你将珍视我们时代最常见、最神秘的黑盒子：你的个人电脑，你指尖的精灵。
本书简介恰当的描述了九类算法：搜索引擎索引、网页排名、密钥交换、纠错码、图像识别、压缩算法、数据库基本算法、数字签名和不可存在程序。
作者挑选的伟大算法基本都满足普通人几乎每天都会用到、不仅限于计算机专业人士使用和解决专有领域问题。所以经典的诸如排序算法、图论等并没有介绍。真正的没有一点儿计算机科学基础是不可能的，但是对专业知识的要求并不高，如果你学过类似的知识，本书的描述绝对会让你眼前一亮。
搜索引擎索引和网页排名算法
这两章几乎没有什么难以理解的东西。作者从科普的角度描述匹配和排序，描述了最原始的搜索引擎原型以及如何采用一些措施来让搜索实现高效。
由简单索引到带词位置的索引。词位置真的很有意思，记录每个单词在哪个页面以及是第几个单词，就可以实现句子查找，也能找到若干单词的相邻位置，从而得到更可能的有用信息。同时将HTML标签作为单词并记录其所在页面和位置，可以实现标题、内容、链接等的查找。
网页排名算法重点介绍了PageRank，Google创始人佩奇和布林在一片学术论文《解析大规模超文本网络搜索引擎》中提及。但书中并没有消息介绍PageRank，而是只介绍了最好理解的超链接实现网页排序。
这也很好理解，如果很多网站可以链接到你的网站，那么你的网站相比同类其他网站排名就会高一些。而引入权重的概念，可以增加权威性和排名的有效性。为了防止恶意刷链，也会采取类似防止垃圾邮件的措施。
公钥加密
作者对公钥加密和密钥交换的描述简直堪称完美，通过一些铺垫以及三个例子，极其优雅的介绍了这一算法。
颜色例子
三个人A、B和C，A和B要实现信息交流，C是企图偷窥秘密的邪恶者。假设要传递的消息是颜色，A和B要达成一致，即他们俩都要知道一种颜色但是C却不知道。作者用了房间、角落、隔板等实物来描述算法，还规定A和B不能通过悄悄话、传纸条来实现。我这里就简单描述。
A用仅自己知道的颜色比如红色，混合某一种ABC都知道的颜色比如黄色，将混合色放出来，B和C 都可以拿到。B用仅自己知道的颜色比如紫色，混合那种ABC都知道的黄色，将混合色放出来，A和C都可以得到。这个时候神奇的事情发生了，A把自己的颜色红色和B放出来的混合色二次混合，得到终极色；同样B用A放出来的混合色和自己的颜色黄色二次混合，也得到终极色。这两种终极颜色是一样的，A和B就某种颜色达成了一致，C虽然也能得到公共信息，但是却无所作为。
这个例子是非常好的，因为颜色混合可以类比hash算法，单向hash。达成一致颜色也可以类比实现密钥交换。
公钥加密的主要用途之一就是实现密钥交换，一旦就密钥达成一致，就可以使用很快的对称加密算法对数据进行加密，这个时候就是很安全的了。
作者还介绍了通过幂运算实现的公钥加密，还有充满传奇色彩的公钥加密历史。很不错。
纠错码
纠错码在于纠正数据传输过程出现的数据遗失、被修改等问题。Richard Hamming，也是充满传奇色彩的一段历史。
通过重复信息可以在一定程度上达到纠错，比如反复请求一段数字，通过比对收到的若干段，尽可能的得到正确数字，但是反复重复复杂性太高。冗余信息比简单重复更高效一些，比如用five表示5，虽然要传输的数据变长，但是收到信息后对five的判断要比单纯判断某个数字5发生变异简单得多。
校验和是纠错领域的重要措施，好的校验算法几乎可以确定数据是否发生正常情况下的错误。这里的正常情况指的是不被黑客等完全篡改。而通过定位校验码还能达到对数据的修复，比如将数据按二维格式放置，计算每一行每一列校验码，就几乎能准确发现哪个数字出现了问题。
这里还提到一个伟大人物：香农。写出了堪称史上最有价值的硕士论文。还有其他的一些故事。
图像识别
对图像识别的研究我们可以找到一些自信：计算机在某些方面，现阶段还远远不能跟人类相比。比如图像识别和人工智能。
作者首先定义了图像识别要研究的问题，即做到对物体的分类。比如判断手写的1属于阿拉伯数字0-9的那个类。要解决这个问题，即做好图像识别，需要两个方面：大量的学习经验和对未知事物的分类阶段。作者介绍了三种算法。
最近邻分类算法。这一算法通过输入大量的数据，比如输入大量的不同风格的手写0，当我们识别新的手写0的时候，就计算这个新的事物和已知经验大量输入的手写0的距离，这个距离也是自己定义的，比如可以根据像素点的不重合度定义距离。距离最小说明最相邻，而属于这一类的可能性也更大。
决策树算法。这个有点类似prolog语言，通过判断是和否得出结论。作者举了一个例子：判断网络垃圾，比如前面提到的恶意刷链接网页。首先，人工输入大量的已知恶意刷链接网页，然后指定一系列问题，通过调整问题，做到尽可能的判断出人工输入的网页，这称之为学习阶段。而分类阶段也就是实用阶段，这就需要根据之前学习的来的那一系列问题，判断未知网页是不是网络垃圾。
神经网络。神经网络很流行，好多人都听说过，但是究竟是怎么一回事，大部分人还是不得而知。简单来说，就是模拟人类大脑的神经元传递信息的过程。某个神经元输入信号，对下一个神经元产生抑制或者兴奋，然后再进行下一次相关传递。神经网络算法就是这样，将原始输入作为原始信号，即初始神经元，这些输入信息将产生兴奋正向判断或抑制反向判断，并对下一个神经元起作用。这样一直链接到最后一个神经元，这里就是我们需要的某个识别结果。神经网络还引入权重，进一步提高识别的准确度。
神经网络也是需要学习的，通过调整每个神经元相关信号的权重正表示兴奋负表示抑制，尽可能准确的做出识别和判断。
同样，这一章也提到了传奇的历史1956年大特茅斯大学的人工智能会议。
读完这一章之后，脑海中回忆起很多相关的算法：并查集、tarjan算法、缩点等等，感觉这些都是解决人工智能领域问题的必要条件。而我几乎不可能在这一领域做出什么贡献，真是很伤心的事情。人总是在不经意间就堕落了。
数据压缩
数据压缩分为无损压缩和有损压缩。
无损压缩常见的有相同前缀合并算法和更短符号替代算法。相同前缀很容易做到无损压缩，比如用1-100表示**AAbfdjkadjfkl……**等100个数字既方便又准确，但是适用范围有限，并不是所有的数据都有大量的重复前缀。更短符号替代跟前面纠错码中提到的在一定程度上相反：为了做到压缩，用5表示five。但是两者并不冲突，只是为了完成不同的任务。更短符号替代有一个经典算法：Huffman树，这个计算机学者应该都知道。
有损压缩用到的有丢弃并不重要的信息和分块然后用一个单位表示。有时候丢弃一些信息并不会产生严重的后果，比如听音乐的时候丢几个音节并不会被大部分人听出来。分块压缩也很常用，比如一张图片，有一片儿全是白色，那么用一个白色像素就可以代替，有的分块后不是同样的颜色，只好选取一个合适的像素来代替。有损压缩还原后并不会和原来的数据完全一样。
这一章也提到了香农，还提到Huffman和法诺。香农和法诺起名，而Huffman居然是法诺的学生，很兴奋的事情。
数据库
今天刚好去上数据库课了，抄select、create、update，觉得严重侮辱智商，抄完作业就跑了。我们的大学课程就是这样，其他课程其实也是这样，从来不关心真正有价值的东西，一些随便一搜索就能学会的东西你用那么多时间讲它干嘛？
不说这个了，回到主题。事实上我也没有意识到数据库要求会有那么高，比我想象的要高。作者又一次举重若轻的描述了问题所在和问题解决方案。
数据库的关键在于一致性、完整性和安全性。一致性很重要，出现冲突是不可忍受的。完整性同样，如果银行丢了你的信息，那你的存款可能变少或者没了。安全性更重要，数据丢失是很可怕的事情。
一致性的解决方案是使用待办事务表。事务定义为数据库要做的一系列操作，也就是你输入一条语句，然后数据库要做的事情。将事务写入表中，完成之后再销毁。如果做事情的过程中出现故障，只需要查看表就可以知道该怎么解决问题。
预备提交可以解决数据完整性和安全性要求。
重要的数据库必须有多份复制，而且要尽可能在地理上分开一些，以免某一处被毁而导致数据丢失。这里的复制指的是实时同步，并不是我们平常使用的备份。备份也可能导致重要数据丢失，这是不能忍受的。事务要允许回滚，这样当出现诸如某个复制点硬盘用完或者出现死锁等情况时事务回到某个合法状态。
有了复制和回滚的概念，理解预备提交就容易了。多个复制中有一个主机，它首先做出某个动作，然后通知其他复制，如果其他主机通过判断这个动作是否可以完成，然后将信息交给主机，预备提交的第一阶段就完成了。第二阶段根据其他主机返回的信息进行决策，如果其他主机不能完成操作，那么就要回滚，反之则完成真正的事务提交。
数据库是大型工具，真的很大型。它的设计并不像想象的那么简单，存几个数据，然后查询。要是一个人用还可以，但一个人用也用不着数据库，直接放文件里就行了嘛。
这章提到的历史跟吉姆格雷相关，这个伟大的任务提出事务处理的概念，但是却在一次游艇出游的时候与世界永远的失去了联系，估计又是上帝觊觎他的才华了。
数字签名
数字签名就是利用公钥加密实现不可否认和认证。作者用了很好的一个例子，将CA比作法官，证书比作锁。我在之前写过类似的文章，这里就不多说了。
数字签名和公钥加密真的是太好了，简直是绝妙啊。直觉告诉我们这种事情不可能实现，但是公钥密码的出现告诉我们这可以实现，计算机科学真是伟大的学科。
有一些程序永远写不出来
第九类算法并不是某个具体的算法，而是说明有些程序永远不可能写出来。作者举了一个很好地悖论例子，说明了这样的程序是不能写出来的，不管人工智能领域再怎么发展、计算机硬件再先进，就像1+1不被人承认是3一样，有些程序就是写不出来。
(⊙o⊙)… 写了好大一段，发现自己并不能很好地描述清楚作者提到的那个Yes和No的例子，而且就要断电了。只好就此结束了。再提一句，算法是美妙的。