Джозеф Бернард Крускал-младший ( / ˈk r ʌ s k əl / ; 29 января 1928 — 19 сентября 2010) — американский математик , статистик , учёный в области информатики и психометрик .
Крускал родился в еврейской семье [2] в Нью-Йорке у успешного оптового торговца мехами Джозефа Б. Крускала-старшего. Его мать, Лилиан Роуз Форхаус Крускал Оппенгеймер , стала известным популяризатором оригами в раннюю эпоху телевидения.
У Краскала было два известных брата: Мартин Дэвид Крускал , один из изобретателей солитонов , и Уильям Крускал , который разработал односторонний дисперсионный анализ Краскала-Уоллиса . Один из племянников Джозефа Краскала — известный компьютерный учёный и профессор Клайд Крускал .
Он был студентом Чикагского университета, получив степень бакалавра наук по математике в 1948 году, и степень магистра наук по математике в следующем 1949 году. [3] После окончания Чикагского университета Крускал поступил в Принстонский университет , где получил докторскую степень в 1954 году, номинально под руководством Альберта В. Такера и Роджера Линдона , [4] но фактически под руководством Пола Эрдёша, с которым у него было два очень коротких разговора. [5] Крускал работал над хорошо-квази-упорядочениями [4] [6] и многомерным шкалированием . [7] Он был членом Американской статистической ассоциации , бывшим президентом Психометрического общества и бывшим президентом Классификационного общества Северной Америки. Он также инициировал и был первым президентом Совета по справедливому жилищному обеспечению Южного Оринджа и Мейплвуда в 1963 году и активно поддерживал гражданские права в нескольких других организациях, таких как CORE . [8]
Он работал в Bell Labs с 1959 по 1993 год . [9]
В статистике наиболее влиятельной работой Крускала является его основополагающий вклад в формулировку многомерного масштабирования . В информатике его наиболее известная работа — алгоритм Крускала для вычисления минимального остовного дерева (MST) взвешенного графа . Алгоритм сначала упорядочивает ребра по весу, а затем проходит по упорядоченному списку, добавляя ребро к частичному MST при условии, что добавление нового ребра не создает цикл. Минимальные остовные деревья применяются для построения и ценообразования сетей связи. В комбинаторике он известен теоремой о дереве Крускала (1960), которая также интересна с точки зрения математической логики, поскольку ее можно доказать только неконструктивно. Крускал также применил свою работу в лингвистике в экспериментальном лексикостатистическом исследовании индоевропейских языков совместно с лингвистами Изидором Дайеном и Полом Блэком. Их база данных до сих пор широко используется.
Он получил степень бакалавра в 1948 году и степень магистра в 1949 году в Чикаго.
