ビッグデータなどの最も中核的なキーテクノロジー：32のアルゴリズム

[[181277]]

オーストリアの記号計算研究所 (RISC) の Christoph Koutschan 博士は、自身のページに記事を投稿し、アンケートを実施し、参加者のほとんどがコンピューター科学者であり、これらの科学者に最も重要なアルゴリズムに投票するよう依頼したと述べています。以下は、英語名のアルファベット順に並べたこのアンケートの結果です。

1. A* 検索アルゴリズム - 指定された開始点から指定された終了点までのパスを計算するグラフ検索アルゴリズム。ヒューリスティック推定を使用して、各ノードを通る最適なパスを推定し、それを使用して場所をランク付けします。アルゴリズムは、取得された順序でノードを訪問します。したがって、A* 検索アルゴリズムは最良優先検索の例です。

2. ビーム検索 (有向検索、ビーム検索とも呼ばれる) - 最良の最初の検索アルゴリズムの最適化。ヒューリスティック関数を使用して、検査する各ノードの機能を評価します。ただし、ビーム検索では、各深度で最初の m 個の最も適格なノードしか見つけることができません。ここで、m は固定数、つまりビームの幅です。

3. バイナリ検索 - 各ステップで要件を満たさないデータの半分を削除しながら、線形配列内の特定の値を見つけるアルゴリズム。

4. 分岐限定法 - さまざまな最適化問題、特に離散最適化と組み合わせ最適化において特定の最適解を見つけるためのアルゴリズム。

5. ブッフベルガーアルゴリズム - 単一変数の最大公約数を求めるユークリッドの互除法と線形システムにおけるガウス消去法の一般化として考えることができる数学アルゴリズム。

6. データ圧縮 - 特定のコーディング方式（ソースコーディングとも呼ばれる）を使用して、より少ないバイト数（またはその他の情報伝達単位）で情報をエンコードするプロセス。

7. Diffie-Hellman 鍵交換アルゴリズム - 2 つの当事者が、お互いの事前の知識なしに、安全でない通信チャネルで共同で共有鍵を確立できるようにする暗号化プロトコル。このキーは、後で対称暗号と組み合わせて使用​​して、後続の通信を暗号化することができます。

8. ダイクストラ アルゴリズム - 負の重みエッジのない有向グラフの場合、単一の開始点を持つ最短アルゴリズムを計算します。

9. 離散微分アルゴリズム。

10. 動的プログラミング - 相互にカバーするサブ問題と最適なサブアーキテクチャアルゴリズムを実証する

11. ユークリッドの互除法 - 2 つの整数の最大公約数を計算します。最も古いアルゴリズムの 1 つで、紀元前 300 年頃にユークリッドの『原論』に登場しました。

12. 期待最大化アルゴリズム (EM トレーニングとも呼ばれる) - 統計計算において、期待最大化アルゴリズムは、モデルが未発見の潜在変数に依存する確率モデルで最も可能性の高いパラメータ推定値を見つけます。 EM は、2 つのステップで交互に計算されます。最初のステップは、隠れ変数の既存の推定値を使用して、それらの最大可能推定値を計算する期待値を計算することです。2 番目のステップは最大化であり、最初のステップで得られた最大可能値を最大化して、パラメーターの値を計算します。

13. 高速フーリエ変換 (FFT) - 離散フーリエ変換 (DFT) とその逆変換を計算します。このアルゴリズムは、デジタル信号処理から偏微分方程式の解法、大きな整数積の高速計算まで、幅広い用途に使用できます。

14. 勾配降下法 – 数学的な最適化アルゴリズム。

15. ハッシュアルゴリズム。

16. たくさん。

17. カラツバ乗算 - コンピュータ代数システムや大規模ライブラリなど、数千の整数の乗算を実行する必要があるシステムで使用されます。長い乗算を使用すると、速度が非常に遅くなります。このアルゴリズムは1962年に発見されました。

18. LLL アルゴリズム (Lenstra-Lenstra-Lovasz 格子縮約) - 格子基底を入力として受け取り、短い直交ベクトル基底を出力します。 LLL アルゴリズムは、ナップザック暗号システム、特別な設定による RSA 暗号化などの公開鍵暗号化方式で広く使用されています。

19. 最大フロー アルゴリズム - このアルゴリズムは、交通ネットワーク内の最大フローを見つけようとします。その利点は、そのようなフローの値を見つけることと定義されます。最大フロー問題は、より複雑なネットワーク フロー問題の特殊なケースとして考えることができます。最大フローはネットワーク内のインターフェースに関連しており、これは最大フロー最小カット定理です。 Ford-Fulkerson は、フロー ネットワーク内の最大フローを見つけることができます。

20. マージソート。

21. ニュートン法 - 非線形方程式（群）のゼロ点を見つけるための重要な反復法。

22. Q 学習アルゴリズム - これは、特定の状態で特定のアクションを実行し、期待される効用値を計算し、固定ポリシーに従うアクション価値関数を学習することによって実行される強化学習アルゴリズムです。 Q 学習の利点は、環境のモデルを必要とせずに、可能なアクションの期待効用を比較できることです。

23. 二次ふるい - 現代の整数因数分解アルゴリズムであり、実際には、この種のアルゴリズムの中で 2 番目に高速であることが知られています (数体ふるいに次ぐ)。これは 10 桁から 110 桁までの整数に対しては依然として最も高速であり、一般に数体ふるいよりも簡単であると考えられています。

24. RANSACは「RANdom SAmple Consensus」の略称です。このアルゴリズムは、外れ値を含む観測データのセットに基づいて数学モデルのパラメータ値を推定します。基本的な前提は、データには非疎外値、つまり特定のモデル パラメータによって説明できる値が含まれており、疎外値はモデルに準拠しないデータ ポイントであるということです。

25. RSA——公開鍵暗号化アルゴリズム。暗号化として署名するのに適した最初のアルゴリズム。 RSA は電子商取引業界で今でも広く使用されており、十分なセキュリティ長さの公開鍵を持っていると誰もが信じています。

26. シェーンハーゲ・シュトラッセンアルゴリズム - 数学において、シェーンハーゲ・シュトラッセンアルゴリズムは大きな整数の乗算のための高速漸近アルゴリズムです。アルゴリズムの複雑さは O(N log(N) log(log(N))) であり、アルゴリズムはフーリエ変換を使用します。

27. シンプレックスアルゴリズム - 数学的最適化理論では、シンプレックスアルゴリズムは線形計画問題の数値解を見つけるためによく使用される手法です。線形計画問題は、実変数の集合に対する線形不等式の集合と、最大化（または最小化）される固定線形関数から構成されます。

28. 特異値分解 (SVD) - 線形代数において、SVD は実数または複素数行列を分解する重要な方法です。信号処理や統計において、行列の擬似逆行列の計算 (最小二乗問題の解決)、過剰決定線形システムの解決、行列近似、数値天気予報など、多くの用途があります。

29. 線形方程式の連立解法 - 線形方程式は数学における最も古い問題です。デジタル信号処理、線形計画法における推定と予測、数値解析における非線形問題の近似など、さまざまな用途があります。線形方程式系を解くには、ガウス・ジョルダン消去法またはコレスキー分解を使用できます。

30. 構造テンソルアルゴリズム - パターン認識の分野で適用され、すべてのピクセルに対して、ピクセルが均質領域内にあるかどうか、エッジに属しているかどうか、頂点であるかどうかを確認する計算方法を見つけます。

31. 結合検索アルゴリズム - 要素のセットが与えられた場合、このアルゴリズムはこれらの要素を複数の重複しないグループに分割するためによく使用されます。分離セットデータ構造は、このような分割方法を追跡できます。マージ検索アルゴリズムは、このデータ構造に対して 2 つの便利な操作を実行できます。

検索: 特定の要素がどのグループに属しているかを判断します。

マージ: 2 つのグループを 1 つのグループに結合またはマージします。

32. ビタビアルゴリズム – 特に隠れマルコフモデルにおいて、観測可能なイベントのシーケンスを生成するビタビパスと呼ばれる隠れ状態の最も可能性の高いシーケンスを見つけるための動的プログラミングアルゴリズム。

これらは、クリストフ博士による最も重要なアルゴリズムに関する調査結果です。どのアルゴリズムに精通していますか? どのアルゴリズムを頻繁に使用しますか?