1986 约翰·霍普克洛夫特

shiyi18

John E Hopcroft
BIRTH:
October 7, 1939, Seattle Washington, USA

EDUCATION:
B.S., Seattle University (1961, Electrical Engineering); M.S., Stanford University (1962 Electrical Engineering); Ph.D., Stanford University (1964, Electrical Engineering).

EXPERIENCE:
Assistant Professor, Princeton University (1964-1967); Cornell University (Associate Professor, 1967-1971; Professor, 1972-85; Joseph C. Ford Professor, College of Engineering, 1985-1994; Chair, Dept. of Computer Science, 1987-92; Associate Dean for College Affairs, 1992-1993; Joseph Silbert Dean, College of Engineering, 1994-2001; Professor, Department of Computer Science, 2001-2004; IBM Professor of Engineering and Applied Mathematics (2004 and onwards).

HONORS AND AWARDS:
National Science Foundation Graduate Fellow, 1961-1964; Association for Computing Machinery A.M. Turing Award (shared with R.E. Tarjan), 1986; Fellow of the American Academy of Arts and Sciences, 1987; Fellow of the American Association for the Advancement of Science, 1987; Fellow of the Institute of Electrical and Electronics Engineers (IEEE), 1987; Member of the National Academy of Engineering, 1989; Fellow of the Association for Computing Machinery, 1994; Life Fellow of IEEE, 2004; Cornell College of Engineering Michael Tien ’72 Excellence in Teaching Award, 2004; IEEE Harry Goode Memorial Award, 2005; Assoc. of Computer Science Undergraduates Faculty of the Year Award, 2006; CRA Distinguished Service Award, 2007; ACM Karl V. Karlstrom Outstanding Educator Award, 2008; Honorary professorship, Beijing Institute of Technology, 2008; Fellow of Society for Industrial and Applied Mathematics, 2009; Member of the National Academy of Sciences, 2009; Einstein professor Chinese Academy of Sciences, 2010; IEEE von Neumann Medal, 2010, 2011; Ralph S. Watts 72 Excellence in Teaching Award, 2011; Recognized by the Societe Mathematique de Tunisie (SMT) for “notable services and outstanding contributions in the application of mathematical theories in theoretical computer science”, March 2010; Honorary professorship, Yunnan University, 2010; Honorary professorship, Chongqing University, 2011; Honorary professorship, Jiao Tong University, 2011; Honorary degrees from: Seattle University; University of Sydney; Saint Petersburg State University of Information Technologies, Mechanics & Optics; HKUST; Beijing Institute of Technology; and National College of Ireland.

JOHN E HOPCROFT DL Author Profile link
United States – 1986
CITATION
With Robert E Tarjan, for fundamental achievements in the design and analysis of algorithms and data structures.

SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE
RESEARCH
SUBJECTS
ADDITIONAL
MATERIALS
VIDEO INTERVIEW
John Hopcroft was born into a working class family on October 7, 1939 in Seattle Washington. His father was a British veteran of the First World War who moved to Canada because he was unable to find employment in Britain. He eventually worked his way to the west coast and finally to Seattle, where he met and married John’s mother and worked as a janitor.

John grew up in Seattle and attended the local schools. Neither of his parents were high school graduates, but they instilled in him a love of learning and worked hard to ensure that he had the chance to obtain more education than either of them had. At an early age John was fascinated by technology – trains at first, and later mathematics and logic, particularly those aspects relating to electrical engineering.

He claims that because of the lack of family experience with higher education, it never occurred to him to look at other than the local Seattle University. He graduated with a BS in Electrical Engineering in 1961.

Hopcroft describers his first computing experience, programming an IBM 650 as an undergraduate.        
He was a fine student and was quickly admitted to graduate studies at Stanford University, where he received a MS in 1962 and a PhD in 1964, both in Electrical Engineering.

John’s first academic job was as an Assistant Professor of Electrical Engineering at Princeton. He became a computer scientist almost by accident, when his department head asked him to teach a class in computing science.

Hopcroft describers being hired for his first academic job, at Princeton, without having published a single paper.        
Since he had no experience in the subject, he had to ask what subjects should be included. The department head recommended a few papers, and John managed to create and teach this first course to six bright students who in turn motivated him. He taught that class for several years, but he says that first year was the most enjoyable because he and his few students were feeling their way into unfamiliar territory together.

One of those first students was Jeff Ullman, who would become a major collaborator in his work. Jeff left Princeton to work at Bell Laboratories and teach an evening course at Columbia University. This was the era when there were few computer science texts, particularly for the theoretical aspects of the subject. Hopcroft and Ullman took John’s course notes and expanded them into one of the earliest and most influential books on the subject [1].  This volume and its many translations educated an entire generation of computer scientists. Its successor [3] is still in use today.

Hopcroft describers the genesis of his textbook with Jeff Ullman, Formal Languages and Their Relationship to Automata.        
John’s first computer science research efforts were in an area that became known as formal language theory. Linguists had developed formal grammars for the study of human languages, and similar tools could be used for the developing high level programming languages. The earliest compilers had not been based on a theoretical foundation like that; they were simply a collection of ad-hoc routines that analyzed the statements in a high level language and created the equivalent set of instructions in computer machine code. This process sufficed for the earliest compliers but quickly became unworkable as languages increased in complexity. John made fundamental advances in formal grammars before turning his attention to the study of algorithms.

In the early days of computers, algorithms tended to be compared based on total running time, which depends on the speed of the computer, the programming efficiency, the constant overhead of the algorithm, and the growth rate of the running time as the input gets larger. John recognized that as computers became faster and worked on larger problems, the most important part to understand was the last: the growth rate of the running time. His focus on this “asymptotic complexity” set the direction for the new field of analysis of algorithms.

Much of this work dealt with the algorithms used to manipulate graphs, which are made from a set of points (vertices) connected by lines (edges). While this may appear to be a very academic and abstract subject, many practical problems can be described using graphs. Thus any improvements in the general algorithms used to manipulate graphs can provide practical improvements to real life problems. Such problems span the range from linguistics (for grammar and syntactic analysis), to chemistry (for modelling of atoms and molecules to compute their properties), to network analysis (for determining the flow of traffic in the World Wide Web or in highways).

Hopcroft describers his work with Robert Tarjan on the analysis of graph algorithms.        
Hopcroft’s work on graph algorithms was not just theoretical analysis, it also included synthesis. He explored efficient structures for storing data in a computer, and created efficient algorithms for solving the problems they could represent. This work, new and exciting at the time, is now part of the standard computer science curriculum.

His work on formal languages and the analysis of algorithms has made John Hopcroft one of the handful of pioneering computer scientists who put the discipline on a firm theoretical foundation. His co-authored texts on formal languages and their relation to automata [1] and on the design and analysis of algorithms [2] became the standards for a generation of computer scientists.

His current work, which again uses graph models, explores ways to track social networks and build the search engines of the future.

John is not only a respected researcher, but also an inspiring teacher. Each year the top 20 graduates at Cornell are asked to name the professor that had the most influence on their education. John has been chosen twice, a record of which he is justly proud.

He believes that students should be required to take fewer specialist courses. They should be allowed acquire a broad education and have more free time to learn things on their own. He admits that his success in changing university curricula requirements has been limited, but he’s still trying.

Hopcroft has been an influential and inspiring PhD advisor to at least 34 students since 1967. His advisees learned how to do research from him, but they also absorbed his sense of discrimination, his standard of excellence, and his commitment to community service. Many of them now serve in influential positions in academia and industry. Among his PhD students are the president of an Israeli university, a MacArthur Fellow, a vice president of a computing research firm, and many chairs of academic departments.

Throughout his career, Hopcroft has helped the field by serving on national and international committees. The respect for his views and his work are evident from the many honors he has received.



ABOUT THE
A.M. TURING
AWARD
NOMINATIONS
VIDEO:
THE ORIGINS
OF THE AWARD

2020 LAUREATES:
ALFRED VAINO AHO
JEFFREY DAVID ULLMAN

THE A.M. TURING AWARD
LECTURES



John E Hopcroft
出生地：美国
1939年10月7日，美国华盛顿州西雅图市

学历：西雅图大学学士（1961年，电气工程）；斯坦福大学硕士（1962年，电气工程）；博士
西雅图大学学士（1961年，电气工程）；斯坦福大学硕士（1962年，电气工程）；斯坦福大学博士（1964年，电气工程）。

工作经验。
普林斯顿大学助理教授（1964-1967）；康奈尔大学（副教授，1967-1971；教授，1972-85；工程学院Joseph C. Ford教授，1985-1994；计算机科学系主任，1987-92；学院事务副院长，1992-1993；工程学院Joseph Silbert院长，1994-2001；计算机科学系教授，2001-2004；IBM工程与应用数学教授（2004及以后）。

荣誉和奖项。
国家科学基金会研究生研究员，1961-1964年；计算机械协会A.M.图灵奖（与R.E.Tarjan共享），1986年；美国国家科学院院士，1961-1964年。Tarjan），1986年；美国艺术与科学学院院士，1987年；美国科学促进会院士，1987年；电气与电子工程师协会（IEEE）院士，1987年；美国国家工程院院士，1989年；计算机械协会院士，1994年；IEEE终身院士，2004年；康奈尔工程学院Michael Tien '72卓越教学奖，2004年；IEEE Harry Goode纪念奖，2005年；Assoc. 2006年，计算机科学本科生协会年度最佳教师奖；2007年，CRA杰出服务奖；ACM卡尔-V。Karlstrom杰出教育家奖，2008年；北京理工大学名誉教授，2008年；工业与应用数学学会会员，2009年；美国国家科学院院士，2009年；中国科学院爱因斯坦教授，2010年；IEEE冯-诺依曼奖章，2010年，2011年；Ralph S．Watts 72卓越教学奖，2011年；因 "在理论计算机科学中应用数学理论的显著服务和杰出贡献 "而被突尼斯数学协会（SMT）认可，2010年3月；云南大学名誉教授，2010年；重庆大学名誉教授，2011年；交通大学名誉教授，2011年；荣誉学位，来自。西雅图大学；悉尼大学；圣彼得堡国立信息技术、机械和光学大学；香港科技大学；北京理工大学；以及爱尔兰国立学院。

JOHN E HOPCROFT DL作者简介链接
美国 - 1986年
参考文献
与Robert E Tarjan一起，在算法和数据结构的设计和分析方面取得了基本成就。

短篇注释
书目
亚马逊图灵奖
讲座
研究
主题
额外的
材料
采访视频
约翰-霍普克罗夫特于1939年10月7日出生在华盛顿州西雅图的一个工人家庭。他的父亲是一位参加过第一次世界大战的英国老兵，因为在英国找不到工作而搬到了加拿大。他最终在西海岸工作，最后到了西雅图，在那里他遇到了约翰的母亲并与之结婚，做了一名看门人。

约翰在西雅图长大，在当地的学校上学。他的父母都不是高中毕业生，但他们向他灌输了对学习的热爱，并努力确保他有机会获得比他们任何人都多的教育。在很小的时候，约翰就对技术很着迷--一开始是火车，后来是数学和逻辑，特别是与电气工程有关的方面。

他声称，由于家庭缺乏接受高等教育的经验，除了当地的西雅图大学外，他从未想过要去看其他学校。他于1961年毕业，获得了电子工程学士学位。

霍普克罗夫特描述了他的第一次计算经验，在本科时为IBM 650编程。        
他是个好学生，很快就被斯坦福大学的研究生录取，1962年获得硕士学位，1964年获得博士学位，都是电气工程专业。

约翰的第一份学术工作是在普林斯顿大学担任电子工程的助理教授。他成为一名计算机科学家几乎是偶然的，当时他的系主任要求他教一门计算科学的课。

霍普克罗夫特描述说，他在普林斯顿的第一份学术工作是在没有发表过一篇论文的情况下被聘用的。        
由于他没有这方面的经验，他不得不询问应该包括哪些科目。系主任推荐了几篇论文，约翰成功地创建了这第一门课程，并为六个聪明的学生授课，这些学生反过来激励了他。他教了那门课好几年，但他说第一年是最愉快的，因为他和他的几个学生一起摸索着进入陌生的领域。

这些第一批学生中的一个是杰夫-乌尔曼，他后来成为他工作中的一个主要合作者。杰夫离开普林斯顿，在贝尔实验室工作，并在哥伦比亚大学教夜校课程。那是一个计算机科学教材很少的时代，特别是关于这个学科的理论方面。霍普克罗夫特和乌尔曼采用了约翰的课程笔记，并将其扩展为关于该主题的最早和最有影响力的书籍之一[1]。 这本书和它的许多译本教育了整整一代计算机科学家。它的后续版本[3]至今仍在使用。

Hopcroft描述了他与Jeff Ullman的教科书《形式语言及其与自动机的关系》的起源。        
约翰的第一个计算机科学研究工作是在一个后来被称为形式语言理论的领域。语言学家已经开发了用于研究人类语言的形式化语法，类似的工具也可用于开发高级编程语言。最早的编译器并不是建立在这样的理论基础上的；它们只是一组临时的例程，分析高级语言中的语句，并在计算机机器代码中创建相应的指令集。这个过程对最早的编译器来说是足够的，但随着语言复杂性的增加，很快就变得不可行了。约翰在把注意力转向算法研究之前，在形式语法方面取得了基本进展。

在计算机的早期，算法往往是根据总的运行时间来比较的，这取决于计算机的速度、编程效率、算法的恒定开销，以及随着输入量的增大，运行时间的增长率。约翰认识到，随着计算机的速度越来越快，处理的问题越来越大，最需要了解的部分是最后一部分：运行时间的增长率。他对这种 "渐进复杂性 "的关注为算法分析的新领域确定了方向。

这项工作的大部分涉及到用于操纵图形的算法，图形是由一组点（顶点）通过线（边）连接而成的。虽然这可能看起来是一个非常学术和抽象的主题，但许多实际问题都可以用图来描述。因此，用于操纵图形的一般算法的任何改进都可以为现实生活中的问题提供实际改进。这些问题的范围从语言学（用于语法和句法分析），到化学（用于原子和分子的建模以计算其属性），再到网络分析（用于确定万维网或高速公路的流量）。

霍普克罗夫特介绍了他与罗伯特-塔扬在图算法分析方面的工作。        
霍普克罗夫特在图算法方面的工作不仅仅是理论分析，还包括综合分析。他探索了在计算机中存储数据的有效结构，并为解决它们所能代表的问题创造了有效的算法。这项工作在当时是新的和令人兴奋的，现在是标准计算机科学课程的一部分。

他在形式语言和算法分析方面的工作使约翰-霍普克罗夫特成为少数几个将该学科建立在坚实理论基础上的先锋计算机科学家之一。他与人合著的关于形式语言及其与自动机的关系[1]和关于算法的设计和分析[2]的文章成为一代计算机科学家的标准。

他目前的工作，再次使用图模型，探索跟踪社会网络和建立未来搜索引擎的方法。

约翰不仅是一位受人尊敬的研究者，也是一位鼓舞人心的老师。每年，康奈尔大学的前20名毕业生被要求说出对他们的教育影响最大的教授。约翰已经两次被选中，这是他引以为豪的记录。

他认为，应该要求学生少修专业课程。应该允许他们获得广泛的教育，并有更多的自由时间来学习自己的东西。他承认，他在改变大学课程要求方面的成功是有限的，但他仍在努力。

自1967年以来，霍普克罗夫特一直是至少34名学生的具有影响力和启发性的博士生导师。他的顾问们从他那里学到了如何做研究，但他们也吸收了他的歧视意识、他的卓越标准以及他对社区服务的承诺。他们中的许多人现在在学术界和工业界担任有影响力的职务。在他的博士生中，有以色列大学的校长、麦克阿瑟研究员、一家计算机研究公司的副总裁，以及许多学术部门的主席。

在他的职业生涯中，霍普克罗夫特通过在国家和国际委员会中任职来帮助这个领域。从他所获得的众多荣誉中，可以看出人们对他的观点和工作的尊重。