Войти
| Рональд Грэм | |
|---|---|
 Грэм в 1998 году | |
| Родился | Рональд Льюис Грэм. (1935-10-31) 31 октября 1935. Тафт, Калифорния, США |
| Умер | 6 июля 2020 (2020-07-06) (84 года). Сан-Диего, Калифорния, США |
| Alma mater | |
| Известен по | |
| Супруг (-и) | Фан Чанг |
| Награды |
|
| Научная карьера | |
| Области | |
| Учреждения | |
| Диссертация | О конечных суммах рациональных чисел (1962) |
| Докторант | Деррик Генри Лемер |
Рональд Льюис Грэм (31 октября 1935 - июль 6, 2020) был американским математиком, признанным Американским математическим обществом как «один из главных архитекторов быстрого развития во всем мире дискретной математики в последние годы
Он проделал важную работу в области теории расписания, вычислительной геометрии, теории Рамсея и квазислучайности. Он много лет работал в Bell Labs, а затем в Калифорнийском университете, Сан-Диего, и был президентом Американского математического общества и Математическая ассоциация Америки.
Рональд Грэм жонглирует четырьмя шарами фонтаном (1986) Грэм был показан в Рипли «Хотите верьте, хотите нет!» за то, что он не только » один из выдающихся математиков мира », но также опытный батутник и жонглер, а в 1972 году был избран президентом Международной ассоциации жонглеров.
Грэм родился в Тафте, Калифорния, 31 октября 1935 г., сын нефтяника, а позже морского торгового флота. Несмотря на его более поздний интерес к гимнастике, он был маленьким и не спортивным. Он рос, часто переезжая из Калифорнии в Джорджию, пропуская из-за этого несколько классов школы и никогда не оставаясь в одной школе дольше года. Подростком он переехал во Флориду со своей теперь разведенной матерью, где он учился, но не окончил среднюю школу. Вместо этого в возрасте 15 лет он выиграл стипендию Фонда Форда для поступления в Чикагский университет, где изучал гимнастику, но не математику.
Через три года, когда истек срок его стипендии, он перешел в Калифорнийский университет в Беркли, официально изучая электротехнику, но также изучая теорию чисел под руководством Деррика Генри. Лемера и завоевал титул чемпиона штата Калифорния по прыжкам на батуте. Он поступил на службу в ВВС США в 1955 году, когда он достиг возраста допуска, покинул Беркли без ученой степени и был размещен в Фэрбенксе, Аляска, где, наконец, закончил степень бакалавра физики в 1959 г. в Университете Аляски в Фэрбенксе. Вернувшись в Калифорнийский университет в Беркли для обучения в аспирантуре, он получил степень доктора философии по математике в 1962 году. Его диссертация, под руководством Лемера, была «О конечных суммах рациональных чисел». Будучи аспирантом, он поддерживал себя, выступая на батуте в цирке, и женился на Нэнси Янг, студентке математического факультета Беркли; у них было двое детей.
Рональд Грэм, его жена Фан Чанг, и Пол Эрдеш, Япония 1986 После получения докторской степени Грэм начал работать в 1962 году в Bell Labs и (как позже стало) ATT Labs в Нью-Джерси в качестве директора по информационным наукам. В 1963 году на конференции в Колорадо он встретил плодовитого венгерского математика Пола Эрдеша (1913–1996), который стал его близким другом и частым сотрудником в исследованиях. Грэм был огорчен тем, что его избил в настольный теннис Эрдёш, тогда уже достигший средних лет; он вернулся в Нью-Джерси, решив улучшить свою игру, и в конце концов стал чемпионом Bell Labs и выиграл титул штата в этой игре. Позже Грэм популяризировал концепцию числа Эрдеша, меры расстояния от Эрдеша в сети сотрудничества математиков; его многочисленные работы с Эрдёшем включают две книги открытых проблем и последнюю посмертную статью Эрдёша. Грэм развелся в 1970-х годах; в 1983 году он женился на своем коллеге по Bell Labs и частом соавторе Фан Чанг.
В то время как в Bell Labs Грэм также занял должность профессора математических наук в Университете Рутгерса в 1986 году и работал президентом Американского математического общества с 1993 по 1994 год. Он стал главным научным сотрудником лаборатории в 1995 году. После 37 лет работы в компании ATT он ушел на пенсию в 1999 году и перешел в университет . Калифорнии, Сан-Диего (UCSD), как дипломированный профессор компьютерных и информационных наук Ирвина и Джоан Джейкобс. В UCSD он также стал главным научным сотрудником Калифорнийского института телекоммуникаций и информационных технологий. В 2003−04 годах он был президентом математической ассоциации Америки.
Грэм умер от бронхоэктаза 6 июля 2020 года в возрасте 84 лет в Ла-Холья, Калифорния..
Грэм внес важный вклад во многие области математики и теоретической информатики. Он опубликовал более 350 статей и шесть книг, в том числе Конкретная математика с Дональдом Кнутом и Ореном Паташником, а проект числа Эрдёша отмечает, что у него почти 200 соавторов.
Известные темы в математике, названные в честь Грэма, включают задачу Эрдеша – Грэма о египетских дробях, теорему Грэма – Ротшильда в Теория Рэмси из слов с параметрами и число Грэма, производное от нее, теорема Грэма – Поллака и гипотеза Грэма в теория графов, алгоритм Коффмана – Грэма для приблизительного планирования и рисования графиков и алгоритм сканирования Грэма для выпуклой оболочки. Он также начал изучение последовательностей без простых чисел, булевой задачи Пифагора о троек, самого большого многоугольника и упаковки квадрата в квадрат.
Помимо публикации под своим именем, Грэм участвовал в публикациях Г. В. Пек, псевдонимное математическое сотрудничество, названное по инициалам его членов, с Грэмом как "G".
Докторская диссертация Грэма была в номере теория, о египетских дробях, и проблема Эрдеша – Грэма тесно связаны. Он попросил доказательства того, что, когда целые числа делятся на конечное число классов, один из классов имеет подмножество, сумма обратных чисел которого равна единице. Доказательство было опубликовано Эрни Крут в 2003 году. Еще одна статья Грэма о египетских дробях была опубликована в 2015 году с участием Стива Батлера и (почти 20 лет посмертно) Пола Эрдеша; это была последняя из опубликованных работ Эрдеша, в результате чего Батлер стал его 512-м соавтором.
В статье 1964 года Грэм начал изучение свободных от простых чисел последовательностей, заметив, что существуют последовательности чисел, определяется тем же рекуррентным отношением , что и числа Фибоначчи, в которых ни один из элементов последовательности не является простым. Позже Дональд Кнут и другие взяли на себя задачу создания большего количества таких последовательностей. Книга Грэма 1980 г. с Полом Эрдёшем «Старые и новые результаты в комбинаторной теории чисел» представляет собой сборник открытых проблем из широкого диапазона подобластей теории чисел.
Теорема Грэма – Ротшильда в Теория Рэмси была опубликована Грэмом и Брюсом Ротшильдом в 1971 году и применяет теорию Рэмси к комбинаторные кубы в комбинаторике слов. Грэм дал большое число в качестве верхней границы для примера этой теоремы, теперь известного как число Грэма, которое было занесено в Книгу рекордов Гиннеса как самое большое число, когда-либо использовавшееся в математическом доказательстве, хотя с тех пор его превзошли еще большие числа, такие как ДЕРЕВО (3).
Грэм предложил денежный приз за решение булевой задачи Пифагора о троек, еще одна проблема в теории Рамсея; приз был востребован в 2016 году. Грэм также опубликовал две книги по теории Рамсея.
Разбиение ребер полного графа 
на пять полных двудольных подграфов в соответствии с теоремой Грэма – Поллака теоремой Грэма – Поллака, которую Грэм опубликовал с Генри О.. Поллак в двух статьях в 1971 и 1972 годах утверждает, что если ребра 
Вскоре. после того, как исследования в квазислучайных графах начались с работ Эндрю Томасона, Грэма и его соавторов Фан Чанг и Р. М. Уилсон опубликовал в 1989 году результат, который был назван «фундаментальной теоремой о квазислучайных графах», заявив, что многие различные определения этих графов эквивалентны.
Гипотеза Грэма, появляющаяся в В статье 1989 года Фань Чжун рассматривается галечное число в декартовых произведениях графиков. По состоянию на 2019 год этот вопрос остается нерешенным.
Ранняя работа Грэхема над планированием цеха представила наихудший случай аппроксимации отношения в изучение алгоритмов аппроксимации и заложил основы для более позднего развития конкурентного анализа онлайн-алгоритмов . Позднее было признано, что эта работа важна также для теории упаковки контейнеров, области, в которой Грэм позже работал более подробно.
Алгоритм Коффмана – Грэма, который Грэм опубликовал с Эдвардом Г. Коффманом-младшим в 1972 году, предоставляет оптимальный алгоритм для двухмашинного планирования и гарантированный алгоритм аппроксимации для большего количества машин. Он также был применен в рисовании многоуровневого графа.
В обзорной статье о статьях планирования, опубликованных в 1979 году, Грэм и его соавторы представили трехсимвольную нотацию для классификации теоретических задач планирования в соответствии с система машин, на которых они должны работать, характеристики задач и ресурсов, такие как требования к синхронизации или непрерывности, и показатель производительности, который необходимо оптимизировать. Эту классификацию иногда называют «нотацией Грэма» или «нотацией Грэма».
Алгоритм сканирования Грэма для выпуклой оболочки сканирование Грэма - это широко используемый и практичный алгоритм для выпуклой оболочки двумерных наборов точек, основанный на сортировке точек с последующей вставкой их в корпус в отсортированном порядке. Грэм опубликовал алгоритм в 1972 году.
Задача самый большой маленький многоугольник требует многоугольника наибольшей площади для данного диаметра. Удивительно, но, как заметил Грэм, ответ не всегда правильный многоугольник. Гипотеза Грэма 1975 года о форме этих многоугольников была окончательно доказана в 2007 году.
В другой публикации 1975 года Грэм и Эрдеш отметили, что для упаковки единичных квадратов в больший квадрат с нецелой стороной длины, можно использовать наклонные квадраты, чтобы оставить непокрытую область, которая является сублинейной по длине стороны большего квадрата, в отличие от очевидной упаковки с выровненными по оси квадратами. Клаус Рот и Боб Воан доказано, что иногда может потребоваться непокрытая площадь, по крайней мере, пропорциональная квадратному корню из длины стороны; остается открытой проблемой.
В непараметрической статистике, статье 1977 года Перси Диаконис и Грэм изучили статистические свойства меры ранговой корреляции, которая сравнивает две перестановки путем суммирования по каждому элементу расстояния между позициями элемента в двух перестановках. Они сравнили эту меру с другими методами ранговой корреляции, в результате чего получили «неравенства Диакониса – Грэма»
где 
Это случайное блуждание целых чисел по модулю нечетного целого 
В 2003 году Грэм выиграл ежегодную премию Лероя П. Стила за заслуги перед Американским математическим обществом. Премия отмечена его вкладом в дискретную математику, популяризацией математики посредством его выступлений и письменных работ, его лидерством в Bell Labs и его служением в качестве президента общества. Он был одним из пяти инаугурационных лауреатов Премии Джорджа Полиа Общества Промышленной и Прикладной математики, поделившись ею с другими теоретиками Рамси Клаусом Леебом, Брюс Ротшильд, Альфред Хейлз и Роберт И. Джуэтт. Он также был одним из двух инаугурационных лауреатов медали Эйлера Института комбинаторики и ее приложений, другой - Клод Берж.
Грэм был избран в 213>Национальная академия наук в 1985 году. В 1999 году он был введен в должность научного сотрудника ACM "за выдающийся вклад в анализ алгоритмов, в частности в анализ эвристики наихудшего случая, теорию планирование и вычислительная геометрия ». Он стал членом Общества промышленной и прикладной математики в 2009 году; Стипендиат назвал его «вклад в дискретную математику и ее приложения». В 2012 году он стал членом Американского математического общества..
Грэм был приглашенным спикером на Международном конгрессе математиков 1982 года (состоявшемся в 1983 году в Варшаве), выступая на тему «Последние разработки в теории Рамсея. ". Он был дважды лектором Джозайи Уилларда Гиббса, в 2001 и 2015 годах. Математическая ассоциация Америки наградила его премией Карла Аллендёрфера за его статью «Деревья Штайнера на шахматная доска »с Фань Чангом и Мартином Гарднером в Mathematics Magazine (1989), и Премия Лестера Р. Форда за его статью« Вихревой тур по вычислительной технике. геометрия »с Фрэнсис Яо в American Mathematical Monthly (1990). Его книга «Магическая математика» с Перси Диаконис выиграла Книжную премию Эйлера.
Труды конференции Integer 2005 были опубликованы как фестивальный сборник к 70-летию Рона Грэма. Еще один праздничный сборник, основанный на конференции, проведенной в 2015 году в честь 80-летия Грэма, был опубликован в 2018 году как книга «Связи в дискретной математике: чествование работы Рона Грэма».
| B1. | Старые и новые результаты комбинаторной теории чисел. С Полом Эрдёшем. Монография 28, L'Enseignement Mathématique, 1980. |
| B2. | Теория Рамси. С Брюсом Ротшильдом и Джоэлом Спенсером. Wiley, 1980; 2-е изд., 1990. |
| B3. | Зачатки теории Рамсея. Американское математическое общество, 1981; 2-е изд., С Стивом Батлером, 2015. |
| B4. | Конкретная математика: основа информатики. С Дональдом Кнутом и Ореном Паташником. Аддисон-Уэсли, 1989; 2-е изд., 1994. |
| B5. | Erds on Graphs. Его наследие нерешенных проблем. С Фань Чанг. А. К. Петерс, 1998. |
| B6. | Магическая математика: математические идеи, воплощающие в жизнь великие фокусы. С Перси Диаконис. Princeton University Press, 2011. |
| V1. | Справочник по комбинаторике. Отредактировано с помощью Мартина Грёчеля и Ласло Ловаса. MIT Press, 1995. |
| V2. | Математика Пола Эрдёша. Отредактировано с помощью Ярослава Нешетржила. 2 тома. Springer, 1997; 2-е изд., 2013. |
| A64. | Грэм, Рональд Л. (1964). «Последовательность составных чисел, подобная Фибоначчи» (PDF). Математический журнал. 37(5): 322–324. doi : 10.2307 / 2689243. JSTOR 2689243. MR 1571455. |
| A66. | Грэм, Р. Л. (1966). "Границы некоторых аномалий многопроцессорной обработки" (PDF). Технический журнал Bell System. 45(9): 1563–1581. doi : 10.1002 / j.1538-7305.1966.tb01709.x. |
| A69. | Грэм, Р. Л. (1969). «Границы временных аномалий многопроцессорной обработки» (PDF). Журнал СИАМ по прикладной математике. 17: 416–429. doi : 10.1137 / 0117039. MR 0249214. |
| A71a. | Graham, R. L.; Ротшильд, Б. Л. (1971). "Теорема Рамсея для наборов n параметров" (PDF). Труды Американского математического общества. 159 : 257–292. DOI : 10.1090 / S0002-9947-1971-0284352-8. JSTOR 1996010. MR 0284352. |
| A71b. | Graham, R.L.; Поллак, Х.О. (1971). «О проблеме адресации для коммутации шлейфов» (PDF). Технический журнал Bell System. 50: 2495–2519. doi : 10.1002 / j.1538-7305.1971.tb02618.x. MR 0289210. |
| A72a. | Graham, R.L.; Поллак, Х. О. (1972). «О вложении графов в сжатые кубы». Теория графов и приложения (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; посвящено памяти Дж. У. Т. Янгса) (PDF). Конспект лекций по математике. 303 . С. 99–110. MR 0332576. |
| A72b. | Коффман, Э. Дж. Младший ; Грэм, Р. Л. (1972). «Оптимальное планирование для двухпроцессорных систем» (PDF). Acta Informatica. 1: 200–213. doi : 10.1007 / bf00288685. MR 0334913. |
| A72c. | Грэм, Р. Л. (1972). «Эффективный алгоритм определения выпуклой оболочки конечного плоского множества» (PDF). Письма об обработке информации. 1(4): 132–133. DOI : 10.1016 / 0020-0190 (72) 90045-2. |
| A74. | Джонсон, Д.С. ; Демерс, А.; Уллман, Дж. Д. ; Гарей, М. Р. ; Грэм, Р. Л. (1974). «Границы производительности в наихудшем случае для простых алгоритмов одномерной упаковки» (PDF). Журнал SIAM по вычислительной технике. 3: 299–325. doi : 10.1137 / 0203025. MR 0434396. |
| A75a. | Graham, R.L. (1975). «Самый большой малый шестиугольник» (PDF). Журнал комбинаторной теории. Серия A. 18 : 165–170. doi : 10.1016 / 0097-3165 (75) 90004-7. MR 0360353. |
| A75b. | Erdős, P. ; Грэм, Р. Л. (1975). «Об упаковке квадратов с равными квадратами» (PDF). Журнал комбинаторной теории. Серия А. 19 : 119–123. doi : 10.1016 / 0097-3165 (75) 90099-0. MR 0370368. |
| A77. | Диаконис, Перси ; Грэм, Р. Л. (1977). «Правило копейщика как мера беспорядка». Журнал Королевского статистического общества. 39(2): 262–268. doi : 10.1111 / j.2517-6161.1977.tb01624.x. JSTOR 2984804. MR 0652736. |
| A79. | Graham, R.L.; Лоулер, Э. Л. ; Ленстра, Дж. К. ; Ринну Кан, А.Х.Г. (1979). «Оптимизация и приближение в детерминированной последовательности и планировании: обзор» (PDF). Анналы дискретной математики. 5 : 287–326. MR 0558574. |
| A84. | Graham, R.L. (1984). «Последние достижения в теории Рамсея» (PDF). Труды Международного конгресса математиков, Vol. 1, 2 (Варшава, 1983). Варшава: PWN. С. 1555–1567. MR 0804796. |
| A87. | Chung, F.R.K. ; Диаконис, Перси ; Грэм, Р. Л. (1987). «Случайные блуждания, возникающие при генерации случайных чисел» (PDF). Анналы вероятности. 15(3): 1148–1165. JSTOR 2244046. MR 0893921. |
| A89a. | Чанг, Ф. Р. К. ; Graham, R.L.; Уилсон, Р.М. (1989). «Квазислучайные графы» (PDF). Combinatorica. 9(4): 345–362. doi : 10.1007 / BF02125347. MR 1054011. |
| A89b. | Чанг, Фан ; Гарднер, Мартин ; Грэм, Рон (1989). «Деревья Штейнера на шахматной доске» (PDF). Математический журнал. 62(2): 83–96. DOI : 10.2307 / 2690388. JSTOR 2690388. MR 0991536. |
| A90. | Грэм, Рон; Яо, Фрэнсис (1990). «Вихревой тур по вычислительной геометрии» (PDF). Американский математический ежемесячник. 97(8): 687–701. DOI : 10.2307 / 2324575. JSTOR 2324575. MR 1072812. |
| A15. | Батлер, Стив ; Эрдеш, Пол ; Грэм, Рон (2015). «Египетские дроби, каждый знаменатель которых имеет три различных простых делителя» (PDF). Целые числа. 15 : A51. MR 3437526. |
