今北産業pedia

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

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

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

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

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

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

音声信号をデジタル化する際に、ダイナミックレンジを圧縮するための標準規格である。

主にヨーロッパや日本の電話回線網で採用されており、対数的な量子化を行う。

北米などで使われるμ-lawアルゴリズムと比較して、低信号時の歪みが少ない特性を持つ。

通信路符号化において、事後確率を最大化するように復号を行うアルゴリズムである。

1974年に開発され、ターボ符号の復号など反復復号のプロセスで中心的な役割を果たす。

ビタビアルゴリズムと異なり、各ビットごとの最適な推定値を算出できるのが特徴である。

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

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

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

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

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

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

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

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

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

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

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

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

通信の秘匿性を高めるため、メッセージごとに暗号鍵を更新し続ける鍵交換プロトコル。

前方秘匿性と将来の秘匿性の両方を提供し、過去や未来の通信内容が漏洩するリスクを低減する。

SignalやWhatsAppなどのアプリにおいて、エンドツーエンド暗号化の基盤として採用されている。

観測できない潜在変数を含む統計モデルにおいて、パラメータの最大尤度推定値を求める反復手法。

期待値を計算するEステップと、尤度を最大化するMステップを交互に繰り返して収束させる。

混合モデルの推定や欠損データの補完など、機械学習や統計学の幅広い分野で利用されている。

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

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

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

与えられたn個の要素から、すべての置換を効率的に生成するためのアルゴリズム。

要素の交換を最小限に抑えるように設計されており、再帰的または反復的な実装が可能。

計算量が最適であり、順列生成の標準的な手法として計算機科学で広く知られている。

入力データの格納領域以外に、追加のメモリ領域をほとんど必要とせずに処理を行う手法。

空間計算量が非常に小さく抑えられるため、メモリ資源が限られた環境で有利である。

代表例として、バブルソートやクイックソート、ヒープソートなどの並べ替えが挙げられる。

複数のスレッドが共有データにアクセスする際、ロックを使用せずに整合性を保つ手法。

Lock-freeはシステム全体の進行を、Wait-freeは各スレッドの完了を保証する。

デッドロックを回避し、高い並列性とリアルタイム性が求められるシステムで利用される。

クレジットカード番号などの識別番号の誤りを確認するためのチェックサムアルゴリズム。

ハンス・ピーター・ルーンによって考案され、単純な計算を用いて入力ミスを検出する。

クレジットカード、マイナンバー、IMEI番号など、世界中の様々なID体系で広く利用されている。

TCP通信において、小さなパケットの送信を遅延させてまとめて送ることで、ネットワーク効率を高める手法。

データ量が少ない場合にACKを待ってから送信することで、ヘッダによるオーバーヘッドを削減する。

通信効率は向上するが、リアルタイム性が求められるオンラインゲームなどでは遅延の原因となる。

分散システムにおいて、信頼性の低いネットワーク上で複数のノードが合意を形成するためのプロトコル。

レスリー・ランポートによって提唱され、一部のノードが故障してもシステム全体で一貫性を保つ。

分散データベースやクラスタ管理システムにおけるリーダー選出や状態複製などの基盤技術として使われる。

関数を多項式で最良近似するために用いられる反復的な計算手法。

チェビシェフの等振動定理に基づき、最大誤差を最小化するミニマックス近似を求める。

デジタルフィルタの設計や数値計算ライブラリの実装において、精度の高い近似に利用される。

プロダクションシステムにおいて、多数のルールと事実を高速に照合するためのアルゴリズム。

ネットワーク状のデータ構造を構築し、過去の照合結果を再利用することで計算量を削減する。

エキスパートシステムやビジネスルール管理システムの推論エンジンで採用されている。

コンピュータサイエンスの歴史において、初期のプログラミング言語を比較するために考案された課題。

配列の読み込み、関数の適用、条件分岐、出力といった基本操作を含む短いプログラム。

クヌースとパルドが論文で発表し、言語ごとの構文や機能の違いを明示する例題として使われた。

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

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

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

Unicode文字列を言語や文化に応じた適切な順序で並べ替えるための標準的な手法である。

多段階の重み付けを用いて、大文字小文字やアクセントの有無などを考慮した比較を行う。

データベースのソートや検索エンジンのインデックス作成など、多言語対応の基盤として広く利用される。

テキサス・インスツルメンツ社が策定した、DSP向けデジタル信号処理アルゴリズムの標準規格。

アルゴリズムの再利用性を高めるため、メモリ管理やリソース割り当てのインターフェースを定義する。

異なるベンダーが作成したソフトウェアを同一のシステム上で容易に統合することを可能にする。

一時的な作業用変数を使わずに、2つの変数の値を入れ替えるための計算手法である。

排他的論理和演算を3回繰り返すことで、ビット反転の性質を利用して値を交換する。

メモリ制約の厳しい古い環境で重宝されたが、現代のCPUでは通常の交換より遅い場合が多い。

北米や日本のデジタル通信で使われる、音声信号の対数圧縮伸張方式。

微小な音の解像度を高め、信号のダイナミックレンジを効率的に符号化する。

ITU-T勧告G.711で規定されており、電話回線の標準規格となっている。

統計力学のイジング模型などのシミュレーションで、スピンの集団を一度に反転させる手法。

相転移付近で計算効率が著しく低下する「臨界スローイングダウン」を劇的に改善する。

クラスター形成アルゴリズムの一種であり、モンテカルロ法の精度向上に貢献した。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

線形計画問題を解くための手法で、領域の内部を通って最適解を探索する内点法の一種。

従来の単体法と比較して、大規模な問題に対して理論的に優れた計算速度を持つ。

最適化数学の分野に革命をもたらし、物流や金融など実社会の複雑な最適化に貢献した。

円周率（π）を非常に高速に計算するための反復アルゴリズム。

反復ごとに精度が倍々で向上する（2次収束）という驚異的な収束速度を持つ。

コンピュータを用いた円周率の世界記録更新において、主要な手法として長年採用されてきた。

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

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

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

一階述語論理の定理証明において、エルブランの定理に基づく初期の手法。

論理式の充足不能性を判定するために、基底例を順次生成して検証する。

計算効率に課題があったが、後の自動定理証明技術の基礎となった。

項書き換え系において、与えられた等式の集合を完備な書き換え系に変形する手法。

合流性と停止性を備えることで、項の等価性を効率的に判定可能にする。

自動定理証明や数式処理システムの最適化などに広く応用されている。

巡回セールスマン問題において、近似比1.5を保証する近似アルゴリズム。

最小全域木と最小重量マッチングを組み合わせ、オイラー閉路を構築する。

多項式時間で動作し、一般的な距離空間におけるTSPの解法として重要である。

未整列のデータベースから特定のデータを探索する、量子コンピュータ向けのアルゴリズム。

古典的な探索がN回必要なのに対し、√N回の試行で目的のデータを見つけ出せる。

量子状態の振幅を増幅させる手法を用いており、暗号解読などへの応用が期待される。

楕円曲線の点の個数を効率的に計算するための数学的アルゴリズム。

スクーフのアルゴリズムを改良し、巨大な素数体上でも高速に動作する。

楕円曲線暗号の安全性評価や鍵生成の実装において不可欠な技術である。

統計力学のイジング模型などをシミュレーションするためのモンテカルロ法の一種。

スピンの集団（クラスター）を一度に更新することで、相転移付近での計算効率を劇的に高める。

臨界減速の問題を解決する手法として、計算物理学で広く利用されている。

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

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

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

2つのプロセスが共有メモリを介して互いに排他制御を行うための、最初期のアルゴリズム。

特別なハードウェア命令を必要とせず、ソフトウェアのみで相互排除を実現する。

現代ではより効率的な手法があるが、並列処理の理論的基礎として重要。

一階述語論理の論理式の妥当性を判定するための、初期の自動定理証明アルゴリズム。

命題論理の充足可能性問題（SAT）を解くDPLLアルゴリズムの基礎となった。

計算機による論理推論の自動化における先駆的な成果である。

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

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

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

与えられた点を通る多項式補間を、再帰的な計算によって効率的に求める手法。

ラグランジュ補間を逐次的に計算する形になっており、計算精度の管理がしやすい。

数値解析において、未知の関数値を近似的に求める際に利用される。

英単語を改行する際、適切な位置にハイフンを挿入するための計算手順。

言語ごとの綴りの規則や例外辞書を組み合わせて、読みやすい組版を実現する。

TeXなどの文書作成ソフトに搭載され、美しいテキストレイアウトを支えている。

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

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

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

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

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

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

凸最適化問題を解くための反復手法で、目的関数を線形近似して解を更新する。

各ステップで線形問題を解くだけで済むため、制約条件が複雑な場合に効率的である。

機械学習のスパース学習や、交通流の割り当て問題などで広く利用されている。

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

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

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