Роберт В. «Боб» Флойд [1] (8 июня 1936 - 25 сентября 2001) был компьютерным ученым . Его вклад включает разработку алгоритма Флойда-Уоршалла (независимо от Стивена Уоршалла ), который эффективно находит все кратчайшие пути в графе , алгоритм поиска циклов Флойда для обнаружения циклов в последовательности и его работу по синтаксическому анализу . В одной изолированной статье он представил важную концепцию диффузии ошибок для рендеринга изображений, также называемую дизерингом Флойда-Стейнберга (хотя он отличал дизеринг от диффузии). Он был пионером в области проверки программ с использованиемлогические утверждения с бумагой 1967 года « Присваивая значения программам» . Это было вкладом в то, что позже стало логикой Хора . Флойд получил премию Тьюринга в 1978 году.
Роберт Флойд | |
---|---|
Родившийся | |
Умер | 25 сентября 2001 г. Стэнфорд , Калифорния , США | (65 лет)
Гражданство | Соединенные Штаты |
Образование | Чикагский университет ( бакалавр , 1953, 1958) |
Известен | Алгоритм Флойда – Уоршалла Дитеринг Флойда – Стейнберга Алгоритм поиска цикла Флойда Треугольник Флойда АЛГОЛ |
Супруг (а) | Яна М. Мейсон; Кристиан Флойд ( урожденная Ридл) |
Дети | 4 |
Награды | Премия Тьюринга (1978), Премия пионера компьютеров (1991) |
Научная карьера | |
Поля | Информатика |
Учреждения | Иллинойский технологический институт, Университет Карнеги-Меллона, Стэнфордский университет |
Докторанты | 7 |
Жизнь
Родился в Нью - Йорке , Флойд закончил среднюю школу в возрасте 14 лет В Чикагском университете он получил степень бакалавра искусств (BA) в области гуманитарных наук в 1953 году (когда еще только 17) и второй степень бакалавра в области физики в 1958 году. Флойд был соседом Карла Сагана по комнате в колледже . [2]
Флойд стал сотрудником Фонда исследования брони (ныне Исследовательский институт IIT ) в Технологическом институте Иллинойса в 1950-х годах. Став оператором компьютера в начале 1960-х, он начал публиковать множество статей, в том числе о компиляторах (в частности, о синтаксическом анализе ). Он был пионером грамматик приоритета операторов , и ему приписывают начало области семантики языков программирования в Флойд (1967) . К 27 годам он был назначен адъюнкт-профессором Университета Карнеги-Меллона, а шесть лет спустя стал профессором Стэнфордского университета . Он получил эту должность без степени доктора философии (Ph.D.).
Он был членом Рабочей группы 2.1 Международной федерации обработки информации (IFIP) IFIP по алгоритмическим языкам и исчислениям [3], которая определяла , поддерживает и поддерживает языки программирования ALGOL 60 и ALGOL 68 . [4]
В 1974 году он был избран членом Американской академии искусств и наук [5].
Он получил премию Тьюринга в 1978 году «за то, что оказал явное влияние на методологии создания эффективного и надежного программного обеспечения, а также за помощь в создании следующих важных областей информатики: теория синтаксического анализа, семантика языков программирования , автоматические программы. верификация , автоматический синтез программ и анализ алгоритмов ».
Флойд тесно сотрудничал с Дональдом Кнутом , в частности, в качестве главного рецензента основополагающей книги Кнута « Искусство компьютерного программирования» , и он является человеком, наиболее цитируемым в этой работе. Вместе с Ричардом Бейгелем он был соавтором учебника «Язык машин: введение в вычислимость и формальные языки» . [6] Флойд руководил семью докторами наук. выпускники. [7]
Флойд был женат и дважды развелся, сначала с Яной М. Мейсон, а затем с компьютерным ученым Кристиан Флойд , и у него было четверо детей. В последние годы он страдал от болезни Пика , в нейродегенеративных заболеваний , и , таким образом , вышел в отставку в начале 1994 года [ править ]
Его хобби - пешие прогулки, и он был заядлым игроком в нарды :
Однажды мы застряли в аэропорту Чикаго О'Хара на несколько часов в ожидании вылета нашего рейса из-за снежной бури. Когда мы сидели у ворот, Боб в непринужденной манере спросил меня: «Ты умеешь играть в нарды?» Я ответил, что знаю правила, но почему он хочет знать? Боб сказал, так как у нас есть несколько часов ожидания, возможно, нам стоит сыграть несколько игр, конечно, с небольшими ставками. Затем он полез в свой портфель и достал набор для игры в нарды.
Мой папа многому меня научил. Один из них - опасаться любого, кто предлагает сыграть в бильярд на деньги, а затем открывает черный футляр и начинает скручивать клюшку. Я подумал, что этот совет применим ко всем, кто путешествовал со своим набором для игры в нарды. Я сказал Бобу, что ни в коем случае не собираюсь играть на деньги. Он немного надавил, но, наконец, сказал: «Хорошо». Вместо этого он дал мне бесплатный урок искусства и науки игры в нарды.
Я был прав, отказавшись играть с ним на деньги - при любых ставках. Урок прошел весело. Позже я узнал, что он много лет работал над изучением игры. Он очень серьезно относился к игре в нарды, изучал игру и ее математику и был почти профессионалом. Думаю, это было больше, чем хобби. Как и его исследования, Боб серьезно относился к тому, что делал, и совершенно очевидно, что он был бы великолепен в нардах.
- Ричард Дж. Липтон . [8]
Избранные публикации
- Флойд, Роберт В. (1967). «Придание смысла программам» (PDF) . В Schwartz, JT (ред.). Математические аспекты информатики . Материалы симпозиума по прикладной математике. 19 . Американское математическое общество. С. 19–32. ISBN 0821867288.
- Флойд, Роберт В .; Кнут, Дональд Эрвин (1970). Проблема сортировки Бозе-Нельсона . Стэнфорд, Калифорния : факультет компьютерных наук Стэнфордского университета.
- Флойд, Роберт В .; Смит, Алан Дж. (1972). «Линейное время слияния двух лент». Стэнфорд, Калифорния : факультет компьютерных наук Стэнфордского университета. Цитировать журнал требует
|journal=
( помощь ) - Флойд, Р.В. (1979). «Парадигмы программирования» . Коммуникации ACM . 22 (8): 455. DOI : 10,1145 / 359138,359140 .
- Флойд, Роберт В .; Ульман, Джеффри Д. (1980). «Составление регулярных выражений в интегральные схемы». NASA Sti / Recon Технический отчет N . Округ Фэрфакс, Вирджиния : Ft. Belvoir: Центр технической информации Министерства обороны. 81 : 12334. Bibcode : 1980STIN ... 8112334F .
- Флойд, Роберт В .; Бейгель, Ричард (1994). «Язык машин: введение в вычислимость и формальные языки». Нью-Йорк : Издательство компьютерных наук. Цитировать журнал требует
|journal=
( помощь )
Заметки
- ↑ Второе имя Флойда «Уиллоуби» было юридически изменено на «W», но было решено сократить его как «W.» действителен ( Knuth 2003 ) (форма Министерства обороны США DD 48-1, личные документы, Архивный каталог Стэнфордского университета SC 625, вставка 4)
- ^ Стэнфордского университета Архивы, каталог SC 625, коробка 7
- ^ Jeuring, Йохан; Меертенс, Ламберт ; Гуттманн, Вальтер (17 августа 2016 г.). «Профиль Рабочей группы 2.1 ИФИП» . Фосвики . Проверено 6 сентября 2020 года .
- ^ Swierstra, Doaitse; Гиббонс, Джереми ; Меертенс, Ламберт (2 марта 2011 г.). "ScopeEtc: IFIP21: Foswiki" . Фосвики . Проверено 6 сентября 2020 года .
- ^ «Список членов по классам на 1 сентября 1997 г.». Записи Академии (Американская академия искусств и наук) (1996/1997): 56–128. 1996. JSTOR 3786119 .
- ^ Флойд, Роберт В .; Бейгель, Ричард (1994). Язык машин: введение в вычислимость и формальные языки . Нью-Йорк: WH Freeman and Company. ISBN 978-0-7167-8266-7.
- ^ «Дерево учеников Роберта Флойда для выставок компьютерной истории» . Стэнфордская история компьютеров . Стэндфордский Университет.
- ^ Липтон, Ричард Дж. (28 августа 2010 г.). «Нижние границы и прогрессивные алгоритмы» . Wordpress .
дальнейшее чтение
- Кнут, Дональд Э. (декабрь 2003 г.). «Памяти Роберта Флойда» . Новости ACM SIGACT . 34 (4): 3–13. DOI : 10.1145 / 954092.954488 . S2CID 35605565 .
- Кнут, Дональд Э. "Мемориальная резолюция: Роберт В. Флойд (1936-2001)" (PDF) . Мемориалы факультета Стэнфордского университета . Стэнфордское историческое общество. Архивировано из оригинального (PDF) 12 марта 2012 года.
Внешние ссылки
- Некролог в Стэнфордском отчете
- Расследование Хирона
- Роберт Флойд на проекте « Математическая генеалогия»