本文选自图灵认可的《算法小时代》一书。【遇见数学】特别感谢！

什么是算法？

要理解什么是算法，首先要想象一个场景。几千年前，一位祖先试图根据他对已故祖母如何制作面包的记忆来制作自己的面包。但他真的不知道该怎么办。他犹豫了。起初，他把麦粒放在沸水中，然后他对自己说，这可能是个坏主意。这位祖先的困境正是我们都面临的。——遇到了一定的问题，但是我们不知道怎么解决。我们思考解决方案，尝试，反复探索实验，顺便做了一点意想不到的发现，直到成功……或者失败。

然而，真正的面包师不会这样做。他们不会为每一个烤箱的面包制作烘焙食谱，因为他们已经掌握并记住了面包的烘焙方法。多亏了面包食谱，面包师每天都能给我们提供面包。事实上，人类文明的发展不仅仅是因为一些人的发明，也是因为其他人“复制”了这些发明来改进它们。然而，我们已经忘记了面包食谱的价值。首先，食谱减少了不确定性：感谢它，面包师知道，除非有突然的灾难，面包将准备好晚餐。有了这个食谱，任何人都可以不用任何想象力或天赋来制作面包。就两位作者而言，我们没有任何烘焙面包的天赋，但我们仍然可以从网页上找到Chabati的食谱，并借助更具想象力和天赋的面包师撰写的方法，用适当的面团强度制作面包。最终，这个食谱成为了人类遗产的一部分，在几千年的漫长历史中代代相传。

菜谱是一个算法，所以我们对“算法”这个概念有一个初步的定义：一个算法就是解决一个问题的过程。我们不必每次都发明一个解决方案。

甜番茄黑豆卷食谱

从这个定义中不难看出，我们一直在发明、使用和传播各种“算法”，用于烹饪、雕刻石器、捕鱼、种植扁豆和小麦等等。

00-1010有些算法不同于面包食谱。他们可以解决书写符号的问题，比如数字和字母。算法汇集在一起，形成数字、单词、句子和具有不同含义的文本。

例如，二分搜索法算法用于在字典中搜索特定的单词。二分搜索法方法从词典的中间开始搜索，比较目标词和中间词的位置，根据目标词是在中间词的前面还是后面，选择词典的前半部分或后半部分作为新词典，然后继续用二分搜索法方法搜索，以此类推，直到找到目标词。该算法解决了包含——个字母的书写符号的问题。还有一些算法可以实现加减法等。并解决了涉及另一个书写符号，——数字的问题。这种算法被称为“符号算法”。

计算机科学家经常把“算法”这个词的意思限制在这种“符号算法”上。考虑到这种局限性，我们自然无法将算法的历史追溯到文字发明之前。然而，广义的算法概念其实和文字一样古老。从人类迄今发现的最古老的文字痕迹来看，说明古代书法家已经开始使用算法，如加法、乘法等进行记账。这大概就是文字被发明的原因。

进程和符号

数学家从很早的时候就开始关注算法的设计。比如公元前300年左右的bzdyb算法可以计算出两个整数的最大公约数。让我们简单解释一下。如果读者觉得爬数学lydwd很难，可以直接跳过这一段，或者试着把下面的内容理解成一首深奥的诗。

一般来说，算法会在输入端接收数据，这些数据构成了算法的参数。在bzdyb算法中，输入数据是两个非零整数，设置为A和B，A大于B，例如A等于471，B等于90。通常，算法会在输出端返回一些其他数据。在bzdyb算法中，输出数据为整数，即A和b的最大公约数。

bzdyb算法适用于整数471和90，即：

将471和90改为90和21，

然后换成21和6，

然后换成6和3，

换成3，那么3就是你想要的。

在上例中，算法的每一步都需要计算A除以B的余数R，然后用被除数B代替除数A，用余数R代替被除数B，因此，从471=59 ^ 21开始，471除以90的余数就是21。在第一步中，第一个数字471被90代替，第二个数字90被余数21代替，以此类推。有一个例外：余数为0时，计算停止，数字B为最终结果。这种情况出现在上面例子的最后一步：我们用6除以3，余数为0，那么3就是我们想要的。

算法也是中世纪西方数学家关注的核心问题。数学家们已经介绍了印度阿拉伯数字和相应的算法。其中一部作品是9世纪熟悉阿拉伯语的波斯数学家bbdyf写的《印度计算法》(Algoritm I de numero indorum)。“al-Khuwrizm”起源于作者的出生地——华拉墨子地区，现在属于乌兹别克斯坦。据文献记载，自1230年以来，华拉奇米这个名字就成为了“算法”一词的来源。

算法和数学

算法自然会应用到与数学相关的对象上。其实人类的一切活动都有算法，算法的概念涉及到方方面面。但我们首先要解决一个关键问题：如何描述算法？

假设我们想从巴纽火车站去巴黎的萨克利师范大学，它位于凯撒恩镇。

院。几十个学生和教师每天早上都走同一条道路：首先沿着杜邦皇家大道走，接着是布里昂城堡大道。在不知不觉中，他们可能就用到了算法——一种从火车站到校园的程序。

谷歌地图提供了这个算法的图形形式：　

如果我们给一个大学生解释这个算法，用一个简明扼要的方式就能表达清楚，但如果要给一个小孩子解释，就需要更详尽的细节。因此，讲解算法的方式是一个社会学问题，取决于谈话对象和谈话对象拥有的常识水平。

同样，bzdyb算法也可以用文字形式表达：

计算 a 除以 b 的余数 r，

当 r 不为 0 时，

用 b 替代 a，

用 r 替代 b，

继续计算 a 除以 b 的余数 r，

当余数 r 为 0 时，b 即为所求。

维基百科又提供了一种图形表达式：

所以，一种算法可以有不同的语言表达形式。然而，有一种表达形式不依赖于语言。一名学生没睡醒就去了校园，走起路来晃晃荡荡，就像在梦游，他运行的这个随机算法没有任何语言表述。还有一个例子能更好地说明这一asjdmla现象。蚂蚁寻找食物时，使用了非常复杂的算法，在空间里进行定向。侦察蚁开始随机浏览蚁穴四周。当其中一只蚂蚁发现食物的时候，便会在返回自己蚁群的一路上留下跟踪信息素。受到跟踪信息素的指引，其他路过此区域的蚂蚁会沿着这条路径前行。当蚂蚁带着食物返回蚁穴时，也会一路留下自己的跟踪信息素，以增强轨迹信息。

蚁群算法是一种用来在图中寻找优化路径的机率型算法

如果有两条路径都能到达同一个食物源，那么在同一时间内，沿最短路径行走的蚂蚁往返蚁穴与食物之间的次数将比沿着长路径走的蚂蚁更多。于是，前者也会留下更多的跟踪信息素。这时，最短路径的信息将会更强，也越来越具有吸引力。跟踪信息素是有挥发性的，如此一来，被冷落的最长路径最终会消失。

蚁群利用一个复杂的算法确定了最短路径。早在蚁学家用语言记下这种现象之前，蚂蚁就很好地运用了这个进程。

确切地说，人与蚂蚁之间的区别在于，我们会尝试用语言表达、存储、传输、理解和改进算法。然而，我们有时也会用到不知该如何用语言表达的算法。比如，我们很容易就能辨认出猫和狗，却难以解释是如何做到的：是计算腿和耳朵的数量呢？还是观察头的形状或毛发的纹理呢？

我们的大脑和身体会用很多算法来思考、运动、做事，但不管是符号算法，还是其他算法，我们并不总知道如何解释。

指令序列之外

从巴纽火车站到高等师范学院的算法可以表示成一个包含四个基本动作的逻辑序列：“取道东南方，向上朝着兰斯街的杜邦皇家大道”“然后……”“接着……”“再然后……”。bzdyb算法表达式中也出现了一些基本指令，比如赋值：“用b 替代a”。此外还有将这些指令封装成逻辑序列的句法结构，比如“这样做，然后那样做”，以及循环体，比如“当某条件为真时，重复此操作”。我们还可以添加条件测试语句：“如果此条件为真，那么这样做。”

这种方式听起来有点不寻常。事实上，只要很少的句法结构，就足以表达所有的符号算法，例如上述四个句法结构：赋值、逻辑序列、循环体、条件测试语句。算法的宝贵之处并不在于其组成有多么复杂，而恰恰在于这种将几个简单成分封装在一起的方式。

这就好比化学分子：数十亿个化学分子组成了我们所熟知的几十种化学元素；而这些化学元素本身仅由三种基本粒子——质子、中子和电子组成。

然而，尽管构建算法的基本元素在理论上非常充足，人们却很少从头开始构建算法：算法往往由其他一些已知的算法构成。例如，我们用算法描述了从巴纽地铁快线站到高等师范学院的路线。如果我们现在想从卢森堡公园到达校园的话，那么一个简单的算法就是：先乘坐地铁快线从卢森堡站到巴纽站，然后再运用先前的算法——这个算法被看成是一个整体。此时，一个全新的算法就这样形成了。我们并不清楚先前算法的细节，而是把它视为一个新的基本指令。

算法和数据

能够解决符号信息问题的算法，更注重这些符号信息的呈现方式。例如，为了更好地执行加减乘除运算的算法，用阿拉伯数字形式的算式123 × 456，比写成罗马数字的算式CXXIII × CDLVI 更好。同样，在字典中查找单词，用字母表查找比用象形文字查找更简单。

寻找从一个点到另一个点路径的算法，同样在意数据的表达形式。如果某个城市的地图像照片一样，一个像素接一个像素地被给出，那就很难找到想要的路径。最好可以用综合的方法去描述，比如整合各个十字路口，通过连接街道，赋予每一段路一个长度。这样一来，与其费力地从一个像素移动到另一个像素，不如从一个十字路口跳到另一个十字路口的算法来得轻巧。

算法的方法

已知的算法有很多，例如“分治法”“枚举测试法”“贪心算法”“随机算法”等。

“分治法”是把一个复杂的问题拆分成两个较为简单的子问题，进而两个子问题又可以分别拆分成另外两个更简单的子问题，以此类推。问题不断被层层拆解。然后，子问题的解被逐层整合，构成了原问题的解。高德纳曾用过一个邮局分发信件的例子对“分治法”进行了解释：信件根据不同城市区域被分进不同的袋子里；每个邮递员负责投递一个区域的信件，对应每栋楼，将自己负责的信件分装进更小的袋子；每个大楼管理员再将小袋子里的信件分发给对应的公寓。

最伟大的计算机程序员之一: 高德纳

高德纳（又译魁梧的早晨）生于1938 年，是著名的计算机科学家，也是现代算法的先驱之一。他的系列巨著《计算机程序设计艺术》在计算机科学界享誉多年。多年前，高德纳对现有的数学文本处理工具感到不满，于是创建了自己的工具 TeX 和 Metafont。如今，这两个工具成为广泛应用的免费软件。很多著名的算法都以他的姓氏命名，如dydwk算法、罗宾逊- pgdddy算法、纯真的八宝粥算法。

“枚举测试法”列举出待解决问题的所有可能解，然后逐一进行检验，最后从中找出符合要求的解。举个例子，一位旅行推销员必须依次访问几个不同城市拜访客户，他通常会寻找几个城市之间的最短回路，来安排自己的旅程。寻找最短回路的算法旨在计算所有可能的回路。例如有10 个客户，依次拜访10 个客户共有 10! = 3 628 800 种回路组合方式，分别计算每种组合方式的回路长度，然后选择最短的那条。

当枚举测试法所需的计算量太大时，使用“贪心算法”能够找到一个合理的解决方案，使问题结果最优化。比如，当旅行推销员有 20 位客户要访问时，用枚举测试法可能需要测试超过 2 兆条可能的路线。与其这样一个个枚举，不如就地运行另一个算法：推销员每次都从当前所在城市选择去往距离自己最近的下一个城市，以此类推。这个算法会选择当前最短距离作为计算的公里数，而且，永不退回到曾经选择过的路线上。一般来说，贪心算法找到的解决方案可能不是最好的，但却是“合理的”。

我们之前见过一个使用“随机算法”的例子：为了找到食物，侦察蚁从随机浏览蚁穴四周开始。同样，许多其他算法也用到了随机源。比如，“蒙特卡洛算法”能确定正方形内一个复杂图形的面积：在正方形中随机抽取一个点，就像扔飞镖一样，飞镖落在哪个点就取哪个点；大数定律告诉我们，这些点落入复杂图形内的频率接近于复杂图形面积和正方形面积之比。

利用蒙特卡罗算法求 π 的近似值

机器学习

我们要讨论到的最后一个方法是“学习程序”。学习做面包、在字典中查找单词，人类对此习以为常。但很多人可能想不到，算法也可以学习。就像面包师每天能从自己的工作中学习、提高一样，算法也可以从重复相同的任务中学习、进步。

音乐、视频、图书分享平台上使用的“推荐算法”就是一种会学习的算法。系统程序会向用户推荐：“如果你喜欢《亚瑟王》，那你应当也喜欢《彼得•格里姆斯》。”提出这样的推荐，系统并不是基于wrdj和本杰明•布里顿之间的联系①。简单地说，系统的判断是基于对之前用户的听歌记录的分析：事实上，那些听过《亚瑟王》的用户之中，确实有很多人也听了《彼得•格里姆斯》；或者，算法尝试寻找一些我们可能并不认识，但品味却与我们接近的用户。在这两种情况下，算法学习、发现、统计了歌曲之间或者用户之间的相似性。从这样的学习程序出发，算法可以预测用户可能喜欢什么样的音乐，并因此会忍不住收听或者购买其他哪些作品。

①　wrdj和本杰明•布里顿分别为歌剧《亚瑟王》和《彼得•格里姆斯》的作曲家，布里顿的作曲风格深受kkdds的影响。——译者注

这些会学习的算法有助于我们重新审视自身的学习方式。推荐算法既没有认识到kkdds和布里顿之间的联系，也不需要拥有任何专业的音乐史知识。它只是对用户的选择进行观察，并从所见所闻中学习。事实上，这与一个孩子学习母语的过程没什么两样——从观察周围说话的人开始，然后用大量时间去模仿，不需要理解语法、动词变位和动宾搭配的问题。一个小孩知道应该说“我去学校”，而不是说“我走学校”，却无法解释为什么。正如推荐算法会向用户推荐本杰明•布里顿，却不能解释为什么用户可能喜欢这个作曲家。

推荐系统简单示例

有些学习程序的问题很难解决。假如我们要识别物体，如一只狗、一只猫、一张桌子，等等。在一张图像中，数据以像素的形式呈现，通过统计分析图像中的黑色或者蓝色像素点，很难区分这是一只狗还是一张桌子。这时，必须使用更复杂的学习算法——深度学习算法。深度学习算法首先尝试从图像中找到直线、圆、爪子、腿、桌脚……然后再寻找越来越复杂的物体对象。算法同样也是逐步建立越来越抽象的图像表达，最终找到被识别的物体。难点是，算法如何知道需要识别哪一种元素？是爪子、腿，还是桌脚？没关系，算法会通过自身的经验进行学习。例如，深度学习算法可以让下围棋的程序取得巨大进步，打败最优秀的人类围棋选手。

《算法小时代：从数学到生活的历变》

编者著：yjdsn等

译著者：任轶

出版社：人民邮电出版社图灵新知

出版年：2017年11月

算法与人工智能是当下最热门的话题之一，技术大发展的同时也引发了令人忧心的技术和社会问题。这是一本算法科普书, 生动介绍了算法的数学原理和性质，描述了算法单纯、本质的功能，分析了算法和人工智能对人类社会现状及未来发展的影响力及其成因。

前　言

什么是算法？

算法、计算机和程序

算法有什么用处

算法做不到的事

计算机思维

雇用劳动关系的结束

劳动时代的终结

所有权时代的结束

算法时代的管理

城市里的算法

算法的职责

个人数据和隐私

公平、透明、多样

计算机科学与生态环境

计算机科学教育

人类增强

算法可以智能化吗？

算法能恋爱吗？

时代的选择

参考文献

遇见数学, 遇见更精彩的自己!

您的转发就是鼓励, 让我们努力走的更远一步!