20世紀の最も偉大なアルゴリズム10選

参考: 20 世紀のベスト: 編集者が選ぶトップ 10 アルゴリズム。

著者：バリー・A・シプラ。アドレス: http://www.uta.edu/faculty/rcli/TopTen/topten.pdf.

トップ10のアルゴリズムを発明したアルゴリズムの巨匠たち

1. 1946年のモンテカルロ法

[1946年: ロスアラモス科学研究所のジョン・フォン・ノイマン、スタン・ウラム、ニック・メトロポリスが、モンテカルロ法としても知られるメトロポリスアルゴリズムを考案。]

1946年、ラスベガス国立研究所の3人の科学者、ジョン・フォン・ノイマン、スタン・ウラム、ニック・メトロポリス

一般的な発明はモンテカルロ法と呼ばれます。

具体的な定義は次のとおりです。

正方形の上に一辺が1メートルの正方形を描き、その正方形の中にチョークで不規則な形を描きます。

次に、この不規則な形状の面積を計算する必要があります。列をどのように計算するのでしょうか?

モンテカルロ法によれば、N（Nは大きな自然数）個の大豆が正方形に均等に散らばっているとすると、

次に、この不規則な幾何学的形状の中に大豆がいくつあるかを数えます。たとえば、大豆は M 個あります。

すると、この奇妙な形の面積はおよそM/Nとなります。Nが大きいほど、計算値はより正確になります。

ここでは、豆がすべて同じ平面上にあり、互いに重なり合っていないと仮定する必要があります。 （大豆を撒くというのは単なる比喩です。）

モンテカルロ法は円周率を近似するのに使用できます。

コンピューターに毎回 0 から 1 の間の 2 つの数字をランダムに生成させ、これらの 2 つの実数が単位円内にあるかどうかを確認します。

一連のランダムな点を生成し、単位円内の点の数と点の総数を数えます。内接円の面積と正方形の面積の比は PI:4 です。ここで、PI は円周率です。

（指摘してくださったネットユーザーのQilihe Chunceiさんに感謝します：S内接円：S正＝円周率：4。詳しくは記事下の99番目のコメントをご覧ください。16日に修正しました）、

より多くのランダムポイントが得られると（10の9乗のランダムポイントが取得されても、結果は最初の4桁の円周率とのみ一致します）、

結果は円周率に近くなります。

2. 1947 シンプレックス法

[1947年: RAND社のジョージ・ダンツィグが線形計画法の単体法を考案した。]

1947 年、RAND 社の Gregorge Dantzig が単体法を発明しました。

それ以来、単体法は線形計画法の重要な基礎となりました。

線形計画法は、簡単に言えば、線形（すべての変数が 1 次べき乗）制約のセットです。

(たとえば、a1*x1+b1*x2+c1*x3>0)、指定された目的関数の極値を見つけます。

これは抽象的すぎるように思えるかもしれませんが、現実にはこの方法を使用できる例がたくさんあります。たとえば、ある会社では生産に使用できる人的資源と物的資源が限られていますが (「線形制約」)、その会社の目標は利益を最大化することです (「目的関数が最適値を取る」)。線形計画法は抽象的ではないことがわかります。

オペレーションズ・リサーチの一環として、線形計画法は経営科学の分野で重要なツールとなっています。

Dantzig によって提案された単体法は、類似の線形計画問題を解くための非常に効果的な方法です。

3. 1950 クリロフ部分空間反復法

[1950年: 国立標準局数値解析研究所のマグナス・ヘステネス、エドゥアルド・シュティーフェル、コーネリアス・ランチョスがクリロフ部分空間反復法の開発を開始。]

1950年: マグナス・ヘステネス、エドワード・スティフェル、

コルネリウス・ランチョスは、クリロフ部分空間反復法を発明しました。

クリロフ部分空間反復法は、Ax=bの形式の方程式を解くのに用いられる。ここでAはn*n行列である。nが十分に大きい場合、直接計算は非常に簡単になる。

クリロフ法はこれを巧みに Kxi+1=Kxi+b-Axi の反復形式に変換して解きます。

ここで、K (著者の姓であるロシア語の Nikolai Krylov の最初の文字に由来) は、A に近い構築された行列です。

反復アルゴリズムの優れた点は、複雑な問題を段階的に計算しやすいサブステップに単純化できることです。

4. 1951 行列計算のための分解法

[1951年: オークリッジ国立研究所のアルストン・ハウスホルダーが行列計算に対する分解アプローチを形式化しました。]

1951 年、オークリッジ国立研究所のアルストン・ハウスホルダーは、行列計算のための分解法を提案しました。

このアルゴリズムは、任意の行列を三角行列、対角行列、直交行列、およびその他の特殊な形式の行列に分解できることを証明します。

このアルゴリズムの重要性により、柔軟な行列計算ソフトウェア パッケージの開発が可能になります。

1957 最適化Fortranコンパイラ

[1957年: ジョン・バッカスがIBMのチームを率いてFortran最適化コンパイラを開発。]

1957 年: ジョン・バッカスが IBM のチームを率いて Fortran 最適化コンパイラを開発。

Fortran は、「Fortran」とも訳され、「数式の翻訳」を意味する「Formula Translation」という 2 つの単語で構成されています。

これは、世界で初めて公式に採用され、今日まで普及している高級プログラミング言語です。

この言語は現在では Fortran 2008 にまで発展し、人々によく知られています。

6. 1959-61 行列の固有値を計算するQRアルゴリズム

[1959〜61年: ロンドンのフェランティ社のJGFフランシスが、QRアルゴリズムとして知られる、固有値を計算するための安定した方法を発見しました。]

1959-61年: ロンドンのフェランティ社のJGFフランシスは、固有値を計算する安定した方法を発見した。

これは有名なQRアルゴリズムです。

これも線形代数に関係するアルゴリズムです。線形代数を勉強したことがある人は「行列の固有値」を覚えているはずです。固有値を計算するのが行列計算です。

最も核心的な問題の 1 つは、従来のソリューションでは高次方程式の根を見つける必要があることです。これは、問題の規模が大きい場合に非常に困難です。

QR アルゴリズムは、行列を直交行列 (この記事を読んでいるときに直交行列が何であるかを知っていることを願います。:D。) と上三角行列の積に分解します。

前述のクリロフ法と同様に、これは高次方程式の根を求める複雑な問題を段階的かつ簡単に解決できる問題に簡素化する別の反復アルゴリズムです。

計算のサブステップにより、コンピューターを使用して大規模な行列の固有値を解くことが可能になります。

このアルゴリズムの作者は英国ロンドンの JGF Francis です。

7. 1962 クイックソートアルゴリズム

[1962年: ロンドンのElliott Brothers社のTony HoareがQuicksortを発表。]

1962年: ロンドンのトニー・エリオット・ブラザーズ社、ホールがクイックソートを提案。

ハハハ、おめでとうございます。ようやく、おそらく初めての馴染みのあるアルゴリズムがわかりましたね〜。

クイックソートアルゴリズムは古典的なソートアルゴリズムとして、あらゆる場所で使用されています。

クイック ソート アルゴリズムは、サー トニー ホーアによって最初に設計されました。その基本的な考え方は、ソートするシーケンスを 2 つに分割することです。

左半分は常に「小さい」、右半分は常に「大きい」です。このプロセスは、シーケンス全体が整うまで再帰的に続行されます。

トニー・ホーア卿といえば、クイックソートアルゴリズムは実は彼が偶然に発見した小さな発見に過ぎません。彼のコンピューターへの主な貢献は、

彼は形式手法の理論と ALGOL60 プログラミング言語の発明への貢献により 1980 年にチューリング賞を受賞しました。

クイックソートの平均時間計算量はわずか O(Nlog(N)) で、通常の選択ソートやバブルソートよりもはるかに高速です。

それはまさに歴史的な取り組みです。

8. 1965 高速フーリエ変換

[1965年: IBM TJワトソン研究所のジェームズ・クーリーとプリンストン大学およびAT&Tベル研究所のジョン・テューキーが高速フーリエ変換を発表。]

1965年: IBMワトソン研究所のジェームズ・クーリーとプリンストン大学のジョン・テューキー、

AT&T ベル研究所が共同で高速フーリエ変換を導入しました。

高速フーリエアルゴリズムは、離散フーリエアルゴリズム（デジタル信号処理の基礎）の高速アルゴリズムであり、時間計算量はわずかOである。

(Nlog(N)); 時間効率よりも重要なのは、高速フーリエアルゴリズムはハードウェアで実装するのが非常に簡単なので、電子技術の分野で広く使用されていることです。

非常に幅広い用途。

今後、私は古典的なアルゴリズム研究シリーズでこのアルゴリズムに焦点を当てるつもりです。

9. 1977 整数関係検出アルゴリズム

[1977年: ブリガムヤング大学のヘラマン・ファーガソンとロドニー・フォーカードが整数関係検出アルゴリズムを開発しました。]

1977 年: バーミンガム大学の Helaman Ferguson と Rodney Forcade が、整数関係を検出するための Forcade アルゴリズムを提案しました。

整数関係を検出することはユークリッドの時代にまで遡る古い問題です。具体的には：

実数の集合X1、X2、...、Xnが与えられたとき、すべてゼロではない整数a1、a2、... anが存在し、a1 x 1 + a2 x2 + . . . + an x

0 ですか?

今年、ブリガムヤング大学のヘラマン・ファーガソン氏とロドニー・フォーカード氏がこの課題を解決しました。

このアルゴリズムは、「量子場理論におけるファインマン図の計算を簡素化する」ことに適用されます。はい、理解する必要はありません。ただ理解してください。 :D.

10. 1987 高速多重極アルゴリズム

[1987年: イェール大学のレスリー・グリーンガードとウラジミール・ロクリンが高速多重極アルゴリズムを発明。]

1987年: イェール大学のグリーンガードとロクリンが高速多重極アルゴリズムを発明。

この高速多極アルゴリズムは、重力または静電気力を介して相互作用する N 個の粒子の正確な動きを計算するために使用されます。

—天の川の星や、タンパク質内の原子間の相互作用など。OK、理解するだけです。

ご意見やご質問がございましたら、メッセージを残すか、ブログにコメントしてください。

元の住所: 7月