John Hopcroft : Le manuel qui a formé une discipline

Des millions d'étudiants en informatique n'ont jamais lu un mot écrit par John Hopcroft dans une revue de recherche, et pourtant, presque tous ont appris grâce à lui — à travers les manuels de théorie des automates et d'algorithmes qui portent son nom aux côtés de ceux de Jeffrey Ullman et Alfred Aho, des livres si largement adoptés comme programme standard qu'ils ont façonné la manière dont la discipline s'enseigne elle-même.

Du fils de concierge à Stanford

John Edward Hopcroft est né le 7 octobre 1939 à Seattle, dans l'État de Washington, dans une famille de la classe ouvrière ; son père, un vétéran britannique de la Première Guerre mondiale, travaillait comme concierge, et aucun de ses parents n'avait terminé ses études secondaires. Il était également le petit-fils de Jacob Nist, fondateur de la Seattle-Tacoma Box Company. Malgré leur scolarité limitée, ses parents ont encouragé sa curiosité intellectuelle, et il a obtenu une licence en génie électrique à l'Université de Seattle en 1961, suivie d'une maîtrise en 1962 et d'un doctorat en 1964, tous deux en génie électrique, à l'Université de Stanford. Cette formation d'ingénieur, plutôt qu'un bagage en mathématiques pures ou en informatique, a façonné son instinct ultérieur pour des algorithmes qui n'étaient pas seulement théoriquement élégants, mais réellement efficaces à exécuter.

Construire les manuels de la discipline

Hopcroft a commencé sa carrière universitaire à l'Université de Princeton en tant que professeur adjoint avant de rejoindre l'Université Cornell, où il passerait la majeure partie de sa carrière, occupant finalement le titre de professeur IBM d'ingénierie et de mathématiques appliquées et occupant des postes de direction, notamment chef de département et doyen de l'ingénierie. C'est à Cornell qu'il a coécrit, avec Jeffrey Ullman puis Alfred Aho, une série de manuels sur les langages formels, la théorie des automates et la conception d'algorithmes qui sont devenus les textes d'enseignement par défaut pour des générations d'étudiants en informatique dans le monde entier. Ces livres ont fait plus que résumer les connaissances existantes — ils ont codifié l'analyse de la complexité asymptotique et la théorie des langages formels sous la forme encore enseignée dans les cours théoriques d'introduction aujourd'hui, donnant au domaine un vocabulaire partagé avant même que ce vocabulaire n'existe pleinement ailleurs.

Des algorithmes qui tournent encore aujourd'hui

Au-delà des manuels, les propres recherches de Hopcroft ont produit des outils encore activement utilisés. L'algorithme de Hopcroft-Karp, développé avec Richard Karp, trouve des couplages maximaux dans les graphes bipartis plus rapidement que toute méthode précédente, et reste une technique standard dans les problèmes de flux réseau et d'affectation. Il a également développé un algorithme efficace pour minimiser les automates finis déterministes, un outil fondamental dans la conception de compilateurs et la vérification formelle. Son résultat le plus célèbre, cependant, fut un travail conjoint avec Robert Tarjan : le premier algorithme en temps linéaire pour tester si un graphe est planaire — s'il peut être dessiné sur une surface plane sans que les arêtes ne se croisent — publié en 1974. Les deux ont construit l'algorithme autour d'une utilisation systématique de la recherche en profondeur, transformant ce qui avait été un problème lent et ad hoc en un problème résoluble en un temps proportionnel à la taille du graphe lui-même.

Le prix Turing et sa nature partagée

En 1986, Hopcroft et Tarjan ont reçu conjointement le prix ACM A.M. Turing, la plus haute distinction en informatique, « pour des réalisations fondamentales dans la conception et l'analyse d'algorithmes et de structures de données ». La citation nomme les deux hommes ensemble et crédite un ensemble de travaux collaboratifs et parallèles plutôt qu'une percée individuelle unique — l'algorithme de planarité étant le principal des accomplissements visés par la citation, aux côtés des contributions indépendantes de chaque homme au domaine plus large de la conception d'algorithmes.

Une seconde carrière en Chine

Dans les décennies suivant son prix Turing, Hopcroft a redirigé une grande partie de son énergie vers le renforcement de l'enseignement de l'informatique en dehors des États-Unis, en particulier en Chine. Il est devenu codirecteur du Center on Frontiers of Computing Studies à l'Université de Pékin et dirige des centres portant son nom à l'Université Jiao Tong de Shanghai et à l'Université des sciences et technologies de Huazhong, encadrant des étudiants et aidant à construire des programmes de recherche en algorithmes et, plus récemment, en apprentissage profond. La Chine lui a décerné son prix de l'amitié en 2016, une reconnaissance réservée aux experts étrangers ayant apporté des contributions exceptionnelles au développement du pays — un second acte inhabituel pour un lauréat du prix Turing déjà éloigné de plusieurs décennies des travaux qui lui ont valu le prix.

Reconnaissance

Hopcroft a été élu à la National Academy of Engineering en 1989, est devenu membre de l'ACM en 1994 et a reçu la médaille IEEE John von Neumann en 2010 pour ses réalisations exceptionnelles en informatique et en ingénierie, en plus du prix Turing de 1986 et du prix de l'amitié chinois de 2016.

Pourquoi John est qualifié de génie

Le cas du génie de Hopcroft ne repose pas sur une seule preuve éblouissante, mais sur une combinaison plus rare : des contributions de recherche suffisamment substantielles pour remporter le prix le plus prestigieux du domaine, associées à un don inégalé pour distiller les fondements de ce domaine sous une forme enseignable. L'algorithme de planarité et l'algorithme de couplage de Hopcroft-Karp sont le genre de résultats que les informaticiens théoriques qualifient de véritablement intelligents — réduisant des problèmes qui semblaient nécessiter une recherche par force brute à un temps linéaire ou quasi linéaire grâce à une intuition structurelle. Mais le cadre honnête, que la citation du prix Turing elle-même rend explicite, est que son résultat le plus célèbre appartient conjointement à lui et à Robert Tarjan ; la citation d'aucun des deux hommes ne se suffit à elle-même, et le prix a été décerné pour un ensemble partagé de réalisations, et non pour une percée en solo. Ce qui est moins partagé, et moins souvent célébré comme du « génie », est son second talent : trois manuels coécrits séparément si bien construits qu'ils sont devenus la manière par défaut dont toute une discipline s'enseigne ses propres fondements, une forme de contribution intellectuelle plus proche de l'enseignement magistral que de l'invention individuelle.

Héritage

L'héritage de Hopcroft suit deux voies parallèles qui coïncident rarement dans une même carrière — un dossier de recherche primé par le prix Turing en algorithmes, et un second acte de plusieurs décennies consistant à construire une infrastructure d'enseignement de l'informatique en Chine. Peu de personnalités dans l'histoire du domaine ont façonné la manière dont il est enseigné aussi directement, ou aussi longtemps, que l'auteur de ses manuels les plus largement prescrits. Que l'homme qui a aidé à formaliser la théorie de la computation dans les années 1960 et 1970 encadrait, dans les années 2010, des étudiants en apprentissage profond à l'Université de Pékin en dit long sur la durée et l'étendue inhabituelles de sa vie professionnelle : une carrière qui a commencé à l'ère de l'ingénierie électrique à tubes à vide et s'est poursuivie à l'ère des réseaux neuronaux, sans jamais perdre son fil conducteur consistant à enseigner à la prochaine génération la structure sous-jacente du domaine.