АссистентНовый вопросИсторияОбласти знаний
Партнёрские проектыМатериалы БРЭСпецпроектыСтать автором
Настроить видСменить языкИнформация
О РУВИКИ
Ответ на вопрос

Флойд, Роберт

Pause

Роберт В[a] Флойд (англ. Robert W Floyd; 8 июня 1936, Нью-Йорк, Нью-Йорк, США — 25 сентября 2001, Стэнфорд, Санта-Клара, Калифорния, США) — американский учёный в области теории вычислительных систем. Лауреат премии Тьюринга.

Общие сведения
Что важно знать
Роберт В Флойд
англ. Robert W Floyd
Дата рождения 8 июня 1936(1936-06-08)[1]
Место рождения
Дата смерти 25 сентября 2001(2001-09-25)[1] (65 лет)
Место смерти
Страна
Научная сфера Информатика
Место работы Университет Карнеги — Меллон
Стэнфордский университет
Образование
Известен как Алгоритм Флойда — Уоршелла
Награды и премии

Биография

Роберт Флойд окончил школу в возрасте 14 лет, перепрыгнув три класса. Три года спустя, в 1953 году, он получил степень бакалавра свободных наук в Чикагском университете. С 1956 по 1962 год работал в Armour Research Foundation, параллельно получив в 1958 году степень бакалавра по физике.

С 1962 по 1965 год работал в компании Computer Associates.

В 1965—1968 годах Флойд был адъюнкт-профессором в Университете Карнеги — Меллон. Затем его академическая карьера продолжилась в Стэнфордском университете: ассоциированный профессор (1968—1970), профессор (1970—1994) и заведующий кафедрой компьютерных наук (1973—1976). Примечательно, что в отличие от большинства коллег, Флойд не имел степени PhD (доктора философии).

В Стэнфорде Флойд тесно работал с Дональдом Кнутом, в том числе в качестве главного редактора серии его книг «Искусство программирования», ставших фундаментальным источником информации о разработке алгоритмов. Сам Кнут называл Флойда «первым назначенным рецензентом» и «главным рецензентом допечатной подготовки» этой фундаментальной серии книг. Вместе они поддержали студенческую акцию протеста 1 мая 1970 года, направленную против решения Никсона о введении американских войск в Камбоджу. Целью акции было препятствие работы сотрудников университета, однако Кнут и Флойд провели весь день, дискутируя об алгоритмах сортировки. Флойд активно принимал участие в работе по освобождению чилийского учёного Фернандо Флореса из тюрьмы[2].

Роберт Флойд ушёл на пенсию в 1994 году. Умер в 2001 году в клинике Стэнфордского университета в возрасте 65 лет после долгой болезни от редкого нейродегенеративного заболевания — болезни Пика.

Личная жизнь

Дважды женат, дважды разведён, имел четверых детей (дочь Сьюзан Барнет и сыновья Майкл Флойд, Шон Флойд и Эрик Шорр)[3]. Второй женой Флойда была австрийская учёная в области компьютерных наук Кристиане Флойд, которая была замужем за Питером Науром.

Помимо научной деятельности, Флойд увлекался игрой в нарды.

Научная деятельность

Алгоритмы

К знаменитым достижениям Флойда относятся эффективный алгоритм поиска кратчайшего пути в ориентированных графах (Алгоритм Флойда — Уоршелла, опубликованный им в современном виде в 1962 году) и алгоритм дизеринга. Кроме того, Флойд работал над проблемой формальной верификации программ, сделав тем самым большой вклад в логику Хоара, которую иногда называют логикой Флойда — Хоара.

Ему также принадлежит алгоритм поиска циклов, известный как «алгоритм черепахи и зайца» (изобретение этого метода Дональд Кнут приписывает Флойду). Алгоритм использует два указателя, которые перемещаются по последовательности с разной скоростью: медленный («черепаха») делает один шаг за итерацию, а быстрый («заяц») — два. Если в последовательности есть цикл, быстрый указатель в конечном итоге догонит медленный. Этот подход позволяет эффективно определять наличие цикла и находить точку его начала с пространственной сложностью O(1)[4][5].

Верификация программ и семантика

Роберт Флойд внёс фундаментальный вклад в развитие формальной верификации программ и создание логики Хоара (также известной как логика Флойда — Хоара). В своей ключевой статье 1967 года «Присвоение значений программам» (англ. Assigning Meanings to Programs) он предложил систематический метод доказательства корректности программ с помощью логических утверждений[6]. Важной частью этого подхода стал метод инвариантов для доказательства корректности циклов, что заложило основы аксиоматической семантики.

Теория парсинга

Роберт Флойд был пионером в области синтаксического анализа (парсинга)[6]. Его работы систематизировали существовавшие подходы и легли в основу создания современных эффективных компиляторов. Флойд разработал грамматики с операторным предшествованием — метод синтаксического анализа, основанный на отношениях предшествования между операторами языка[7]. Этот подход оказался эффективным для анализа многих конструкций языков программирования, а соответствующие грамматики иногда называют «грамматиками Флойда»[8]. Кроме того, в 1961 году в статье «A descriptive language for symbol manipulation» он представил концепцию «продукций Флойда» — нотацию для описания процесса трансляции программ, позволившую формально описывать компиляторы и автоматизировать создание парсеров[9].

Библиография

  • Floyd R. W. Algorithm 97: Shortest path // Communications of the ACM. — 1962[10].
  • Floyd R. W. Syntactic Analysis and Operator Precedence // Journal of the ACM. — 1963[11].
  • Floyd R. W. Assigning Meanings to Programs // Mathematical Aspects of Computer Science, Proceedings of Symposia in Applied Mathematics. — American Mathematical Society, 1967. — Vol. 19. — P. 19—32. — ISBN 0821867288[12].
  • Floyd R. W. Nondeterministic Algorithms // Journal of the Association for Computing Machinery. — 1967[13].
  • Floyd R. W. The Paradigms of Programming // Communications of the ACM. — 1979. (Текст лекции при вручении премии Тьюринга)[14].
  • Floyd R. W., Beigel R. The Language of Machines: an introduction to computability and formal languages. — 1994. (Учебник по теории вычислимости и формальным языкам)[15].

Награды и премии

Примечания

Комментарии

  1. ↑ Флойд сменил своё второе имя, которое начиналось на букву W, на саму букву, поэтому после него не ставится точка. Сам Флойд шутил по этому поводу, что «W.» — это приемлемая аббревиатура от «W».

Источники

  1. ↑ 1 2 Robert W. Floyd // SNAC (англ.) — 2010.
  2. ↑ Modern problems of informatic. www.nsc.ru. Дата обращения: 10 апреля 2026.
  3. ↑ Robert W. Floyd, 65; Computer Science Pioneer. Los Angeles Times (9 ноября 2001). Дата обращения: 1 апреля 2026.
  4. ↑ Floyd's Linked List Cycle Finding Algorithm (Tortoise And Hare algorithm). CP-Algorithms. Дата обращения: 1 апреля 2026.
  5. ↑ Floyd’s Cycle Finding Algorithm. GeeksforGeeks. Дата обращения: 1 апреля 2026.
  6. ↑ 1 2 Robert W. Floyd. IEEE Computer Society. Дата обращения: 1 апреля 2026.
  7. ↑ Operator Precedence Parsing. Politecnico di Milano. Дата обращения: 1 апреля 2026.
  8. ↑ Floyd Grammars. Università degli Studi di Milano. Дата обращения: 1 апреля 2026.
  9. ↑ Robert W. Floyd: A Pioneer in Computer Science. Indian Academy of Sciences. Дата обращения: 1 апреля 2026.
  10. ↑ Algorithm 97: Shortest path. dblp computer science bibliography. Дата обращения: 1 апреля 2026.
  11. ↑ Operator Precedence Parsing. Università degli Studi di Milano. Дата обращения: 1 апреля 2026.
  12. ↑ Assigning Meanings to Programs. New Mexico State University. Дата обращения: 1 апреля 2026.
  13. ↑ Nondeterministic Algorithms. dblp computer science bibliography. Дата обращения: 1 апреля 2026.
  14. ↑ The Paradigms of Programming. arXiv. Дата обращения: 1 апреля 2026.
  15. ↑ The Language of Machines. University of York. Дата обращения: 1 апреля 2026.
  16. ↑ Computer Pioneer List.
  17. ↑ 1 2 Professor Robert W. Floyd. Stanford Computer Science. Дата обращения: 1 апреля 2026.

Ссылки

Дополнительно по теме

Категории

Pause