付録A 記号一覧
集合
| 記号 | 意味 |
|---|---|
x ∈ A |
x は A の要素 |
x ∉ A |
x は A の要素ではない |
A ⊆ B |
A は B の部分集合 |
A ⊂ B |
A は B の真部分集合 |
A = B |
A と B は同じ要素を持つ |
∅ |
空集合 |
A ∪ B |
和集合 |
A ∩ B |
共通部分 |
A \ B |
差集合 |
A^c |
補集合 |
P(A) |
A の冪集合 |
A × B |
直積 |
|A| |
A の要素数。文脈により文字列長も表す |
論理
| 記号 | 意味 |
|---|---|
¬P |
P でない |
P ∧ Q |
P かつ Q |
P ∨ Q |
P または Q |
P -> Q |
P ならば Q |
P <-> Q |
P と Q は同値 |
∀x P(x) |
すべての x について P(x) |
∃x P(x) |
ある x が存在して P(x) |
⊤ |
真 |
⊥ |
偽、矛盾 |
関数・関係
| 記号 | 意味 |
|---|---|
f: A -> B |
A から B への関数 |
f(a) |
a の f による値 |
g∘f |
関数合成。先に f、次に g |
R ⊆ A×B |
A と B の間の二項関係 |
a R b |
(a,b)∈R |
[a] |
a の同値類 |
≤ |
順序関係の典型記号 |
数
| 記号 | 意味 |
|---|---|
N |
自然数。文脈により 0 を含むか明示する |
Z |
整数全体 |
Q |
有理数全体 |
R |
実数全体 |
a | b |
a は b を割り切る |
a ≡ b (mod m) |
a と b は m を法として合同 |
組合せ
| 記号 | 意味 |
|---|---|
n! |
n の階乗。n(n-1)...1 |
P(n,k) |
n 個から k 個を順序付きで選ぶ数 |
C(n,k) |
n 個から k 個を順序なしで選ぶ数 |
(n choose k) |
C(n,k) と同じ意味 |
Σ |
総和記号。文脈によりアルファベットも表す |
漸近記法
| 記号 | 意味 |
|---|---|
O(g(n)) |
漸近的上界 |
Ω(g(n)) |
漸近的下界 |
Θ(g(n)) |
漸近的に同じ増加率 |
o(g(n)) |
厳密に小さい増加率 |
ω(g(n)) |
厳密に大きい増加率 |
グラフ
| 記号 | 意味 |
|---|---|
G=(V,E) |
頂点集合 V、辺集合 E を持つグラフ |
(u,v)∈E |
u から v への有向辺、または u-v の無向辺 |
deg(v) |
頂点 v の次数 |
dist(s,v) |
s から v への距離 |
DAG |
有向非巡回グラフ |
|V| |
頂点数 |
|E| |
辺数 |
データ構造
| 表記 | 意味 |
|---|---|
push(x) |
スタックへ x を積む |
pop() |
スタックから要素を取り出す |
enqueue(x) |
キューへ x を入れる |
dequeue() |
キューから要素を取り出す |
find(x) |
Union-Find で x の代表を返す |
union(x,y) |
x と y の属する集合を併合する |
deg(v) |
グラフで v に隣接する辺の数 |
文字列・形式言語
| 記号 | 意味 |
|---|---|
Σ |
アルファベット |
Σ* |
Σ 上のすべての有限文字列の集合 |
ε |
空文字列 |
uv |
文字列 u と v の連結 |
|w| |
文字列 w の長さ |
L |
言語。通常は L⊆Σ* |
L1L2 |
言語の連結 |
L* |
L の Kleene star。0回以上の連結 |
G=(V,Σ,R,S) |
文法。文脈によりグラフと同じ G を使うため注意 |
δ |
オートマトンの遷移関数 |
q0 |
初期状態 |
F |
受理状態集合 |
擬似コード
| 表記 | 意味 |
|---|---|
return |
値を返して関数を終了する |
break |
ループを抜ける |
continue |
次の反復へ進む |
A[i] |
配列 A の i 番目の要素 |
len(A) |
配列や文字列の長さ |
[left,right) |
left を含み right を含まない半開区間 |
確率
| 記号 | 意味 |
|---|---|
Ω |
標本空間 |
A, B |
事象。通常は Ω の部分集合 |
Pr[A] |
事象 A の確率 |
Pr[A | B] |
B が起きた条件のもとで A が起きる条件付き確率 |
A^c |
A の補事象 |
X, Y |
確率変数 |
E[X] |
X の期待値 |
Var[X] |
X の分散 |
I_A |
事象 A の指示変数 |
Bin(n,p) |
試行回数 n、成功確率 p の二項分布 |
H(X) |
確率変数 X のエントロピー |
数論・代数
| 記号 | 意味 |
|---|---|
gcd(a,b) |
a と b の最大公約数 |
a mod n |
a を n で割った余り |
a^{-1} mod n |
mod n における a の逆元 |
Z_n |
mod n の剰余類全体 |
Z_n^* |
mod n で乗法逆元を持つ剰余類全体 |
G |
群 |
e |
群の単位元 |
<g> |
g が生成する巡回群 |
F_p |
p 個の要素を持つ有限体。p が素数のとき mod p の体 |
F_2 |
2要素体。ビット計算で使う |
線形代数
| 記号 | 意味 |
|---|---|
R^n |
n 次元実ベクトル空間 |
F_2^n |
n 次元のビットベクトル空間 |
A |
行列 |
A^T |
A の転置行列 |
I |
単位行列 |
A^{-1} |
A の逆行列 |
Ax |
行列 A とベクトル x の積 |
rank(A) |
A のランク |
span(S) |
S の線形結合全体 |
ker(A) |
A の核。{x | Ax=0} |
im(A) |
A の像。{Ax | x} |
G |
線形符号の生成行列。文脈によりグラフや群も表す |
H |
線形符号の検査行列。文脈によりエントロピーも表す |
d(x,y) |
Hamming 距離などの距離 |
並行性・形式モデル
| 記号 | 意味 |
|---|---|
S |
状態集合 |
s, s' |
状態 |
s -> s' |
状態 s から s’ への遷移 |
s0 |
初期状態 |
T=(S,->,s0) |
遷移システム |
trace |
実行で観測されるイベント列 |
HB |
happens-before 関係を表す記号として使うことがある |
safety |
悪いことが起きない性質 |
liveness |
良いことがいつか起きる性質 |
invariant |
到達可能な全状態で成り立つ性質 |
m |
Petriネットのマーキング |
C |
Petriネットの接続行列 |