Robert W Floyd (June 8, 1936 – September 25, 2001) was a

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (a ...

. 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 ...

(independently of

Stephen Warshall Stephen Warshall (November 15, 1935 – December 11, 2006) was an American computer scientist. During his career, Warshall carried out research and development in operating systems, compiler design, language design, and operations research. W ...

), 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 discre ...

and his work on

parsing Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from ...

; Floyd's cycle-finding algorithm for detecting cycles 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 Floyd–Steinberg dithering is an image dithering algorithm first published in 1976 by Robert W. Floyd and Louis Steinberg. It is commonly used by image manipulation software, for example when an image is converted into GIF format that is restr ...

(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 intended algorithms underlying a system with respect to a certain formal specification or property, using formal metho ...

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 compu ...

in 1978.

Life

Born in

New York City New York, often called New York City or NYC, is the List of United States cities by population, most populous city in the United States. With a 2020 population of 8,804,190 distributed over , New York City is also the L ...

, Floyd finished high school at age 14. At the

University of Chicago The University of Chicago (UChicago, Chicago, U of C, or UChi) is a private research university in Chicago, Illinois. Its main campus is located in Chicago's Hyde Park neighborhood. The University of Chicago is consistently ranked among the b ...

, he received a

Bachelor of Arts Bachelor of arts (BA or AB; from the Latin ', ', or ') is a bachelor's degree awarded for an undergraduate program in the arts, or, in some cases, other disciplines. A Bachelor of Arts degree course is generally completed in three or four yea ...

(B.A.) in

liberal arts Liberal arts education (from Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally a dialect spoken in the lower Tiber area (then known as La ...

in 1953 (when still only 17) and a second

bachelor's degree A bachelor's degree (from Middle Latin ''baccalaureus'') or baccalaureate (from Modern Latin ''baccalaureatus'') is an undergraduate academic degree awarded by colleges and universities upon completion of a course of study lasting three to si ...

physics Physics is the natural science that studies matter, its 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 which ...

in 1958. Floyd was a college roommate of

Carl Sagan Carl Edward Sagan (; ; November 9, 1934December 20, 1996) was an American astronomer, planetary scientist, cosmologist, astrophysicist, astrobiologist, author, and science communicator. His best known scientific contribution is research on ex ...

. Floyd became a staff member of the Armour Research Foundation (now IIT Research Institute) at

Illinois Institute of Technology Illinois Institute of Technology (IIT) is a private research university in Chicago, Illinois. Tracing its history to 1890, the present name was adopted upon the merger of the Armour Institute and Lewis Institute in 1940. The university has prog ...

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 translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs tha ...

s (particularly

). He was a pioneer of operator-precedence grammars, and is credited with initiating the field of programming language semantics in . He was appointed an associate professor at

Carnegie Mellon University Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...

by the time he was 27 and became a full professor at

Stanford University Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is conside ...

six years later. He obtained this position without a

Doctor of Philosophy A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is ...

(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 196 ...

(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. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...

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 that was conceived as a successor to the ALGOL 60 programming language, designed with the goal of a much wider scope of application and more rigorously d ...

. He was elected a Fellow of the

American Academy of Arts and Sciences The American Academy of Arts and Sciences (abbreviation: AAA&S) 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, a ...

in 1974. He received 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, 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. Semantics describes the processe ...

, automatic

program synthesis In computer science, program synthesis is the task to construct a program that provably satisfies a given high-level formal specification. In contrast to program verification, the program is to be constructed rather than given; however, both fields ...

, 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, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...

, 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 monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of com ...

'', 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 Christiane Floyd (née Riedl; born 26 April 1943) is an Austrian computer scientist. In 1978, she became the first female professor of computer science in Germany, and was a pioneer of evolutionary participatory software design—a precursor to ...

, and he had four children. In his last years he suffered from

Pick's disease Frontotemporal dementia (FTD), or frontotemporal degeneration disease, or frontotemporal neurocognitive disorder, encompasses several types of dementia involving the progressive degeneration of frontal and temporal lobes. FTDs broadly present a ...

, a

neurodegenerative disease A neurodegenerative disease is caused by the progressive loss of structure or function of neurons, in the process known as neurodegeneration. Such neuronal damage may ultimately involve cell death. Neurodegenerative diseases include amyotrophi ...

, 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 nearly 5,000 years to the regions of Mesopotamia and Pe ...

player:

Selected publications

* * * * * *

Notes

External links

Obituary
in th
Stanford Report
* {{DEFAULTSORT:Floyd, Robert 1936 births 2001 deaths American computer scientists Turing Award laureates Fellows of the American Academy of Arts and Sciences Fellows of the Association for Computing Machinery Formal methods people University of Chicago alumni Stanford University School of Engineering faculty

Life

Selected publications

Notes

Further reading

External links