Robert Floyd
Encyclopedia
Robert W Floyd (June 8, 1936 – September 25, 2001) was an eminent computer scientist
.
His contributions include the design of the Floyd–Warshall algorithm (independently of Stephen Warshall
), which efficiently finds all shortest paths in a graph
, Floyd's cycle-finding algorithm
for detecting cycle
s in a sequence, and his work on parsing
. 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). A significant achievement was pioneering the field of program verification using logical assertion
s with the 1967 paper Assigning Meanings to Programs. This was an important contribution to what later became Hoare logic
.
, Floyd finished school at age 14. At the University of Chicago
, he received a Bachelor's degree
in liberal arts
in 1953 (when still only 17) and a second Bachelor's degree in physics
in 1958.
Floyd became a staff member of the Armour Research Foundation (now IIT Research Institute) at Illinois Institute of Technology
in the 1950s. Becoming a computer operator in the early 1960s, he began publishing many noteworthy papers and was appointed an associate professor at Carnegie Mellon University
by the time he was 27 and became a full professor at Stanford University
six years later. He obtained this position without a Ph.D.
He received the Turing Award
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, automatic program verification, automatic program synthesis
, and analysis of algorithms
".
Floyd worked closely with Donald Knuth
, in particular as the major reviewer for Knuth's seminal book The Art of Computer Programming
, and is the person most cited in that work. He was the co-author, with Richard Beigel, of the textbook The Language of Machines: an Introduction to Computability and Formal Languages (1994, W.H. Freeman and Company, ISBN 978-0716782667).
Floyd married and divorced twice, including with computer scientist Christiane Floyd, and he had four children. His hobbies included hiking and he was an avid backgammon
player:
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
.
His contributions include the design of the Floyd–Warshall algorithm (independently of Stephen Warshall
Stephen Warshall
Stephen Warshall was born in New York City. During his career Warshall carried out research and development in operating systems, compiler design, language design, and operations research. Warshall died on December 11, 2006 of cancer at his home in Gloucester, MA. He is survived by his wife, Sarah...
), which efficiently finds all shortest paths in a graph
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, Floyd's cycle-finding algorithm
Floyd's cycle-finding algorithm
In computer science, cycle detection is the algorithmic problem of finding a cycle in a sequence of iterated function values.For any function ƒ that maps a finite set S to itself, and any initial value x0 in S, the sequence of iterated function values x_0,\ x_1=f,\ x_2=f,\ \dots,\ x_i=f,\ \dotsmust...
for detecting cycle
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
s in a sequence, and his work on parsing
Parsing
In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens , to determine its grammatical structure with respect to a given formal grammar...
. 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). A significant achievement was pioneering the field of program verification using logical assertion
Logical assertion
A logical assertion is a statement that asserts that a certain premise is true, and is useful for statements in proof. It is equivalent to a sequent with an empty antecedent....
s with the 1967 paper Assigning Meanings to Programs. This was an important contribution to what later became Hoare logic
Hoare logic
Hoare logic 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 logician C. A. R. Hoare, and subsequently refined by Hoare and other researchers...
.
Life
Born in New YorkNew York
New York is a state in the Northeastern region of the United States. It is the nation's third most populous state. New York is bordered by New Jersey and Pennsylvania to the south, and by Connecticut, Massachusetts and Vermont to the east...
, Floyd finished school at age 14. At the University of Chicago
University of Chicago
The University of Chicago is a private research university in Chicago, Illinois, USA. It was founded by the American Baptist Education Society with a donation from oil magnate and philanthropist John D. Rockefeller and incorporated in 1890...
, he received a Bachelor's degree
Bachelor's degree
A bachelor's degree is usually an academic degree awarded for an undergraduate course or major that generally lasts for three or four years, but can range anywhere from two to six years depending on the region of the world...
in liberal arts
Liberal arts
The term liberal arts refers to those subjects which in classical antiquity were considered essential for a free citizen to study. Grammar, Rhetoric and Logic were the core liberal arts. In medieval times these subjects were extended to include mathematics, geometry, music and astronomy...
in 1953 (when still only 17) and a second Bachelor's degree in physics
Physics
Physics is a natural science that involves the study of matter and its motion through spacetime, along with related concepts such as energy and force. More broadly, it is the general analysis of nature, conducted in order to understand how the universe behaves.Physics is one of the oldest academic...
in 1958.
Floyd became a staff member of the Armour Research Foundation (now IIT Research Institute) at Illinois Institute of Technology
Illinois Institute of Technology
Illinois Institute of Technology, commonly called Illinois Tech or IIT, is a private Ph.D.-granting university located in Chicago, Illinois, with programs in engineering, science, psychology, architecture, business, communications, industrial technology, information technology, design, and law...
in the 1950s. Becoming a computer operator in the early 1960s, he began publishing many noteworthy papers and was appointed an associate professor at Carnegie Mellon University
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
by the time he was 27 and became a full professor at Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
six years later. He obtained this position without a Ph.D.
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
He received the Turing Award
Turing Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
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
Parsing
In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens , to determine its grammatical structure with respect to a given formal grammar...
, the semantics of programming languages, automatic program verification, automatic program synthesis
Program synthesis
Program synthesis is a special form of automatic programming that is most often paired with a technique for formal verification. The goal is to automatically construct a program that provably satisfies a given high-level specification...
, and analysis of algorithms
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
".
Floyd worked closely with Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
, in particular as the major reviewer for Knuth's seminal book The Art of Computer Programming
The Art of Computer Programming
The Art of Computer Programming is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis....
, and is the person most cited in that work. He was the co-author, with Richard Beigel, of the textbook The Language of Machines: an Introduction to Computability and Formal Languages (1994, W.H. Freeman and Company, ISBN 978-0716782667).
Floyd married and divorced twice, including with computer scientist Christiane Floyd, and he had four children. His hobbies included hiking and he was an avid backgammon
Backgammon
Backgammon is one of the oldest board games for two players. The playing pieces are moved according to the roll of dice, and players win by removing all of their pieces from the board. There are many variants of backgammon, most of which share common traits...
player:
Selected publications
- R.W. Floyd, "Assigning Meaning to Programs", in Proceedings of Symposium on Applied Mathematics, Vol. 19, J.T. Schwartz (Ed.), A.M.S., 1967, pp. 19–32