John Hopcroft

John Edward H. Hopcroft, né le 7 octobre 1939 à Seattle[2], est un informaticien américain, professeur émérite à l'université Cornell.

John Hopcroft

John Hopcroft, lors de sa nomination de docteur honoris causa de l'Université ITMO de Saint-Pétersbourg[1] (2009).

Biographie
Naissance	7 octobre 1939 Seattle
Nationalité	Américaine
Formation	Université Stanford Université de Seattle
Activités	Informaticien, professeur d'université

Autres informations
A travaillé pour	Université Cornell, Université de Seattle
Membre de	Association for Computing Machinery Académie américaine des arts et des sciences Académie nationale d'ingénierie des États-Unis (1989) Académie américaine des sciences (2009) Society for Industrial and Applied Mathematics (2009)
Dir. de thèse	Richard Mattson (en)
Site web	www.cs.cornell.edu/jeh
Distinctions	Prix Turing (1986) Liste détaillée Prix Turing (1986) ACM Fellow (1994) Prix commémoratif Harry H. Goode (2005) Fellow of the Society for Industrial and Applied Mathematics (2009) Médaille John von Neumann (2010) Honorary doctor of the Beijing Institute of Technology (2010) Prix de l'amitié (en) (2016)

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.

Biographie

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.

Recherche

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 Rus (en).

Activités diverses

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.

Livres

John E. Hopcroft et Jeffrey D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, 1969, vii+242 (ISBN 0-201-02983-9)
Alfred V. Aho, John E. Hopcroft et Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974, 470 p. (ISBN 0-201-00029-6)
John E. Hopcroft et Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979, x+418 (ISBN 0-201-02988-X, SUDOC 005953170)
Alfred V. Aho, John E. Hopcroft et Jeffrey D. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983 — traduit en français par Jean-Michel Moreau Structures de données et algorithmes, et en 3 autres langues.
John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Pearson Education, 2014, 3^e éd., ii+488 (ISBN 978-1-292-03905-3, SUDOC 182498972) — Deux autres éditions ont précédé, en 2001 et 2007. Traduit en 3 langues.

Prix et distinctions (sélection)

1961–1964 : Graduate Fellow de la National Science Foundation
1986 : Prix Turing, avec Robert Tarjan, « pour ses contributions fondamentales à la conception et l'analyse des algorithmes et des structures de données »[8].
1990 : Docteur honoris causa de l'université de Seattle
2005 : Harry H. Goode Memorial Award (en) « pour ses contributions fondamentales à l’étude des algorithmes et leurs applications au traitement de l'information »[9]
2008 : Karl V. Karlstrom Outstanding Educator Award « pour sa vision et son impact en informatique, y compris comme coauteur de textes délimitant les domaines en théorie et algorithmique qui continuent à influencer des étudiants après 40 ans, en dirigeant des étudiantes en Ph. D. qui eux-mêmes contribuent maintenant grandement à l'informatique, et en exerçant une direction en science et enseignement de l'informatique aux niveaux national et international »[10]
2005 : Docteur honoris causa de l'université de Sydney, Australie.
2008 : Professeur honoraire de l’université de technologie de Pékin
2009 : Professeur émérite (ou docteur honoris causa) de l'université ITMO[1].
2010 : Médaille John von Neumann avec Jeffrey Ullman « pour avoir contribué aux fondements du domaine des automates et langages formels et de nombreuses contributions séminales en informatique théorique »[11], professeur honoraire de l'université du Yunnan et professeur Einstein de l’Académie chinoise des sciences

Nominations

1987 : Fellow de l'IEEE, Fellow de l'American Association for the Advancement of Science, Fellow de l'American Academy of Arts and Sciences
1989 : Membre de la National Academy of Engineering
1992-1998 : Membre du National Science Board (en).
1994 : Fellow de l'Association for Computing Machinery.

Notes et références

Professeur émérite.
« Biographie de John E Hopcroft », sur amturing.acm.org/
(en) « John Edward H. Hopcroft », sur le site du Mathematics Genealogy Project
John E. Hopcroft et Richard M. Karp, « An n^5/2 algorithm for maximum matchings in bipartite graphs », SIAM Journal on Computing, vol. 2, n^o 4,‎ 1973, p. 225-231 (DOI 10.1137/0202019).
John E. Hopcroft et Jin-Kue Wong, « Linear time algorithm for isomorphism of planar graphs », dans Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, 1974 (DOI 10.1145/800119.803896), p. 172–184
John E. Hopcroft et Robert Endre Tarjan, « Efficient Algorithms for Graph Manipulation [H] (Algorithm 447) », Communications of the ACM, vol. 16, n^o 6,‎ 1973, p. 372-378 (DOI 10.1145/362248.362272).
John E. Hopcroft et Robert Endre Tarjan, « Efficient Planarity Testing », Journal of the ACM, vol. 21, n^o 4,‎ 1974, p. 549-568 (DOI 10.1145/321850.321852)
« ACM Awards: A. M. Turing Award » [archive du 12 décembre 2009], ACM (consulté le 5 février 2011).
« Harry H. Goode Memorial Award Past Recipients », IEEE (consulté le 8 mai 2009).
« Karl V. Karlstrom Outstanding Educator Award » [archive du 19 avril 2012], ACM (consulté le 28 octobre 2009)
(en) « IEEE John von Neumann Medal Recipients », IEEE (consulté le 4 février 2010)

Liens externes

Site Internet de John Hopcroft
John Hopcroft sur le site de l'université Cornell
Ressources relatives à la recherche :
Notices d'autorité :

Portail de l’informatique
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[ITMO-1] Professeur émérite.

[2] « Biographie de John E Hopcroft », sur amturing.acm.org/

[3] (en) « John Edward H. Hopcroft », sur le site du Mathematics Genealogy Project

[4] John E. Hopcroft et Richard M. Karp, « An n^5/2 algorithm for maximum matchings in bipartite graphs », SIAM Journal on Computing, vol. 2, n^o 4,‎ 1973, p. 225-231 (DOI 10.1137/0202019).

[5] John E. Hopcroft et Jin-Kue Wong, « Linear time algorithm for isomorphism of planar graphs », dans Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, 1974 (DOI 10.1145/800119.803896), p. 172–184

[6] John E. Hopcroft et Robert Endre Tarjan, « Efficient Algorithms for Graph Manipulation [H] (Algorithm 447) », Communications of the ACM, vol. 16, n^o 6,‎ 1973, p. 372-378 (DOI 10.1145/362248.362272).

[7] John E. Hopcroft et Robert Endre Tarjan, « Efficient Planarity Testing », Journal of the ACM, vol. 21, n^o 4,‎ 1974, p. 549-568 (DOI 10.1145/321850.321852)

[8] « ACM Awards: A. M. Turing Award » [archive du 12 décembre 2009], ACM (consulté le 5 février 2011).

[IEEE-9] « Harry H. Goode Memorial Award Past Recipients », IEEE (consulté le 8 mai 2009).

[ACM2-10] « Karl V. Karlstrom Outstanding Educator Award » [archive du 19 avril 2012], ACM (consulté le 28 octobre 2009)

[11] (en) « IEEE John von Neumann Medal Recipients », IEEE (consulté le 4 février 2010)