约翰·霍普克罗夫特

约翰·爱德华·霍普克罗夫特（John Edward Hopcroft）是计算机科学家和教育者，主要研究算法分析、自动机理论与图算法。1961年，他在西雅图大学获得电气工程学士学位，随后于1962年、1964年分别获得斯坦福大学电气工程硕士和博士学位。

他在普林斯顿大学任教三年后，于1967年加入康奈尔大学，1972年成为教授。其工作把具体计算问题与数学化的效率分析联系起来：不仅问某种程序能否完成任务，也考察输入规模增长时所需运算量如何变化。这种研究取向与自动机、形式语言及算法理论的发展相互联系，但不意味着这些领域由他一人创立。

参考：[1] [2]

霍普克罗夫特与杰弗里·厄尔曼的合作可追溯到普林斯顿时期。工程与技术史档案记载，厄尔曼在1964年参加了他的自动机理论课程，两人后来合著《Formal Languages and Their Relation to Automata》，将自动机与形式语言组织为可系统学习的理论内容。

康奈尔大学的学术介绍还记录了他与厄尔曼、阿尔弗雷德·阿霍在形式语言和算法教材上的合作。教材的作用在于整理概念、论证和方法，使研究成果进入课程与后续研究；这与提出某项新算法是不同类型的贡献。书中的理论不能仅因出现在合著教材里，就全部归为霍普克罗夫特的发明。

参考：[1] [2]

霍普克罗夫特与理查德·卡普合作的最大二分图匹配算法，是理解其算法研究的一例。把人员放在图的一侧、任务放在另一侧，能够胜任某任务就连接一条边；目标是在每人和每项任务至多参与一对的条件下，尽量增加配对数量，而不是给每条边赋分后追求偏好总分最大。

设甲能做任务X和Y，乙只能做X。如果先把甲配给X，就可以沿乙、X、甲、Y组成的交替路径调整配对，改为乙做X、甲做Y，使配对数从一变成二。这只是增广思想的示意，并非把完整算法等同于一次换位。

2023年的匹配研究论文在介绍经典方法时说明，霍普克罗夫特—卡普算法并非每轮只找一条增广路径，而是结合广度优先与深度优先搜索，成批寻找互不冲突的最短增广路径。改进来自搜索阶段的组织方式与复杂度分析，而不是更快的硬件。这项以二人共同命名的成果，应明确保留卡普的贡献。

参考：[3]

霍普克罗夫特于1987年至1992年担任康奈尔大学计算机科学系主任，1994年1月至2001年6月担任工程学院院长，2020年起列为荣休教授。这些职位体现了教学与学术组织方面的工作，不能用来代替具体研究贡献的证明。

1986年，他与罗伯特·塔扬共同获得图灵奖；2008年又获得ACM的Karl V. Karlstrom杰出教育家奖。共同获奖、教材合著和匹配算法合作涉及不同人物及工作，应分别说明。将这些脉络分开，才能既看到他的个人贡献，也保留理论计算机科学由众多研究者共同发展的历史。

参考：[1]