Robert Floyd
| Robert W Floyd | |
| americký informatik | |
| Narodenie | 8. jún 1936 New York, USA |
|---|---|
| Úmrtie | 25. september 2001 (65 rokov) Stanford, Kalifornia, USA |
Robert W Floyd (* 8. jún 1936, New York, USA - † 25. september 2001, Stanford, Kalifornia, USA) bol americký informatik. Svoje stredné meno si počas života nechal zmeniť na "W", ktoré sa vďaka tomu píše bez bodky. Floyd však pripúšťal, že je možné jeho meno "W" skracovať ako "W.".
V roku 1978 dostal Turingovu cenu za svoj všeobecný prínos v oblasti informatiky - v odôvodnení sa spomínajú oblasti ako syntaktická analýza, sémantika programovacích jazykov, verifikácia programov, či analýza algoritmov.
Je známy predovšetkým ako výrazná osobnosť v oblasti grafových algoritmov, kde je jedným z objaviteľov Floydovho-Warshallovho algoritmu.
Život
Robert Floyd sa narodil v New Yorku v roku 1936. Už ako štrnásťročný ukončil strednú školu a v roku 1953, ako sedemnásťročný, získal na Chicagskej univerzite titul bakalára slobodných umení. Ďalší titul bakalára získal v roku 1958, keď úspešne vyštudoval fyziku.
Začiatkom šesťdesiatych rokov 20. storočia začal pracovať ako informatik, pričom publikoval niekoľko povšimnutiahodných článkov. Ako dvadsaťsedemročný získal miesto na Carnegie Mellon University a už o šesť rokov neskôr sa stal profesorom na Stanfordovej univerzite, pričom toto miesto získal bez titulu PhD.
Floyd bol dvakrát ženatý a rozvedený, mal štyri deti. Bol aktívnym hráčom backgammonu a zapáleným turistom.
Práca
Robert W Floyd je známy predovšetkým ako pôvodca Floydovho-Warshallovho algoritmu (niekedy známy aj ako Royov-Floydov algoritmus, Royov-Warshallov algoritmus, WFI algoritmus alebo len ako Floydov algoritmus), ktorý objavil v roku 1962. V podstate rovnaký algoritmus objavili nezávisle na sebe aj Bernard Roy v roku 1959 a Stephen Warshall v roku 1962, čo je aj dôvodom rôznych názvov algoritmu. Najčastejšie sa však pripisuje práve Robertovi Floydovi. Ide o algoritmus na výpočet najkratších ciest medzi každými dvoma vrcholmi v orientovanom grafe. Využíva dynamické programovanie a jeho časová zložitosť je .
Významný je tiež Floydov prínos v oblasti verifikácie programov. Jeho článok Assigning Meanings to Programs (1967) bol významným príspevkom k teórii neskôr nazývanej Hoareova logika.
Spolupracoval s Donaldom Knuthom, bol hlavným recenzentom jeho svetoznámej knihy The Art of Computer Programming. V tejto knihe bol tiež najcitovanejším autorom v zozname použitej literatúry.
Externé odkazy
- Spomienková reč Donalda Knutha
- Nekrológ, ktorý sa objavil v Stanford Report