笑傲演算法江湖的独孤九剑

2020-07-28 878人围观 ,发现71个评论
笑傲演算法江湖的独孤九剑

图片来源:The Social Network

最近恰巧在书店看到了一本书,书名叫做演算法统治世界说明了演算法如何的重要如何与生活息息相关,很可惜书中并没有提到太多关于演算法的实质内容。最近刚好在因缘际会下也读到了一本觉得非常实用的书 “ Algorithms That Changed the Future”,中译 “ 改变世界的九个演算法 ” 由 John MacCormick 合着。 本书以一种非常浅显易懂的方式,试图让不论是否具有背景的读者们都能够了解这些伟大的演算法如何运作,以及他们是怎幺样在各层面影响我们的生活。

为何需要了解演算法

不论看到各种议题,大家心中所想到的往往是:与我何干?。 在如此繁忙的生活下,我们已经很难拿出额外的精力去注意与自己不相关的议题了。但是电脑运算正一点一滴地改变我们的生活,我们或许没有办法全盘的去了解它的运作。但我们可以藉由概念性的去理解其核心,然后去明白究竟在生活上电脑运算的发展会对生活产生什幺样的影响。举个例子来说:我们知道轮胎或者是鞋子上了防滑纹路是为了要增加摩擦力,因此我们知道当纹路磨损之后要换新的。但非专业人士的我们不需要去了解纹路的设计对摩擦力的影响,以及计算究竟可以产生多少摩擦力。

什幺是演算法

那究竟何谓演算法? 演算法简单来说就好比是一个「精确的食谱」,把我们所遭遇到的问题的解决方法,藉由有系统与条理的方式一步一步的解释清楚。从上述我们可以知道几件事情:

因为上面的几个特性,我们才能够藉由将演算法编写成程式利用电脑做运行计算,来解决我们生活上的问题。

在这里举一个很简单的演算法实例,费波纳契数列求解给想要看一下演算法长什幺样子的读者们。但这部分与书中内容无关只是让读者知道真正的演算法大概长什幺样子。

费波纳契数列

首先先解释费波纳契数列: 0、1、1、2、3、5、8、13、21、34 。这个数列的特性是:

  1. 第一个数为 0
  2. 第二个数为 1
  3. 从第三个数开始,每个当前的数为前面两个数的总和。举例来讲:
    2 = 1 + 1,3 = 1 + 2,5 = 2 + 3。
问题

现在的问题是费波纳契数列的第 n 个数是什幺? 举例来讲,当 n 为 1,答案就是 0,n = 3 答案就是 1,n = 5 答案就是 3。

演算法

我们可以发现,除了第一个与第二个费波纳契数没有办法用公式解之外,其他的数字都有规律。。

从上面这个数列我们得到下述的演算法:

  1. 当 n = 1 答案就是 0
  2. 当 n = 2 答案就是 1
  3. 当 n 不为 1 或者是 2 ,我从第三位开始将每一位算出来并记下来直到我算到第 n 位。计算的方法是: 当前的数字等于前两个数字之和。然后得到第 n 位的答案。

我们再举个例:假设今天 n 是 5 。我的演算法会有如下的步骤:

  1. n = 3,于是我把已知的第二位与第一位相加 1 + 0 = 1
  2. n = 4,我把刚得到的第三位与已知的第二位相加 1 + 1 = 2
  3. n = 5,我把刚得到的第四位与刚得到的第三位相加 1 + 2 = 3
  4. 我得到第五个费波纳契数是 3

读到这里或许有读者问为什幺要这幺麻烦?第五个数不是一看就知道是 3 吗? 是的,因为我们现在数字很小,那假设我们说的是第两千个费波纳契数呢? 或者是第两万个费波纳契数呢?人没有办法在这幺短的时间内计算并记住这幺多数字,所以才需要利用演算法,让电脑来为我们处理。

九大演算法

当然,在书中并不是像上面那样子,一行一行的列出解法,而是藉由简单有趣的例子,以及一些简化的数字运算来为我们点出这几个演算法的精髓部份。在书中提出了八个与我们生活切身相关的演算法与一个如果存在将会很了不起的演算法来讨论电脑能力的极限。其中现存的八种如下:

搜寻引擎的索引

搜寻引擎的索引,是帮助你我在网路上正确地找到资料不可或缺的工具,我们要怎幺样才能够做有效的搜寻让我们从网路海中捞出一根针?

网页排序

当我们搜寻关键字,出来了这幺多的页面,我要怎幺样才能判断哪个页面是真正重要的?才能优先将它列出来?

公钥加密

我在亚马逊上输入我的信用卡买东西,我要怎幺才能够确定我的资料只有亚马逊才看得到?

错误更正码

网路更正码被应用在网路之间封包的传递,以及 CD、DVD 还有硬碟上。祝要是用来确认我所读取以及接收到的资料是否正确。举例而言:假设我电话传错一码,那我整个传送就没有意义了。

辨识模式

辨识模式被广泛应用在人工智能上,像是语音便是服务客户的自动电话,网路上按照个人兴趣推荐商品以及大数据的处理,辨识模式都占有一席之地。

资料压缩

我们总打开或者是将档案做成过 zip 或 rar 档吧? 图片以及文字是怎幺样缩小与放大都与资料压缩有关。

资料库

银行的资料库要怎幺样才能确保我的交易是正确的?我会不会在交易的时候因为银行的伺服器当机然后钱没了?我要怎幺样才能够让资料可以更快的储存与被读取都跟这部分有关

数位签章

一般而言我们并不会接触到数位签章,因为我们的电脑会自动对数位签章做检验,通常发生在下载软体的时候。

这些演算法所包含的範围有:网际网路搜寻、网路安全、资料传输的正确性、大数据、以及资料储存与处理等。每项都与我们的生活紧扣,除非我们完全不使用电脑,否则你我都会多少接触到上述演算法所涉及的领域。

公钥加密

在书中,最令我印象深刻的一段是公钥加密的部分,利用以涂漆做举例让大家来了解公钥的基本精神,因此在这里特别和大家分享。

问题如下:假设今天有三个人我、你、他以及有很多罐颜料,每个人有自己的小房间可以藏自己的颜料。在所有的沟通必须公开透明的情况下,我该怎幺样才能够在他不知道的情况下混合出和你相同的颜色?假设颜色代表秘密,我和你该怎幺样才能在他的眼皮下传达你我共同的小秘密?

演算法如下:

  1. 我们每个人选出自己的个人色
  2. 我们任一个人选出公共色
  3. 我与你将公共色与自己的颜色做混合,并公开混合之后的颜色
  4. 解答慎入 1

为了不妨碍读者思考的乐趣,在这里将演算法的最后一步写在最后,但在这里有两个重要的假设,其中之一是颜色非常的多,所以他无法知道我选的个人色是什幺,再来是我无法将颜色重新分开来得到原本你选的颜色。

结语

演算法一直是每个电脑科学系的必修,常常我们在学习的时候却陷入了数字的囹圄或者是因为理论而晕头转向但很多的时候我们不妨可以像书中介绍的方法一样,退一步,仔细看清楚这些演算法的全貌仔细想清楚他们想要解决的问题试着用生活的方式所举例来加深自己的了解。

书中所介绍的演算法其实都非常的重要,在笔者就学的期间几乎学过,或接触过更甚至亲手写出程式来执行一半以上的演算法。往往很多人认为现在在写 App 大多都是使用 Library,究竟演算法有什幺重要的?我记得当时在演算法课上,老师告诉我们两个答案:

  1. 因为国外面试都问演算法
  2. 学习演算法是一种思维的训练可以让你变聪明。

很多的时候学习演算法可以让你在学习各种新的东西上都快速了许多,因为我们必须从每个角度来检视自己的思考是否正确,然后将每一步都说明清楚来得到正确的答案,长久下来训练自己的思维就是让你自己与别人可以分出差距的地方。

也同样的,很多新的想法都是建立在原有的基础上,学习演算法可以让我们在遇到新的问题的时候,靠着原有的基础想出更新更快的解法。这也就是为什幺在国外公司面试的时候,演算法受到如此的重视。因为知识性的考题可以靠着记来补强,但是思维却没有办法短时间训练。

这里再举个例:假设学过化学,我们就不会说出类似吃盐细胞会爆炸或让身体腐蚀之类的话 2。

在电脑运算如此发达的时代,我们非常幸运的可以站在这些巨人的肩膀上了解好几十年下来所累积的智慧。

  1. 只要你我都个把对方的公共混合色带回自己的房间加上自己的个人色即可 ↩
  2. 宝杰,你说说看钠有多恐怖?↩
不容错过