ドナルド・クヌース：アルゴリズムの分析を始めた経緯と、そのためにソ連に行きました（37.91.97 / 97）

「アンドレイ（エルショフ）、巡礼のようなものを組織することがいかに素晴らしいか想像してください。世界中のプログラマーがホレズムに来て、このコンセプトの誕生を祝うことができます。」

-ドナルド・クヌートはエルショフに国際シンポジウムを開催するよう説得する







クヌートとエルショフ



1967年の秋、数学者の会議がサンタバーバラで開催されました。これはおそらくチャペルヒルでの会議にも出席したのと同じ年だったでしょう。 私は刺激を受けた多くの人々に会い、お互いに話し合うべき多くの興味深い問題がありました。 しかし、サンタバーバラでの会議に参加したとき、これが研究を行う唯一のチャンスであることに気付きました。 私は講義に出席しませんでした。 私はちょうどビーチに座って、会議中に属性文法に関する記事を書きました。 しかし、私は夕食に参加しました。 自分が何をしているのか誰かが私に尋ねたときのことを思い出し、そのときは数学者ではなくプログラマーになることを決めました。



-私はプログラマになるつもりだと思う。

「ああ、数値解析をしますか？」

「そうでもない。」

-ああ、人工知能。

-いいえ、人工知能ではありません。

「では、プログラミング言語で作業している必要がありますか？」

新しい領域-アルゴリズム分析

つまり、最終的にコンパイラに関する本を書くように頼まれました。 実際、当時のプログラミングは、数値解析、人工知能、プログラミング言語の3つの部分で構成されていると考えられていました。 スタンフォード大学の教員も、3つの主要なブロックに分かれていました。 彼らは3つの資格試験などをしました。 しかし、「プログラミング言語の分野で多くの研究を行い、プログラミング言語の雑誌の編集者でしたが、私の主な関心は少し異なります。」と言いました。 そして、私が最も興味を持っているものの名​​前がないことに気付きました。 そして、あなたはそれを何と呼びますか？



その時までに、私はすでに3000ページの「プログラミングの芸術」を書いて、それらのいくつかを印刷して、それらをほとんど出版する準備ができていました。 そして、コンピュータ手法の品質を理解するために数学的な基礎が必要であることが判明しました。 メソッドがどれだけ優れているか、他のメソッドよりも2倍優れているかどうかなどを知りたいと考えました。 「はい、良い」だけでなく、どれだけ改善したのか、理由を説明する必要がありました。 そのため、コンピューターの美徳を評価する方法を見つけるために、これを私の本を統一するメインテーマにすることにしました。 しかし、私は彼の名前を持っていませんでした。



サンタバーバラでの会議で、自分が働いている地域の誰かに説明しようと思ったら、名前をつけるべきだと思いました。 したがって、私はそれをアルゴリズムの分析と呼ぶことにしました。 私は本を​​書いていますが、これが何を意味するのかを人々に説明できます。 出版社と話をして、「本のタイトルを変えましょう。「アルゴリズム分析」と呼びましょう。」



このアイデアは承認されませんでしたが、いずれにせよ、これが私のキャリアであり、主にアルゴリズムの分析に集中することを決定しました。 これは、このアルゴリズムまたはコンピューターメソッドがどれだけ優れているかを判断することを意味します。



1971年に情報処理国際会議で講演を依頼されたことがありました。その講演を「アルゴリズムの分析」と題しました。 また、1970年にフランスで開催された国際数学会議でスピーチをするように依頼され、「アルゴリズムの数学的分析」と名付けました。 人々が私がしていることを理解できるように、私はこの用語を宣伝しようとしました。 そして、10年ほど後、70年代後半に雑誌にコラムが登場し始め、「アルゴリズムの分析」と呼ばれる本が登場し始めたことを報告できてうれしいです。



実際、私の出版社はこの名前を好まなかったという事実にもかかわらず、かなりの数の本が同じようなタイトルを持っています。 しかし、私は何らかの形で自分が働いている地域に名前を付ける必要がありました。 誰かがこれが本当に何を意味するのか説明するように頼んだら、これはまさに私が興味を持っていることだと言うでしょう。

ソ連のアルゴリズムに関する国際シンポジウム

私はアルゴリズム分析を私の人生の仕事にしたいと言った。 「プログラミングの芸術」を書くことを含む私の仕事のほとんどは、アルゴリズムがどれほど良いかを決定する方法を見つけることでした。 私はアルゴリズムの研究が何よりも好きで、そもそも私にとってはいつもそうでした。



「アルゴリズム」という言葉がアラビア語のアル・クワリズミに由来することを知って嬉しかったです。 現在、 ホレズムはウズベキスタンの地域ですが、その後は湖でした。 私は、コレズミ湖と呼ばれていたアラル海を意味します。 これは完全に忘れられている世界の一部です。











イランの地図を見ると、この場所は北にあり、ルーマニアの地図を見ると、東、インドまたはアフガニスタンの地図を見ると、ロシアの西、南がわかりますか？ 彼らは世界のこの部分を忘れてしまいました。 しかし、「アルゴリズム」という言葉、ホレズムがそこから来ていることがわかりました。 アルメニア人が住んでいる場所があり、彼らはそれをアルメニア人ディアスポラと呼んでいますか？ バグダッドにはホレズム地区全体があります。 そして、私は大丈夫、一度ホレズムを訪れるのは面白いだろうと思った。 私はアトラスを覗き込み、恐ろしくなりました。 それはソ連のまさに中心にあります、どうやってそこに着くのですか？！？ この場所に直接つながる道路はありません。



ソビエト科学アカデミーのロシア出身の友人アンドレイ・エルショフにこれを伝えました。 まあ、彼は当時の私の友人ではなかった、私は彼をあまりよく知らなかったが、彼はジョン・マッカーシーの友人であり、私たちは彼の家でパーティーをしていた。 アンドレイに言った：「アルゴリズム」という言葉がソビエト連邦の場所から来ていることを知っていますか？ これに何らかの注意を払う必要があります。 世界中のプログラマーがホレズムに来て、この概念の誕生を祝うことができる巡礼のようなものを組織することがどれほど素晴らしいか想像してみてください。



そして彼は言った：「素晴らしいアイデアのように聞こえる！」 彼は家に戻り、これらすべてを整理する作業を始めました。 彼はソビエト科学アカデミーに、2週間続き、ホレズム地域で開催されるアルゴリズムに関する国際シンポジウムのスポンサーを依頼しました。



ホレズムに着く前でさえ、飛行機を降りたばかりの頃、花を運んだ200人の子供たちに会い、地元のテレビでインタビューを受けました。 誰もが自分の土地にそのような関心を示したのはこれが初めてでした。 中東の人々のおもてなしは驚くべきものです。 実際、オーナーはとても寛大だったので、私は冗談めかして、飼われている女性を私に提供するように頼みました。 そして、私が冗談を言っていることを彼らに保証しなければ、彼らはそうするだろうと確信しています。 Al-Khwarizmiアルゴリズムの作成者がおそらく出身だったヒヴァの独特な都市博物館を訪れることができました。







よくわかりませんが、いずれにせよ、この文化の偉大な遺産を示しているのは保存された都市です。 この会議に出席した人々の半分はソ連出身で、残りの半分は世界各地から来ていました。 アルゴリズムの重要性だけを議論することができます。 この小さな会議を手配し、世界のこのコーナーを見る機会は、私の人生で最大の成果の1つでした。





D.むち踊り



驚くべきことに、私たちはこの村でさまざまな国籍の子供たちに会いました。金髪、青い目、韓国系の人たちです。 私たちは綿の農場に行き、綿を収穫しました。 ホレズムの人々が着る帽子を手に入れました。 アルゴリズムに取り組んでいる今、私は適切な服装をすることができます。

研究分野としてアルゴリズム分析を選んだ理由

書かれた各作品の背後に、私がそれらの多くを書いた後、興味深い物語があります。 アルゴリズム自体は有名になりましたが、私自身は過去20年間使用していません。 しかし、彼はすべての教科書に載っており、有益な例です。



たとえば、特定の単語を見つけるためにテキストから長いパッセージを調べようとする場合に使用するとよいでしょう。 単語the（*英語の記事）またはそのようなものを探しているとします。 この単語を検索するのは愚かなことですが、dikran（* plant dikran）を探しましょう。



明らかに、テキストのあらゆる場所で立ち止まって、「これは文字Dですか？ 素晴らしい。 次の手紙は？ いいね 次はK？ いいえ、これは「方向」という言葉です（*英語からの距離）。 次に、先に進み、このアルゴリズムを繰り返します。 Dですか？ いいえ、これは私であることがすでにわかっています。したがって、さらに先へ進む必要があります。 しかし、それはそれほど単純ではありません。 もっと複雑な言葉があります。 2つの文字Dがある「didymus」（*英語の双子）という単語を探していた場合、アルゴリズムは機能しなくなります。



バークレーの教授であるスティーブクックは、この主題に関して驚くべき定理を持っています。 彼は、能力が非常に限られたコンピューターを使用し、問題を解決するプログラムを作成できる場合、この愚かなコンピューターに対して、このプログラムの動作速度に関係なく、同じものをすばやく書く方法があると主張します通常のコンピューター用のプログラム。



言い換えれば、機能が制限されている特定のコンピューターを使用し、そのコンピューターで問題を解決できる場合は、通常のコンピューターでそれを行う簡単な方法があります。 このコンピューターで解決する必要がある唯一の問題は、文字のセットが回文であるかどうかを判断し、回文のチェーンで同じを回す機能です。



私はただ興味がありました。 実際、パリンドロームの連結には誰も興味がありません。 クックの定理によれば、この面白いコンピューターでこの問題を解決する方法があれば、通常のコンピューターでこれらのパリンドロームの接続をすばやく確認する方法があります。 しかし、私は通常のコンピューターでこれを行う良い方法を考えることができませんでした、それははるかに複雑になるように思えました。



私はかなり優れたプログラマーでしたが、この定理はこれを行う方法があると主張しましたが、その方法はわかりませんでした。 私がこのようなデッドロックに陥ったのはこれが初めてであり、それについて考えることをやめられませんでした。 私は昼と夜を使ってクックの理論を黒板に詳細に描き、最終的にコンピューターでこれを実現するための簡単な方法を見つけました。



突然、私は手がかりを見つけました。 当初は、この一般的な定理を反映するプログラムを作成するという考えでしたが、テキストを検索する問題を解決することもできました。 私はバークレーへの旅行でこれについて言及し、そこでヴォーン・プラットに会いました。 彼は最大の貢献をした人であり、私はその後それを書き留めただけでした。



それから、同じアイデアが数ヶ月前にジム・モリスを訪れたが、人々は彼のプログラムを見て、理解しなかったので、それを受け入れなかったことを知りました。 いずれにせよ、これはテキストを検索するための効果的な方法であり、コンピューターサイエンスの基礎についての良いアイデアも提供すると考えています。 この方法は有名になり、私の名前に関連付けられています。



私が言ったように、私は160の作品を書きました、そして、それらの各々の後ろにいくらかの面白い物語があります。



翻訳：ダイアナ・シェレミエワ





A. P.エルショフ共和党の指導者と綿花畑のウズベキスタンのソビエト団体の間。









記事「クワリズミの故郷への科学的巡礼」



序文 （A.P. ErshovとD. Knutが共同執筆、A.P。Ershovによるロシア語への翻訳）



ドナルド・クヌースの記事「現代数学と計算科学のアルゴリズム」は 、GSによってロシア語に翻訳されました。 ツァイチン。







Yershovアーカイブの資料： 国際シンポジウム「現代数学のアルゴリズムとその応用」

続きを読む

• ドナルドクヌース：私はバックデスクに座って冗談を言ったが、先生たちは我慢しなかった。
• ドナルド・クヌース：「若者への私のアドバイス」（93/97）および「自分を主張する必要性を感じている」（9/97）
• 「超現実的な数字」：私は6日間働き、7日目に休みました（40,41,42 / 97）
• ドナルド・クヌース：プログラミングの芸術はどのように作られたのか（33.38.39 / 97）
• ソーシャルアーキテクチャ：オープンソースプロジェクトの成功のための戦略

---

パブリッシングサポート-Edisonは、 製品を宣伝するためのクラウドソーシングプラットフォームを開発 し、インタラクティブな不動産データベースの設計アプリケーションを作成しています 。