Uit Wikipedia, de vrije encyclopedie
Robert W. Floyd
(
New York
,
8 juni
1936
?
Stanford
,
25 september
2001
) was
Amerikaans
informaticus
. Hij ontwikkelde
algoritmes
voor verschillende deelgebieden van de informatica. Bovendien stamde van hem het idee om logische uitspraken aan computerprogramma's toe te voegen om formele verificatie van software mogelijk te maken. Dit idee werd later door
Tony Hoare
uitgewerkt tot
Hoarelogica
. In 1978 kreeg hij de
Turing Award
voor zijn werk op het gebied van parsen en programmaverificatie.
Floyd werd geboren in
New York
en behaalde zijn middelbareschooldiploma op 14-jarige leeftijd. Zijn bachelor-graad in de letteren behaalde hij op 17-jarige leeftijd, maar daarna behaalde hij ook nog een bachelor-diploma in de natuurkunde. In de jaren vijftig en zestig werkte Floyd onder andere aan het
Illinois Institute of Technology
en
Carnegie Mellon University
. In deze tijd publiceerde hij een aantal invloedrijke artikelen. In 1968 werd hij hoogleraar in
Stanford
, hoewel hij nooit was gepromoveerd. In 2001 overleed hij aldaar na een lang ziekbed op 65-jarige leeftijd.
Floyd werkte aan algoritmes in de
grafentheorie
en
beeldverwerking
. Onafhankelijk van
Stephen Warshall
ontwikkelde hij het
Floyd-Warshall-algoritme
om alle kortste paden in een graaf te vinden en een algoritme om lussen in grafen te vinden. Bovendien ontwikkelde hij
Floyd-Steinberg-dithering
, een algoritme om foto's af te beelden met een klein aantal kleuren. Ook stamt de meest gebruikte variant van het sorteeralgoritme
heapsort
van hem.
Hij is echter voornamelijk bekend geworden om zijn werk in het parsen en de programmaverificatie. Van hem stamt het idee om programma's te voorzien van logische uitspraken die voorwaardes beschrijven waaraan de programmatoestand op een bepaald moment moet voldoen. Voorbeelden hiervan zijn
precondities
(voorwaarden waaraan voldaan moet zijn aan het begin van het uitvoeren van een
subprogramma
),
postcondities
(voorwaarden waaraan voldaan moet zijn aan het einde van het uitvoeren van een subprogramma) en
invarianten
(voorwaarden waaraan altijd voldaan moet zijn). Deze logische uitspraken maken het makkelijker om van programma's de juistheid te bepalen, omdat bewijzen zich nu op kleine stukken van het programma kunnen richten. Voor Floyds werk op dit gebied ontving hij in 1978 de
Turing Award
.
1966:
Alan J. Perlis
·
1967:
Maurice V. Wilkes
·
1968:
Richard Hamming
·
1969:
Marvin Minsky
·
1970:
J.H. Wilkinson
·
1971:
John McCarthy
·
1972:
Edsger Dijkstra
·
1973:
Charles W. Bachman
·
1974:
Donald E. Knuth
·
1975:
Allen Newell
,
Herbert Simon
·
1976:
Michael Rabin
,
Dana S. Scott
·
1977:
John Backus
·
1978:
Robert W. Floyd
·
1979:
Kenneth E. Iverson
·
1980:
Tony Hoare
·
1981:
Edgar F. (Ted) Codd
·
1982:
Stephen A. Cook
·
1983:
Ken Thompson
,
Dennis M. Ritchie
·
1984:
Niklaus Wirth
·
1985:
Richard M. Karp
·
1986:
John Hopcroft
,
Robert Tarjan
·
1987:
John Cocke
·
1988:
Ivan Sutherland
·
1989:
William Kahan
·
1990:
Fernando J. Corbato
·
1991:
Robin Milner
·
1992:
Butler Lampson
·
1993:
Juris Hartmanis
,
Richard E. Stearns
·
1994:
Edward Feigenbaum
,
Raj Reddy
·
1995:
Manuel Blum
·
1996:
Amir Pnueli
·
1997:
Douglas Engelbart
·
1998:
Jim Gray
·
1999:
Frederick P. Brooks, Jr.
·
2000:
Andrew Chi-Chih Yao
·
2001:
Ole-Johan Dahl
,
Kristen Nygaard
·
2002:
Ron Rivest
,
Adi Shamir
,
Leonard M. Adleman
·
2003:
Alan Kay
·
2004:
Vinton G. Cerf
,
Robert E. Kahn
·
2005:
Peter Naur
·
2006:
Frances E. Allen
·
2007:
Edmund M. Clarke
,
E. Allen Emerson
,
Joseph Sifakis
·
2008:
Barbara Liskov
·
2009:
Charles Thacker
·
2010:
Leslie Valiant
·
2011:
Judea Pearl
·
2012:
Shafi Goldwasser
,
Silvio Micali
·
2013:
Leslie Lamport
·
2014:
Michael Stonebraker
·
2015:
Martin Hellman
,
Whitfield Diffie
·
2016:
Tim Berners-Lee
·
2017:
John L. Hennessy
,
David Patterson
·
2018:
Yoshua Bengio
,
Geoffrey Hinton
,
Yann LeCun
·
2019:
Patrick M. Hanrahan
,
Edwin E. Catmull
·
2020:
Alfred Aho
,
Jeffrey Ullman
·
2021:
Jack Dongarra
·
2022:
Robert Metcalfe
·
2023:
Avi Wigderson