Роберт Флойд [1] (8 июня 1936 — 25 сентября 2001) был учёным-компьютерщиком . Его вклад включает разработку алгоритма Флойда-Уоршалла (независимо от Стивена Уоршалла ), который эффективно находит все кратчайшие пути в графе , и его работу по синтаксическому анализу ; Ему также приписали алгоритм поиска циклов Флойда для обнаружения циклов в последовательности. В одной отдельной статье он представил важную концепцию диффузии ошибок при рендеринге изображений, также называемую сглаживанием Флойда-Стейнберга (хотя он отличал сглаживание от диффузии). Он был пионером в области верификации программ с использованием логических утверждений , опубликовав в 1967 году статью « Присвоение значений программам» . Это был вклад в то, что позже стало логикой Хоара . Флойд получил премию Тьюринга в 1978 году.
Флойд родился в Нью-Йорке и окончил среднюю школу в 14 лет. В Чикагском университете он получил степень бакалавра гуманитарных наук (BA) в области гуманитарных наук в 1953 году (когда ему было всего 17 лет) и вторую степень бакалавра по физике в 1958 году. Флойд был соседом Карла Сагана по комнате в колледже . [2]
Флойд стал сотрудником Фонда исследований брони (ныне Исследовательский институт ИИТ ) при Технологическом институте Иллинойса в 1950-х годах. Став оператором компьютера в начале 1960-х годов, он начал публиковать множество статей, в том числе по компиляторам (особенно синтаксическому анализу ). Он был пионером в области грамматик с приоритетом операторов , и ему приписывают начало области семантики языков программирования у Флойда (1967). К 27 годам он был назначен доцентом Университета Карнеги-Меллон , а шесть лет спустя стал профессором Стэнфордского университета . Он получил эту должность, не имея степени доктора философии (Ph.D.).
Он был членом рабочей группы 2.1 IFIP Международной федерации обработки информации (IFIP) по алгоритмическим языкам и исчислениям, [3] которая определила , поддерживает и поддерживает языки программирования ALGOL 60 и ALGOL 68 . [4]
В 1974 году он был избран членом Американской академии искусств и наук .
Он получил премию Тьюринга в 1978 году «за явное влияние на методологии создания эффективного и надежного программного обеспечения, а также за помощь в создании следующих важных разделов информатики: теория синтаксического анализа, семантика языков программирования , автоматическое программирование» . верификация , автоматический синтез программ и анализ алгоритмов ». [6]
Флойд тесно сотрудничал с Дональдом Кнутом , в частности, в качестве главного рецензента плодотворной книги Кнута « Искусство компьютерного программирования» , и является человеком, наиболее цитируемым в этой работе. Вместе с Ричардом Бейгелем он был соавтором учебника « Язык машин: введение в вычислимость и формальные языки» . [7] Флойд руководил семью докторами философии. выпускники. [8]
Флойд женился и развелся дважды, сначала с Яной М. Мейсон, а затем с ученым-компьютерщиком Кристианой Флойд , и у него было четверо детей. В последние годы своей жизни он страдал от болезни Пика , нейродегенеративного заболевания , и поэтому вышел на пенсию в начале 1994 года .
В число его хобби входили пешие походы, и он был заядлым игроком в нарды :
Однажды мы застряли в аэропорту Чикаго О'Хара на несколько часов, ожидая вылета нашего рейса из-за снежной бури. Когда мы сидели у наших ворот, Боб небрежно спросил меня: «Ты умеешь играть в нарды?» Я ответил, что знаю правила, но зачем ему это знать? Боб сказал, что, поскольку нам осталось ждать несколько часов, возможно, нам стоит сыграть несколько игр, конечно, по небольшим ставкам. Затем он полез в портфель и достал набор для игры в нарды.
Мой папа научил меня многому. Нужно было опасаться любого, кто предлагает сыграть в бильярд на деньги, а затем открывает черный футляр и начинает собирать клюшку для игры в бильярд. Я полагал, что этот совет распространяется на всех, кто путешествовал со своим собственным набором для игры в нарды. Я сказал Бобу, что ни в коем случае не буду играть на деньги. Он немного надавил, но в конце концов сказал: «Хорошо». Вместо этого он дал мне бесплатный урок искусства и науки игры в нарды.
Я был прав, отказавшись играть с ним на деньги – при любых ставках. Урок был веселым. Позже я узнал, что он много лет работал над изучением игры. Он очень серьезно относился к игре в нарды, изучал игру и ее математику и был почти профессионалом. Я думаю, это было больше, чем хобби. Как и его исследование, Боб серьезно относился к тому, что делал, и совершенно очевидно, что он будет потрясающим игроком в нарды.
- Ричард Дж. Липтон . [9]