優秀なプログラマーが開発効率を上げるために知っておくべき32のアルゴリズム

検索アルゴリズム - 指定された開始点から指定された終了点までのパスを計算するグラフ検索アルゴリズム。ヒューリスティック推定を使用して、各ノードを通る最適なパスを推定し、それを使用して場所をランク付けします。アルゴリズムは、取得された順序でノードを訪問します。したがって、A* 検索アルゴリズムは最良優先検索の例です。
ビーム検索 (有向検索、ビーム検索とも呼ばれる) - 最良優先検索アルゴリズムの最適化。ヒューリスティック関数を使用して、検査する各ノードの機能を評価します。ただし、ビーム検索では、各深度で最初の m 個の最も適格なノードしか見つけることができません。ここで、m は固定数、つまりビームの幅です。
バイナリ検索 - 各ステップで要件を満たさないデータの半分を削除しながら、線形配列内の特定の値を見つけるアルゴリズム。
分岐限定法 - さまざまな最適化問題、特に離散最適化と組み合わせ最適化において特定の最適解を見つけるためのアルゴリズム。
ブッフバーガーアルゴリズム - 単一変数の最大公約数を求めるユークリッドの互除法と線形システムのガウス消去法の一般化と考えられる数学アルゴリズム。
データ圧縮 - 特定のコーディング方式を使用して、より少ないバイト数 (またはその他の情報伝達単位) で情報をエンコードするプロセス。ソースエンコードとも呼ばれます。
Diffie-Hellman 鍵交換アルゴリズム - 2 つの当事者が、相手方の事前の知識なしに、安全でない通信チャネルを介して共有秘密鍵を共同で確立できるようにする暗号化プロトコル。このキーは、後で対称暗号と組み合わせて使用して、後続の通信を暗号化することができます。
ダイクストラのアルゴリズム - 負の重みエッジのない有向グラフの単一開始の最短アルゴリズム。
離散微分
動的プログラミング - 相互にカバーするサブ問題と最適なサブアーキテクチャアルゴリズムのデモンストレーション
ユークリッドの互除法 - 2 つの整数の最大公約数を計算します。最も古いアルゴリズムの 1 つで、紀元前 300 年頃にユークリッドの『原論』に登場しました。
期待最大化アルゴリズム (EM トレーニングとも呼ばれる) - 統計計算において、期待最大化アルゴリズムは、モデルが未発見の潜在変数に依存する確率モデル内のパラメータの最も可能性の高い推定値を見つけます。 EM は、2 つのステップで交互に計算されます。最初のステップは、隠れ変数の既存の推定値を使用して、それらの最大可能推定値を計算する期待値を計算することです。2 番目のステップは最大化であり、最初のステップで得られた最大可能値を最大化して、パラメーターの値を計算します。
高速フーリエ変換 (FFT) - 離散フーリエ変換 (DFT) とその逆変換を計算します。このアルゴリズムは、デジタル信号処理から偏微分方程式の解法、大きな整数積の高速計算まで、幅広い用途に使用できます。
勾配降下法 - 数学的な最適化アルゴリズム。
ハッシュ
ヒープ
カラツバ乗算 - コンピュータ代数システムや大規模ライブラリなど、数千の整数の乗算を実行する必要があるシステムで使用されます。長い乗算を使用すると、速度が遅くなりすぎます。このアルゴリズムは1962年に発見されました。
LLL アルゴリズム (Lenstra-Lenstra-Lovasz 格子縮小) - 格子基底を入力として受け取り、短い直交ベクトル基底を出力します。 LLL アルゴリズムは、ナップザック暗号システム、特別な設定による RSA 暗号化などの公開鍵暗号化方式で広く使用されています。
最大フローアルゴリズム - このアルゴリズムは、交通ネットワーク内の最大フローを見つけようとします。その利点は、そのようなフローの値を見つけることと定義されます。最大フロー問題は、より複雑なネットワークフロー問題の特殊なケースとして考えることができます。最大フローはネットワーク内のインターフェースに関連しており、これは最大フロー最小カット定理です。 Ford-Fulkerson は、フローネットワーク内の最大フローを見つけることができます。
マージソート
ニュートン法 - 非線形方程式（グループ）のゼロ点を見つけるための重要な反復法。
Q 学習アルゴリズム - これは、特定の状態で特定のアクションを実行し、期待される効用値を計算し、固定ポリシーに従うアクション値関数を学習することによって実行される強化学習アルゴリズムです。 Q 学習の利点は、環境のモデルを必要とせずに、可能なアクションの期待効用を比較できることです。
二次ふるい - 最新の整数因数分解アルゴリズムであり、実際には数体ふるいに次いで 2 番目に高速な既知のアルゴリズムです。これは 10 桁から 110 桁までの整数に対しては依然として最も高速であり、一般に数体ふるいよりも簡単であると考えられています。
RANSAC——「RANdom SAmple Consensus」の略称です。このアルゴリズムは、外れ値を含む観測データのセットに基づいて数学モデルのパラメータ値を推定します。基本的な前提は、データには非疎外値、つまり特定のモデルパラメータによって説明できる値が含まれており、疎外値はモデルに準拠しないデータポイントであるということです。
RSA——公開鍵暗号化アルゴリズム。暗号化として署名するのに適した最初のアルゴリズム。 RSA は電子商取引業界で今でも広く使用されており、十分なセキュリティ長さの公開鍵を持っていると誰もが信じています。
シェーンハーゲ・シュトラッセンアルゴリズム - 数学において、シェーンハーゲ・シュトラッセンアルゴリズムは、大きな整数を乗算するための高速漸近アルゴリズムです。アルゴリズムの複雑さは O(N log(N) log(log(N))) であり、アルゴリズムはフーリエ変換を使用します。
シンプレックスアルゴリズム - 数学的最適化理論において、シンプレックスアルゴリズムは線形計画問題の数値解を見つけるために使用される一般的な手法です。線形計画問題は、実変数の集合に対する線形不等式の集合と、最大化（または最小化）される固定線形関数から構成されます。
特異値分解 (SVD) - 線形代数において、SVD は実数または複素数の行列を分解する重要な方法です。信号処理や統計では、行列の擬似逆行列の計算 (最小二乗問題の解決)、過剰決定線形システムの解決、行列近似、数値天気予報など、多くの用途があります。
線形方程式の連立解法 - 線形方程式は数学における最も古い問題です。デジタル信号処理、線形計画法における推定と予測、数値解析における非線形問題の近似など、さまざまな用途があります。線形方程式系を解くには、ガウス・ジョルダン消去法またはコレスキー分解を使用できます。
Strukturtensor アルゴリズム - パターン認識の分野で適用され、すべてのピクセルに対して計算方法を見つけて、ピクセルが均質領域内にあるかどうか、エッジに属しているかどうか、または頂点であるかどうかを確認します。
結合検索アルゴリズム - 要素のセットが与えられた場合、このアルゴリズムはこれらの要素を複数の重複しない個別のグループに分割するためによく使用されます。分離セットデータ構造は、このような分割方法を追跡できます。マージ検索アルゴリズムは、このデータ構造に対して 2 つの便利な操作を実行できます。
- 検索: 特定の要素がどのグループに属しているかを判断します。
- マージ: 2 つのグループを 1 つのグループに結合またはマージします。
ビタビアルゴリズム - 特に隠れマルコフモデルにおいて、観測可能なイベントのシーケンスを生成するビタビパスと呼ばれる最も可能性の高い隠れ状態のシーケンスを見つける動的プログラミングアルゴリズム。