Robert W. Floyd

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.

Levensloop

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.

Werk

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.