Joseph Kruskal

Joseph Kruskal

Fonction

Président Psychometric Society (en)
1974-1975
Roger Shepard J. Douglas Carroll (d)

Biographie

Naissance	29 janvier 1928 New York
Décès	19 septembre 2010 (à 82 ans) Maplewood
Sépulture	B'nai Abraham Memorial Park (d)
Nationalité	américaine
Formation	Université de Chicago (1946-1949) Université de Princeton (docteur) (1950-1954)
Activités	Mathématicien, informaticien, statisticien, professeur d'université
Mère	Lillian Oppenheimer (en)
Fratrie	William Kruskal Martin Kruskal
Parentèle	Clyde Kruskal (en) (neveu)

Autres informations

A travaillé pour	Laboratoires Bell (1959-1993) Université du Wisconsin à Madison (1956-1959) Office of Naval Research (1950-1956)
Membre de	Congress of Racial Equality
Directeurs de thèse	Paul Erdős, Roger Lyndon
Distinction	Fellow de la Société américaine de statistique (1971)
Archives conservées par	Dolph Briscoe Center for American History (en)

Œuvres principales

Algorithme de Kruskal, théorème de Kruskal, théorème de Kruskal-Katona, Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture (d), On the shortest spanning subtree of a graph and the traveling salesman problem (d)

Joseph Kruskal (né le 29 janvier 1928 à New York et mort le 19 septembre 2010 à Princeton) est un mathématicien, statisticien, chercheur en informatique et psychométricien américain.

Biographie

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, 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.

Travaux

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.

Notes et références

• (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).

Articles connexes

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