理論計算機科学教科書

付録D: 用語集・索引

理論計算機科学で使用される専門用語の日英対訳と詳細な説明です。

A

アルゴリズム (Algorithm)

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

アクセプタ (Acceptor)

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

アルファベット (Alphabet)

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

AND演算 (AND Operation)

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

B

ビッグオー記法 (Big-O Notation)

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

二分探索 (Binary Search)

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

背理法 (Proof by Contradiction)

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

C

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

  • 理論計算機科学の基本的計算モデル
  • 無限テープ、ヘッド、状態集合から構成
  • 計算可能性の定義に使用

Church-Turing仮説 (Church-Turing Thesis)

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

複雑性クラス (Complexity Class)

  • 同程度の計算資源で解ける問題の集合
  • P, NP, PSPACE, EXPTIME等

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

  • 型2文法、プッシュダウンオートマトンと対応
  • A → α の形の生成規則（Aは非終端記号）

計算可能性 (Computability)

  • アルゴリズムによって解ける問題の性質
  • チューリング機械による定式化

D

決定可能性 (Decidability)

  • ある問題に対してyes/noの答えを常に出力するアルゴリズムが存在する性質
  • 決定可能言語 = 再帰言語

決定性有限オートマトン (Deterministic Finite Automaton, DFA)

  • 各状態・入力記号の組に対して遷移先が一意に決まるFA
  • 正規言語を認識する最も基本的な計算モデル

深さ優先探索 (Depth-First Search, DFS)

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

分割統治法 (Divide and Conquer)

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

動的計画法 (Dynamic Programming)

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

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)
  • 有向グラフと無向グラフがある

貪欲法 (Greedy Algorithm)

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

最大公約数 (Greatest Common Divisor, GCD)

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

H

停止問題 (Halting Problem)

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

ハッシュ関数 (Hash Function)

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

ハミルトン経路 (Hamiltonian Path)

  • グラフのすべての頂点を正確に一度ずつ通る経路
  • NP完全問題

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}

J

結合 (Join)

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

K

Kleene閉包 (Kleene Closure)

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

L

言語 (Language)

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

線形探索 (Linear Search)

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

対数時間 (Logarithmic Time)

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

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

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

M

Master定理 (Master Theorem)

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

マッチング (Matching)

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

メモ化 (Memoization)

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

N

非決定性 (Nondeterminism)

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

NP完全 (NP-Complete)

  • NPクラスに属し、NPの任意の問題から多項式時間還元可能な問題
  • SAT、クリーク問題、巡回セールスマン問題等

非決定性有限オートマトン (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)

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

Q

クイックソート (Quicksort)

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

キュー (Queue)

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

R

還元 (Reduction)

  • ある問題を別の問題に変換すること
  • 計算可能性、複雑性の研究で重要

正規言語 (Regular Language)

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

正規表現 (Regular Expression)

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

再帰 (Recursion)

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

S

SAT問題 (Satisfiability Problem)

  • 論理式が充足可能かを判定する問題
  • 最初に証明されたNP完全問題

集合 (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問題の定義で使用

頂点被覆 (Vertex Cover)

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

W

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

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

X

XOR演算 (XOR Operation)

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

Y

なし

Z

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

  • 知識を明かすことなく知識の保有を証明する手法
  • 暗号理論で重要

記号索引

論理記号

  • ∧ (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): 頂点間距離

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