Robert Floyd

Robert „Bob“ W Floyd (* 8. Juni 1936 in New York City; † 25. September 2001 in Stanford, Kalifornien) war ein US-amerikanischer Informatiker und Turing-Preisträger. Er ließ seinen ursprünglichen zweiten Vornamen auf „W“ ändern, jedoch betonte er oft, dass „W.“ eine gültige Abkürzung dafür sei.^[1]

Floyd wurde 1936 in New York City geboren und mit sechs Jahren als Wunderkind erkannt. Er übersprang drei Schulklassen und beendete die Schule mit 14. An der University of Chicago erhielt er dank eines Stipendiums 1953 (also mit 17 Jahren) einen Bachelor-Grad in Liberal Arts, einen zweiten Bachelor-Grad erhielt er 1958 in Physik.

Schon während seines Studiums wurde er Computer-Operator und später Programmierer am Illinois Institute of Technology. 1959 begann er, mehrere bemerkenswerte Artikel in Computer-Journalen zu publizieren (Donald E. Knuth: „Als ich 1966 Material für eine Monographie zum Thema Parsen sammelte, kam ich zu dem Schluss, dass bis dahin nur fünf wirklich gute Papers über Compiler geschrieben worden waren, und Bob war der Autor von allen fünf.“^[2]). 1962 wurde er Senior Project Scientist bei Computer Associates.

1965 wurde er zum außerordentlichen Professor an der Carnegie Mellon University berufen und kam in den redaktionellen Beirat des Journal of the ACM. 1968 ging er an die Stanford University, wo er 1970 eine ordentliche Professur erhielt und von 1973 bis 1975 die Fakultät für Informatik leitete. Er erreichte diese Position ohne einen Doktortitel. Ein Jahr verbrachte Floyd auch an der Naval Postgraduate School. 1994 ging er in den Ruhestand. Zu Floyds Doktoranden gehören die späteren Turing-Preisträger Robert Tarjan und Ronald L. Rivest.

Zu seinen Beiträgen gehören effiziente Algorithmen zum Finden aller kürzesten Wege in einem Graphen (Algorithmus von Floyd und Warshall), zum Parsen und zur Bildbearbeitung (Floyd-Steinberg-Algorithmus), sowie die Entdeckung von Bottom-Up-Heapsort. Aber seine wahrscheinlich wichtigste Leistung war seine Pionierarbeit auf dem Gebiet der Programmverifikation mittels logischer Zusicherungen in seinem 1967 erschienenen Artikel Assigning Meanings to Programs. Dies war ein wichtiger Beitrag, der später zum Hoare-Kalkül führte.

Mit Manuel Blum, Vaughan Pratt, Robert Tarjan und Ron Rivest^[3] entwickelte er 1973 einen approximativen Selektionsalgorithmus (Bestimmung der k-ten kleinsten Zahl in Listen und Arrays), den median of median Algorithmus.

Floyd arbeitete eng mit Donald E. Knuth zusammen. Er war der Hauptrezensent für Knuths wegweisendes Buch The Art of Computer Programming, und er ist derjenige, der in diesem Werk am häufigsten zitiert wird.

Floyd erhielt 1978 den Turing Award für seinen Einfluss auf die Methoden zur Erzeugung effizienter und verlässlicher Software und für seinen Beitrag zur Gründung der folgenden Gebiete der Informatik: Theorie des Parsens, Semantik von Programmiersprachen, automatische Programmverifikation, automatische Programmsynthese und Analyse von Algorithmen. Daneben erhielt er unter anderem 1991 den Computer Pioneer Award der IEEE und ist Fellow der American Academy of Arts and Sciences, der American Association for the Advancement of Science und der ACM.

Floyd war zweimal verheiratet (zuletzt mit der Informatikerin Christiane Floyd) und hatte drei Söhne und eine Tochter. 2001 starb er an der Pick-Krankheit.

• A descriptive language for symbol manipulation. 1961.
• Syntactic analysis and operator precedence. 1963.
• The syntax of programming languages – A survey. 1964.
• Assigning Meaning to Programs. (PDF; 668 kB) In: Jacob T. Schwartz (Hrsg.): Proceedings of Symposium on Applied Mathematics. Vol. 19. American Mathematical Society, 1967, S. 19–32.
• mit Richard Beigel: The language of machines. Computer Science Press, 1994 (deutsch Die Sprache der Maschinen. International Thomson Publishing, Bonn, 1996, ISBN 3-8266-0216-1).

• Donald E. Knuth: Robert W Floyd, In Memoriam. In: SIGACT News. 34, 4, 2003, S. 3–13. Neudruck in: IEEE Annals of the History of Computing. 26, 2004.

• Robert Floyd, pioneer in computer programming, dead at 65, Stanford Report, 7. November 2001 (englisch)

1. ↑ Donald E. Knuth: Robert W Floyd, In Memoriam
2. ↑ Donald E. Knuth: Memorial Resolution Robert W. Floyd (1936–2001) (online (Memento vom 3. Juli 2010 im Internet Archive); PDF; 12 kB)
3. ↑ M. Blum, R. W. Floyd, V. R. Pratt, R. Rivest, R. E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences, Band 7, 1973, S. 448–461.