John Hopcroft

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
John Hopcroft à l'occasion de l'attribution du doctorat honoris causa de l’Université d'État de Saint-Pétersbourg (2009).

John Edward Hopcroft, né le 7 octobre 1939, est un informaticien américain, enseignant à l'université Cornell et dont il devient le doyen de la Faculté d'Ingénierie en 1994.

Il est l'un des trois auteurs de deux livres importants sur la compilation[1],[2], écrits avec Jeffrey D. Ullman et Alfred V. Aho.

Il a reçu le prix Turing en 1987.

Travaux[modifier | modifier le code]

Il est l'auteur avec Richard Karp de l'algorithme de Hopcroft-Karp (en) pour le Problème d'affectation qui consiste à trouver un couplage dans un graphe biparti[3]. Il a aussi créé avec Jin-Kue Wong, un algorithme linaire pour le problème de l'isomorphisme de graphes sur les graphes planaires[4].

Distinctions[modifier | modifier le code]

Il reçut le Prix Turing en 1987 et la médaille John von Neumann en 2010[5].

Notes et références[modifier | modifier le code]

  1. Alfred V. Aho, J.E. Hopcroft, Jeffrey D. Ullman, Data Structures and Algorithms, Addison-Wesley Series in Computer Science and Information Processing. (1983)
  2. Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, coll. « Series in Computer Science and Information Processing »,‎ 1974, 470 p. (ISBN 0201000296)
  3. John E. Hopcroft et Richard M. Karp, « An n5/2 algorithm for maximum matchings in bipartite graphs », SIAM Journal on Computing, vol. 2, no 4,‎ 1973, p. 225-231 (DOI 10.1137/0202019).
  4. 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
  5. « IEEE John von Neumann Medal Recipients », IEEE (consulté le 15 mars 2010)

Liens externes[modifier | modifier le code]