John Edward Hopcroft约翰·E·霍普克洛夫特（John Edward Hopcroft）是康奈尔大学计算机科学系工程与应用数学的IBM教授。
他在西雅图大学获得学士学位（1961年），在斯坦福大学获得了电子工程硕士学位（1962年）和博士学位（1964年）。他的研究方向主要是计算机科学的理论方面。
他于1994年至2001年担任康奈尔大学工学院的院长。他是美国国家科学院院士以及美国艺术与科学院、美国科学进步协会、电气与电子工程师学院成员、计算机协会等机构的成员。
1986年，他因为在研究方面的贡献而被授予图灵奖(A.M. Turing Award)。1992年，他被布什总统指定为监督国家科学基金会的国家科学委员会成员，一直到1998年5月为止。
他于2005年获得IEEE哈里·古德(Harry Goode)纪念奖，并且于2007年获得计算机研究协会的杰出贡献奖。他获得西雅图大学、爱尔兰国家学院和悉尼大学的荣誉学位，同时他还是帕卡德基金会科学顾问委员会成员。
约翰·霍普克洛夫特和罗伯特·陶尔扬——硕果累累的算法设计大师编辑本段回目录
1986年的图灵奖由康乃尔大学机器人实验室主任约翰·霍普克洛夫特(John Edward Hopcroft)和普林斯顿大学计算机科学系教授罗伯特·陶尔扬(Robert Endre Tarjan)共享，而陶尔扬曾是霍普克洛夫特的学生。这师生两人由于在数据结构和算法的设计和分析方面的众多创造性贡献而共同获此殊荣，在业界传为美谈。
John Edward Hopcroft霍普克洛夫特1939年10月7日生于西雅图。1961年在西雅图大学获得电气工程学士学位以后，进入斯坦福大学研究生院深造，师从著名的学者威德罗(Bernard Widrow)。威德罗是研究自适应信号处理和神经元网络的鼻祖。霍普克洛夫特1962年获得硕士学位，1964年获得博士学位，也就是说只用了3年时间就拿下了硕士、博士2个学位，其勤奋和聪颖由此可见。学成以后，霍普克洛夫特曾先后在普林斯顿大学、康乃尔大学、斯坦福大学等著名高等学府工作，也曾任职于一些科学研究机构如NSF(美国科学基金会)和NRC(美国国家研究院)，从事对科学研究的规划和行政管理工作，但时间不长。
霍普克洛夫特成为著名的计算机科学家起源于一个十分偶然的机会。他学习的专业是电气工程，对计算机科学原本没有多少知识，只学过一门“开关电路和逻辑设计”算是多少有些关系的。因此他原打算毕业后去西海岸的一所大学执教电气工程方面的课程。但就在毕业以前，有一次他偶然经过他的导师威德罗办公室的门口，当时，普林斯顿大学的麦克卢斯基教授(Edward McCluskey，他也是一位著名的学者，是研究数理逻辑的专家，他和奎因(Quine)共同创造的化简开关函数的一种方法就被叫做奎因—麦克卢斯基法(Quine-McCluskey method)。他还曾出任IEEE计算机协会的主席。)正为筹建“数字系统实验室”打电话给威德罗，请他推荐毕业博士生去那里工作。威德罗一眼瞥见从门口走过的霍普克洛夫特，觉得勤奋好学、悟性又高的这位得意门生正是一个值得推荐的人才，当即把他叫进办公室，并把电话听筒递给了他。霍普克洛夫特在电话里听了麦克卢斯基对普林斯顿大学拟建数字系统实验室的考虑和打算，以后又前去面谈了一次，实地了解一番以后，一则普林斯顿大学作为美国一流大学的名望吸引着他，二则对数字系统这一全新的学科领域产生了强烈的兴趣，霍普克洛夫特欣然放弃了原先的计划，接受了普林斯顿的聘任，从而改变了他一生的道路。
John Edward Hopcroft年青的霍普克洛夫特来到普林斯顿之后接受的第一项任务是开设一门新课：自动机理论。这对他来说是富有挑战性的，因为他之前并未接触过这个课题。面对挑战，他虚心地请麦克卢斯基推荐有关参考资料。由于当时没有任何一所学校开过自动机理论的课程，也没有一本自动机理论的书籍，对自动机理论这门课到底应该包含哪些内容，麦克卢斯基本人心里也没有底。但凭着他对计算机科学的深刻理解和对文献的广泛了解，他为霍普克洛夫特开列了包括图灵、麦柯劳赫(Warren McCulloch)和皮茨(Walter Pitts)、拉宾(M．Rabin)和斯科特(D．Sco R，这两人是1976年图灵奖获得者)、巴克斯(J.Backus，1977年图灵奖获得者)和诺尔(P．Naur)、哈特马尼斯(J.Hartmanis)和斯特恩斯(R．Steams，这两人是1993年图灵奖获得者)以及乔姆斯基(N．Chomsky)等人所写的6篇论文。基于这些论文，霍普克洛夫特对图灵的计算模型(也就是图灵机)，麦柯劳赫和皮茨在研究神经网络中用0和1的串描述神经元所产生和传递的电脉冲，从而导出的正规表达式概念(regular expression)，拉宾和斯科特的有限状态自动机理论，巴克斯和诺尔描述程序设计语言语法的BNF范式，乔姆斯基的上下文无关文法(context-free grammar)等等进行了深入钻研和消化，并加以分析、综合和比较，逐渐理出了头绪。他把有关自动机理论的上述分散而零星的材料全面地条理化、系统化，有机地联系在一起，成功地开出了新课，并为这门计算机科学中的基础性课程建立起了框架。后来，霍普克洛夫特和著名的计算机科学家、教育家厄尔曼(J．D．Ullman，1997年ACM优秀计算机教育奖获得者)合作编写了《形式语言及其与自动机的关系》(Formal Language and Their Relation to Automata，Addison-Wesley，1969)，这本书是学术界公认的在自动机理论方面有代表性的一部成功之作(此书中译本由莫绍揆等译，科学出版社出版)。
然而，霍普克洛夫特更感兴趣的课题是与实际应用有密切联系的“算法”。当时，算法复杂性理论虽已由哈特马尼斯、斯特恩斯和布卢姆(M．Blum，1995年图灵奖获得者)等人奠定了基础，但对具体算法的优劣和效率的判断尚未建立起客观和明确的准则，因此，往往出现这样的情况：有人公布了解某类问题的一种算法，给出对若干样本问题进行测试的执行时间；过了一段时间，另外一个人发布对它的“改进算法”，给出对相同样本问题进行测试的执行时间(当然比前者少，所以宣称算法获得了“改进”)。而实际上，执行时间的减少很可能是由于所用机器性能提高了，或者是所用语言比前者效率高所致，所谓“改进算法”实际上不见得比原算法高明。霍普克洛夫特对这种情况很不满意，决心加以解决。经过反复研究，他终于提出了一种“算法的最坏情况渐近分析法”(worst-case asymptotic analysis of algorithms)，这种方法先确定问题的大小尺度，然后把计算时间当作问题大小尺度的一个函数去算出计算时间的增长率，以此衡量算法的效率和优劣。这个方法由于与机器性能及所用语言无关，成为测量算法好坏的数学准则，被学界所广泛认同和接受。
John Edward Hopcroft著作但是导致他和陶尔扬共同获得图灵奖的最主要原因则是他们解决了图论算法中的一些难题，创造了新的、重要的数据结构和影响深远的算法。1970年，霍普克洛夫特在康乃尔大学获得一年学术休假(他是1967年被哈特马尼斯招至麾下的)。他决定回母校斯坦福大学到克努特教授名下做研究，因为克努特虽然只比他年长一岁，但因在1968年和1969年连出两卷《计算机程序设计的艺术》(The Art of Computer Programming)而已名满天下，成为算法领域的权威。克努特知道霍普克洛夫特对算法有兴趣并有独到见解，就把他和自己的得意门生、研究方向也是算法的陶尔扬安排在一个办公室(也有资料说是相邻办公室)，为他们的合作创造了条件。他们选择了图论中与实际应用有很大关系的图的连通性(connectivity，也就是图中任意两个结点是否都是相互可达的)和平面性(planarity，也就是图中所有的边是否都可以安排得互不交叉)的测试难题进行攻关。拿如下所示的平面图来说，它对印刷电路板设计这样一类问题有十分重要的意义。学过图论的人都知道，平面图判断问题的研究可以上溯到18世纪，伟大的数学家欧拉早就证明，若结点数为n，则当n等于大于3时，所有边数等于大于(3n—6)的图都不是平面图。但边数小于(3n—6)的图是否是平面图呢?欧拉没有给予说明。1930年，波兰数学家库拉托夫斯基(Kuratowski)解决了这个问题，他给出了如下的判断法则：如果一个图既不包括5个结点的完全图(叫K5)作子图，也不包括6个结点的偶图(叫K3，3，)作子图，则该图是平面图，否则为非平面图。所谓完全图(complete graph)就是任意2个结点之间都有边的图，见图(a)；所谓偶图(bipartite graph)就是可以把全部结点分成两个不相交的集合，所有边的两个端点分属于这两个集合的图，见图(b)。这个判据看似简单，但实现起来很难。对于有100个结点的图，用普通的算法，计算机需要1万亿步才能确定它是否是平面图。因此，寻找高效的平面图测试算法成为摆在当时计算机科学家面前的一大难题。霍普克洛夫特和陶尔扬都是富有创造性的人，又都善于合作共事，因此当两朵智慧的火花碰在一起时，就很快进发出耀眼的光芒!在解决这个难题的过程中，霍普克洛夫特首先提出了一种新的思路，经过陶尔扬的反复推敲和完善，一种适于解这类问题的新的算法终于诞生了，这就是著名的“深度优先搜索算法”(depth-first search algorithm)。利用这种算法对图进行搜索时，结点扩展的次序是向某一个分枝纵深推进，到底后再回溯，这样就能保证所有的边在搜索过程中都经过一次，但也只经过一次，从而大大提高了效率。新算法的运行时间是线性的，也就是说时间与图的大小成正比关系，大小翻一倍，解问题所需的时间也只翻一倍，不像用库拉托夫斯基判断的老算法那样，所需时间要增加60倍以上。利用他们创造的新算法，陶尔扬用Algol W为一个包含900个结点和2 694条边的图编制了一个测试其平面性的程序，程序只有500行，在IBM 360／67上运行，只用了12 s就得到了结果。霍普克洛夫特和陶尔扬的研究成果在《ACM学报》(Journal of ACM)上公布以后，引起学术界很大的轰动，而他们创造的深度优先算法则被推广到信息检索、人工智能等方面成功地得到应用。在向霍普克洛夫特和陶尔扬授予图灵奖的仪式上，当年的国际象棋程序比赛的优胜者就说，他的程序在搜索可能的棋步时用的就是深度优先算法，这是他的程序所以能出奇制胜的关键。
平面图
(a)K5
(b)k3,3
在取得辉煌成功之后，霍普克洛夫特和陶尔扬并不满足，继续致力于开发效率更高的算法。不久，他们又发明了一种新的数据结构叫“双堆栈叠”(pile of twin stacks)，这种数据结构使深度优先搜索算法的优点更加发扬光大。陶尔扬的一个学生用这种新的数据结构和深度优先算法编写了一个Algol W程序，只有250行，在IBM 370／168上测试有8 000个结点的图的平面性，只用了8s。
霍普克洛夫特除了和陶尔扬合作取得上述成果外，在数据结构和算法方面还有其他一系列创造。比如常用于索引组织的著名数据结构B树，是一种平衡的多分树，对查找、插入、删除等操作能始终保持动态平衡，具有很高的效率。霍普克洛夫特在对B树进行深入研究以后，为了进一步提高其操作效率和空间利用率，创造了它的一种变形叫“2—3树”，这种树的每个结点有2个键，每个键都有2-3个儿子。
John Edward Hopcroft（左）霍普克洛夫特著述颇丰，除前面已经提到过的他的处女作以外，还有以下多部著作问世。
《计算机算法的设计与分析》(The Design and Analysis of Computer Algorithms，Addison-Wesley，1974)
《数据结构和算法》(Data Structures and Algorithms，Addison-Wes1ey，1982，1983，1987)
《自动机理论，语言和计算导论》(Introduction to Automata Theory，Languages，and Computation，Addison-Wesley，1979。本书有中译本，徐美瑞译，科学出版社出版)
《计算机科学：成就与机遇》(Computer Science：Achievements and Opportunities，SIAM，1989)
霍普克洛夫特近期的研究兴趣集中在机器人学方面，这从他现任康乃尔大学机器人实验室主任这一点上可以看出。
在接受图灵奖时，霍普克洛夫特和陶尔扬分别发表了演说，前者的演说题为“计算机科学：作为一门学科的出现”(Computer Science：the Emergence of a Discipline)，后者的演说题为“算法设计”(Algorithm Design)。两人还一起接受了记者卡伦·弗兰克尔(Karen A．Frenkel)的采访。两篇演说及与记者的对话刊于Communications of ACM，1987年3月，197-222页。颁奖典礼是在德克萨斯州的达拉斯召开的1986年秋季联合计算机会议期间举行的。
1986年图灵奖获得者John E. Hopcroft更多资料编辑本段回目录
作者 陈怀临
John E. Hopcroft(10/07/1939–)图灵奖获得时间：1986年。 第二十一位图灵奖(1986年)获得者。
图灵奖引用(Turing Award Citation) ：
John Edward HopcroftFor fundamental achievements in the design and analysis of algorithms and data structures.
(授予John E. Hopcroft图灵奖以表彰其在)数据结构和算法设计与分析领域的重要的基础性的贡献。
算法分析：
http://www.algorithmist.com/index.php/Main_Page
http://en.wikipedia.org/wiki/Analysis_of_algorithms
http://en.wikipedia.org/wiki/Algorithm
http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node8.html
Big-O Notation: http://en.wikipedia.org/wiki/Big_O_notation
Hopcroft撰写的计算理论，数据结构，算法分析方面的书籍：
J.E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman, Introduction to Automata Theory, Languages, and Computation Second Edition. Addison-Wesley (2001).
Alfred V. Aho, J.E. Hopcroft, Jeffrey D.Ullman, Data Structures and Algorithms, Addison-Wesley Series in Computer Science and Information Processing. (1983)
Alfred V. Aho, J.E. Hopcroft, Jeffrey D.Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley Series in Computer Science and Information Processing (1974).
John Hopcroft发表的一些重要学术论文：
J. E. Hopcroft and J. D. Ullman. Decidable and undecidable questions about automata. Journal of the ACM, 15(2):317-324, April 1968. References and Citations.
John E. Hopcroft and Jeffrey D. Ullman. Relations between time and tape complexities. Journal of the ACM, 15(3):414-427, July 1968. References and Citations.
J. E. Hopcroft and J. D. Ullman. Some results on tape-bounded Turing machines. Journal of the ACM, 16(1):168-177, January 1969. References, Citations, etc.
Seymour Ginsburg and John Hopcroft. Two-way balloon automata and AFL. Journal of the ACM, 17(1):3-13, January 1970. References, etc.
J. Hartmanis and J. E. Hopcroft. An overview of the theory of computational complexity. Journal of the ACM, 18(3):444-475, July 1971. References, Citations, etc.
John Hopcroft and Robert Tarjan. Efficient planarity testing. Journal of the ACM, 21(4):549-568, October 1974. References, Citations, etc.
John Hopcroft, Wolfgang Paul, and Leslie Valiant. On time versus space. Journal of the ACM, 24(2):332-337, April 1977.
Turing Award Lecture(图灵奖演讲文章)：
Computer Science: The Emergence of a Discipline. Commun. ACM 30(3): 198-202(1987)
John E. Hopcroft简介:
John Edward HopcroftHopcroft在康乃尔大学(www.cornell.edu )的主页: http://www.cs.cornell.edu/jeh/
Hopecroft Wiki: http://en.wikipedia.org/wiki/John_Hopcroft
John E. Hopcroft于1939年10月7日出生。
Hopcroft于1961年从西雅图大学(Seattle University: www.seattleu.edu) 获得其电子工程的学士学位。1962年和1964年在斯坦福大学获得其电子工程专业的硕士和博士学位。1964年到1967年，Hopcroft在普林斯顿大学(www.princeton.edu)担任助理教授一职。然后，Hopcrosft基本上就一直出任Cornell大学工学院的教授，院长，计算机系的教授等职位。
Hopcroft获得过许多学术荣誉，可参见：
Honors (awards, medals, prizes, offices held in professional societies, with years):
2005- IEEE Harry H. Goode Memorial Award
2004- IBM Professor of Engineering and Applied Mathematics
1994- Fellow of the Association for Computing Machinery
1990 Doctor of Humanities Degree, Honoris Causa, Seattle University
1989- Member of the National Academy of Engineering
1987- Fellow of the Institute of Electrical and Electronics Engineering
1987- Fellow of the American Association for the Advancement of Science
1987- Fellow of the American Academy of Arts and Sciences
1986 Association for Computing Machinery A.M. Turing Award (shared with R.J. Tarjan)
1985-1993 Joseph C. Ford Professor of Computer Science
1961-1964 National Science Foundation Graduate Fellow
