ドナルド・クヌース

ドナルド・クヌースはウィスコンシン州ミルウォーキーで、アーヴィン・ヘンリー・クヌースとルイーズ・マリー・ボーニングの間に生まれた。 ^{[ 6 ]}彼は自身の出自を「中西部のルーテル派ドイツ人」と表現している。^{[ 7 ] : 66}彼の父親は小さな印刷会社を経営し、簿記を教えていた。^{[ 8 ]}ミルウォーキー・ルーテル高校の生徒だった頃、クヌースは独創的な方法で問題を解決しようと考えた。例えば、8年生の時、「Ziegler's Giant Bar」 ^{[ 9 ]}の文字を並べ替えて作れる単語の数を調べるコンテストに参加した。審査員は2,500個の単語を特定していた。クヌースは腹痛を装って学校を休んだ時間を利用して、完全版の辞書を使い、各辞書の項目がフレーズの文字を使って作れるかどうかを調べた。彼は4,500個以上の単語を特定し、コンテストで優勝した。^{[ 7 ] : 3}賞品として、学校は新しいテレビと、彼のクラスメート全員が食べられるだけのキャンディーバーを受け取った。^{[ 10 ] [ 11 ]}

クヌースは、1956年にオハイオ州クリーブランドのケース工科大学（現在はケース・ウェスタン・リザーブ大学の一部）に物理学の奨学金を得て入学した。 ^{[ 12 ]}また、シータ・カイ友愛会のベータ・ニュー支部にも入会した。ケースで物理学を学んでいたクヌースは、初期の商用コンピュータであるIBM 650に出会った。コンピュータのマニュアルを読んだ後、クヌースは自分の学校で使用されていたマシンのアセンブリコードとコンパイラコードを書き直すことにした。自分の方がうまく書けると思ったからである。^{[ 13 ]}

1958年、クヌースは学校のバスケットボールチームが試合に勝つためのプログラムを作成しました。^{[ 14 ]}彼は選手に「値」を割り当てて得点する確率を測りました。これは斬新なアプローチで、後にニューズウィークやCBSイブニングニュースが報じました。^{[ 13 ]}

クヌースは、ケース・インスティテュートの『エンジニアリング・アンド・サイエンス・レビュー』の創刊編集者の1人であり、同誌は1959年に最優秀技術雑誌として全国的な賞を受賞した。^{[ 15 ] [ 16 ]}その後、彼は物理学から数学に転向し、1960年にケースから2つの学位を取得した。^{[ 12 ]}理学士号と、同時に、彼の業績が非常に優れていると評価された教員からの特別賞による理学修士号である。^{[ 4 ] [ 13 ]}

1960年、ケース・ウェスタン・リザーブ大学の最終学年を終える頃、クヌースはバロウズ社にB205用のALGOLコンパイラを5,500ドルで開発することを提案した。この提案は受け入れられ、彼はケース・ウェスタン・リザーブ大学卒業後からカリフォルニア工科大学に進学するまでの間、ALGOLコンパイラの開発に取り組んだ。^{[ 7 ] : 66 [ 17 ] : 7}

1963年、数学者のマーシャル・ホールを指導教官として、カリフォルニア工科大学から数学の博士号を取得した。 ^{[ 2 ]}博士論文のタイトルは「有限半体と射影平面」である。^{[ 18 ]}

1963年、クヌースは博士号を取得後、カリフォルニア工科大学の助教授として教員に加わった。^{[ 19 ]}

カリフォルニア工科大学在籍中、そしてバローズB205 ALGOLコンパイラの成功後、彼はバローズ社のコンサルタントとなり、製品企画部に加わった。カリフォルニア工科大学では数学者として活動していたが、バローズ社ではプログラマーとして、当時最高のソフトウェアを開発したと彼が考えていた人々、すなわちB205の後継機であるB220コンピュータ用のALGOLコンパイラの開発に携わった。^{[ 7 ]： 9}

クヌースはグリーンツリー社からコンパイラ開発の10万ドルの契約を提示されたが、これを断り、収入を最大化するためにカリフォルニア工科大学とバロウズ社での仕事を続けることを決めた。彼は全米科学財団フェローシップとウッドロー・ウィルソン財団フェローシップを受給したが、受給者は大学院生として研究に専念しなければならないという条件が付いていたため、バロウズ社のコンサルタントを続けることはできなかった。彼はフェローシップを辞退し、バロウズ社での仕事を続けることを選んだ。^{[ 7 ]： 12} 1962年の夏、彼はユニバック社のためにFORTRANコンパイラを開発したが、FORTRANコンパイラを開発するために「悪魔に魂を売った」と考えていた。^{[ 7 ]： 15}

卒業後、クヌースは1961年6月にバロウズ社に戻ったが、期待されていた学士号ではなく修士号を取得して卒業したことを彼らには伝えなかった。ALGOLの構文表、シンボルテーブル、再帰下降方式、そしてコンパイラのスキャン、構文解析、出力機能の分離に感銘を受けたクヌースは、シンボルテーブルの拡張として、1つのシンボルでシンボルの文字列を表すことができるというアイデアを提案した。これがバロウズALGOLのDEFINEの基礎となり、その後他の言語にも採用された。しかし、このアイデアを非常に嫌う者もおり、DEFINEの削除を求めた。このアイデアをひどいものだと考えた最後の人物は、バロウズ社を訪れたエドガー・ダイクストラであった。 ^{[ 17 ]： 17}

クヌースはバロウズでシミュレーション言語に取り組み、J. マクニーリーと共同で設計した、最先端技術を改良した SOL 'Simulation Oriented Language' を開発した。彼は 1967 年 5 月にノルウェーで開催された、Simula 言語を発明した人々が主催する会議に出席した。クヌースはバロウズに Simula を使用するよう影響を与えた。^{[ 20 ] [ 21 ]}クヌースは 1960 年から 1968 年までコンサルタントとしてバロウズと長く関わり、1969 年にスタンフォードでより学術的な仕事に移った。^{[ 22 ] [ 23 ]}

1962年、クヌースはアディソン・ウェスリー社からコンピュータプログラミング言語コンパイラに関する書籍の執筆依頼を受けた。このプロジェクトに取り組む中で、彼はまずコンピュータプログラミングの基礎理論を構築しなければこのテーマを十分に扱うことはできないと判断し、それが『コンピュータプログラミングの技法』となった。当初は1冊の本として出版する予定だったが、本の構成を練るうちに、このテーマを徹底的に扱うには6巻、そして7巻が必要だと結論づけた。彼は1968年に第1巻を出版した。^{[ 24 ]}

『コンピュータプログラミングの技法』の第1巻を出版する直前、クヌースはカリフォルニア工科大学を離れ、当時プリンストン大学キャンパスにあった国防分析研究所の通信研究部門に就職した^{[ 25 ]}。同部門は国家安全保障局を支援するために暗号学の数学的研究を行っていた。

1967年、クヌースは応用数理学会の会議に出席し、そこで誰かに何をしているのかと尋ねられた。当時、コンピュータ科学は数値解析、人工知能、プログラミング言語に分かれていた。クヌースは自身の研究と著書『コンピュータプログラミングの技法』に基づいて、次に誰かに尋ねられたら「アルゴリズム解析」と答えることに決めた。^{[ 26 ]}

1969年、クヌースはプリンストン大学の職を辞し、スタンフォード大学の教員となり、^{[ 27 ]} 1977年にフレッチャー・ジョーンズ記念コンピュータサイエンス教授に就任した。1990年にはコンピュータプログラミングの芸術教授となり、1993年からは名誉教授である。^{[ 28 ] [ 29 ]}

「人間同士がコミュニケーションをとる最良の方法は、物語を通してである。」

1970年代、クヌースはコンピュータサイエンスを「明確なアイデンティティを持たない全く新しい分野」と呼んだ。「入手可能な出版物の水準はそれほど高くなく、発表される論文の多くは単純に間違っていた。... だから私の動機の一つは、ひどく誤って伝えられてきた話を正すことだった。」^{[ 30 ]}

1972年から1973年にかけて、クヌースはオーレ＝ヨハン・ダールなどの人々と共にオスロ大学で1年間を過ごした。当初、彼はここでプログラミング言語を扱う予定だった著書シリーズの第7巻を執筆するつもりだった。しかし、オスロに来た時点でクヌースは最初の2巻しか完成させておらず、そのため1年間は教鞭を執りながら第3巻の執筆に費やした。第3巻は、クヌースが1973年にスタンフォード大学に戻った直後に出版された。^{[ 31 ]}

『Concrete Mathematics: A Foundation for Computer Science』は、『 TAoCP』第1巻の数学的予備知識のセクションを拡張することから始まった。クヌースは、第1巻に必要な数学的ツールが自身の知識には欠けていることに気づき、それらのツールをコンピュータサイエンスの学生に紹介するコースが有用だと考えた。クヌースは1970年にスタンフォード大学でこのコースを開設した。オレン・パタシュニクが作成した講義ノートは、ロナルド・グラハム、クヌース、パタシュニクの共著による1988年のテキストへと発展した。 『Concrete Mathematics』の第2版は1994年に出版された。

2011年までにTAoCPの第4A巻が出版された。^{[ 24 ]} 2020年4月、クヌースはTAoCPの第4巻には少なくともA部からF部が含まれると予想していると述べた。 ^{[ 26 ]}第4B巻は2022年10月に出版された。

クヌースはまた、『超現実数』^{[ 32 ]}の著者でもある。これは、ジョン・ホートン・コンウェイによる別の数体系の集合論的構築に関する数学的な短編小説である。この本は単に主題を説明するのではなく、数学の発展を示すことを目的としている。クヌースはこの本を通して、学生が独創的で創造的な研究を行うための準備をさせたいと考えていた。

1995年、クヌートはマルコ・ペトコフシェク、ハーバート・ウィルフ、ドロン・ツァイルベルガー共著の『 A=B』の序文を執筆した。^{[ 33 ]}また、時折『Word Ways: The Journal of Recreational Linguistics』に言語パズルを寄稿している。^{[ 34 ]}

クヌースはレクリエーション数学に深く関わってきた。彼は1960年代から『 Journal of Recreational Mathematics』に記事を寄稿し、ジョセフ・マダキーの『Mathematics on Vacation』では主要な貢献者として認められた。^{[ 35 ]}

クヌースは、 YouTubeのNumberphile ^{[ 36 ]}やComputerphile の動画にも多数出演しており、そこで彼は、超現実数の書き方^{[ 37 ]}から、なぜ電子メールを使わないのか^{[ 38 ]まで、さまざまなトピックについて語っている。}

クヌースは、コンピュータ科学の分野に「アルゴリズム学」という名称の方がより適切だと提案した。 ^{[ 39 ]}

クヌースは安定マッチング問題の研究に多大な貢献をした。^{[ 40 ]}

ルター派のクヌースは、コンピュータ科学に関する著作に加えて、^{[ 41 ]}『3:16 Bible Texts Illuminated』^{[ 42 ]}の著者でもあり、この中で彼は、体系的なサンプリング、つまり各書の第 3 章第 16 節の分析というプロセスで聖書を考察している。各節には、ヘルマン・ツァップ率いる書道家グループによる書道作品が添えられている。クヌースは、3:16 プロジェクトの背景にある宗教とコンピュータ科学に関する見解について MIT で一連の講義を行うよう招待され、その結果、別の著書『Things a Computer Scientist Rarely Talks About』が出版され、その中で彼は「神とコンピュータ科学」という講義を発表した。^{[ 43 ]}

クヌースは、自明であるべき些細な解決策にソフトウェア特許を与えることに強く反対しているが、線形計画法の内点法のような非自明な解決策については、より微妙な見解を示している。^{[ 44 ]}彼は米国特許商標庁と欧州特許機構の両方に直接反対意見を表明している。^{[ 45 ] [ 46 ]}

1970年代、TAOCPの出版社はモノタイプを放棄し、写真植字を採用した。クヌースは、旧システムで組版された以前の巻の品質に、このシステムが到底及ばないことに非常に不満を感じ、デジタル組版に取り組むために時間を割き、TeXとMetafontを作成した。^{[ 47 ]}

TeXの開発中に、クヌースはプログラミングの新しい方法論を生み出した。彼はそれを「リテラシープログラミング」と呼んだ。なぜなら、プログラマーはプログラムを文学作品のように考えるべきだと考えていたからだ。

私たちの主な仕事はコンピュータに何をすべきかを指示することだと考えるのではなく、むしろコンピュータに何をしてほしいかを人間に説明することに集中しましょう。^{[ 48 ]}

クヌースは、 WEBシステムにおいてリテラル プログラミングの考え方を具体化した。同じ WEB ソースを使用してTeX ファイルを生成し、 Pascalソースファイルを絡め取る。これらはそれぞれ、プログラムの読みやすい記述と実行可能なバイナリを生成する。システムの後のイテレーションであるCWEBでは、Pascal がC、C++、およびJavaに置き換えられている。^{[ 49 ]}

Knuth は WEB を使用して TeX と METAFONT をプログラミングし、両方のプログラムを書籍として出版しました。どちらも元々は同じ年に出版されました。TeX : The Program (1986) とMETAFONT: The Program (1986) です。^{[ 50 ]} ほぼ同時期に、現在広く採用されている TeX ベースのマクロパッケージであるLaTeXがLeslie Lamportによって最初に開発され、後に 1986 年に最初のユーザーマニュアルが出版されました。^{[ 51 ]}

クヌースは、著書の中で見つかった誤植や間違いに対して、2.56ドルの謝礼金を支払っていた。「256セントが16進数で1ドルだから」という理由からである。また、「貴重な提案」に対しては0.32ドルを支払っていた。マサチューセッツ工科大学のテクノロジーレビュー誌の記事によると、これらのクヌースの謝礼金は「コンピュータ界で最も貴重なトロフィーの一つ」である。クヌースは、銀行詐欺のため2008年に実際の小切手を送るのをやめざるを得なくなり、現在は、架空の「サン・セリフ銀行」の公開残高から、各誤り発見者に「預金証書」を渡している。^{[ 59 ]}

彼はかつて通信員に「上記のコードにはバグがあるかもしれないので注意してください。私はそれが正しいことを証明しただけで、試したことはありません」と警告したことがある。^{[ 3 ]}

クヌートは1957年に学校雑誌に「ポトシェビエ度量衡システム」というタイトルの最初の「科学的」論文を発表した。その中で彼は長さの基本単位をMad No. 26の厚さと定義し、力の基本単位を「whatmeworry」と名付けた。Mad誌は1957年6月号の第33号にこの論文を掲載した。^{[ 60 ] [ 61 ]}

再帰の概念を説明するために、クヌースは『コンピュータプログラミングの技法』第1巻の索引で「循環定義」と「循環定義」を意図的に相互に参照させた。

『具体数学』 の序文には、次の段落がある。

DEKがスタンフォード大学で初めて「コンクリート数学」という講義を担当した際、彼はそのやや奇妙なタイトルについて、軟弱な数学ではなく、より難解な数学の授業を開こうとした試みだと説明した。そして、同僚たちの予想に反して、集合体理論も、ストーンの埋め込み定理も、ストーン＝チェフのコンパクト化も教えないと発表した。（土木工学科の学生数名が立ち上がり、静かに教室を出て行った。）

TUG 2010 カンファレンスで、クヌースは、TeX の後継となるXMLベースの風刺的なソフトウェア「iTeX」（ [ iː˨˩˦tɛks˧˥⸨bell⸩ ]と発音され、ベルを鳴らしながら発音される）を発表した。このソフトウェアは、任意にスケーリングされた無理数単位、3D 印刷、地震計や心拍モニターからの入力、アニメーション、ステレオ音声などの機能をサポートする予定である。^{[ 62 ] [ 63 ] [ 64 ]}