Joseph Kruskal
Joseph Kruskal (né le  à New York et mort le  à 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 couvrants 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  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

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

Naissance en janvier 1928
Naissance à New York
Décès en septembre 2010
Décès à Princeton (New Jersey)
Personnalité américaine de l'informatique
Personnalité en théorie des graphes
Scientifique des laboratoires Bell
Personnalité liée au New Jersey
Étudiant de l'université de Chicago
Étudiant de l'université de Princeton
Membre de la Société américaine de statistique
Décès à 82 ans