Robert Floyd

Robert W Floyd (8. června 1936, New York – 25. září 2001, Stanford) byl americký informatik.

V roce 1978 dostal Turingovu cenu za svůj všeobecný přínos v oblasti informatiky – v odůvodnění se zmiňují oblasti jako syntaktická analýza, sémantika programovacích jazyků, verifikace programů a analýza algoritmů.

Je znám především jako výrazná osobnost v oblasti grafových algoritmů, kde je jedním z objevitelů Floydova-Warshallova algoritmu.

Život

Robert Floyd se narodil v New Yorku v roce 1936. Už jako čtrnáctiletý ukončil střední školu a v roce 1953, jako sedmnáctiletý, získal na Chicagské univerzitě titul bakaláře svobodných umění. Další titul bakaláře získal v roce 1958, když úspěšně vystudoval fyziku.

Začátkem šedesátých let začal pracovat jako informatik, přičemž publikoval několik povšimnutíhodných článků. Jako sedmadvacetiletý získal místo na Carnegie Mellon University a už o šest let později se stal profesorem na Stanfordově univerzitě, přičemž toto místo získal bez titulu Ph.D.

Práce

Robert W. Floyd je známý především jako původce Floydova-Warshallova algoritmu, který objevil v roce 1962. V podstatě stejný algoritmus objevili nezávisle na sobě i Bernard Roy v roce 1959 a Stephen Warshall v roce 1962, což je také důvodem různých názvů algoritmu. Nejčastěji se však připisuje právě Robertu Floydovi. Jde o algoritmus pro výpočet nejkratších cest mezi každými dvěma vrcholy v orientovaném grafu. Využívá dynamické programování a jeho časová složitost je ${\displaystyle \theta (n^{3})}$.

Významný je také Floydův přínos v oblasti verifikace programů. Článek Assigning Meanings to Programs (1967) byl významným příspěvkem k teorii později zvané Hoareova logika.

Spolupracoval s Donaldem Knuthem, byl hlavním recenzentem jeho světoznámé knihy The Art of Computer Programming. V této knize byl také nejcitovanější autorem v seznamu použité literatury.

Reference

V tomto článku byl použit překlad textu z článku Robert Floyd na slovenské Wikipedii.