看完这本书,印证了一个基本想法:思考方法,产生思想;思想,产生算法。
灵锐的思考方法,产生灵锐的思想;灵锐的思想,产生灵锐的算法;灵锐的算法,加上贴合上时代的呼唤、普及的应用,华丽变身,成为伟大的算法。
作者眼中,“伟大”算法,要满足三个标准:
1、要被普通计算机用户每天用到;
2、它是针对某个特定问题的具体程序,而不是一些通用的,能解决众多问题的程序;
3、要跟计算机科学理论相关。
(I)搜索引擎索引&PageRank算法
索引算法,包括匹配算法和排名算法两部分。
匹配算法,背后基要而朴素的思想是:只要知道查询词在哪(页面编号、位置),就能将包含查询词的页面找出来(技术上,生成一张查询词与页面编号-位置的对应表,etc.);
排名算法,背后基要而朴素的思想是:越与用户查询相关的页面,理应排在越前面;相关的标准可能很多样,比如查询词距离靠的越近、出现在页面越重要的位置(etc. 标题、描述行…),说明这个页面的内容与查询词的相关性可能越高…
PageRank算法(网络时代,更好的排名算法),背后基要而朴素的思想是:权威性网页通过超链接向其他网页传输权重;权重越高的网页,其重要性,以及查询相关性越高,应该排在越前面。
上述这些思想背后,都用到了这种思考方法:
1、简化问题与思想实验:1)思考匹配问题,将问题简化到我们是如何查找一个词在书中哪些地方出现的?(“cheetah,124,156”,“cheetah”,在书中124页和156页出现)
2)思考排名问题,将问题简化到我们如何确定某两个网页哪个应排在前面(“malaria cause”,第一个页面malaria cause靠在一起,第二个页面两词远离,通过理性我们知道第一个页面与我们查询词相关),说明查询词离的越近,查询相关性越高,排名应越高…
3)思考网页排名问题,将问题简化到只有两个教授菜谱的页面,一个有5个导入链接,另一个有2个导入链接,从理性角度看,导入链接越多的,说明人们对这个页面的反应越热烈,应该有更好的排名。
(II)公钥加密算法
公钥加密算法,背后基要而朴素的思想是:
a. 如果发信人和收信人,都知道一个其它人不知道的共享密码(信息),发信人就可以把要发送的信息与共享密码混合起来,发给收信人;收信人可以凭共享密码和约定的规则解密;
b. 如果发信人和收信人互不认识,也可以凭借数字混合的技巧,达到信息加密的目的。
上述这些思想背后,也用到了这种思考方法:简化问题与思想实验。
假设在一个房间里有三个人,A、B和C。A要传给C一个1位的信用卡卡号,比如7,且不能耍小把戏比如递纸条或小声说。因为A和C熟识且是多年朋友,A可以利用两人之间共有的记忆,比如A小时候住家的门牌号322(C小时候经常在A家门口玩,记的A的门牌号)来进行加密。比如A可以说:C,还得的小时候我家的门牌号吗?把这个门牌号加上我要你知道的信用卡卡号,你会得到329。这时,A的门牌号322,就是只有A与C知道,但B不知道的秘密信息,也称共享密钥。借由共享密钥,C将329-322,就可以得到信用卡卡号7,成功解密了。
上述思想实验,是非常简化的一个例子。实际上,为防止共享密钥被破译,共享密钥往往是128甚至更多位的数字,且要进行复杂的数学加密处理(分块、转换、混合)。但这些只是算法与技巧上的处理,其基本核心的思想,就是在上述描述的例子里。