ロバート・フロイド
ロバート・W・フロイド（Robert W. Floyd[1]、1936年6月8日 - 2001年9月25日）は、アメリカ合衆国の計算機科学者。
| ロバート・W・フロイド | |
|---|---|
| 生誕 |
1936年6月8日 アメリカ合衆国 ニューヨーク |
| 死没 |
2001年9月25日（65歳没） アメリカ合衆国 カリフォルニア州スタンフォード |
| 国籍 |
アメリカ合衆国 |
| 研究分野 | 計算機科学 |
| 研究機関 |
カーネギーメロン大学 スタンフォード大学 イリノイ工科大学 |
| 出身校 | シカゴ大学 |
| 博士課程 指導学生 |
ロナルド・リベスト ロバート・タージャン |
| 主な業績 |
ワーシャル-フロイド法 フロイド-スタインバーグ・ディザリング フロイドの循環検出法 |
| 主な受賞歴 | チューリング賞 (1978) |
| プロジェクト:人物伝 | |
彼の貢献としてワーシャル-フロイド法の設計がある（スティーブン・ワーシャルとはそれぞれ独立に考案）。これはグラフ理論における最短経路問題の解法のひとつである。また、数列の循環を検出するフロイドの循環検出法があり、これらは構文解析にも利用できる。また、別の論文で彼は画像描画のための誤差拡散に関する重要な概念を提案しており、これがフロイド-スタインバーグ・ディザリングとして知られている（ただしフロイド自身は誤差拡散とディザリングは区別して考えていた）。特に有名な貢献は1967年の論文 Assigning Meanings to Programs（プログラムへの意味の割り当て）である。この中でプログラム検証を数理論理学の手法を使って行うという先駆的な試みがなされている。これは後のホーア論理につながる重要な貢献となった。
生涯
編集ニューヨーク州で生まれ、飛び級により14歳で高校を卒業。1953年にはシカゴ大学でリベラル・アーツの学士号を取得し（17歳）、1958年には物理学でも学士号を取得した。
1950年代、イリノイ工科大学の Armour Research Foundation のスタッフとなる。1960年代初めにはコンピュータオペレータとなり、数々の注目すべき論文を発表し始めた。これにより27歳でカーネギーメロン大学の助教授に招かれ、6年後にはスタンフォード大学の教授となった。彼は博士号を取得することなく教授となったのである。
フロイドは、「効率的で信頼できるソフトウェアの作成手法への明確な寄与に対して。および構文解析理論、プログラミング言語の形式意味論、自動プログラム検証、自動プログラム合成、アルゴリズム解析といった情報工学の下位分野の開拓への重要な寄与に対して」1978年にチューリング賞を授与された。
フロイドはドナルド・クヌースと親しく、クヌースの著書 The Art of Computer Programming の主な査閲者でもあった。同書でもよく言及されている。Richard Beigel との共著（教科書） The Language of Machines: an Introduction to Computability and Formal Languages (1994, W.H. Freeman and Company, ISBN 978-0-7167-8266-7) がある。生涯に7人の博士課程学生を指導した[2]。
主な著作
編集- R.W. Floyd, "Assigning Meaning to Programs", in Proceedings of Symposium on Applied Mathematics, Vol. 19, J.T. Schwartz (Ed.), A.M.S., 1967, pp. 19–32
脚注
編集- ^ フロイドは正式にミドルネームを "W" 一文字に変更したが、"W." のように記述することを好んだ。 (Knuth 2003)
- ^ http://infolab.stanford.edu/pub/voy/museum/floydtree.html
参考文献
編集- Knuth, Donald E. (2003-12). “Robert W Floyd, In Memoriam”. ACM SIGACT News 34 (4): 3–13.
- Knuth, Donald E.. “Memorial Resolution: Robert W. Floyd (1936-2001)”. Stanford University Faculty Memorials. Stanford Historical Society. 2012年8月14日閲覧。