プログラマーが知っておくべき 20 世紀の 10 大アルゴリズム

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

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

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

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

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

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

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

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

モンテカルロ法では、N個（Nは大きな自然数）の大豆を正方形の中に均等に散らし、この不規則な幾何学的形状の中に大豆がいくつあるかを数えます。例えば、M個の大豆がある場合、
すると、この奇妙な形の面積はおよそM/Nとなります。Nが大きいほど、計算値はより正確になります。ここでは、豆がすべて同じ平面上にあり、互いに重なり合っていないと仮定する必要があります。

モンテカルロ法は円周率を近似的に計算するのに使用できます。つまり、コンピューターに毎回 0 から 1 の間の 2 つの数値をランダムに生成させ、これら 2 つの実数が単位円内にあるかどうかを確認します。一連のランダムな点を生成し、単位円内の点の数と点の総数を数えます (円の面積と正方形の面積の比は PI:1 で、PI は円周率です)。取得されるランダムな点が多いほど (ただし、10 の 9 乗のランダムな点を取得しても、結果は最初の 4 桁のみが円周率と一致します)、結果は円周率に近くなります。

2. 1947 シンプレックス法

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

1947 年、RAND 社の Gregorge Dantzig が単体法を発明しました。それ以来、単体法は線形計画法の重要な基礎となりました。簡単に言えば、線形計画法とは、一連の線形（すべての変数が 1 次べき乗）制約（たとえば、a1*x1+b1*x2+c1*x3>0）が与えられた場合に、特定の目的関数の極値を見つけることです。

これは抽象的すぎるように思えるかもしれませんが、現実にはこの方法を使用できる例がたくさんあります。たとえば、ある会社では生産に使用できる人的資源と物的資源が限られていますが (「線形制約」)、その会社の目標は利益を最大化することです (「目的関数が最適値を取る」)。線形計画法は抽象的ではないことがわかります。オペレーションズ・リサーチの一環として、線形計画法は経営科学の分野で重要なツールとなっています。 Dantzig によって提案された単体法は、類似の線形計画問題を解くための非常に効果的な方法です。

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

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

1950 年: アメリカ国立標準局数値解析研究所の Magnus Hestenes、Edward Stiefel、Cornelius Lanczos が Krylov サブスペース反復法を発明。クリロフ部分空間反復法は、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 年: ロンドンの Ferranti Ltd. の JGF Francis が、固有値を計算するための安定した方法を発見しました。これが有名な QR アルゴリズムです。これも線形代数に関連するアルゴリズムです。線形代数を学んだことがある人は、「行列の固有値」を覚えているはずです。固有値の計算は、行列計算の核心的な内容の1つです。従来の解決法では、高次方程式の根を見つける必要があり、問題が大きい場合は非常に困難です。 QR アルゴリズムは、行列を直交行列 (この記事を読んでいるときに、直交行列が何であるかを知っていることを願います。:D。) と上三角行列の積に分解します。これは、前述のクリロフ法と同様に、高次方程式の根を見つけるという複雑な問題を段階的で計算しやすいサブステップに簡素化する別の反復アルゴリズムであり、コンピューターを使用して大規模な行列の固有値を解くことを可能にします。このアルゴリズムの作者は英国ロンドンの JGF Francis です。

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

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

1962年: ロンドンのトニー・エリオット・ブラザーズ社、ホールがクイックソートを提案。ハハハ、おめでとうございます。ようやく、おそらく初めての馴染みのあるアルゴリズムがわかりましたね〜。クイックソートアルゴリズムは古典的なソートアルゴリズムとして、あらゆる場所で使用されています。クイックソートアルゴリズムは、最初にトニーホーア卿によって設計されました。その基本的な考え方は、ソートするシーケンスを 2 つの半分に分割し、左半分は常に「小さい」、右半分は常に「大きい」というものです。このプロセスは、シーケンス全体が整列するまで再帰的に続行されます。トニー・ホーア卿といえば、クイックソートアルゴリズムは実は彼が偶然に発見した小さな発見に過ぎませんでした。彼のコンピューターへの貢献は主に形式手法の理論と ALGOL60 プログラミング言語の発明です。彼はこれらの功績により 1980 年にチューリング賞も受賞しました。

========

クイックソートアルゴリズムの具体的な理解と応用については、私が書いた記事を参照してください。

8 つのソートアルゴリズムをマスターするシリーズ、1. クイックソートアルゴリズム:

http://blog.csdn.net/v_JULY_v/archive/2011/01/04/6116297.aspx

------------------------------------------------------------

クイックソートの平均時間計算量はわずか 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 x 1 + a2 x2 + . . . + an xn = 0 となるような、すべてゼロではない整数 a1、a2、... an が存在するでしょうか。

今年、ブリガムヤング大学のヘラマン・ファーガソン氏とロドニー・フォーカード氏がこの課題を解決しました。このアルゴリズムは、「量子場理論におけるファインマン図の計算を簡素化する」ことに適用されます。はい、理解する必要はありません。ただ理解してください。

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

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

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

高速多重極アルゴリズムは、「重力や静電気力によって相互作用する N 個の粒子の動き、たとえば天の川の星やタンパク質内の原子間の相互作用を正確に計算する」ために使用されます。わかりました、理解してください。

この記事は CSDN ブログからの引用です。転載の際は出典を明記してください: http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6127953.aspx

【編集者のおすすめ】