今北産業pedia

コンピュータビジョンにおいて、2枚の画像からカメラの動きと構造を推定する手法である。

対応する8組以上の点を用いることで、基礎行列や本質行列を線形計算により算出する。

実装が容易で高速だが、ノイズに弱いためRANSACなどの手法と組み合わせて使われる。

ビット演算を利用して、テキスト内からパターンを検索する文字列探索アルゴリズムである。

完全一致だけでなく、編集距離を許容するあいまい検索を高速に行えるのが強みである。

Unixのagrepコマンドなどで採用されており、短いパターンの検索に非常に適している。

分散システムにおいて、一貫性・可用性・分断耐性の3つを同時に満たすことはできないとする定理。

ブリュワーの定理とも呼ばれ、分散データベースの設計における基本的なトレードオフを示している。

NoSQLデータベースなどの特性を理解し、用途に応じたシステムを選択するための指針となる。

命題論理式の充足可能性問題（SAT）を解くための、バックトラッキングに基づく完備な手法。

単位伝播や純リテラル除去などの手法を組み合わせ、探索空間を効率的に削減するのが特徴である。

現代の高性能なSATソルバーの多くが、このアルゴリズムを基礎として設計されている。

二分探索木を平衡二分探索木へ再構築するための、効率的なインプレースアルゴリズム。

木を一度線形なリストに変換した後、回転操作を繰り返してバランスを整える手順を踏む。

追加のメモリ領域をほとんど必要とせず、O(n)の時間計算量で木を平衡化できる利点がある。

1桁の入力ミスや隣接する2桁の入れ替えミスを検出できる、チェックデジット算出手法。

準群（クアジグループ）の理論に基づいており、10進数以外の基数にも適用可能である。

識別番号の入力誤り防止において、Luhnアルゴリズムなどと同様に利用される。

デジタル回路の故障診断において、テストパターンを効率的に生成するためのアルゴリズム。

PODEMアルゴリズムを改良したもので、ファンアウトポイントに着目して探索空間を削減する。

大規模な集積回路の設計検証や、製造時の不良品検査を高速化するために利用される。

計算理論において、計算可能関数のパラメータの一部を固定して新しい関数を作る性質。

プログラミング言語における部分適用やカリー化の理論的な裏付けとなる重要な定理。

帰納的関数のゲーデル数化に関連し、計算の構造を解析する基礎的な道具として使われる。

コンピュータのCPUにおいて、命令を順不同に実行するためのハードウェアアルゴリズム。

レジスタ・リネーミングと予約ステーションを用いることで、データ依存による待機を最小化する。

高性能プロセッサの命令レベルの並列性を引き出すための基盤技術として広く採用された。

コンピュータシステムの並列化による高速化の限界を示す法則。

プログラムの一部を並列化しても、残りの直列部分が全体の性能を制約する。

並列処理の設計において、投資対効果を予測するための重要な指標となる。

特定の問題を解決したり、計算を実行したりするための明確な手順や規則。

入力に対して一定の処理を行い、有限の時間内で正しい出力を得ることを目指す。

コンピュータプログラムの核となり、検索や暗号化など現代社会を支えている。

ネットワークにおける最大流問題を解くための、フォード・ファルカーソン法の改良版。

幅優先探索を用いて増加道を最短経路で選ぶことで、計算量の最悪時間を保証した。

輸送網の最適化や通信経路の割り当てなど、グラフ理論の実用的な問題に広く使われる。

エドワーズ曲線を用いた公開鍵暗号方式による、高速で安全なデジタル署名アルゴリズム。

決定論的な署名生成により、乱数生成器の不備による秘密鍵の漏洩リスクを排除している。

SSHやTLS、仮想通貨の技術基盤として、現代のセキュリティ通信で多用されている。

一階述語論理の妥当性を、命題論理の有限集合の充足不能性に帰着させる論理学の定理。

コンピュータによる自動定理証明の理論的基盤となり、解像原理などの手法を生み出した。

数学的証明の構造をアルゴリズム的に解析することを可能にした、重要な成果である。

ディスクの読み書きヘッドを効率的に動かすためのスケジューリング手法。

一方向に移動しながら要求を処理し、端に到達すると逆方向に折り返す。

HDDのアクセス効率向上や実際の昇降機の制御システムに利用される。

入力データが時系列に従って順次与えられ、全データを見ずに即座に判断を下す手法。

将来の入力を予測できない状況下で、いかに最適な解に近い結果を出すかが課題となる。

ページ置換や株取引、リアルタイムのデータ処理など、動的な環境で広く活用される。

浮動小数点数の計算において、丸め誤差の蓄積を最小限に抑えるための加算手法。

計算途中で失われる微小な値を補正項として保持し、次の加算で反映させる。

数値解析やシミュレーションなど、高い精度が要求される計算処理において重要な役割を果たす。

限られた高速メモリ（キャッシュ）に、どのデータを残すかを決定する制御手法。

参照頻度の高いデータを保持することで、システム全体の処理速度を大幅に向上させる。

LRUなどが代表的で、CPUやWebブラウザ、データベースなどで広く使われる。

並列計算において、問題サイズを大きくすれば並列化による加速効果も向上するという法則。

並列化できない部分が固定されていても、全体の処理量を増やせば効率が改善することを示す。

アムダールの法則が示す限界に対し、実用的な並列処理の有効性を肯定した。

コンピュータの性能は価格の2乗に比例し、計算コストは性能の平方根に反比例するという法則。

1950年代にハーブ・グロッシュが提唱し、大型計算機の集中運用の根拠となった。

後の分散処理やPCの普及により、現代では必ずしも成立しなくなっている。

発生確率が極めて低い問題に対し、あえて何も対策をせず無視する手法。

砂の中に頭を隠して危険をやり過ごすというダチョウの俗説に由来する。

デッドロック対策などで、複雑な回避策を講じるよりコストが低い場合に採用される。

ラムダ計算において、項の書き換え順序によらず最終的な結果が一意に定まることを示す定理。

計算の合流性（コンフルエンス）を保証し、計算体系の整合性を証明する。

関数型プログラミング言語の理論的基礎を支える重要な定理である。

量子コンピュータが、古典コンピュータよりも圧倒的に速く問題を解けることを示した例。

関数が「定数」か「均衡」かを、わずか1回の試行で判定することができる。

量子アルゴリズムの優位性を理論的に証明した、歴史的に重要な手法。

2つのプロセスが共有リソースを競合せず安全に使用するための相互排除手法。

フラグと共有変数を用いることで、デッドロックや割り込みを防ぎつつ実行権を制御する。

複雑なハードウェア支援を必要とせず、ソフトウェアのみで実装可能な古典的解法。

ネットワークフロー問題において、始点から終点への最大流量を求める手法。

増加道（余裕のある経路）を繰り返し探し、流量を更新し続けることで最適解を得る。

最大流最小カット定理に基づき、通信網や輸送経路の最適化に広く応用されている。

計算複雑性理論において、どんなアルゴリズムよりも速いアルゴリズムが常に存在する問題。

特定の計算問題に対し、計算時間をいくらでも短縮できる「最速の解」がないことを示す。

マヌエル・ブラムによって提唱され、計算量の理論的な限界を浮き彫りにした。

遅れているソフトウェア開発プロジェクトに人員を追加すると、さらに遅れるという法則。

増員によるコミュニケーションコストの増大や、教育の手間が生産性を低下させる。

フレデリック・ブルックスが著書『人月の神話』で提唱した、プロジェクト管理の金言。

コンピュータグラフィックスにおいて、ディスプレイ上に直線を高速に描画する手法。

浮動小数点演算を避け、整数の加減算のみでピクセルの配置を決定できるのが特徴。

計算負荷が極めて低いため、初期のPCから現代の描画エンジンまで広く採用されている。