ドナルド・クヌース
表示
ドナルド・エルビン・クヌース | |
---|---|
Open Content Alliance のレセプションでのクヌース(2005年10月25日) | |
生誕 |
1938年1月10日(86歳) アメリカ合衆国 ウィスコンシン州ミルウォーキー |
居住 | アメリカ合衆国 |
国籍 | アメリカ合衆国 |
研究分野 |
数学 計算機科学 |
研究機関 | スタンフォード大学 |
出身校 |
ケース・ウェスタン・リザーブ大学 カリフォルニア工科大学 |
博士課程 指導教員 | Marshall Hall, Jr. |
主な業績 |
The Art of Computer Programming TeX, METAFONT クヌース-モリス-プラット法 クヌース・ベンディックス完備化アルゴリズム MMIX |
主な受賞歴 |
チューリング賞 (1974) アメリカ国家科学賞 (1979) フランクリン・メダル(1988) フォン・ノイマンメダル (1995) |
プロジェクト:人物伝 |
ドナルド・エルビン・クヌース[1]︵Donald Ervin Knuth, 1938年1月10日 -︶は数学者、計算機科学者。スタンフォード大学名誉教授[2]。
クヌースによるアルゴリズムに関する著作 The Art of Computer Programming のシリーズはプログラミングに携わるものの間では有名である[3]。アルゴリズム解析と呼ばれる分野を開拓し、計算理論の発展に多大な貢献をしている。その過程で漸近記法で計算量を表すことを一般化させた。
理論計算機科学への貢献とは別に、コンピュータによる組版システム TeXとフォント設計システム METAFONT の開発者でもあり、Computer Modern という書体ファミリも開発した。
作家であり学者であるクヌースは[4]、文芸的プログラミングのコンセプトを生み出し、そのためのプログラミングシステム WEB / CWEB を開発。また、MIX / MMIX 命令セットアーキテクチャを設計。
生い立ち
ウィスコンシン州ミルウォーキー生まれ。父は小さな印刷会社を経営し、近くの高校で簿記の講師をしており、その高校にクヌースも進学した。高校2年生のとき、"Ziegler's Giant Bar" という文字列から文字を取り出して組み合わせ、どれだけ意味のある単語を作れるかというコンテストが行われた。審査員が事前に用意した回答例は2500語だったが、クヌースは4500語も見つけ出すという才能を発揮し優勝した。賞品として学校にテレビ受像機が贈られ、クラス全員にキャンディバーが配られた[5]。大学教育と初期の職歴
大学進学にあたって、音楽と物理学のどちらを選ぶかで悩んだ末、ケース工科大学︵現在はケース・ウェスタン・リザーブ大学︶で物理学を学ぶことにした。ケース工科大学で物理学を学んでいた頃、初期のコンピュータの一つである IBM 650 と出会う。そのマニュアルを読んだクヌースは、自分ならもっとうまくできると信じ、アセンブラとコンパイラのコードを書き換えることを決心した[6]。1958年、大学のバスケットボールのチームがリーグ優勝するのを助けるため、クヌースは各選手の能力に基づいたプログラムを構築した。これは当時あまりにも画期的だったため、ニューズウィーク誌に記事が掲載され、CBSイブニングニュースでウォルター・クロンカイトも取り上げた[6]。Engineering and Science Review という技術専門誌の立ち上げに編集者として参加しており、同誌は1959年に技術誌の国家的な賞を受賞している[7]。その頃物理学から数学に転向し、1960年には、ずば抜けた成果により学士号と修士号を同時に与えられた[6]。 1963年、カリフォルニア工科大学で数学の博士号を取得し[8]、同大学で準教授として働き始め、そこで The Art of Computer Programming の執筆を開始した。元々はコンパイラに関する本の執筆を依頼されたのだが、それが The Art of Computer Programming という大作になってしまった。当初1冊で完結する予定だったが、それが6部作となり、さらに7部作へと構想が膨らんでいった。第1巻を出版する直前の1968年、プリンストン大学キャンパスにあった Institute for Defense Analyses (IDA) の通信研究部門を通してアメリカ国家安全保障局 (NSA) の仕事を請け負う職に就いた。しかし、その仕事はクヌースの政治信条には合わなかったようで、間もなくスタンフォード大学に移った。執筆
The Art of Computer Programming (TAOCP)
詳細は「The Art of Computer Programming」を参照
当時、計算機科学は第一歩を恐る恐る踏み出したばかりで、クヌースは﹁それは正体不明の全く新しい領域だった﹂と述べている。さらに﹁入手可能な出版物の水準はあまり高いとは言えなかった︵中略︶。多くの論文が単に全く間違っていた。︵中略︶だから私はひどい形で語られていることを真っ直ぐなストーリーに置き直すことを動機とした﹂と述べている。
1976年に第3巻を刊行後、当時新しく開発された電子出版ツールに不満を持ち、TeX と METAFONT を自ら開発することとなった。
2012年現在、最初の3巻と第4巻の第1部が出版済みである[9]。
クヌースの賞金小切手︵一部ボカシ入︶
●彼は自身の著作の間違いやタイポに対して 2.56ドルを支払うとしている。この金額は256ペニーが1︵16進数︶ドルになるということで決められた。また、﹁価値ある示唆﹂に対しては0.32ドルを支払う。なお、3:16 Bible Texts Illuminated の間違いに関しては 3.16ドルを支払うことになっている。MIT の Technology Review によれば、これらの賞金の小切手は﹁コンピュータ界の最高の栄誉﹂だという。ただし2008年、実際の小切手を送ることは止め、架空の銀行 "Bank of San Serriffe" から預金証明書を送ることにした[15]。
●彼は自身のソフトウェアに﹁上記コードのバグに注意; 正しいことは確認したが使ってみたことはない﹂と警告を入れたことがある[16]。
●Concrete Mathematics の序文より: クヌースが Concrete Mathematics をスタンフォードで最初に教えたとき、彼はその奇妙なタイトルについて﹁この数学コースは決してソフトではない﹂という意味であると説明した。実際、誤解した土木工学などの学生が講義室にやってきて、静かに帰っていったという。
●クヌースは1957年、"Potrzebie System of Weights and Measures"︵度量衡のPotrzebieシステム︶というタイトルで学内雑誌に科学論文を発表した。その中で長さの基本単位を MAD誌︵アメリカのユーモア雑誌︶の26号の厚さとし、力の基本単位を "whatmeworry" とした。MAD誌はこの記事を買い取り、1957年6月号 (#33) に掲載した。
●クヌースの "The Complexity of Songs"︵歌の計算複雑性︶という論文は計算機科学の学会誌に2回掲載された。
●The Art of Computer Programming 第3巻の索引には "Royalties, use of, 405" という行がある。しかし405ページを見ても著作権使用料 (Royalty) に関する記述はなく、図2として "organ-pipe arrangement"︵オルガン-パイプ配置︶の図がある。彼の自宅のパイプオルガンは同書の著作権使用料で購入したのであった[17]。
●TeX のバージョン番号は、3, 3.1, 3.14, … というように円周率 π に近づいている。METAFONTのバージョン番号は同様にネイピア数 eに近づいている。
●Computers and Typesetting シリーズの全ての付録は、付録を識別する文字から始まるタイトルになっている。
●TUG 2010 Conference にて、クヌースは XML をベースとしたTeXの後継 "iTeX" を発表した。任意の縮尺の無理数単位、3Dプリンティング、アニメーション、ステレオ音声などをサポートするとしている[18][19]。
他の業績
他に﹃超現実数﹄(Surreal Numbers) という本も執筆している[10]。ジョン・ホートン・コンウェイの集合論に基づいて代替の数体系を構築するという数学的小説である。この本は単に主題をそのまま説明するのではなく、数学の発展過程を示すことに努めている。クヌースはこの本を読んだ学生がオリジナルの創造的研究を行うことを望んでいる。信仰と宗教的業績
クヌースの他の著作として 3:16 Bible Texts Illuminated がある[11]。これは聖書に層化抽出法を適用するという試みをしたもので、それぞれの本の3章、韻文16を抜き出して解析している。それぞれの節を美しく効果的に見せるため、ヘルマン・ツァップの指揮でカリグラファー達が協力した。クヌースはルター派である[12]。健康問題
2006年、前立腺癌を患っている。同年12月に手術を受け、放射線療法を受けているが予後はかなり良好だと動画にて報告している[13]。Computer Musings
名誉教授となった今も、年に数回スタンフォード大学で非公式の講義を行っている。彼はこれを Computer Musings と呼ぶ。また、オックスフォード大学コンピュータ研究所の客員教授であり、同大学モードリン・カレッジの名誉フェローでもある[14]。クヌースのユーモア
クヌースはプログラマとしても有名で、専門的ユーモアでも知られている。受賞歴と栄誉
●1971年 - 第1回 ACM グレース・ホッパー賞 ●1974年 - チューリング賞 ●1979年 - アメリカ国家科学賞 ●1988年 - フランクリン・メダル ●1995年 - IEEE フォン・ノイマンメダル ●1995年 - ハーヴェイ賞︵テクニオン︶[20] ●1996年 - 京都賞先端技術部門 ●1998年 - コンピュータ歴史博物館フェロー ●2009年 - 片柳コンピュータ科学賞片柳優秀研究賞[21] ●2010年 - BBVA Foundation Frontiers of Knowledge Award[22] ●2011年 - Hero Award︵スタンフォード大学工学部︶[23] クヌースの計算機科学への貢献に敬意を表し、1990年、彼は﹁プログラミング技法の教授; Professor of the Art of Computer Programming﹂という唯一の称号を与えられた︵現在では﹁名誉教授﹂に変更されている︶。 1992年、クヌースはフランスの科学アカデミーの準会員となった。同年教授職を引退し、The Art of Computer Programming の完成に専念するようになった。2003年、イギリスの王立協会の外国人会員に選ばれた。 2009年、アメリカ応用数理学会 (SIAM) の特別フェローに選ばれた[24]。Norwegian Academy of Science and Letters の会員でもある[25]。著作
主な著作を以下に示す[26]。- The Art of Computer Programming, Volumes 1–4, Addison-Wesley Professional
- Volume 1: Fundamental Algorithms (3rd edition), 1997. Addison-Wesley Professional, ISBN 0-201-89683-4
- 『基本算法 基礎概念』広瀬健訳 サイエンス社 1978年(第二版対応)
- 『基本算法 情報構造』米田信夫,筧捷彦共訳 サイエンス社 1978年(第二版対応)
- 『Fundamental algorithms 日本語版』有澤誠,和田英一監訳 青木孝他訳、アスキー、2004年
- Volume 2: Seminumerical Algorithms (3rd Edition), 1997. Addison-Wesley Professional, ISBN 0-201-89684-2
- 『準数値算法 乱数』渋谷政昭訳 サイエンス社 1981年(第二版対応)
- 『準数値算法 算術演算』中川圭介訳 サイエンス社 1986年(第二版対応)
- 『Seminumerical algorithms 日本語版』有澤誠,和田英一監訳、斎藤博昭他訳、アスキー 2004年
- Volume 3: Sorting and Searching (2nd Edition), 1998. Addison-Wesley Professional, ISBN 0-201-89685-0
- 『Sorting and searching 日本語版』有澤誠,和田英一監訳 石井裕一郎,伊知池宏,小出洋,高岡詠子,田中久美子,長尾高弘訳 アスキー 2006年
- Volume 4A: Combinatorial Algorithms, Part 1, 2011. Addison-Wesley Professional, ISBN 0-201-03804-8
- Volume 4: Combinatorial Algorithms (remainder), 準備中
- Volume 5: Syntactic Algorithms, 準備中, 2015年に出版可能になる予定 [27]
- The Art of Computer Programming, fascicles(分冊):
- Volume 1, Fascicle 1: MMIX—A RISC Computer for the New Millennium, 2005. ISBN 0-201-85392-2
- 『MMIX-a risc computer for the new millennium 日本語版』有澤誠,和田英一監訳 青木孝訳 アスキー 2006年
- Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions. 2008. ISBN 0-321-53496-4
- 『Introduction to Combinatorial Algorithms and Boolean Functions 日本語版』和田英一訳 アスキー 2009年
- Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. 2009. ISBN 0-321-58050-8
- 『Bitwise Tricks & Techniques; Binary Decision Diagrams 日本語版』 和田英一訳 アスキー 2011年
- Volume 4, Fascicle 2: Generating All Tuples and Permutations, 2005. ISBN 0-201-85393-0
- 『Generating all tuples and permutations 日本語版』有澤誠,和田英一監訳 小出洋訳 アスキー 2006年
- Volume 4, Fascicle 3: Generating All Combinations and Partitions, 2005. ISBN 0-201-85394-9
- 『Generating all combinations and partitions 日本語版』有澤誠,和田英一監訳 筧一彦訳 アスキー 2008年
- Volume 4, Fascicle 4: Generating All Trees—History of Combinatorial Generation, 2006. ISBN 0-321-33570-8
- 『Generating all trees-history of combinatorial generation 日本語版』有澤誠,和田英一監訳 筧一彦,小出洋訳 アスキー 2010年
- Computers & Typesetting:[28]
- Volume A, The TeXbook (Reading, Massachusetts: Addison-Wesley, 1984), x+483pp. ISBN 0-201-13447-0
- 『TEXブック コンピュータによる組版システム』鷺谷好輝訳 アスキー 1989年
- Volume B, TeX: The Program (Reading, Massachusetts: Addison-Wesley, 1986), xviii+600pp. ISBN 0-201-13437-3
- Volume C, The METAFONTbook (Reading, Massachusetts: Addison-Wesley, 1986), xii+361pp. ISBN 0-201-13445-4
- 『METAFONTブック タイポグラファのためのプログラミング言語』鷺谷好輝訳 アスキー 1994年
- Volume D, METAFONT: The Program (Reading, Massachusetts: Addison-Wesley, 1986), xviii+566pp. ISBN 0-201-13438-1
- Volume E, Computer Modern Typefaces (Reading, Massachusetts: Addison-Wesley, 1986), xvi+588pp.
- Literate Programming[30] (Stanford, California: Center for the Study of Language and Information — CSLI Lecture Notes, no. 27), 1992. ISBN 0-937073-80-6
- 『文芸的プログラミング』有沢誠訳 アスキー 1994.3
- Selected Papers on Computer Science[31] (Stanford, California: Center for the Study of Language and Information — CSLI Lecture Notes, no. 59), 1996. ISBN 1-881526-91-7
- Digital Typography[32] (Stanford, California: Center for the Study of Language and Information — CSLI Lecture Notes, no. 78), 1999. ISBN 1-57586-010-4
- Selected Papers on Analysis of Algorithms[33] (Stanford, California: Center for the Study of Language and Information — CSLI Lecture Notes, no. 102), 2000. ISBN 1-57586-212-3
- Selected Papers on Computer Languages[34] (Stanford, California: Center for the Study of Language and Information — CSLI Lecture Notes, no. 139), 2003. ISBN 1-57586-381-2 (cloth), ISBN 1-57586-382-0 (paperback)
- Selected Papers on Discrete Mathematics[35] (Stanford, California: Center for the Study of Language and Information — CSLI Lecture Notes, no. 106), 2003. ISBN 1-57586-249-2 (cloth), ISBN 1-57586-248-4 (paperback)
- Selected Papers on Design of Algorithms[36] (Stanford, California: Center for the Study of Language and Information — CSLI Lecture Notes, no. 191), 2010. ISBN 1-57586-583-1 (cloth), ISBN 1-57586-582-3 (paperback)
- Selected Papers on Fun and Games[37] (Stanford, California: Center for the Study of Language and Information — CSLI Lecture Notes, no. 192), 2011. ISBN 978-1-57586-585-0 (cloth), ISBN 978-1-57586-584-3 (paperback)
- Companion to the Papers of Donald Knuth[38] (Stanford, California: Center for the Study of Language and Information — CSLI Lecture Notes, no. 202), 2011. ISBN 978-1-57586-635-2 (cloth), ISBN 978-1-57586-634-5 (paperback)
- Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics: A foundation for computer science (Second ed.). Reading, MA: Addison-Wesley Publishing Company. pp. xiv+657. ISBN 0-201-55802-5. MR1397498
- Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. 1974, ISBN 0-201-03812-9.[39]
- The Stanford GraphBase: A Platform for Combinatorial Computing (New York, ACM Press) 1993. second paperback printing 2009. ISBN 0-321-60632-9
- 3:16 Bible Texts Illuminated (Madison, Wisconsin: A-R Editions), 1990. ISBN 0-89579-252-4
- Things a Computer Scientist Rarely Talks About (Center for the Study of Language and Information — CSLI Lecture Notes no 136), 2001. ISBN 1-57586-326-X
- 『コンピュータ科学者がめったに語らないこと』滝沢徹,牧野祐子,富澤昇訳 エスアイビー・アクセス 2003年
- Mathematical Writing 1989年(共著)
- 『クヌース先生のドキュメント纂法』有沢誠訳 共立出版 1989年
- Mmixware: A Risc Computer for the Third Millennium 2000年
- 『MMIXware 第三千年紀のためのRISCコンピュータ』滝沢徹訳 エスアイビー・アクセス 2001年
- 『クヌース先生のプログラム論』有沢誠編 共立出版 1991年(日本オリジナル編集)
脚注
(一)^ Knuth, Don. “Knuth: Frequently Asked Questions”. Don Knuth's home page. Stanford University. 2010年11月2日閲覧。 “How do you pronounce your last name? Ka-NOOTH.”
(二)^ Donald Knuth's Homepage at Stanford.
(三)^ The Art of Computer Programming (Stanford University).
(四)^ Knuth's CV
(五)^ Dennis Elliott Shasha; Cathy A. Lazere (1998). Out of their minds: the lives and discoveries of 15 great computer scientists. Springer. p. 90. ISBN 978-0-387-98269-4
(六)^ abcThomas Koshy (2004). Discrete mathematics with applications. Academic Press. p. 244. ISBN 978-0-12-421180-3 2011年7月30日閲覧。
(七)^ History of Beta Nu Chapter
(八)^ Finite Semifields and Projective Planes – Donald Knuth's Ph.D. dissertation
(九)^ Knuth, Donald E.. “The Art of Computer Programming (TAOCP)”. 2012年5月20日閲覧。
(十)^ Knuth, Donald (1974). Surreal numbers : how two ex-students turned on to pure mathematics and found total happiness : a mathematical novelette. Addison-Wesley. ISBN 978-0-201-03812-5
(11)^ Knuth, Donald (1991). 3:16 : Bible texts illuminated. A-R Eds.. ISBN 978-0-89579-252-5
(12)^ Love at First Byte. Stanford Magazine, May/June 2006.
(13)^ “Donald Knuth: 85 - Coping with cancer”. Web of Stories (2006年4月). 2012年5月2日閲覧。
(14)^ “Professor Donald Knuth”. Magdalen College. 2010年12月6日閲覧。
(15)^ MITの Technology Reviewの"Rewriting the Bible in 0's and 1's"
(16)^ Knuth, Don. “Knuth: Frequently Asked Questions”. Don Knuth's home page. Stanford University. 2010年11月2日閲覧。
(17)^ "Pipe Organ" at Stanford site
(18)^ クヌースの許可を得て、録画した動画が River Valley TV で公開されている。
(19)^ Knuth, Donald (2010). “An Earthshaking Announcement”. TUGboat 31 (2): 121–124. ISSN 0896-3207.
(20)^ http://www.admin.technion.ac.il/harvey/1995-2.html
(21)^ http://www.cs.cmu.edu/~katayanagi/
(22)^ http://www.fbbva.es/TLFU/tlfu/ing/microsites/premios/fronteras/galardonados/2010/informacion.jsp
(23)^ Andrew Myers (2001年6月1日). “Stanford's Don Knuth, a pioneering hero of computer programming”. Stanford Report 2011年6月27日閲覧。
(24)^ http://fellows.siam.org/index.php?sort=year&value=2009
(25)^ “Gruppe 1: Matematiske fag” (Norwegian). Norwegian Academy of Science and Letters. 2010年10月7日閲覧。
(26)^ 完全な著作リストは "Books" at Stanford site にある。
(27)^ http://www-cs-faculty.stanford.edu/~uno/taocp.html
(28)^ 完全なリストは "Books" at Stanford site にある。
(29)^ "Selected Papers" at Stanford site
(30)^ "Literate Programming"
(31)^ "Selected Papers on Computer Science"
(32)^ "Digital Typography"
(33)^ "Selected Papers on Analysis of Algorithms"
(34)^ "Selected Papers on Computer Languages"
(35)^ "Selected Papers on Discrete Mathematics"
(36)^ "Selected Papers on Design of Algorithms"
(37)^ "Selected Papers on Fun and Games"
(38)^ "Companion to the Papers of Donald Knuth"
(39)^ the book's official homepage
インタビューなど
- Woehr, J. An interview with Donald Knuth Dr. Dobb's Journal, 1996年4月, p. 16-22.
- Donald Knuth on The Art of Computer Programming Addison-Wesley Innovations, 1996年
- Knuth meets NTG members, アムステルダム, 1996年3月13日
- Knuth Comments on Code, Byte magazine, 1996年9月
- Donald Knuth: A life's work in the art of programming Amazon.com, 1997年
- Wallace, Mark. The art of Don E. Knuth salon.comによるインタビュー, 1999年
- TUG'95 (St Petersburg, FL, USA) Questions and answers with Prof. Donald E. Knuth. TUGboat 17 (1), 1996年
- Advogato, 2000 TUGboat 21 (2), 2000年
- U.K. TUG, Oxford, 12 September 1999:Question & Answer Session with Donald Knuth. TUGboat, 22 (1/2), 2001年
- Oslo, 2002 TUGboat 23 (3/4), 2002年
- AMS, 2001
- Geek Celebs, 2001
- c't, 2002
- Donald Knuth, Founding Artist of Computer Science. David Kestenbaum による National Public Radio でのインタビューの録音; または 書き起こしたもの, 2005年3月14日
- Free Software Magazine interview by Gianluca Pignalberi, August 2005.
関連項目
外部リンク
- クヌースのホームページ スタンフォード大学
- Oral history interview with Donald E. Knuth at Charles Babbage Institute, University of Minnesota.
- “Love at First Byte,” Kara Platoni, with photography by Timothy Archibald, STANFORD Magazine, May/June 2006. A retrospective of Knuth’s life and work, with some rare, recent photos.
- Knuth ドナルド・クヌース - Mathematics Genealogy Project
- O'Connor, John J.; Robertson, Edmund F., “Donald Knuth”, MacTutor History of Mathematics archive, University of St Andrews.
- 図書館にあるDonald Knuthに関係する蔵書一覧 - WorldCatカタログ
- Donald Knuth's Stanford lectures archive
- Donald Knuth: Leonard Euler of Computer Science (Softpanorama)
- The Potrzebie System of Weights and Measures