Joseph Kruskal
Pour les articles homonymes, voir Kruskal.
Cet article est une ébauche concernant un mathématicien.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
| Président Psychometric Society (en) | |
|---|---|
| - | |
J. Douglas Carroll (d) |
| Naissance | |
|---|---|
| Décès | |
| Sépulture |
B'nai Abraham Memorial Park (d) |
| Nationalité | |
| Formation | |
| Activités | |
| Mère |
Lillian Oppenheimer (en) |
| Fratrie | |
| Parentèle |
Clyde Kruskal (en) (neveu) |
| A travaillé pour | |
|---|---|
| Membre de | |
| Directeurs de thèse | |
| Distinction | |
| Archives conservées par |
Dolph Briscoe Center for American History (en) |
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 à New York et mort le à Princeton) est un mathématicien, statisticien, chercheur en informatique et psychométricien américain.
Biographie
[modifier | modifier le code]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.
Travaux
[modifier | modifier le code]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 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
[modifier | modifier le code]- (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).
- (en) « Joseph Kruskal », sur le site du Mathematics Genealogy Project
Articles connexes
[modifier | modifier le code]- Algorithme de Kruskal (1956)
- Théorème de Kruskal sur les arbres (1960)
- Théorème de Kruskal-Katona (1963)
