エドガー・ダイクストラ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
エドガー・ダイクストラ
Edsger Wybe Dijkstra (1930-2002)
人物情報
生誕 1930年5月11日
オランダの旗 オランダ ロッテルダム
死没 2002年8月6日(満72歳没)
オランダの旗 オランダ ニューネン
学問
研究分野 計算機科学
研究機関 オランダ国立情報数学研究所英語版
アイントホーフェン工科大学
テキサス大学オースティン校
博士課程
指導教員
Adriaan van Wijngaarden
博士課程
指導学生
Nico Habermann
Jan L.A. van de Snepscheut
主な業績 ダイクストラ法
構造化プログラミング
THEマルチプログラミングシステム
セマフォ
主な受賞歴 チューリング賞
テンプレートを表示

エドガー・ダイクストラEdsger Wybe Dijkstra, 1930年5月11日 - 2002年8月6日)は、オランダ人計算機科学者。1972年、プログラミング言語の基礎研究への貢献に対してチューリング賞を受賞。構造化プログラミングの提唱者。1984年から2002年に亡くなるまでテキサス大学オースティン校の計算機科学の Schlumberger Centennial Chair を務めた。

2002年の死の直前、プログラム計算の自己安定化英語版についての仕事に対して ACM PODC Influential Paper Award を授与された。この賞は翌年からダイクストラを称えてダイクストラ賞英語版と呼ばれるようになった。

エズガー・ダイクストラと表記されることもある。オランダ語での発音は、IPA表記でˈɛtsxər ˈwibə ˈdɛɪkstraで、エツハー・ウィベ・デイクストラに近い。

生涯[編集]

ロッテルダム生まれ。ライデン大学理論物理学を学んだが、計算機科学の方に興味があることに気が付くのに時間はかからなかった。最初にアムステルダムの国立数学研究所 (Mathematisch Centrum) に職を得たが、オランダのアイントホーフェン工科大学で教授職を得る。1970年代初期にはバロースフェローとしても働いた。その後、アメリカのテキサス大学オースティン校に移り、2000年に引退した。

彼の計算機科学に関する貢献としては、グラフ理論最短経路問題におけるダイクストラ法逆ポーランド記法とそれに関連する操車場アルゴリズム、初期の階層型システムの例であるTHEマルチプログラミングシステム銀行家のアルゴリズム排他制御のためのセマフォの考案などがある。分散コンピューティング分野では自己安定化英語版というシステムの信頼性を保証する手法を提案した。ダイクストラ法は SPF (Shortest Path First) で使われており、それがOSPFIS-ISといったルーティングプロトコルで使われている。操車場アルゴリズムやセマフォ(鉄道でかつて使われた腕木式信号機)に代表されるが、説明に鉄道を使用したことでも知られる。

1950年代には機械語でプログラムを組むことが多かったダイクストラだが、プログラミングにおけるGOTO文を評価しないという意見を持っていることで知られ、1968年に "A Case against the GO TO Statement"[1]を発表してgoto文撲滅運動の端緒とし、while文などの構造化制御構文への転換を促した。これが『Go to文は有害だと考えられる』(Go To Statement Considered Harmful) という刺激的な題名で学会誌に掲載されたが、これはダイクストラ本人がつけたものではなく、Communications of the ACM の編集者だったニクラウス・ヴィルトが付けたもので、"considered harmful" というフレーズが業界で流行るきっかけとなった。このような方法論を「構造化プログラミング」と呼び、1972年にアントニー・ホーアオーレ=ヨハン・ダールとの共著を "Structured Programming" という題名にした。ダイクストラはBASICを教育に使うことにも強く反対していた[2]

ダイクストラは ALGOL 60 のファンとしても知られ、最初のコンパイラを実装したチームにも参加していた。そのコンパイラ開発に関わった Jaap Zonneveld とダイクストラはプロジェクトが完了するまで髭を剃らないという誓いを立てた[3]。それは、世界初の再帰をサポートしたコンパイラの1つである[4]

1968年には、THEと呼ばれるマルチプログラミング方式のオペレーティングシステムの構造に関する論文と、"Cooperating Sequential Processes" についての論文[5]を発表している。

1970年代になると、ダイクストラの主要な興味は形式的検証に移っていった。当時の一般的手法は、とりあえずプログラムを書いてからその正当性数学的に証明するというものであった。ダイクストラはこれに対して、検証に時間がかかって面倒であるし、プログラムの開発手法に何ら洞察を与えない点が問題であるとした。一方「検証とプログラミングを同時に行う」のが「プログラム導出」と呼ばれる別の手法である。まず、プログラムの動作に関する数学的な「仕様」を記述し、その仕様に数学的な変換を加えて最終的にプログラムを導き出す。このように作成されたプログラムは「構造上正しい」ことが知られている。ダイクストラの後期の仕事は、この数学的手法を効率化することに関係している。2001年のインタビューで[6]彼は「優雅さ」への渇望について述べていた。すなわち、完全さを求めるのではなく、思考を精神的に処理することが正しいアプローチであると。彼はたとえ話としてモーツァルトベートーヴェンの作曲法を対比させている。

ダイクストラは分散コンピューティングの先駆者の1人でもある。例えば、彼の "Self-stabilizing Systems in Spite of Distributed Control" という論文は自己安定化英語版というサブフィールドを創始した。

計算機科学とプログラミングについての彼の意見は広範囲に及んだ。例えば、プログラミングについて「2以上なら、forを使え」という警句を作り[要出典]、あるデータ構造の複数のインスタンスを処理している場合、経験則としてそのロジックをループ内にカプセル化すべきだと示唆した。彼は、プログラミングが本来非常に難しく複雑であり、プログラマはその複雑性をうまく管理するために可能な限り技巧と抽象化を利用する必要がある、という主張をした最初の人物でもある。計算機科学の抽象的性質について、次のように記している。

(コンピュータを操作するという)仕事は実のところ当時の電子工学技術の域を超えていて、物理的装置を動作可能にしてその状態を保つことが当初は何にも増して重要な課題だった。結果として特にアメリカでは「計算機科学」という用語が時期尚早な形で使われるようになり(実際、それは外科を「ナイフ科学」と呼ぶようなものである)、それが計算機と周辺機器についての科学であるという概念が人々の心に強く植えつけられた。Quod non(ラテン語で「それは正しくない」)[7]

長年のとの戦いの末、2002年8月6日オランダニューネンで亡くなった[8]

EWD と手書き文書[編集]

彼はまた、万年筆で慎重に原稿を書く習慣があることでも知られていた。ダイクストラは原稿に自分のイニシャルである EWDという記号と番号を付与したため、彼の原稿は一般に EWD と呼ばれている。ダイクストラ自身によれば、アムステルダムの数学研究所を離れてアイントホーフェン工科大学に移った後、この習慣が始まったという。アイントホーフェンに移った後、ダイクストラは1年以上何も書けない状態が続いた。自分を省みたダイクストラは、数学研究所の元同僚が理解するようなことを書けばアイントホーフェンの同僚には理解されず、アイントホーフェンの同僚が望むようなことを書けば数学研究所の元同僚に軽蔑されるという懸念があることを発見する。そこで彼は自分自身のためだけに書くことを決め、EWDが生まれた。ダイクストラは新たに EWD を書き上げると、そのコピーを同僚に配布した。それがさらにコピーされて世界中に配布されていき、計算機科学界全体に広がったのである。主題は計算機科学か数学であるが、一部は旅行記だったり、手紙だったり、講演記録だったりする。1300以上のEWDが電子化され、テキサス大学のダイクストラのアーカイブで検索・入手可能である。 [9]

ダイクストラの空想上の副業として、空想上の企業 Mathematics Inc. の会長という仕事があった。この企業はコンピュータのプログラム製造を商業化したソフトウェア企業のように、数学の定理を製造することを商業化した会社である。彼は Mathematics Inc. の様々な活動や課題を考案し、それをEWDシリーズのいくつかの文書で発表している。この空想上の企業はリーマン予想の証明を製造したが、リーマン予想が正しいと仮定して様々な証明を行ってきた数学者たちからロイヤルティーを徴収するという難題に直面する。証明そのものは企業秘密 (trade secretである[10]。同社の証明の多くは急いで生産され、同社はそれらの保守に追われることになった[11]。より成功した成果として、ピタゴラスの定理の標準的証明があり、100以上存在した既存の証明群を置換した[12]。ダイクストラは Mathematics Inc. について「これまでに考案された最もエキサイティングで最もみじめなビジネス」と評した[10]。EWD 443 (1974) では彼の想像した会社が世界の75%のシェアを獲得したとされている[13][14]

チューリッヒ工科大学でのカンファレンスで黒板に向かっているダイクストラ (1994)

ダイクストラはソフトウェアについて様々な発明をしたが、自分のコンピュータを所有したのは比較的遅く、しかもめったに使わなかった。1972年以降のEWDはほとんどが手書きである。講義の際は黒板にチョークで書き、オーバーヘッドプロジェクタも滅多に使わなかった。アップルのMacintoshを購入してからも、電子メールとWebブラウザ以外には使わなかった[15]

受賞歴[編集]

以下のような賞と栄誉を受けている[15]

著作[編集]

脚注[編集]

  1. ^ Dijkstra, Edsger W. A Case against the GO TO Statement (EWD-215). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  2. ^ Dijkstra, Edsger W. How do we tell truths that might hurt? (EWD-498). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  3. ^ van Emden, Maarten (2008年5月6日). “I remember Edsger Dijkstra (1930–2002)”. 2010年12月22日閲覧。
  4. ^ Daylight, E. G. (2011). “Dijkstra's Rallying Cry for Generalization: the Advent of the Recursive Procedure, late 1950s - early 1960s”. The Computer Journal. doi:10.1093/comjnl/bxr002. http://www.dijkstrascry.com/node/4. 
  5. ^ Dijkstra, Edsger W. Cooperating sequential processes (EWD-123). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  6. ^ Edsger Dijkstra - Discipline in Thought (visit www.catonmat.net for notes)”. Video.google.com. 2012年4月20日閲覧。
  7. ^ Dijkstra, Edsger W. On a cultural gap (EWD-924). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription) Dijkstra, E.W. (1986). “On a cultural gap”. The Mathematical Intelligencer 8 (1): 48–52. http://www.cs.utexas.edu/users/EWD/transcriptions/EWD09xx/EWD924.html. 
  8. ^ Goodwins, Rupert (2002年8月8日). “Computer science pioneer Dijkstra dies”. http://news.cnet.com/2100-1001-949023.html 2010年12月22日閲覧。 
  9. ^ Online EWD archive, University of Texas, http://www.cs.utexas.edu/users/EWD/ .
  10. ^ a b Dijkstra, Edsger W. EWD-475. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  11. ^ Dijkstra, Edsger W. EWD-539. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  12. ^ Dijkstra, Edsger W. EWD-427. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  13. ^ Dijkstra, Edsger W. EWD-433. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  14. ^ Dijkstra, Edsger W (1982). Selected Writings on Computing: A Personal Perspective. Berlin: Springer-Verlag. ISBN 978-0-387-90652-2. 
  15. ^ a b In Memoriam Edsger Wybe Dijkstra (memorial), University of Texas, http://www.utexas.edu/faculty/council/2002-2003/memorials/Dijkstra/dijkstra.html .
  16. ^ A. M. Turing Award”. Association for Computing Machinery. 2011年2月5日閲覧。
  17. ^ ACM Fellows - D”. Association for Computing Machinery. 2011年2月15日閲覧。

参考文献[編集]

関連項目[編集]

外部リンク[編集]