理論計算機科学教科書

付録D: 用語集・索引

理論計算機科学で使用される専門用語の日英対訳と詳細な説明です。 （主要トピックへの関連章リンクを併記しています）

A

アルゴリズム (Algorithm)

  • 問題を解くための明確で有限な手順の集合
  • 入力から出力への変換プロセス
  • 正確性、有限性、効率性が要求される

アクセプタ (Acceptor)

  • 入力文字列を受理または拒否する計算装置
  • 有限オートマトン、プッシュダウンオートマトン等

アルファベット (Alphabet)

  • 記号の有限集合（通常Σで表記）
  • 例: Σ = {0, 1}, Σ = {a, b, c}

AND（論理積, AND Operation）

  • 論理積、∧記号で表記
  • P ∧ Q は P と Q が共に真のときのみ真

等確率分割性（AEP, Asymptotic Equipartition Property）

  • 長い列の振る舞いが“ほぼ一様”な典型集合に集中するという情報源の性質
  • 情報源符号化（データ圧縮）の理論的基盤（→ 第10章: 情報理論: ../chapter-10/index.md）

増加路 (Augmenting Path)

  • 残余グラフ G_f における s から t へのパスで、各辺に正の残余容量があるもの
  • 見つかった場合、そのボトルネック残余容量だけフローを増やせる（→ 第8章: ネットワークフロー: ../chapter-8/index.md）

B

ビッグオー記法（Big-O Notation）

  • 関数の上界を表す漸近記法
  • f(n) = O(g(n)): f(n)はg(n)の定数倍を漸近的に超えない
  • 時間・空間複雑性の解析に使用

二分探索 (Binary Search)

  • ソート済み配列に対する効率的な探索アルゴリズム
  • 時間複雑性: O(log n)
  • 分割統治法の典型例

背理法 (Proof by Contradiction)

  • 証明したい命題の否定を仮定し、矛盾を導く証明技法
  • 決定不可能性の証明によく使用される

C

チューリング機械 (Turing Machine)

  • 理論計算機科学の基本的計算モデル
  • 無限テープ、ヘッド、状態集合から構成
  • 計算可能性の定義に使用（→ 第2章: 計算理論の基礎: ../chapter-2/index.md）

Church-Turing仮説 (Church-Turing Thesis)

  • 直感的に計算可能な関数はチューリング機械で計算可能
  • 計算可能性の基本仮説

複雑性クラス (Complexity Class)

  • 同程度の計算資源で解ける問題の集合
  • P, NP, PSPACE, EXPTIME等（→ 第5章: 計算複雑性理論: ../chapter-5/index.md）

文脈自由文法 (Context-Free Grammar)

  • 型2文法、プッシュダウンオートマトンと対応
  • A → α の形の生成規則（Aは非終端記号）（→ 第3章: 形式言語とオートマトン理論: ../chapter-3/index.md）

計算可能性 (Computability)

  • アルゴリズムによって解ける問題の性質
  • チューリング機械による定式化（→ 第4章: 計算可能性理論: ../chapter-4/index.md）

通信路容量（Channel Capacity）

  • ある通信路で任意に小さい誤り確率で伝送できる最大レート C。離散無記憶通信路では C = max_{P(X)} I(X;Y)
  • 通信路符号化定理の中心概念（→ 第10章: 情報理論: ../chapter-10/index.md）

補有限 (Cofinite)

  • 補集合が有限である言語（Σ* \ L が有限）
  • 例: L が「有限に多くの語を除いてすべてを含む」場合
  • Rice の定理の例として登場（→ 第4章: 計算可能性理論: ../chapter-4/index.md）

カット (s–t Cut)

  • フローネットワークの頂点分割 (S,T) で s∈S, t∈T を満たすもの
  • カット容量 c(S,T) = ∑_{u∈S, v∈T} c(u,v)
  • 最大フロー最小カット定理（→ 第8章: ネットワークフロー: ../chapter-8/index.md）

D

決定可能性（Decidability）

  • ある問題に対してyes/noの答えを常に出力するアルゴリズムが存在する性質
  • 決定可能言語 = 再帰言語
  • 参考: 第4章「決定不能問題」「還元可能性」（→ ../chapter-4/index.md）

決定性有限オートマトン（Deterministic Finite Automaton, DFA）

  • 各状態・入力記号の組に対して遷移先が一意に決まるFA
  • 正規言語を認識する最も基本的な計算モデル（→ 正規言語とDFA: ../chapter-3/index.md）

深さ優先探索（Depth-First Search, DFS）

  • グラフ探索アルゴリズムの一種
  • スタックまたは再帰を使用
  • 時間複雑性: O(V + E)

分割統治法（Divide and Conquer）

  • 問題を小さな部分問題に分割し、解を統合する手法
  • マージソート、クイックソート等で使用

動的計画法（Dynamic Programming）

  • 最適部分構造を持つ問題に対する最適化手法
  • メモ化により重複計算を避ける

ブロッキングフロー (Blocking Flow)

  • レベルグラフにおいて、s→t のすべてのパスが少なくとも1本の飽和辺を含むまで押し上げたフロー
  • Dinic の各フェーズで計算（→ 第8章: ネットワークフロー: ../chapter-8/index.md）
  • この状態では当該レベルグラフに増加路は存在しない

学習節（Learned Clause）

  • CDCLにおいて競合分析で導出される節。以後の探索で同じ失敗を避けるために追加される

非年代戻り（Non-chronological Backtracking）

  • CDCLで、直前の分岐に限らず原因レベルまで戻るバックトラック戦略

E

空文字列（Empty String）

  • 長さ0の文字列、εまたはλで表記
  • すべての言語の部分集合

空集合（Empty Set）

  • 要素を含まない集合、∅で表記
  • すべての集合の部分集合

ユークリッドアルゴリズム（Euclidean Algorithm）

  • 最大公約数を求める効率的アルゴリズム
  • 時間複雑性: O(log min(a,b))

指数時間（Exponential Time）

  • 実行時間がO(2^n)等の指数関数となるアルゴリズム
  • 多くのNP完全問題の既知最良解法

F

有限オートマトン（Finite Automaton）

  • 有限個の状態を持つ計算装置
  • DFA（決定性）とNFA（非決定性）がある

形式言語（Formal Language）

  • ある言語が表現するパターンを数学的に定義したもの
  • チョムスキー階層による分類

関数（Function）

  • 定義域の各要素を値域の要素に対応させる規則
  • f: A → B で表記

G

文法（Grammar）

  • 言語を生成するための規則の集合
  • G = (V, T, P, S)で定義（V: 非終端記号, T: 終端記号, P: 生成規則, S: 開始記号）

グラフ（Graph）

  • 頂点（V）と辺（E）の集合 G = (V, E)
  • 有向グラフと無向グラフがある
  • 応用と表現は第8章を参照（→ 第8章: グラフ理論とネットワーク: ../chapter-8/index.md）

貪欲法（Greedy Algorithm）

  • 各段階で局所的に最適な選択をする手法
  • 最短路問題（ダイクストラ法）等で使用

最大公約数（Greatest Common Divisor, GCD）

  • 2つの整数の共通約数の最大値
  • ユークリッドアルゴリズムで効率的に計算

H

停止問題（Halting Problem）

  • チューリング機械が与えられた入力で停止するかを判定する問題
  • 決定不可能問題の代表例

ハッシュ関数（Hash Function）

  • 任意サイズのデータを固定サイズの値に写像する関数
  • ハッシュテーブルで使用

ハミルトン経路（Hamiltonian Path）

  • グラフのすべての頂点を正確に一度ずつ通る経路
  • NP完全問題
  • NP完全性の文脈は第5章を参照（→ 第5章: 計算複雑性理論: ../chapter-5/index.md）

I

帰納法（Induction）

  • 数学的帰納法: P(1) ∧ ∀k(P(k) → P(k+1)) → ∀n P(n)
  • 構造帰納法: データ構造に対する帰納的証明

単射（Injection）

  • 異なる入力は異なる出力を持つ関数
  • ∀x,y ∈ A, f(x) = f(y) → x = y

共通部分（intersection）

  • 2つの集合の共通要素の集合
  • A ∩ B = {x x ∈ A ∧ x ∈ B}

相互情報量（Mutual Information）

  • 確率変数 X と Y の情報共有量：I(X;Y) = H(X) + H(Y) − H(X,Y) = H(X) − H(X Y)
  • 情報源・通信路の依存関係や特徴量選択の評価に用いる（→ 第10章: 情報理論: ../chapter-10/index.md）

J

結合 (Join)

  • グラフ理論: 2つの頂点を結ぶ操作
  • データベース: テーブル間の結合操作

K

Kleene閉包 (Kleene Closure)

  • 言語Lに対するL* = L⁰ ∪ L¹ ∪ L² ∪ …
  • 0回以上の連接

クラフトの不等式（Kraft–McMillan Inequality）

  • 一意復号可能符号の符号長 l₁,…,lₙ に対し ∑ D^{-lᵢ} ≤ 1（D は符号アルファベットの基数）
  • 逆に、この不等式を満たす長さの組から瞬時符号の構成が可能（→ 第10章: 情報理論: ../chapter-10/index.md）

L

言語 (Language)

  • アルファベット上の文字列の集合
  • L ⊆ Σ*

線形探索 (Linear Search)

  • 配列を先頭から順番に探索するアルゴリズム
  • 時間複雑性: O(n)

対数時間 (Logarithmic Time)

  • 実行時間がO(log n)のアルゴリズム
  • 二分探索等で実現

最長共通部分列 (Longest Common Subsequence, LCS)

  • 2つの列の最長の共通部分列を求める問題
  • 動的計画法で O(mn) で解ける

Lempel–Ziv 符号（LZ 符号）

  • 辞書ベースの可逆圧縮（LZ77, LZ78）。定常エルゴード情報源で漸近的最適性（→ 第10章: 情報理論: ../chapter-10/index.md）

レベルグラフ (Level Graph)

  • 残余グラフ上で s からの BFS 距離で層を分け、距離が1増える辺のみを残したグラフ
  • Dinic のアルゴリズムでブロッキングフローを見つけるために用いる（→ 第8章: ネットワークフロー: ../chapter-8/index.md）

M

Master定理 (Master Theorem)

  • 分割統治アルゴリズムの漸化式を解く定理
  • T(n) = aT(n/b) + f(n) の形の式に適用

マッチング (Matching)

  • グラフにおいて、端点を共有しない辺の集合
  • 二部グラフの最大マッチング問題

メモ化 (Memoization)

  • 計算結果を保存して重複計算を避ける技法
  • 動的計画法の実装手法

最小カット (Minimum Cut)

  • ある s–t カット (S,T) のうち、容量 c(S,T) が最小のもの
  • 最大フロー最小カット定理により、最大フロー値と等しい（→ 第8章: ネットワークフロー: ../chapter-8/index.md）

N

非決定性 (Nondeterminism)

  • 複数の計算経路が可能な計算モデル
  • NFA、非決定性チューリング機械

NP完全 (NP-Complete)

  • NPクラスに属し、NPの任意の問題から多項式時間還元可能な問題
  • SAT、クリーク問題、巡回セールスマン問題等
  • 定義と例は第5章を参照（→ 第5章: 計算複雑性理論: ../chapter-5/index.md）

非決定性有限オートマトン (Nondeterministic Finite Automaton, NFA)

  • 各状態・入力記号の組に対して複数の遷移先を持てるFA
  • DFAと同等の認識能力

O

オラクル (Oracle)

  • ある問題を1ステップで解ける仮想的装置
  • 相対化による複雑性理論の研究

最適化問題 (Optimization Problem)

  • 制約の下で目的関数を最小化/最大化する問題
  • 決定問題の対比概念

P

多項式時間 (Polynomial Time)

  • 実行時間がO(n^k)（kは定数）のアルゴリズム
  • 効率的に解けるとみなされる

P vs NP問題 (P vs NP Problem)

  • P = NP か否かを問うミレニアム問題の一つ
  • 理論計算機科学の最重要未解決問題

プッシュダウンオートマトン (Pushdown Automaton, PDA)

  • スタックを持つ有限オートマトン
  • 文脈自由言語を認識

ポンピング補題（Pumping Lemma）

  • 言語のクラスに属さないことを証明する技法
  • 正規言語、文脈自由言語にそれぞれ存在

接頭語符号（Prefix Code, 瞬時符号）

  • どの符号語も他の符号語の接頭辞でない符号（瞬時復号可能）
  • クラフト–マクミランの不等式を満たす長さから構成可能（→ 第10章: 情報理論: ../chapter-10/index.md）

Q

クイックソート (Quicksort)

  • 分割統治による効率的ソートアルゴリズム
  • 平均時間複雑性: O(n log n)

キュー (Queue)

  • FIFO（先入れ先出し）データ構造
  • 幅優先探索で使用

R

還元 (Reduction)

  • ある問題を別の問題に変換すること
  • 計算可能性、複雑性の研究で重要
  • 形式と用例は第5章を参照（→ 第5章: 計算複雑性理論: ../chapter-5/index.md）

正規言語 (Regular Language)

  • 有限オートマトンで認識可能な言語
  • 正規表現で表現可能

正規表現 (Regular Expression)

  • 正規言語を表現する記法
  • 文字列パターンマッチングで使用

再帰 (Recursion)

  • 自分自身を呼び出すアルゴリズム設計技法
  • 数学的帰納法と密接な関係

Rice の定理 (Rice’s Theorem)

  • チューリング機械が受理する言語 L(M) に関する任意の「非自明な」意味的性質 P に対して、{⟨M⟩ L(M) が P を満たす} は決定不能
  • 非自明: P を満たす言語と満たさない言語が少なくとも1つずつ存在
  • 対象は意味的性質のみ（内部構造・状態数など構文的性質は対象外）
  • 典型例: 空言語性、有限性、正規性、ある語を含むか 等（いずれも決定不能）
  • 参考: 第4章「Rice の定理」（→ ../chapter-4/index.md）

残余グラフ (Residual Graph)

  • 現在のフロー f に対して、使用可能な追加容量（順方向）と巻き戻し容量（逆方向）を表すグラフ G_f
  • 増加路（augmenting path）の探索は残余グラフ上で行う（→ 第8章: ネットワークフロー: ../chapter-8/index.md）

残余ネットワーク (Residual Network)

  • 残余グラフと同義。文献によって network/graph を使い分ける
  • 辺の残余容量 c_f(u,v) に基づくネットワーク（→ 残余グラフ）

逆向き辺 (Reverse Edge)

  • 残余グラフにおける (v,u) の辺。現在のフロー f(u,v) を巻き戻す余地を表し、残余容量は c_f(v,u) = f(u,v)
  • 増加後の調整や循環の解消に用いられる（→ 第8章: ネットワークフロー）

残余容量 (Residual Capacity)

  • 残余グラフ G_f の辺 (u,v) における利用可能容量 c_f(u,v)
  • 順方向は未使用の余地、逆方向は既存フローの巻き戻し余地を表す

S

SAT問題 (Satisfiability Problem)

  • 論理式が充足可能かを判定する問題
  • 最初に証明されたNP完全問題（→ 第5章: NP完全性（Cook–Levin）: ../chapter-5/index.md）

集合 (Set)

  • 異なる要素の集まり
  • 数学の基本概念

スタック (Stack)

  • LIFO（後入れ先出し）データ構造
  • 深さ優先探索、再帰で使用

全射 (Surjection)

  • 値域のすべての要素が像に含まれる関数
  • ∀b ∈ B, ∃a ∈ A, f(a) = b

T

時間複雑性 (Time Complexity)

  • アルゴリズムの実行時間の解析
  • 入力サイズnの関数として表現

チューリング還元 (Turing Reduction)

  • オラクルを用いた還元
  • many-one還元より一般的

木 (Tree)

  • サイクルのない連結グラフ
  • データ構造、探索アルゴリズムで重要

U

和集合 (Union)

  • 2つの集合のいずれかに属する要素の集合
  • A ∪ B = {x x ∈ A ∨ x ∈ B}

全単射 (Bijection)

  • 単射かつ全射の関数
  • 一対一対応

V

検証器 (Verifier)

  • 解候補の正当性を確認するアルゴリズム
  • NP問題の定義で使用（→ 第5章: NPの検証的特徴付け: ../chapter-5/index.md）

頂点被覆 (Vertex Cover)

  • グラフのすべての辺を被覆する頂点集合
  • NP完全問題

W

最悪時間複雑性 (Worst-Case Time Complexity)

  • すべての入力に対する実行時間の上界
  • アルゴリズム解析の基本指標

X

XOR演算 (XOR Operation)

  • 排他的論理和、⊕記号で表記
  • P ⊕ Q は P と Q の真偽値が異なるときのみ真

Y

なし

Z

ゼロ知識証明 (Zero-Knowledge Proof)

  • 知識を明かすことなく知識の保有を証明する手法
  • 暗号理論で重要（→ 第11章: ゼロ知識証明: ../chapter-11/index.md）

記号索引

論理記号

  • ∧ (AND): 論理積
  • ∨ (OR): 論理和
  • ¬ (NOT): 否定
  • → (IMPLIES): 含意
  • ↔ (IFF): 同値
  • ∀ (FOR ALL): 全称量詞
  • ∃ (EXISTS): 存在量詞

集合記号

  • ∈ (IN): 要素の所属
  • ⊆ (SUBSET): 部分集合
  • ∪ (UNION): 和集合
  • ∩ (intersection): 共通部分
  • ∅ (EMPTY): 空集合
  • × (CARTESIAN): 直積

複雑性記号

  • O (BIG-O): 上界
  • Ω (BIG-OMEGA): 下界
  • Θ (BIG-THETA): 厳密な界
  • o (LITTLE-O): 真の上界
  • ω (LITTLE-OMEGA): 真の下界

形式言語記号

  • Σ (SIGMA): アルファベット
  • Σ* (SIGMA-STAR): 文字列全体
  • ε (EPSILON): 空文字列
  • w (LENGTH): 文字列の長さ

関数記号

  • f: A → B: AからBへの関数
  • dom(f): 定義域
  • ran(f): 値域
  • f⁻¹: 逆関数
  • g ∘ f: 合成関数

グラフ記号

  • G = (V,E): グラフ
  • V : 頂点数
  • E : 辺数
  • deg(v): 頂点vの次数
  • d(u,v): 頂点間距離

この用語集は理論計算機科学の学習において頻繁に参照されることを想定しており、各用語の正確な定義と関連概念を効率的に確認できるよう構成されています。

Edit this page on GitHub