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

Роберт Флойд окончил школу в возрасте 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].

• 1978 — Премия Тьюринга «за его несомненное влияние на методологию создания эффективного и надёжного программного обеспечения и за его помощь в становлении таких областей компьютерных наук как теория парсинга, семантика языков программирования, автоматическая верификация программ, автоматический синтез программ, и анализ алгоритмов».
• 1991 — Медаль «Пионер компьютерной техники» за первые компиляторы^[16].
• 1974 — член Американской академии искусств и наук^[17].
• 1994 — член (Fellow) Ассоциации вычислительной техники (ACM).
• Член Американской ассоциации содействия развитию науки (AAAS)^[17].