現在世界で最も重要な古典的アルゴリズムトップ10

最近、誰かが StackExchange で、ネットユーザーに現在世界で最も古典的なアルゴリズムのトップ 10 を集めるよう求める質問をしました。観客は多数の候補アルゴリズムの中から投票し、最終的に最も人気の高い 10 個のアルゴリズムを決定しました。

聖書からの 10 の偉大なアルゴリズム: 発案者による説明: 「聖書からの証明」には、簡潔でエレガントな数学的証明が数十個集められており、すぐに多くの数学愛好家の注目を集めました。「聖書からのアルゴリズム」という別の本があったら、そこにはどのようなアルゴリズムが含まれているでしょうか?さて、皆さん、ここに候補となるアルゴリズムが何十個もあります。これが今日の世界で最も古典的なアルゴリズムだと思うなら、ぜひ投票してください.....

最終的に、最も多くの票を獲得した上位 10 個のクラシックアルゴリズムが生成されました (投票統計は 2011 年 3 月 7 日時点で集計されています)。

免責事項: 以下のトップ 10 アルゴリズムは、今日の世界で最も古典的なトップ 10 アルゴリズムと同等ではなく、決してそうではないことを読者にご理解いただきたいと思います。
--------------------------

10位: ハフマン符号化

ハフマン符号化は、ロスレスデータ圧縮に使用される符号化方式およびエントロピー符号化（重み符号化）アルゴリズムです。これは、1952 年に MIT で博士号取得を目指していた David A. Huffman によって発明され、「最小冗長コードの構築方法」という論文で発表されました。

第9回: バイナリ検索

順序付けられたコレクション内の要素を見つけるには、バイナリ検索アルゴリズム (バイナリサーチとも呼ばれます) を使用できます。バイナリ検索アルゴリズムは、まずセットの中央にある要素をキーのサイズと比較します。次の 3 つのケースがあります (セットが小さいものから大きいものの順に並べられていると仮定)。

キーが中央の要素より小さい場合、一致する要素は左側にあるはずなので (存在する場合)、左側の領域にバイナリ検索が適用されます。
キーは中央の位置にある要素と等しいので、要素が見つかります。
キーが中央の要素より大きい場合、一致する要素は右側にあるはずなので (存在する場合)、右側の領域にバイナリ検索が適用されます。

また、コレクションが空の場合は、見つからないことを意味します。

8. ミラー・ラビン類似実験テスト

アイデアは、素数の特性 (フェルマーの最終定理の使用など) を使用して、証人が素数を数えない小さな確率を見つけることです。十分なランダムテストを行っても証拠が見つからない場合、その数は素数です。

No. 7: 深さ優先探索、幅優先探索

これらは他の多くのアルゴリズムの基礎となります。深さ優先探索アルゴリズムと幅優先探索アルゴリズムの詳細な紹介については、この記事を参照してください: BFS および DFS 優先探索アルゴリズムの徹底的な理解を教えます。

No. 6: Gentry の完全準同型暗号化方式アルゴリズム。

このアルゴリズムは非常に優れており、第三者が秘密鍵を取得せずに暗号化されたデータに対して任意の操作を実行できるようになります（よく理解されていません）。

5. フロイド・ワーシャル全ペア最短経路アルゴリズム

このアルゴリズムの紹介については、私が書いたこの記事「いくつかの最短経路アルゴリズムの比較」(http://blog.csdn.net/v_JULY_v/archive/2011/02/12/6181485.aspx) を参照してください。

d[]: 2D配列。d[i,j]は最小コストまたは最短パスを持つ隣接エッジです。

 kは1からn までです: 
     iは1からn までです: 
       jは1からnまで:
        d[i,j] = min(d[i,j], d[i,k] + d[k,j])

4. クイックソート

クイックソートアルゴリズムは、すべての古典的なアルゴリズムのほぼすべてのリストをカバーします。これは、20 世紀の 10 大アルゴリズムの 1 つに選ばれました (こちらを参照: 20 世紀の 10 大アルゴリズムを数える)。クイックソートアルゴリズムの詳細な紹介については、私が書いたこの記事を参照してください: パート I の続き: クイックソートアルゴリズムの詳細な分析。

3位: BFPRTアルゴリズム

1973 年、Blum、Floyd、Pratt、Rivest、および Tarjan は共同で「選択の時間境界」というタイトルの論文を執筆しました。この論文では、配列内の k 番目に大きい要素を選択するアルゴリズムが提示され、一般に「中央値のアルゴリズム」として知られています。慎重に設計されたピボット選択方法に依存するこのアルゴリズムは、理論的には最悪の場合でも線形時間計算量を保証し、平均線形計算量と最悪の O(n^2) 計算量を持つ従来のアルゴリズムを上回ります。専門家のグループが再帰アルゴリズムの複雑性分析を習得し、まさにバイブルアルゴリズムと呼ぶにふさわしいアルゴリズムを構築しました。

ここでは、配列内の k 番目に大きい要素を選択するための時間計算量が O(N) のアルゴリズムを簡単に紹介します。

クイックソートのセグメンテーションアルゴリズムに似ています:

各分割後、配列内のピボットポイントの位置 s を返すことができ、次に s のサイズが k と比較されます。
大きい場合は、配列[s..n]を再度再帰的に分割します。
小さい場合は、再帰的にarray[left...s-1] //sは中央のピボットポイント要素です。
それ以外の場合は、partition で返される値である配列[s]を返します。 //この s を見つけるだけです。
要件を満たす s 値を見つけたら、 s より小さい側の要素を走査して出力します。
参照できるのは、『アルゴリズム入門』の第 9 章、「期待される線形時間での選択」のセクションで、配列内の k 番目に小さい要素を見つける平均時間計算量は O(N) であるという証明です。これは、要素が一意であると仮定すると、上記のプログラムの期待される実行時間であり、最終的に O(n) であることが証明されました。

2位: Knuth-Morris-Pratt 文字列マッチングアルゴリズム

このアルゴリズムの紹介については、こちらの記事を参照してください: 6. KMP アルゴリズムを最初から最後まで徹底的に理解する方法を教えます。 KMP アルゴリズムは 20 世紀の 10 大アルゴリズムの 1 つには選ばれませんでしたが、このように美しく効率的な KMP アルゴリズムが選ばれないことを人々が受け入れることは明らかにできませんでした。そのため、最終投票では、KMP アルゴリズムが 2 位になりました。

1位: Union-find

厳密に言えば、union-find セットは、セットのマージとクエリ操作を処理するために特別に使用されるデータ構造です。ユニオン検索アルゴリズムは、ツリー構造を巧みに使用してプログラミングの複雑さを信じられないほどのレベルまで低減します。いくつかの再帰テクニックを使用すると、ほぼすべての操作を 2 行のコードで実行できます。パス圧縮の優れたアイデアは、データ構造全体の最後の仕上げです。 union-find の効率は非常に高く、単一の操作の時間計算量はほぼ一定レベルとみなすことができますが、データ構造の実際の動作を予測することは難しいため、正確な時間計算量分析には多くの高度な技術が必要です。最終的に、並列検索がこのリストの 1 位を獲得しました。

補足：上位 3 位の得票数はわずか 4 票と 8 票の差でした。そのため、このランキングは今後も変化し続けるでしょう。しかし、最終結果がどうであろうと、トップ 10 のアルゴリズムは基本的に確定しています。

元の投票 URL: http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book。

---------------------------------------------------------
いかがですか、上記のアルゴリズムについてご存知ですか? 今、私があなたに投票権を与えるとしたら、どのアルゴリズムに投票しますか? では、投票してみましょう。この記事の下にあるコメント欄に、あなたの意見や決定を書き込んでください。

簡単に投票できるように、生成された上位 10 個のアルゴリズムを以下に書き留めました。

1. ハフマン符号化。

2. バイナリ検索。

3. ミラー・ラビン氏による同様の実験テスト。

4. 深さ優先探索。

5. ジェントルマンの完全準同型暗号化メカニズム

6. フロイド-ワーシャル全ペア最短経路アルゴリズム。

7. クイックソート。

8. BFPRTアルゴリズム。

9. Knuth-Morris-Pratt 文字列マッチングアルゴリズム。

10. 結合検索。

より多くの選択肢を提供するために、同様に古典的だが、上記のリストのトップ 10 にまだランクされていない他の候補アルゴリズムをいくつか投稿します。

11. Cooley-Tukey FFT アルゴリズム。高速フーリエ変換アルゴリズム。フーリエ変換アルゴリズムの紹介については、こちらの記事を参照してください: 10. フーリエ変換アルゴリズムを最初から最後まで徹底的に理解する、パート 1。

12. 線形計画法。

13. ダイクストラアルゴリズム。詳しい紹介については、こちらの記事を参照してください: パート 2: ダイクストラのアルゴリズムを徹底的に理解する。

14. マージソート。マージソート。

15. フォード・フルカーソンアルゴリズム。ネットワーク最大フローアルゴリズム。

16. ユークリッド法。

数学において、ユークリッドの互除法は、ユークリッドの互除法とも呼ばれ、最大公約数、つまり 2 つの正の整数の最大公約数を見つけるアルゴリズムです。このアルゴリズムは TAOCP の最初のアルゴリズムとして説明されており、このアルゴリズムがいかに注目されているかがわかります。これは 3000 年前に遡る、最も古い既知のアルゴリズムです。ユークリッドの互除法は、ユークリッドの『原論』（第 7 巻、命題 i と ii）で初めて登場し、中国では東漢の時代に登場した『九章算術』にまで遡ることができます。拡張ユークリッド定理は、任意の整数 a と b に対して、ax + by = gcd(a, b) となる x、y のペアが存在することを構成的に証明します。

17. RSA暗号化アルゴリズム。暗号化アルゴリズムについては後ほど詳しく説明します。

18. 遺伝的アルゴリズム。 GA アルゴリズムについては、私が書いたこの記事を参照してください: 7. 遺伝的アルゴリズムが GA の本質を分析します。

19. 期待最大化（EM）アルゴリズム。

統計計算において、期待値最大化 (EM) アルゴリズムは、観測不可能な潜在変数に依存する確率モデル内のパラメータの最大尤度推定値を見つけるためのアルゴリズムです。最大期待値は、機械学習やコンピュータービジョンにおけるデータクラスタリングの分野でよく使用されます。最大期待値アルゴリズムは、2 つのステップで交互に計算を実行します。最初のステップは期待値 (E) を計算し、隠れ変数の既存の推定値を使用して最大尤度推定値を計算します。2 番目のステップは最大化 (M) で、E ステップで取得した最大尤度値を最大化して、パラメータの値を計算します。 M ステップで見つかったパラメータ推定値は次の E ステップの計算に使用され、このプロセスが交互に継続されます。

20. データ圧縮

データ圧縮は、コンピューターや通信に保存されるデータの冗長性を削減することでデータ密度を高め、最終的にデータの保存スペースを削減するテクノロジです。データ圧縮は、ファイルストレージや分散システムで広く使用されています。データ圧縮は、メディア容量の増加とネットワーク帯域幅の拡張も意味します。

21. ハッシュ関数

ハッシュ関数は、あらゆる種類のデータから小さなデジタル「指紋」を作成する方法です。この関数はデータをシャッフルし、ハッシュ値と呼ばれる指紋を再作成します。ハッシュ値は通常、文字と数字の短いランダムな文字列を表すために使用されます。優れたハッシュ関数では、入力ドメインでハッシュ衝突が発生することはほとんどありません。ハッシュテーブルとデータ処理では、衝突を抑制してデータを区別しないと、データベースレコードを見つけるのが難しくなります。

22. 動的プログラミング。動的プログラミングの大まかな概要については、こちらの記事を参照してください: 3. 動的プログラミング。

まだ何を迷っているのですか? 今すぐ貴重な一票を投じてください。投票はお一人様一票までとさせていただきます。このアルゴリズムが最も古典的なアルゴリズムだと思う方は、下のコメント欄にシリアルナンバーとアルゴリズム名をご記入ください。

もちろん、最も古典的だと思うアルゴリズムが上記に記載されていない場合は、コメントに書いて、お気に入りのアルゴリズムに投票することもできます。その後、皆様のご意見を参考にして、お気に入りのアルゴリズムを候補アルゴリズムとして追加させていただきます。

最後に、私たち自身でトップ 10 の古典的なアルゴリズムのランキングリストを作成し、世界中の人々に私たちの中国語の意見を見てもらいます。どう思いますか? なぜまだ躊躇しているのですか? 急いでコメントして投票してください...

元のソース: http://blog.csdn.net/v_JULY_v/archive/2011/03/07/6228235.aspx

【編集者のおすすめ】