ロバート・フロイド
ウィキペディア フリーな encyclopedia
ロバート・W・フロイド(Robert W. Floyd[1]、1936年6月8日 - 2001年9月25日)は、アメリカ合衆国の計算機科学者。
概要 ロバート・W・フロイド, 生誕 ...
ロバート・W・フロイド | |
---|---|
生誕 |
(1936-06-08) 1936年6月8日 アメリカ合衆国 ニューヨーク |
死没 |
(2001-09-25) 2001年9月25日(65歳没) アメリカ合衆国 カリフォルニア州スタンフォード |
国籍 | アメリカ合衆国 |
研究分野 | 計算機科学 |
研究機関 |
カーネギーメロン大学 スタンフォード大学 イリノイ工科大学 |
出身校 | シカゴ大学 |
博士課程 指導学生 |
ロナルド・リベスト ロバート・タージャン |
主な業績 |
ワーシャル-フロイド法 フロイド-スタインバーグ・ディザリング フロイドの循環検出法 |
主な受賞歴 | チューリング賞 (1978) |
プロジェクト:人物伝 | |
テンプレートを表示 |
閉じる
彼の貢献としてワーシャル-フロイド法の設計がある(スティーブン・ワーシャル(英語版)とはそれぞれ独立に考案)。これはグラフ理論における最短経路問題の解法のひとつである。また、数列の循環を検出するフロイドの循環検出法があり、これらは構文解析にも利用できる。また、別の論文で彼は画像描画のための誤差拡散に関する重要な概念を提案しており、これがフロイド-スタインバーグ・ディザリングとして知られている(ただしフロイド自身は誤差拡散とディザリングは区別して考えていた)。特に有名な貢献は1967年の論文 Assigning Meanings to Programs(プログラムへの意味の割り当て)である。この中でプログラム検証を数理論理学の手法を使って行うという先駆的な試みがなされている。これは後のホーア論理につながる重要な貢献となった。