記号索引
各章で使う主要記号の早見表。章本文の「この章で使う記号」と同じ情報を横断的に確認する。
| 記号 | 意味 | 関連章 |
|---|---|---|
x ∈ A |
x が集合 A の要素である |
第1章 集合と論理 |
A ⊆ B |
A が B の部分集合である |
第1章 集合と論理 |
A ∪ B |
和集合 | 第1章 集合と論理 |
A ∩ B |
共通部分 | 第1章 集合と論理 |
∅ |
空集合 | 第1章 集合と論理 |
¬P |
命題 P の否定 |
第1章 集合と論理 |
P → Q |
P ならば Q |
第1章 集合と論理 |
∀x P(x) / ∃x P(x) |
全称量化 / 存在量化 | 第1章 集合と論理 |
f: A → B |
集合 A から集合 B への関数 |
第2章 関数と関係 |
f(x) |
x に対する関数値 |
第2章 関数と関係 |
f ∘ g |
関数合成 | 第2章 関数と関係 |
R ⊆ A × B |
A と B の間の二項関係 |
第2章 関数と関係 |
a R b |
a と b が関係 R にある |
第2章 関数と関係 |
[a] |
a の同値類 |
第2章 関数と関係 |
≤ |
順序関係の代表記号 | 第2章 関数と関係 |
R* |
反射推移閉包を表すことが多い記号 | 第2章 関数と関係 |
P ⇒ Q |
P から Q が従う |
第3章 証明技法 |
¬Q ⇒ ¬P |
対偶 | 第3章 証明技法 |
∀n ∈ N |
自然数全体に対する主張 | 第3章 証明技法 |
Base |
帰納法の基底部 | 第3章 証明技法 |
Step |
帰納法の帰納ステップ | 第3章 証明技法 |
I(k) |
ループ不変条件や帰納法の仮定を表す記号 | 第3章 証明技法 |
⊥ |
矛盾を表すことがある記号 | 第3章 証明技法 |
O(g(n)) |
上界 | 第4章 漸近記法 |
Ω(g(n)) |
下界 | 第4章 漸近記法 |
Θ(g(n)) |
上下界が同じ増加率 | 第4章 漸近記法 |
o(g(n)) |
真に小さい増加率 | 第4章 漸近記法 |
Σ |
総和 | 第4章 漸近記法 |
log n |
対数。底は定数なら漸近的に同等 | 第4章 漸近記法 |
T(n) |
入力サイズ n に対する実行時間の関数 |
第4章 漸近記法 |
x := v |
x に v を代入する擬似コード記法 |
第5章 擬似コードと再帰 |
if / else |
条件分岐 | 第5章 擬似コードと再帰 |
while / for |
反復 | 第5章 擬似コードと再帰 |
return |
関数の戻り値 | 第5章 擬似コードと再帰 |
A[i] |
配列 A の i 番目の要素 |
第5章 擬似コードと再帰 |
len(A) |
列や配列の長さ | 第5章 擬似コードと再帰 |
call f(x) |
関数呼び出し | 第5章 擬似コードと再帰 |
G = (V, E) |
頂点集合 V と辺集合 E からなるグラフ |
第6章 グラフと木 |
deg(v) |
頂点 v の次数 |
第6章 グラフと木 |
u ↝ v |
u から v へ到達可能であることを表す記法 |
第6章 グラフと木 |
d(s, v) |
始点 s から v までの距離 |
第6章 グラフと木 |
T |
木を表すことが多い記号 | 第6章 グラフと木 |
DAG |
有向非巡回グラフ | 第6章 グラフと木 |
|A| |
集合 A の要素数 |
第7章 組合せと数え上げ |
n! |
n の階乗 |
第7章 組合せと数え上げ |
C(n,k) / \binom{n}{k} |
n 個から k 個を選ぶ組合せ数 |
第7章 組合せと数え上げ |
P(n,k) |
n 個から k 個を順に選ぶ順列数 |
第7章 組合せと数え上げ |
2^A |
集合 A の冪集合を表すことがある記号 |
第7章 組合せと数え上げ |
Σ / Π |
総和 / 総積 | 第7章 組合せと数え上げ |
push(x) / pop() |
スタック操作 | 第8章 データ構造と基本アルゴリズム |
enqueue(x) / dequeue() |
キュー操作 | 第8章 データ構造と基本アルゴリズム |
find(x) / union(x,y) |
Union-Find の代表元取得と併合 | 第8章 データ構造と基本アルゴリズム |
key |
比較・検索に使う値 | 第8章 データ構造と基本アルゴリズム |
h(k) |
ハッシュ関数 | 第8章 データ構造と基本アルゴリズム |
O(1) / O(log n) / O(n) |
主要操作の計算量表記 | 第8章 データ構造と基本アルゴリズム |
Σ |
アルファベット | 第9章 形式言語の入口 |
Σ* |
Σ 上のすべての有限文字列の集合 |
第9章 形式言語の入口 |
ε |
空文字列 | 第9章 形式言語の入口 |
|w| |
文字列 w の長さ |
第9章 形式言語の入口 |
uv |
文字列 u と v の連結 |
第9章 形式言語の入口 |
L ⊆ Σ* |
言語 L は文字列集合である |
第9章 形式言語の入口 |
δ |
遷移関数 | 第9章 形式言語の入口 |
q0, F |
初期状態、受理状態集合 | 第9章 形式言語の入口 |
Ω |
標本空間 | 第10章 確率の基礎 |
A ⊆ Ω |
事象 | 第10章 確率の基礎 |
Pr[A] |
事象 A の確率 |
第10章 確率の基礎 |
Pr[A | B] |
B が起きた条件での A の条件付き確率 |
第10章 確率の基礎 |
X |
確率変数 | 第10章 確率の基礎 |
E[X] |
期待値 | 第10章 確率の基礎 |
Var(X) |
分散 | 第10章 確率の基礎 |
I_A |
事象 A の指示変数 |
第10章 確率の基礎 |
a | b |
a が b を割り切る |
第11章 数論・代数の基礎 |
gcd(a,b) |
a と b の最大公約数 |
第11章 数論・代数の基礎 |
a ≡ b (mod n) |
a と b が n を法として合同 |
第11章 数論・代数の基礎 |
[a]_n |
n を法とした剰余類 |
第11章 数論・代数の基礎 |
Z_n |
n を法とする剰余類の集合 |
第11章 数論・代数の基礎 |
x^{-1} |
乗法逆元 | 第11章 数論・代数の基礎 |
G = <g> |
g が生成する巡回群 |
第11章 数論・代数の基礎 |
F_p |
素数 p 個の元を持つ有限体 |
第11章 数論・代数の基礎 |
x ∈ F^n |
体 F 上の n 次元ベクトル |
第12章 線形代数の最小限 |
A ∈ F^{m×n} |
m × n 行列 |
第12章 線形代数の最小限 |
Ax = b |
連立一次方程式 | 第12章 線形代数の最小限 |
rank(A) |
行列 A のランク |
第12章 線形代数の最小限 |
I |
単位行列 | 第12章 線形代数の最小限 |
F_2 |
2元体 | 第12章 線形代数の最小限 |
G / H |
生成行列 / 検査行列として使われることが多い記号 | 第12章 線形代数の最小限 |
d(x,y) |
Hamming距離などの距離 | 第12章 線形代数の最小限 |
S |
状態集合 | 第13章 並行性と形式モデルの入口 |
s → s' |
状態 s から s' への遷移 |
第13章 並行性と形式モデルの入口 |
trace |
実行の列 | 第13章 並行性と形式モデルの入口 |
□P |
常に P が成り立つ |
第13章 並行性と形式モデルの入口 |
◇P |
いつか P が成り立つ |
第13章 並行性と形式モデルの入口 |
hb |
happens-before 関係 | 第13章 並行性と形式モデルの入口 |
f |
許容故障数として使われることが多い記号 | 第13章 並行性と形式モデルの入口 |