Иосиф Крускал - Joseph Kruskal

Джозеф Крускал
Родился ( 1928-01-29 )29 января 1928 г.
Нью-Йорк , США
Умер 19 сентября 2010 г. (2010-09-19)(82 года)
Альма-матер Чикагский
университет, Принстонский университет
Известен Алгоритм
Крускала Теорема Крускала о дереве Теорема
Крускала – Катона
Научная карьера
Тезис Теория частично упорядоченных множеств  (1954)
Докторанты Роджер Линдон
Пол Эрдёш

Джозеф Бернард Крускала-младший ( / к г ʌ s к əl / ; 29 января 1928 - 19 сентября 2010) был американский математик , статистик , компьютерный ученый и psychometrician .

Личная жизнь

Крускал родился в еврейской семье в Нью-Йорке в семье успешного оптовика мехом Джозефа Б. Крускала-старшего. Его мать, Лилиан Роуз Форхаус Крускал Оппенгеймер , стала известным пропагандистом оригами в раннюю эпоху телевидения.

У Краскала было два известных брата, Мартин Дэвид Крускал , соавтор солитонов , и Уильям Крускал , который разработал односторонний дисперсионный анализ Краскала – Уоллиса . Один из племянников Джозефа Крускала - известный ученый-компьютерщик и профессор Клайд Крускал .

Образование и карьера

Он был студентом Чикагского университета, получив степень бакалавра математических наук в 1948 году и степень магистра математических наук в следующем 1949 году. После обучения в Чикагском университете Краскал поступил в Принстонский университет , где он закончил свою докторскую степень в 1954 году номинально при Альберте У. Таккере и Роджере Линдоне , но де-факто при Поле Эрдеше, с которым у него было два очень коротких разговора. Краскал работал над квазиупорядочением и многомерным масштабированием .

Он был членом Американской статистической ассоциации , бывшим президентом Психометрического общества и бывшим президентом Классификационного общества Северной Америки . Он также инициировал и был первым президентом Совета справедливого жилищного строительства Саут-Орандж и Мейплвуд в 1963 году и активно поддерживал гражданские права в нескольких других организациях, таких как CORE .

Он работал в Bell Labs с 1959 по 1993 год.

Исследовать

В статистике наиболее влиятельная работа Крускала - его основополагающий вклад в формулировку многомерного шкалирования . В информатике его самая известная работа - это алгоритм Крускала для вычисления минимального остовного дерева (MST) взвешенного графа . Алгоритм сначала упорядочивает ребра по весу, а затем переходит к упорядоченному списку, добавляя ребро к частичному MST при условии, что добавление нового ребра не создает цикла. Минимальные остовные деревья находят применение при построении сетей связи и ценообразовании. В комбинаторике он известен теоремой Крускала о дереве (1960), которая также интересна с точки зрения математической логики, поскольку ее можно доказать только неконструктивно. Краскал также применил свои работы в лингвистике в экспериментальном лексикостатистическом исследовании индоевропейских языков вместе с лингвистами Исидором Дьеном и Полом Блэком. Их база данных по-прежнему широко используется.

Концепты имени Иосифа Крускала

использованная литература

внешние ссылки