今北産業pedia

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

形式論理学において、証明図から「カット」と呼ばれる中間ステップを取り除けるという定理。

任意の証明は、遠回りせずに直接的な推論のみで構成できることを数学的に示した。

計算機科学における型理論や、自動定理証明のアルゴリズムの基礎となっている。

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

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

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

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

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

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

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

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

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

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

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

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

集合論や論理学において、論理和と論理積の否定に関する基本的な法則。

「AかつB」の否定は「Aの否定またはBの否定」に等しいことを示す。

プログラミングの条件分岐を整理する際など、論理設計の現場で不可欠。

あらゆる問題に対して、常に他の手法より優れた万能な最適化アルゴリズムは存在しない。

特定の問題で高い性能を出す手法は、別の問題では必ず平均以下の性能になる。

機械学習において、モデルの選択が対象データに依存することを理論的に示した。

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

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

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