算法小时代一书,已获图灵许可,（遇见数学）

什么是算法？

要理解什么是算法，我们首先必须想象一个场景。 几千年前，一位祖先试图依靠已故祖母如何制作面包的记忆来制作自己的面包。 然而，他实在不知道该怎么办。 他先是犹豫着把麦粒放进沸水中，后来又想这可能是个坏主意。 这位祖先的困境正是我们所有人所面临的——遇到某个问题却不知道如何解决。 我们思考解决方案，尝试它们，反复探索和实验，并做出一些意想不到的发现，直到成功……或失败。

然而，真正的面包师并不是这么做的。 他们不会为每个烤箱重新制定烘焙食谱，因为他们已经知道如何烘焙面包并且熟记于心。 感谢面包食谱，面包师可以每天为我们提供面包。 事实上，人类文明的发展不仅是由于某些人的发明创造，更是因为其他人“复制”了这些发明并加以改进。 然而，我们忘记了面包食谱的价值。 首先，食谱减少了不确定性：多亏了食谱，面包师知道，除非发生突然的灾难，面包将在晚餐时间准备好。 有了这个食谱，任何人都可以制作面包，不需要想象力或天赋。 以两位作者为例。 我们没有任何烘焙面包的天赋，但我们仍然可以从网上找到薄煎饼的食谱，使用适当的揉捏力度，并使用更有想象力和才华的面包师写的说明。 面包制作方法。 最终，这个食谱成为人类遗产的一部分，代代相传数千年。

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

甜番茄——黑豆卷食谱

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

过程和符号

与面包食谱不同，有些算法解决的是书写符号的问题，例如数字、字母等。算法组合在一起形成具有不同含义的数字、单词、句子和文本。

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

计算机科学家倾向于将“算法”一词的含义限制为此类“符号算法”。 鉴于这种限制，我们自然无法将算法的历史追溯到文字发明之前。 然而，广义上的算法概念与文字一样古老。 迄今为止发现的最古老的书面痕迹表明，古代抄写员已经在使用加法和乘法等算法来进行记账。 文字可能就是因为这个原因而被发明的。

算法和数学

数学家很早就开始关注算法的设计。 例如，公元前 300 年左右的欧几里得算法可以计算两个整数的最大公约数。 我们简单解释一下。 如果读者觉得攀登数学高峰有困难，可以直接跳过这一段，或者把下面的内容当成一首深刻的诗，尽量去理解。

一般来说，算法在其输入处接收数据，这些数据形成算法的参数。 在欧几里德算法中，输入数据是两个非零整数，设置为a和b，并且a大于b，例如a等于471，b等于90。通常，算法会返回一些额外的数据在输出端。 在欧几里得算法中，输出数据是一个整数，它是a和b的最大公约数。

将欧几里得算法应用于整数 471 和 90，我们有：

在上面的例子中，算法的每一步都需要计算a除以b时的余数r，然后用被除数b替换除数a，并用余数r替换被除数b。 因此，从471=5×9 + 21，我们知道471除以90时的余数是21。第一步，将第一个数471替换为90，将第二个数90替换为余数21，等等。 但有一个例外：当余数为0时，计算停止，数字b就是最终结果。 这发生在上例的最后一步：我们将 6 除以 3，余数为 0，所以 3 就是我们想要的。

算法也是中世纪西方数学家关注的核心问题。 数学家介绍了印度-阿拉伯数字以及与该数字系统相关的算法。 其中一本是由精通阿拉伯语的波斯数学家穆罕默德·穆萨·花剌子米于 9 世纪撰写的《印度教计算》（de）一书。 “al-Khuwārizmī”这个名字来自作者的出生地花剌子模地区，即现在的乌兹别克斯坦。 有文献证据表明，自1230年以来，Al-这个名字就成为“算法”一词的起源（）。

用语言表达

算法自然适用于数学对象。 事实上，算法存在于人类的一切活动中，算法的概念涉及方方面面。 但我们首先需要解决一个关键问题：如何描述算法？

假设我们想从 火车站前往位于卡尚镇的巴黎萨克雷师范学院。 每天早上，数十名学生和老师都会走同一条路线：首先沿着皇家杜邦大道，然后沿着布赖恩城堡大道。 在没有意识到的情况下，他们可能正在使用一种算法——一种从火车站到校园的程序。

地图提供了该算法的图形形式：

如果我们向大学生解释这个算法，我们可以用简洁明了的方式表达清楚，但如果我们要向孩子解释，则需要更详细的细节。 因此，你解释算法的方式是一个社会学问题，取决于你正在与谁交谈以及他们拥有的常识水平。

同样，欧几里得算法也可以用文字形式表示：

计算a除以b时的余数r，

当r不为0时，

将 a 替换为 b，

将 b 替换为 r，

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

当余数r为0时，求b。

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

因此，一个算法可以有不同的语言表达。 然而，有一种不依赖于语言的表达形式。 一名学生在没有醒来的情况下走进校园，摇摇晃晃地像梦游一样，在没有任何语言的情况下运行着随机算法。 这是另一个例子，可以更好地说明这种令人费解的现象。 当蚂蚁寻找食物时，它们使用非常复杂的算法来在空间中定位自己。 侦察蚁开始在蚁巢周围随机浏览。 当其中一只蚂蚁找到食物时，它会在返回蚁群的途中留下追踪信息素。 在跟踪信息素的引导下，经过该区域的其他蚂蚁将遵循这条路径。 当蚂蚁带着食物返回蚁巢时，它们也会沿途留下自己的跟踪信息素，以增强轨迹信息。

蚁群算法是一种用于在图中寻找最优路径的概率算法

如果有两条路径到达同一食物源，那么沿着最短路径行走的蚂蚁将比沿着较长路径行走的蚂蚁在同一时间内在蚁巢和食物之间进行更多的行程。 因此，前者也会留下更多的追踪信息素。 这时，最短路径的信息就会更强，也越来越有吸引力。 跟踪信息素是不稳定的，因此留下的最长路径最终会消失。

蚁群使用复杂的算法确定最短路径。 早在蚂蚁学家将这一现象付诸文字之前，蚂蚁就已经充分利用了这一过程。

相反，人类和蚂蚁之间的区别在于我们尝试用语言表达、存储、传输、理解和改进算法。 然而，我们有时会使用不知道如何用语言表达的算法。 例如，我们可以很容易地识别出猫和狗，但很难解释如何识别：数腿和耳朵的数量？ 或者看头的形状或者头发的质地？

我们的大脑和身体使用许多算法来思考、移动和做事，但无论它们是符号算法还是其他算法，我们并不总是知道如何解释它们。

指令序列之外

从巴尼奥火车站到巴黎高等师范学院的算法可以表示为包含四个基本动作的逻辑序列：“向东南方向行驶，沿着杜邦皇家大道朝兰斯路行驶”“然后...”“然后...“ “进而……”。 一些基本指令也出现在欧几里得算法表达式中，例如赋值：“用b替换a”。 还有将这些指令封装成逻辑序列的语法结构，例如“做这个，然后做那个”，以及循环体，例如“当某个条件为真时，重复这个操作”。 我们还可以添加一个条件测试语句：“如果这个条件为真，则执行此操作”。

这种方法听起来有点不寻常。 事实上，只需要很少的语法结构就足以表达所有的符号算法，比如上面的四种语法结构：赋值、逻辑序列、循环体和条件测试语句。 算法的价值不在于其复杂性，而在于它封装几个简单组件的方式。

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

然而，尽管构建算法的基本要素在理论上是足够的，但人们很少从头开始构建算法：算法往往由一些其他已知的算法组成。 例如，我们使用算法来描述从班育地铁快线站到巴黎高等师范学院的路线。 如果我们现在想从卢森堡花园到达校园，那么一个简单的算法是：先从卢森堡站乘坐地铁快线到巴格纽站，然后使用之前的算法——这个算法被视为一个整体。 至此，一个全新的算法就形成了。 我们不知道之前算法的细节，但可以将其视为新的基本指令。

算法和数据

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

寻找从一点到另一点的路径的算法也关心数据的表示。 如果城市地图就像一张照片，逐个像素地给出，那么就很难找到所需的路径。 最好用综合的方式来描述，比如整合各个路口，通过连接街道来赋予每一段道路一定的长度。 这样，算法就不用费力地从一个像素移动到另一个像素，而是轻松地从一个交叉点跳转到另一个交叉点。

算法方法

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

“分治法”就是将一个复杂的问题拆分为两个较简单的子问题，然后这两个子问题又可以拆分为另外两个较简单的子问题，以此类推。 问题正在逐层拆解。 然后，将子问题的解逐层整合，形成原问题的解。 高德纳曾用邮局分发信件的例子来解释“分而治之”的方法：信件根据不同的城市区域分装到不同的袋子里； 每位邮递员负责在与每栋大楼相对应的一个区域内投递信件。 将您负责的信件分成较小的袋子； 然后，每个大楼经理将小袋子里的信件分发到相应的公寓。

最伟大的计算机程序员之一：Knuth

Knuth（又译 Knuth）出生于1938年，是著名的计算机科学家，现代算法的先驱之一。 他的系列代表作《计算机编程的艺术》多年来蜚声计算机界。 几年前，Knuth 对现有的数学文本处理工具感到不满，并创建了自己的工具 TeX 和 . 如今，这两个工具已作为免费软件广泛提供。 许多著名的算法都以他的姓氏命名，例如 Knus--Pratt 算法、--Knus 算法、Knus- 算法等。

“枚举测试法”列出了要解决的问题的所有可能的解决方案，然后一一进行测试，最终找到符合要求的解决方案。 例如，旅行推销员必须访问几个不同的城市才能拜访客户。 他通常会寻找几个城市之间最短的环路来安排行程。 寻找最短循环的算法旨在计算所有可能的循环。 例如，有 10 个客户。 如果你按顺序拜访10个客户，那就是10个！ = 3 628 800 个循环组合。 计算每个组合的环长度并选择最短的一个。

当枚举测试方法所需的计算量过大时，可以采用“贪心算法”来寻找合理的解，优化问题结果。 例如，当旅行推销员要拜访 20 个客户时，枚举测试可能需要测试超过 2 万亿条可能的路线。 与其这样一一枚举，不如就地运行另一种算法：每次推销员选择从当前城市前往距离他最近的下一个城市，以此类推。 该算法会选择当前最短距离作为计算公里数，并且永远不会返回之前选择的路线。 一般来说，贪心算法找到的解可能不是最好的，但却是“合理的”。

我们之前见过一个使用“随机算法”的例子：为了寻找食物，侦察蚁首先在蚁巢周围随机浏览。 同样，许多其他算法也利用随机性来源。 例如，“蒙特卡罗算法”可以确定正方形内复杂图形的面积：随机选择正方形中的一个点，就像扔飞镖一样，选择飞镖落在哪个点上； 大数定律告诉我们，这些点落入复数图形内的频率接近于复数图形面积与正方形面积的比值。

使用蒙特卡洛算法求出π的近似值

机器学习

我们要讨论的最后一种方法是“学习计划”。 学习做面包和查字典是人类认为理所当然的事情。 但很多人可能不认为算法也能学习。 就像面包师每天从工作中学习和改进一样，算法也可以通过重复相同的任务来学习和改进。

音乐、视频、图书分享平台上使用的“推荐算法”是一种可以学习的算法。 系统程序会向用户推荐：“如果你喜欢《亚瑟王》，那么你也应该喜欢《彼得·格莱姆斯》。在做出这样的推荐时，系统并不是基于亨利·珀塞尔和本杰明·布里顿之间的联系①。简单来说，系统的判断是基于对之前用户收听记录的分析：事实上，在那些听过《亚瑟王》的用户中，有很多人也听过《Peter 》；或者，算法试图找到一些我们可能不认识的用户，但他们的品味与我们相似。在这两种情况下，算法都会学习、发现和计算歌曲之间或用户之间的相似性，从这样的学习过程开始，算法可以预测哪种类型。用户可能喜欢的音乐以及他们可能想听或购买的其他作品。

① 亨利·珀塞尔和本杰明·布里顿分别是歌剧《亚瑟王》和《彼得·格莱姆斯》的作曲家。 布里顿的作曲风格深受珀塞尔的影响。 ——译者注

这些学习算法帮助我们重新审视我们的学习方式。 推荐算法既不认识珀塞尔和布里顿之间的联系，也不需要任何音乐史专业知识。 它只是观察用户的选择并从所看到的内容中学习。 其实，这和孩子学习母语的过程没有什么不同——从观察周围人说话开始，然后花大量时间模仿，而不了解语法、动词变位和动宾匹配。 孩子知道他应该说“我去学校”而不是“我步行去学校”，但无法解释原因。 正如推荐算法会将 推荐给用户一样，它无法解释用户为什么会喜欢这位作曲家。

推荐系统的简单例子

有些学习计划问题很难解决。 假设我们要识别物体，例如狗、猫、桌子等。在图像中，数据以像素的形式呈现。 通过统计分析图像中的黑色或蓝色像素，很难区分它是狗还是桌子。 这时候就必须使用更复杂的学习算法——深度学习算法。 深度学习算法首先尝试从图像中找到直线、圆形、爪子、腿、桌腿……，然后转向越来越复杂的物体。 该算法还逐渐建立越来越抽象的图像表示，最终找到识别的对象。 困难在于，算法如何知道要识别哪个元素？ 它是爪子、腿还是桌腿？ 没关系，算法会通过自己的经验来学习。 例如，深度学习算法可以让围棋程序做出巨大改进并击败最优秀的人类围棋棋手。

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

编辑：Serge 等人。

译者：任毅

出版社: 人民邮电出版社 图灵新闻

出版年份：2017 年 11 月

算法和人工智能是当下最热门的话题之一。 科技的快速发展也引发​​了令人担忧的技术和社会问题。 这是一本算法科普书籍，生动地介绍了算法的数学原理和性质，描述了算法简单而本质的功能，分析了算法和人工智能对人类社会现状和未来发展的影响和原因。 。

遇见数学，遇见更精彩的自己！

您的转发是鼓励，让我们努力走得更远！