Селмер М. Джонсон - Selmer M. Johnson
Селмер Мартин Джонсон (21 мая 1916 - 26 июня 1996) был американским математиком, исследователем в RAND Corporation .
биография
Джонсон родился 21 мая 1916 года в городе Буль, штат Миннесота . Он получил степень бакалавра, а затем магистра математики в Университете Миннесоты в 1938 и 1940 годах соответственно. Вторая мировая война прервала математические занятия Джонсона: он поступил на службу в ВВС США , получив звание майора. Во время службы, он также получил степень магистра в области метеорологии из Нью - Йоркского университета в 1942 г. После войны, Джонсон вернулся в аспирантуру по математике в Университете штата Иллинойс в Урбана-Шампань , заканчивая его докторантуру в 1950 году; его диссертацию по теории чисел возглавлял Дэвид Бурджин, ученик Джорджа Дэвида Биркгофа . В том же году он присоединился к корпорации RAND, став частью так называемой «самой замечательной группы математиков, работающих над оптимизацией, из когда-либо собранных».
Исследовать
Вместе с Джорджем Данцигом и Д. Р. Фулкерсоном Джонсон впервые применил методы секущей плоскости для целочисленного линейного программирования при решении задачи коммивояжера . Он также внес важный вклад в теорию планирования производственных процессов , написав раннюю статью по проблеме планирования производственных процессов , которая заложила основу для многих будущих исследований.
Вместе с Л. Р. Фордом-младшим он разработал алгоритм сортировки Форда – Джонсона , который в течение 20 лет был сортировкой для сравнения с минимально известным числом сравнений.
Графы Джонсона и тесно связанная с ними схема Джонсона названы в честь Джонсона, как и алгоритм Штейнхауса – Джонсона – Троттера для генерации всех перестановок n элементов путем перестановки соседних элементов.