今北産業pedia

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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