专栏首页前沿技墅从图灵到高德纳:《算法分析导论》作者师承考据

从图灵到高德纳:《算法分析导论》作者师承考据

Robert Sedgewick

普林斯顿大学计算机系创始人,在斯坦福大学师从D. E. Knuth院士;曾任Adobe Systems公司董事会成员,并在Xerox PARC、IDA和INRIA等机构从事研究;名著Algorithms(4th)作者。

公元 2014 年的冬天,一部讲述计算机科学之父艾伦·图灵(Alan Turing)传奇人生的传记电影在美国上映,这部影片就是《模仿游戏》。次年,该片荣获第 87 届奥斯卡金像奖最佳改编剧本奖,以及包括最佳影片、最佳导演、最佳男主角、最佳女配角在内的 7 项提名,一时风光无限。

图灵一生最重要的三大贡献包括图灵机、图灵测试,以及破译 Enigma 密码机,其中的每一项都值得全世界感谢和纪念他。在提出图灵测试的论文中,图灵石破天惊地预言了创造出具有真正智能的机器的可能性,这也是后来人工智能研究的源头。事实上,《模仿游戏》这个名字正是图灵那篇著名论文第 1 章的标题。后人为了纪念图灵对计算机科学所做出的巨大贡献,也将该领域的最高奖命名为“图灵奖”。另一方面,破译 Enigma 密码更是直接帮助盟军在战场上取得先机,甚至拯救了无数人的性命并最终导致第二次世界大战反法西斯阵营的全面胜利。

尽管前面提到的两大贡献已是功若丘山,但笔者这里将从图灵的另外一个贡献——“图灵机”谈起,因为这与本书所要讨论的话题息息相关。不过,为此我们还得把时间再往前推。1900 年,德国数学家大卫·希尔伯特(David Hilbert)在巴黎举行的国际数学家大会上做了题为《数学问题》的演讲。在这篇重要的演讲中,他提出了著名的希尔伯特之 23 个问题。尽管此后的数学发展远远超过了希尔伯特的预料,但他所提出的 23 个问题仍然对 20世纪的数学发展起到了重要的推动作用。

希尔伯特的第 10 个问题是要设计一个算法来测试多项式是否有整数根。他没有使用“算法”这个术语,而是采用了下面这种表述:“通过有限多次运算就可以决定的过程。”有意思的是,从希尔伯特对这个问题的陈述中可以看出,他明确地要求设计一个算法。因此,他显然是假设这样的算法存在,人们所要做的只是找到它。现在我们知道,这个任务是无法完成的,即它是算法上不可解的。但对那个时期的数学家来说,以他们对算法的直观认识,得出这样的结论是不可能的。

非形式地说,算法是为实现某个任务而构造的简单指令集。用日常用语来说,算法又被称为过程或者方法。算法在数学中也起着非常重要的作用。古代数学文献中就包含执行各种各样计算任务的算法描述。例如,我国古代数学经典《九章算术》中就记述了包括求最大公约数、最小公倍数、开平方根、开立方根等在内的诸多算法。

虽然算法在数学中已有很长的历史,但在 20 世纪之前,算法本身一直没有精确的定义。数学家们面对希尔伯特的第 10 个问题显得束手无策。由于缺乏对算法本身的精确定义,所以要证明某个特定任务不存在算法就更不可能了。要想破解希尔伯特的第 10 个问题,人们不得不等待算法的精确定义的出现。

直到 1936 年,曙光似乎出现了。图灵向伦敦的权威数学杂志递交了一篇题为《论数字计算在决断难题中之应用》的论文。该文最终于 1937 年正式发表,并立即引起了广泛关注。在论文中,图灵描述了一种可以辅助数学研究的机器,也就是后来被称为“图灵机”的抽象系统。与此同时,另外一位数学家阿隆佐·丘奇(Alonzo Church)也独立地提出了另外一套系统,即所谓的 Lambda 演算。图灵采用他的图灵机来定义算法,而丘奇则采用 Lambda演算来定义算法,后来图灵证明这两个定义是等价的。由此,人们在算法的非形式概念和精确定义之间建立了联系,即算法的直觉概念等价于图灵机,这就是所谓的“丘奇-图灵”论题。

“丘奇-图灵”论题提出的算法定义是解决希尔伯特第 10 个问题所需的。而第 10 个问题的真正解决则要等到 1970 年,借助于丘奇与图灵的杰出贡献,马提亚塞维齐(Yuri Matiyasevich)在戴维斯(Martin Davis)、普特纳姆(Hilary Putnam)和罗宾逊(Julia Robinson)等人工作的基础上,最终证明检查多项式是否有整数根的算法是不存在的。上述四人的名字也紧紧地同希尔伯特的第 10 个问题联系在了一起。破解希尔伯特的第 10 个问题的过程更像一场声势浩大又旷日持久的国际协作和学术接力。每个人的工作都必不可少,而且大家都感觉已经相当接近问题的最终答案。后来的历史见证了马提亚塞维齐敏锐地接过最后一棒并完成终点冲刺的伟大一幕。更有意思的是,彼时正值美苏冷战最为紧张的时期,两个超级大国之间的正常学术交流几乎完全中断。但这或许就是科学无国界的一个重要体现,尽管国家层面上双方剑拔弩张,而科学家在私下仍然以一种惺惺相惜的默契方式彼此神交。特别是在得知苏联数学家完成了最终的证明时,美国同行都表现得相当振奋和由衷的喜悦,这不得不说是学术界的一段佳话。

回顾建立算法形式化定义和破解希尔伯特之第 10 个问题的那段风起云涌的历史,我们不得不由衷地感叹:算法对于我们的世界是多么重要。可以这样说,自计算机科学诞生之日起,关于算法的研究就一直是一个核心话题。现代计算机科学中充满了各种各样的算法,许多图灵奖得主也正是因提出的各种经典算法而闻名于世。例如,提出单源最短路径算法的迪可斯特朗(Edsger Dijkstra)、提出字符串匹配算法的高德纳(Donald Knuth)、提出多源最短路径算法的弗洛伊德(Robert Floyd),以及提出快速排序算法的霍尔(Antony Hoare)等。其中,高德纳是最年轻的图灵奖得主这一纪录的保持者(获奖时年仅 36 岁),并以计算机算法设计与分析领域的经典巨著the Art of computer Programming而广为人知。

作为导师,高德纳一生共指导过 28 位博士生,而本书作者之一的罗伯特·塞奇威克(Robert Sedgewick)便是其中之一。塞奇威克曾经是普林斯顿大学计算机科学系的创立者暨首任系主任,他同时还是著名的 Adobe 公司的董事。作为一位世界知名的计算机科学家,塞奇威克于 1997 年当选 ACM(Association for Computing Machinery,国际计算机学会)院士,并因从“对称二叉树”中导出了红黑树而享誉计算机界。

塞奇威克与费利佩·弗拉若莱(Philippe Flajolet)曾合作撰写过数本算法分析领域的著作,本书即为其中一部在全世界范围内广泛流传的经典之作。弗拉若莱是一名法国计算机科学家,法国科学院院士,同时也被称为“分析组合学之父”。他与合作者共同提出的Flajolet-Martin 算法更是当今互联网与大数据时代背景下,网站分析统计的重要基石。

然而,天妒英才,2011 年 3 月,休假期间的塞奇威克惊悉多年的老友弗拉若莱突然离世。悲痛万分的塞奇威克怀着对逝者的无限缅怀写了感人至深的悼词:“弗拉若莱的离世意味着很多秘密再也无法揭开。但他给世人留下了很多追随他脚步的继承者,他们可再续他的数学梦想。”在这样的背景下,塞奇威克以极大的热情投入工作,历经数百个日夜,终于在 2012 年 10 月将本书的第 2 版付梓。塞奇威克坚信弗拉若莱的精神会在后来人的工作中得到永生,进而希冀本书读者能够循着弗拉若莱的脚步,继续追求他的数学梦想。

本书全面系统地介绍了算法分析中需要使用的基本技术,所涉及的内容既来自包括离散数学、组合数学、概率论等在内的经典数学问题,也有来自算法及数据结构等计算机科学问题。像递归、母函数、树形结构、字符串、映射以及散列等算法分析话题均有讨论。可以说本书是一本研究算法分析的权威之作。

作为译者,我们希望自图灵以来的算法研究能够在更宽阔的范围内,被更光大地发扬,尤其希望中国的计算机科研人员能够从本书中找到启迪研究工作的智慧。同时,也希望通过本书向神交已久的两位大师——弗拉若莱和塞奇威克送上最崇高的敬意。

本文分享自微信公众号 - 前沿技墅(Edge-Book)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 复杂网络算法在平台业务安全中的应用

    对于电商平台和社交平台为主的平台业务,其安全涉及方方面面,常见的如刷单、黑灰产。本文以 Louvain、FRAUDAR 和 CatchSync 这三种典型的复杂...

    用户1682855
  • 剁手党复盘双11:猫狗如何猜透你的心

    双11刚刚过去,双12即将到来,不知大家的手是否还在?经历过某猫某东某宝拼杀的各位买家,大概都有过被这些平台猜透小心思,“看了又看、买了又买”的经历。那么,它们...

    用户1682855
  • 极简Python:数据分析与机器学习最小化知识库

    我们正处于一个数据科技(Data Technology,DT)时代。在这个时代,我们的一举一动都能在数据空间留下电子印记,于是海量的社交、电商、科研大数据扑面而...

    用户1682855
  • 书单丨从0起步探秘算法世界 畅享编程之趣

    本书围绕程序设计典型算法,编织了一个扣人心弦又趣味横生的侦探缉凶故事。小说主人公运用高超的搜索技巧和精深的算法知识,最终识破阴谋、缉拿元凶,让你在愉悦的沉浸式体...

    博文视点Broadview
  • 【易错概念】国密算法SM1(SCB2)、SM2、SM3、SM4、SM7、SM9、ZUC

    众所周知,为了保障商用密码的安全性,国家商用密码管理办公室制定了一系列密码标准,包括SM1(SCB2)、SM2、SM3、SM4、SM7、SM9、祖冲之密码算法(...

    辉哥
  • 主宰这个世界的10种算法

    ---- Reddit有篇帖子介绍了算法对我们现在生活的重要性,以及哪些算法对现代文明所做贡献最大。如果对算法有所了解,读这篇文章时你可能会问“作者知道算法为...

    机器人网
  • 让我们像驯化小狗一样驯化算法

    人类进化学家当中有一种理论,说的是小狗这种宠物是从野兽进化而来,因为只有那些获得了社会化智慧的犬科动物才能存活下来。几千年前狼群在人类聚集地的周围活动,逐渐开始...

    小莹莹
  • 原创 | 初学者友好!最全算法学习资源汇总(附链接)

    在计算机发展飞速的今天,也许有人会问,“今天计算机这么快,算法还重要吗?”其实永远不会有太快的计算机,因为我们总会想出新的应用。虽然在摩尔定律的作用下,计算机的...

    数据派THU
  • 【学习】从入门到精通,我是这样学习算法的

    这篇文章讲了什么? 我这些年学习数据结构和算法的总结。 一些不错的算法书籍和教程。 算法的重要性。 初学 第一次接触数据结构是在大二下学期的数据...

    小莹莹
  • 极客算法训练笔记(一),算法学习方法篇

    付完款那一刻我忍不住吐槽“哇塞,我可真有钱”,一看余额“我去,伤心的人那么多~我变成了其中一个~”(这首歌叫啥来着,好像有点应景)。

    阿甘的码路

扫码关注云+社区

领取腾讯云代金券