Loading AI tools
informaticien américain De Wikipédia, l'encyclopédie libre
John Edward H. Hopcroft, né le à Seattle[2], est un informaticien américain, professeur émérite à l'université Cornell.
| Naissance | |
|---|---|
| Nationalité | |
| Formation | |
| Activités |
| A travaillé pour | |
|---|---|
| Membre de | |
| Directeur de thèse |
Richard Mattson (en) |
| Site web | |
| Distinctions |
Il est coauteur, avec Jeffrey D. Ullman et Alfred V. Aho ou les deux, de plusieurs livres importants sur les algorithmes, les structures de données, et sur les automates et langages formels qui ont été des ouvrages de références pendant très longtemps. Il s'est impliqué dans la définition de l'enseignement de l'informatique aux États-Unis depuis le début, et a formé quantité de scientifiques en informatique.
Il a reçu le prix Turing en 1986.
En 1961, Hopcroft obtient le diplôme de bachelor en électrotechnique à l'université de Seattle, puis il poursuit ses études à l'université Stanford, où il obtient en 1962 la maîtrise et en 1964 un Ph. D. sous la direction de Richard L. Mattson, avec une thèse intitulée « Synthesis of Threshold Logic Networks »[3]. Après trois années à l'université de Princeton, il obtient un poste de professeur à l'université Cornell à Ithaca; en 2016, il y est IBM Professor of Engineering and Applied Mathematics in Computer Science. De 1987 à 1992, il dirige à Cornell la faculté d'informatique, puis il est Associate Dean for College Affairs du College of Engineering, et doyen du collège de 1994 à 2001. De 1970 à 1971 il est en année sabbatique professeur invité à l'université Stanford.
Hopcroft travaille principalement en analyse des algorithmes, théorie des automates, théorie des graphes, langages formels, et plus récemment sur la saisie et l'accès à l'information. Avec Ravindran Kannan, il travaille sur un livre intitulé Computer Science Theory for the Information Age, dont la version préliminaire est disponible en ligne.
Il est l'auteur, avec Richard Karp, de l'algorithme de Hopcroft-Karp pour le problème d'affectation qui consiste à trouver un couplage dans un graphe biparti[4]. Il a aussi créé avec Jin-Kue Wong, un algorithme linéaire pour le problème de l'isomorphisme de graphes sur les graphes planaires[5].
Il a participé activement à l'introduction de la notion de complexité asymptotique des algorithmes, en faisant adopter par la communauté scientifique la notation de Landau pour mesurer la complexité dans le cas le plus défavorable; en cela, il s'est opposé à Knuth par exemple qui comptait les opérations élémentaires dans un langage symbolique abstrait. Il a aussi discuté de la place du formalisme mathématique dans l'enseignement de l'algorithmique. Ainsi, son livre Data Structures and Algorithms ne contient ni « énoncé » ni « démonstration », tout en donnant des bornes sur l'efficacité et leurs preuves.
Hopcroft a développé, en collaboration avec Tarjan, un ensemble important de structures de données et d'algorithmes pour la manipulation de graphes[6]. L'une des contributions majeures, dans ses travaux avec Tarjan, est le test de planarité d'un graphe en temps linéaire[7].
Parmi ses élèves, il y a Alfred Aho, Chandrajit Bajaj (en), Gilles Brassard, Cynthia Dwork, Zvi Galil (en), Daniela L. Rus.
En dehors de l'université Cornell, Hopcroft est ou a été conseiller, membre de comité ou éditeur d'environ 130 entreprises, institutions, conférences ou journaux scientifiques, parmi lesquels la Alfred P. Sloan Foundation, les Laboratoires Bell, l'université Carnegie-Mellon, le Goddard Space Flight Center, IBM, Microsoft, la NASA, l'Académie nationale d'ingénierie des États-Unis, l'Académie nationale des sciences, le Conseil national de la recherche des États-Unis, le National Science Board (en), les Laboratoires Sandia, le SIAM Journal on Scientific Computing, la Society for Industrial and Applied Mathematics, la United States Army, la United States Air Force et l'université Yale.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
