ドナルド・クヌース：リチャード・ファインマン、賞、ILCアルゴリズムについて

クヌートはグレースマレーホッパー賞を初めて受賞しました 。 フォンノイマン、チューリングメダル、京都賞、米国国立科学メダルなどの業績。







「賞は、他の人があなたの仕事を大切にしていることの確認として、人間の生活において重要な役割を果たすと思います。 ほとんどの場合、私たちの仕事は興味深いという事実にもかかわらず、時にはそれが困難であり、感謝されていることに気付くのは楽しいことです。 したがって、賞のプレゼンテーションは良い伝統です。」



パブリッシングサポート-Edisonは、 重要なシステムのフォールトトレランスをテストし 、クラスターコンピューティング用のソフトウェアを設計および開発しています 。

賞と京都賞の重要性（87/97）

カーター大統領が提示した米国科学賞を受賞することが重要になりました。 リチャードファインマンが米国科学賞を受賞したとき、私はリチャードファインマンと一緒に座ることができました。 そして彼の賞のために上昇する前に、彼は彼の肩で私を微調整し、言った。 これがあなたの重要なポイントです。」 彼は私のヒーローでした。 カリフォルニア工科大学で彼を知っていましたが、この日は私にとって特に重要になりました。



また、イスラエルのハーベイ賞など、コンピューターサイエンスを代表する他の賞も受賞しました。 繰り返しになりますが、これらの賞はコンピューターの専門家だけでなく、化学者、物理学者、生物学者にも利用できます。 さまざまな科学分野の人々。 人文科学にもいくつかの賞が授与されましたが、METAFONTプログラミング言語に取り組んだことで人文科学博士も授与されたことをうれしく思います。 これが私の魂を満足させ、前進する力を与えてくれます。











もちろん、最大の賞は約10年前に受賞した京都賞でした 。 これは最高のコンピューター科学者が望んでいる賞です。 特定の分野で生涯にわたって達成された成果を認識し、3〜4年ごとに授与されます。



当時、私は家族と妻の家族を連れて日本で数週間過ごすことができました。それは私たち全員に良い影響を与えました。 私たちはそこに3週間滞在しましたが、この間に13の異なる科目について13の講義を行い、そのうち8つを準備し、5つの講義を即興で行わなければなりませんでした。



また、日本の天皇と皇后とも会いました。 そして、あなたは知っている、皇后は信じられないほど印象的な人だった。 パズルの最高の専門家であるアイドルノブに会いました。彼らと一緒に熱いお風呂を試し、日本の多くの地域を訪れました。これは人生のもう1つの重要なイベントでした。









吉ヶ原ノブ



[Q]そして、私が間違っていなければ、ミローク小学校で、いわばキャリアの始まりについて興味深い言及があります。 報酬の一部を小学校に寄付しました。



そうそう、あなたは正しい。 京都賞には現金報酬も付いています。 もちろん、これはノーベル賞ではありませんが、それを渡す前に二度考えたことを世界に納得させるのに十分な大きさです。 賞金は約400,000ドルで、ジルと私はこれが私たちの生活を台無しにしたくありませんでした。



お金がなくて幸せだったので、自分たちに任せたらどうなるかわかりませんでしたが、何かが悪いことがわかったのです。 したがって、私たちは家族の旅行に10万ドルを費やし、小学校に100,000ドルを寄付し、1年生から8年生まで勉強し、スタンフォードに10万ドルを寄付し、パロアルトにある教会で新しいオルガンを購入するために10万ドルを費やしました。



ドナルド・クヌースが日本の「ノーベル賞」である京都賞を受賞

Knuth-Morris-Prattアルゴリズム（92/97）

興味深い話がありますが、これまで言及していません。



このアルゴリズムは非常に人気がありますが、過去20年間使用していませんが、多くの教科書で言及されており、膨大なテキストで単語を見つけるには本当に良い方法です。 たとえば、「the」という単語を探している場合、テキスト内の単語を探すのは愚かなことです。 さて、または「ディクラン」という言葉の例を見てみましょう。 テキストの任意のポイントから始めて、「これは「d」ですか？」 はい 次の手紙を検討してください。 それは「i」ですか？ はい 次の「k」？ いいえ、これは、たとえば「方向」という言葉だからです。 次の単語に進み、もう一度確認してください。 最初の文字は「I」ですが、「d」ではありませんか？ 次に、単語をスキップし、次の単語に進み、もう一度確認します...



しかし、たとえば文字が2倍になるなど、より複雑な単語もあります。 バークレーの教授であるスティーブ・クックは、そのような事例に関連する驚くべき理論を提案しました。 彼は、メモリが非常に限られたコンピューターを使用してそのソリューションを作成すると、このソリューションの動作がどれほど遅くても、通常のコンピューター用に高速バージョンを作成できると主張しました。



したがって、このような「制限された」コンピューターで解決しようとした問題の1つは、文字列が回文であるか、むしろ回文の接続カスケードであるかを解決できることでした。 カスケード接続されたパリンドロームに誰も真剣に興味を持っていなかったので、それは私にとってちょうど好奇心が強いものでした。



その結果、クックの定理に従って、限られたコンピューター用のプログラムを作成できた後、通常のコンピューターでそのような回文を認識するためのより高速なソリューションが必要でした。 しかし、私はこれを通常のコンピューターで再現する良い方法を考えることができませんでした。それははるかに難しい仕事であることがわかりました。



当時私は自分を優れたプログラマーと考えていましたが、それが可能であると主張する定理があり、この問題の解決策を思い付くことができませんでした。 これが私の最初の行き止まりでした。 誰かがそれをもっと良くする方法があると言ったが、何も考えられなかった。 そこで、私は自分自身のために夕方を選んで、黒板にクックの解釈を細部にわたって描きました。これは、通常のコンピューターでこのプログラムを高速化する方法についての答えを最終的に与えるはずです。



そして、突然、ここにキャッチがあります。 最終的に、一般的な定理が通常のコンピューターにどのように適合するかというアイデアを思いつきました。これは、テキスト内の検索の問題も解決することに気付きました。 それで、私はバークレーへの旅行でこれについて言及しました、そこで私はヴォーン・プラットに会いました。











彼は研究で最も重要な人物の一人であり、私は後でそれらを説明した人物でした。 後に、ジムモリスが数か月前に同じアイデアを発見し、すでにプログラムでそれらを使用していたことがわかりました。 しかし、他の人が彼のソースコードを見たとき、彼らはそれが何であるか理解していなかったので、彼はそれを削除しなければなりませんでした。



それにもかかわらず、この方法はテキストを見つけるのに非常に効果的です。 さらに、彼はコンピューターサイエンスの基礎を教える上で非常に有益であるため、彼は非常に人気があり、私の名前に関連付けられています。



This Little Miracle-Knuth-Morris-Pratt（CLC）アルゴリズム



翻訳：ニキータシャヴリン

続きを読む

• ドナルドクヌース：私はバックデスクに座って冗談を言ったが、先生たちは我慢しなかった。
  
  
• ドナルド・クヌース：「若者への私のアドバイス」（93/97）および「自分を主張する必要性を感じている」（9/97）
  
  
• 「超現実的な数字」：私は6日間働き、7日目に休みました（40,41,42 / 97）
  
  
• ドナルド・クヌース：プログラミングの芸術はどのように作られたのか（33.38.39 / 97）
  
  
• ドナルド・クヌース：妻、キス、「特定の数学」、そして大学での指導の様子について
• Donald Knuth：第4巻がついにリリースされるのはいつですか
• Donald Knuth：女の子とではなく、コンピューターで夏を過ごした方法（19,20,21,22 / 97）
• Donald Knuth：アセンブラー、翻訳者、有能なプログラミングについて