Robert W. Floyd (born Robert Willoughby Floyd; June 8, 1936 – September 25, 2001) was an American
computer scientist
A computer scientist is a scientist who specializes in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...
. His contributions include the design of the
Floyd–Warshall algorithm
In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with po ...
(independently of
Stephen Warshall), which efficiently finds all shortest paths in a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
and his work on
parsing
Parsing, syntax analysis, or syntactic analysis is a process of analyzing a String (computer science), string of Symbol (formal), symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal gramm ...
;
Floyd's cycle-finding algorithm for detecting
cycles
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
* Cyclic history, a theory of history
* Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr.
* Social cycle, various cycles in ...
in a sequence was attributed to him as well. In one isolated paper he introduced the important concept of error diffusion for rendering images, also called
Floyd–Steinberg dithering (though he distinguished dithering from diffusion). He pioneered in the field of
program verification
In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of a system with respect to a certain formal specification or property, using formal methods of mathematics.
Formal ver ...
using
logical assertion
In mathematical logic, a judgment (or judgement) or assertion is a statement or enunciation in a metalanguage. For example, typical judgments in first-order logic would be ''that a string is a well-formed formula'', or ''that a proposition is tru ...
s with the 1967 paper ''Assigning Meanings to Programs''. This was a contribution to what later became
Hoare logic
Hoare logic (also known as Floyd–Hoare logic or Hoare rules) is a formal system with a set of logical rules for reasoning rigorously about the correctness of computer programs. It was proposed in 1969 by the British computer scientist and l ...
. Floyd received the
Turing Award
The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in the fi ...
in 1978.
Life
Born in
New York City
New York, often called New York City (NYC), is the most populous city in the United States, located at the southern tip of New York State on one of the world's largest natural harbors. The city comprises five boroughs, each coextensive w ...
, Floyd finished high school at age 14. At the
University of Chicago
The University of Chicago (UChicago, Chicago, or UChi) is a Private university, private research university in Chicago, Illinois, United States. Its main campus is in the Hyde Park, Chicago, Hyde Park neighborhood on Chicago's South Side, Chic ...
, he received a
Bachelor of Arts
A Bachelor of Arts (abbreviated B.A., BA, A.B. or AB; from the Latin ', ', or ') is the holder of a bachelor's degree awarded for an undergraduate program in the liberal arts, or, in some cases, other disciplines. A Bachelor of Arts deg ...
(B.A.) in
liberal arts
Liberal arts education () is a traditional academic course in Western higher education. ''Liberal arts'' takes the term ''skill, art'' in the sense of a learned skill rather than specifically the fine arts. ''Liberal arts education'' can refe ...
in 1953 (when still only 17) and a second
bachelor's degree
A bachelor's degree (from Medieval Latin ''baccalaureus'') or baccalaureate (from Modern Latin ''baccalaureatus'') is an undergraduate degree awarded by colleges and universities upon completion of a course of study lasting three to six years ...
in
physics
Physics is the scientific study of matter, its Elementary particle, fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge whi ...
in 1958. Floyd was a college roommate of
Carl Sagan
Carl Edward Sagan (; ; November 9, 1934December 20, 1996) was an American astronomer, planetary scientist and science communicator. His best known scientific contribution is his research on the possibility of extraterrestrial life, including e ...
.
Floyd became a staff member of the Armour Research Foundation (now
IIT Research Institute) at
Illinois Institute of Technology
The Illinois Institute of Technology, commonly referred to as Illinois Tech and IIT, is a Private university, private research university in Chicago, Illinois, United States. Tracing its history to 1890, the present name was adopted upon the m ...
in the 1950s. Becoming a computer operator in the early 1960s, he began publishing many papers, including on
compiler
In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ...
s (particularly
parsing
Parsing, syntax analysis, or syntactic analysis is a process of analyzing a String (computer science), string of Symbol (formal), symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal gramm ...
). He was a pioneer of
operator-precedence grammar An operator precedence grammar is a kind of grammar for formal languages.
Technically, an operator precedence grammar is a context-free grammar that has the property (among others)
that no production has either an empty right-hand side or two adjac ...
s, and is credited with initiating the field of
programming language semantics
In programming language theory, semantics is the rigorous mathematical study of the meaning of programming languages. Semantics assigns computational meaning to valid strings in a programming language syntax. It is closely related to, and ofte ...
in . He was appointed an associate professor at
Carnegie Mellon University
Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania, United States. The institution was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools. In 1912, it became the Carnegie Institu ...
by the time he was 27 and became a full professor at
Stanford University
Leland Stanford Junior University, commonly referred to as Stanford University, is a Private university, private research university in Stanford, California, United States. It was founded in 1885 by railroad magnate Leland Stanford (the eighth ...
six years later. He obtained this position without a
Doctor of Philosophy
A Doctor of Philosophy (PhD, DPhil; or ) is a terminal degree that usually denotes the highest level of academic achievement in a given discipline and is awarded following a course of Postgraduate education, graduate study and original resear ...
(Ph.D.) degree.
He was a member of the
International Federation for Information Processing
The International Federation for Information Processing (IFIP) is a global organisation for researchers and professionals working in the field of computing to conduct research, develop standards and promote information sharing.
Established in 19 ...
(IFIP)
IFIP Working Group 2.1 on Algorithmic Languages and Calculi, which
specified, maintains, and supports the
programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
s
ALGOL 60
ALGOL 60 (short for ''Algorithmic Language 1960'') is a member of the ALGOL family of computer programming languages. It followed on from ALGOL 58 which had introduced code blocks and the begin and end pairs for delimiting them, representing a ...
and
ALGOL 68
ALGOL 68 (short for ''Algorithmic Language 1968'') is an imperative programming language member of the ALGOL family that was conceived as a successor to the ALGOL 60 language, designed with the goal of a much wider scope of application and ...
.
He was elected a Fellow of the
American Academy of Arts and Sciences
The American Academy of Arts and Sciences (The Academy) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, and other ...
in 1974.
He received the
Turing Award
The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in the fi ...
in 1978 "for having a clear influence on methodologies for the creation of efficient and reliable software, and for helping to found the following important subfields of computer science: the theory of parsing, the
semantics of programming languages
In programming language theory, semantics is the rigorous mathematical study of the meaning of programming languages. Semantics assigns computational meaning to valid strings in a programming language syntax. It is closely related to, and oft ...
, automatic
program verification
In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of a system with respect to a certain formal specification or property, using formal methods of mathematics.
Formal ver ...
, automatic
program synthesis
In computer science, program synthesis is the task to construct a computer program, program that provably correct, provably satisfies a given high-level formal specification. In contrast to program verification, the program is to be constructed rat ...
, and
analysis of algorithms
In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that r ...
".
Floyd worked closely with
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of comp ...
, in particular as the major reviewer for Knuth's seminal book ''
The Art of Computer Programming
''The Art of Computer Programming'' (''TAOCP'') is a comprehensive multi-volume monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. it consists of published volumes 1, 2, 3, 4A, and 4 ...
'', and is the person most cited in that work. He was co-author, with Richard Beigel, of the textbook ''The Language of Machines: an Introduction to Computability and Formal Languages''. Floyd supervised seven Ph.D. graduates.
Floyd married and divorced twice, first with Jana M. Mason and then computer scientist
Christiane Floyd, and he had four children. In his last years he suffered from
Pick's disease
Frontotemporal dementia (FTD), also called frontotemporal degeneration disease or frontotemporal neurocognitive disorder, encompasses several types of dementia involving the progressive degeneration of the brain's frontal and temporal lobes. Men ...
, a
neurodegenerative disease
A neurodegenerative disease is caused by the progressive loss of neurons, in the process known as neurodegeneration. Neuronal damage may also ultimately result in their death. Neurodegenerative diseases include amyotrophic lateral sclerosis, mul ...
, and thus retired early in 1994.
His hobbies included hiking, and he was an avid
backgammon
Backgammon is a two-player board game played with counters and dice on tables boards. It is the most widespread Western member of the large family of tables games, whose ancestors date back at least 1,600 years. The earliest record of backgammo ...
player:
Selected publications
*
*
*
*
*
*
Notes
Further reading
*
*
External links
Obituaryin th
Stanford Report 2003. (archived 2016)
*
{{DEFAULTSORT:Floyd, Robert
1936 births
2001 deaths
American computer scientists
Turing Award laureates
Fellows of the American Academy of Arts and Sciences
1994 fellows of the Association for Computing Machinery
Formal methods people
University of Chicago alumni
Stanford University School of Engineering faculty