Joseph Kruskal

Né dans une famille juive, Joseph Kruskal fit ses études à l’université de Chicago et à l’université de Princeton, où il soutint sa thèse de doctorat en 1954[1], officiellement sous la direction d’Albert W. Tucker et Roger Lyndon, mais en fait sous celle de Paul Erdős. Ses recherches concernent la notion de bel ordre et les algorithmes de positionnement multidimensionnel.

Il a été membre titulaire de l'American Statistical Association, président de la Psychometric Society et de la Classification Society of North America. Il est le fondateur et premier président du Conseil pour la qualité de l'habitat des districts de South Orange et de Maplewood en 1963, et a milité pour les droits civiques dans de nombreuses associations.

Dans le domaine des statistiques, la principale contribution de Kruskal aura été la formulation du concept de positionnement multidimensionnel. En informatique, sa découverte la plus connue est l’algorithme de Kruskal pour la détermination de l’arbre couvrant de poids minimal (ARM) dans les graphes pondérés : cet algorithme consiste à trier d’abord les arêtes du graphe par poids décroissant, puis à balayer les arêtes ainsi triées et à les empiler chaque fois que leur insertion ne crée pas de sous-circuit. Les arbres recouvrants minimaux interviennent dans la conception et le tarifage des réseaux de communication/distribution les plus généraux.

Dans le domaine de l'analyse combinatoire, on lui doit le théorème de Kruskal (1960) qui, par delà son énoncé, intéresse aussi la logique mathématique car il n'est démontrable que par un raisonnement non constructif. Kruskal, en collaboration avec les linguistes Isidore Dyen (en) et Paul Black, a appliqué ses travaux à la linguistique, avec une analyse fréquentielle des mots dans les langues indo-européennes. La base de données qu'ils ont réussi à constituer est toujours beaucoup utilisée.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Joseph Kruskal » (voir la liste des auteurs).

• Algorithme de Kruskal (1956)
• Théorème de Kruskal sur les arbres (1960)
• Théorème de Kruskal-Katona (1963)

• Portail de l'informatique théorique
• Portail des probabilités et de la statistique