Robert W. Floyd | |
|---|---|
 Floydc. 1970s | |
| Born | Robert Willoughby Floyd (1936-06-08)June 8, 1936 New York City,New York, U.S. |
| Died | September 25, 2001(2001-09-25) (aged 65) Stanford,California, U.S. |
| Education | University of Chicago (BA,BA) |
| Known for | Floyd–Warshall algorithm Floyd–Steinberg dithering Floyd's cycle-finding algorithm Floyd's triangle ALGOL |
| Spouse(s) | Jana M. Mason;Christiane Floyd (née Riedl) |
| Children | 4 |
| Awards | Turing Award (1978) Computer Pioneer Award (1991) |
| Scientific career | |
| Fields | Computer science |
| Institutions | Illinois Institute of Technology Carnegie Mellon University Stanford University |
| Doctoral students | |
Robert W. Floyd[1] (bornRobert Willoughby Floyd; June 8, 1936 – September 25, 2001) was an Americancomputer scientist. His contributions include the design of theFloyd–Warshall algorithm (independently ofStephen Warshall), which efficiently finds all shortest paths in agraph and his work onparsing;Floyd's cycle-finding algorithm for detectingcycles 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 calledFloyd–Steinberg dithering (though he distinguished dithering from diffusion). He pioneered in the field ofprogram verification usinglogical assertions with the 1967 paperAssigning Meanings to Programs. This was a contribution to what later becameHoare logic. Floyd received theTuring Award in 1978.
Born inNew York City, Floyd finished high school at age 14. At theUniversity of Chicago, he received aBachelor of Arts (B.A.) inliberal arts in 1953 (when still only 17) and a secondbachelor's degree inphysics in 1958. Floyd was a college roommate ofCarl Sagan.[2]
Floyd became a staff member of the Armour Research Foundation (nowIIT Research Institute) atIllinois Institute of Technology in the 1950s. Becoming a computer operator in the early 1960s, he began publishing many papers, including oncompilers (particularlyparsing). He was a pioneer ofoperator-precedence grammars, and is credited with initiating the field ofprogramming language semantics inFloyd (1967). He was appointed an associate professor atCarnegie Mellon University by the time he was 27 and became a full professor atStanford University six years later. He obtained this position without aDoctor of Philosophy (Ph.D.) degree.
He was a member of theInternational Federation for Information Processing (IFIP)IFIP Working Group 2.1 on Algorithmic Languages and Calculi,[3] whichspecified, maintains, and supports theprogramming languagesALGOL 60 andALGOL 68.[4]
He was elected a Fellow of theAmerican Academy of Arts and Sciences in 1974.[5]
He received theTuring 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, thesemantics of programming languages, automaticprogram verification, automaticprogram synthesis, andanalysis of algorithms".[6]
Floyd worked closely withDonald Knuth, in particular as the major reviewer for Knuth's seminal bookThe Art of Computer Programming, and is the person most cited in that work. He was co-author, with Richard Beigel, of the textbookThe Language of Machines: an Introduction to Computability and Formal Languages.[7] Floyd supervised seven Ph.D. graduates.[8]
Floyd married and divorced twice, first with Jana M. Mason and then computer scientistChristiane Floyd, and he had four children. In his last years he suffered fromPick's disease, aneurodegenerative disease, and thus retired early in 1994.[6]
His hobbies included hiking, and he was an avidbackgammon player:
We once were stuck at the Chicago O'Hare airport for hours, waiting for our flight to leave, owing to a snow storm. As we sat at our gate, Bob asked me, in a casual manner, "do you know how to play backgammon?" I answered I knew the rules, but why did he want to know? Bob said since we had several hours to wait perhaps we should play a few games, for small stakes of course. He then reached into his briefcase and removed a backgammon set.
My Dad taught me many things. One was to be wary of anyone who suggests a game of pool for money, and then opens a black case and starts to screw together a pool stick. I figured that this advice generalized to anyone who traveled with their own backgammon set. I told Bob that I was not going to play for money, no way. He pushed a bit, but finally said fine. He proceeded instead to give me a free lesson in the art and science of playing backgammon.
I was right to pass on playing him for money—at any stakes. The lesson was fun. I found out later that for years he had been working on learning the game. He took playing backgammon very seriously, studied the game and its mathematics, and was a near professional. I think it was more than a hobby. Like his research, Bob took what he did seriously, and it is completely consistent that he would be terrific at backgammon.
