约翰·霍普克罗夫特：培养了一个领域的教科书

数百万计算机科学专业的学生从未读过约翰·霍普克罗夫特在研究期刊上写的任何文章，但他们几乎都通过他学习过——通过那些与杰弗里·乌尔曼 (Jeffrey Ullman) 和阿尔弗雷德·阿霍 (Alfred Aho) 联名出版的自动机理论和算法教科书。这些书籍被如此广泛地采纳为标准课程，以至于它们塑造了该学科的教学方式。

从看门人的儿子到斯坦福

约翰·爱德华·霍普克罗夫特于1939年10月7日出生在华盛顿州西雅图的一个工人阶级家庭；他的父亲是一位第一次世界大战的英国退伍军人，从事看门工作，父母双方都没有完成高中学业。他还是西雅图-塔科马箱包公司 (Seattle-Tacoma Box Company) 创始人雅各布·尼斯特 (Jacob Nist) 的外孙。尽管父母受教育程度有限，但他们鼓励了他的求知欲。他于1961年在西雅图大学获得了电气工程学士学位，随后于1962年获得硕士学位，并于1964年获得博士学位（均为电气工程专业），均来自斯坦福大学。这种工程训练，而不是纯数学或计算机科学背景，塑造了他后来对算法的直觉，这些算法不仅在理论上优雅，而且在运行上确实高效。

构建学科的教科书

霍普克罗夫特在普林斯顿大学开始了他的学术生涯，担任助理教授，随后转到康奈尔大学，在那里他度过了职业生涯的大部分时间，最终获得了IBM工程与应用数学教授的头衔，并担任了包括系主任和工程学院院长在内的领导职务。正是在康奈尔大学，他与杰弗里·乌尔曼以及后来的阿尔弗雷德·阿霍合著了一系列关于形式语言、自动机理论和算法设计的教科书，这些书成为了全球几代计算机科学学生的默认教学文本。这些书不仅仅是总结了现有知识——它们将渐近复杂度分析和形式语言理论编纂成了今天仍在入门理论课程中教授的形式，在这些词汇在其他地方完全存在之前，就为该领域提供了共享的词汇。

至今仍在运行的算法

除了教科书之外，霍普克罗夫特自己的研究也产生了至今仍在积极使用的工具。与理查德·卡普 (Richard Karp) 共同开发的霍普克罗夫特-卡普算法 (Hopcroft-Karp algorithm) 寻找二分图最大匹配的速度比之前任何方法都快，并且仍然是网络流和分配问题中的标准技术。他还开发了一种用于最小化确定性有限自动机的有效算法，这是编译器设计和形式验证中的基础工具。然而，他最著名的成果是与罗伯特·塔扬 (Robert Tarjan) 的联合工作：1974年发表的第一个用于测试图是否为平面的线性时间算法——即是否可以在平面上绘制而没有边交叉。两人围绕深度优先搜索的系统使用构建了该算法，将原本缓慢且临时的难题变成了可以在与图本身大小成比例的时间内解决的问题。

图灵奖及其共享性质

1986年，霍普克罗夫特和塔扬共同获得了计算机科学的最高荣誉——ACM A.M.图灵奖，“以表彰他们在算法和数据结构设计与分析方面的基础性成就”。引文将两人并列，并归功于一系列协作和并行的工作，而不是单一的个人突破——平面性算法是引文所指的主要成就，此外还有两人各自对更广泛的算法设计领域的独立贡献。

在中国的第二职业

在获得图灵奖后的几十年里，霍普克罗夫特将大部分精力转向加强美国以外，特别是中国的计算机科学教育。他成为了北京大学计算研究前沿中心的联合主任，并领导着以上海交通大学和华中科技大学命名的中心，指导学生并帮助建立算法和最近的深度学习研究项目。中国在2016年授予他友谊奖，这是授予为国家发展做出杰出贡献的外国专家的认可——对于一位距离获得奖项的工作已经过去几十年的图灵奖得主来说，这是一个不同寻常的第二幕。

认可

霍普克罗夫特于1989年当选为美国国家工程院院士，1994年成为ACM会士，并于2010年获得IEEE约翰·冯·诺依曼奖章，以表彰其在计算机科学和工程方面的杰出成就，此外还有1986年的图灵奖和2016年的中国友谊奖。

为什么约翰被称为天才

霍普克罗夫特被称为天才的理由并不在于单一的耀眼证明，而在于一种更罕见的组合：足以赢得该领域最高奖项的实质性研究贡献，加上将该领域基础提炼成可教形式的无与伦比的天赋。平面性算法和霍普克罗夫特-卡普匹配算法是理论计算机科学家所指出的那种真正聪明的成果——通过结构洞察力将似乎需要暴力搜索的问题简化为线性或近线性时间。但图灵奖引文本身明确指出的诚实框架是，他最著名的成果是他与罗伯特·塔扬共同拥有的；两人的引文都不能独立存在，奖项是为了表彰共同的成就，而不是个人的突破。较少被分享，也较少被赞誉为“天才”的是他的第二个才能：三本合著的教科书，它们构建得如此之好，以至于成为了整个学科教授其自身基础的默认方式，这是一种更接近大师教学而非个人发明的智力贡献形式。

遗产

霍普克罗夫特的遗产沿着两条在职业生涯中很少重合的平行轨道运行——图灵奖级别的算法研究记录，以及在中国建立计算机科学教育基础设施的几十年第二幕。在该领域的历史上，很少有人像他这样直接或长期地塑造了教学方式，他是其最广泛指定的教科书的作者。那个在20世纪60年代和70年代帮助形式化计算理论的人，在2010年代却在北京大学指导深度学习学生，这说明了他工作生涯不同寻常的长度和广度：一个始于真空管附近电气工程时代并延续到神经网络时代的职业生涯，却从未失去其向下一代传授该领域底层结构的初衷。