コンピュータサイエンス基礎：直前対策パック

記数法

位取り

2 進数 2^k、8 進数 8^k、16 進数 16^k

10 進数へ

Σ d_k·b^k

10 進数から

基数で割り、余りを下から上へ読む

16 進数 ↔ 2 進数

16 進数 1 桁 = 4 ビット

2 の補数

ビットを反転して 1 を足す

命題論理と証明

真理値表の行

2ⁿ

含意

p → q ≡ ¬p ∨ q ≡ ¬q → ¬p

含意の否定

¬(p → q) ≡ p ∧ ¬q

同値（双条件）

p ↔ q ≡ (p → q) ∧ (q → p)

ド・モルガンの法則

¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q

分配法則

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

量化子の否定

¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)

肯定式（modus ponens）、否定式（modus tollens）

p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

解き方

1. 異なる変数の数を数えます：真理値表の行数は 2ⁿ で、最初の行はすべて 1 です。
2. 部分式ごとに列を用意し、内側から順に列を埋めていきます。
3. 各結合子の規則を適用します：→ が 0 になるのは 1 → 0 のときだけ、↔ は両辺が一致するとき 1 です。
4. 同値の判定では最後の列を行ごとに比べます。論証の判定では、すべての前提が 1 である行だけを見ます。
5. 量化された文を否定するには、¬ を内側へ移し、∀ と ∃ を入れ替え、内側の式を否定します。

デジタル論理：ゲート・カルノー図・フリップフロップ

基本ゲート

A·B, A + B, A′, (A·B)′, (A + B)′, A ⊕ B

ブールの規則

X + X′ = 1, X·X′ = 0, X + XY = X, XY + XY′ = X

ド・モルガンの法則

(X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′

カルノー図の並び順

00, 01, 11, 10 (Gray code)

2ᵏ 個のセルのグループ

k 個の変数が消える

4 対 1 マルチプレクサ

F = A′B′I₀ + A′BI₁ + AB′I₂ + ABI₃

フリップフロップ

D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q

カウンタ

n ビット：2ⁿ 状態； mod-N：2ⁿ ≥ N を満たす最小の n； f_out = f_clk/N

リップルカウンタ

f_max = 1/(n·t_pd)

リングカウンタとジョンソンカウンタ

n 状態と 2n 状態

解き方

1. 回路では、入力から出力へ向かってゲートを 1 つずつ進み、各配線に値を書き込むか、式を書いて真理値表を埋めましょう。
2. 簡単化するには、1（とドントケアは X として）を、行と列がグレイコード 00, 01, 11, 10 のカルノー図に書き込みましょう。
3. 1 を、1, 2, 4, 8, 16 個のセルからなる、できるだけ少なくできるだけ大きなグループで、端をまたぎながら覆いましょう。各グループは、一定のままの変数からなる 1 つの積項です。POS 形には 0 をグループ化します。
4. フリップフロップとカウンタでは、各有効クロックエッジで入力を読み取り、エッジごとの状態を書き出し、n ビットのカウンタは 2ⁿ 個の状態で折り返すことを忘れないようにしましょう。

整数論と合同式

余りのある割り算

a = q·n + r, 0 ≤ r < n

ユークリッド

gcd(a, b) = gcd(b, a mod b)

最小公倍数

lcm(a, b) = a·b/gcd(a, b)

逆行列

a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1

一次合同式

a·x ≡ b → x ≡ a⁻¹·b (mod n)

オイラーのトーシェント関数

φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹

フェルマー

aᵖ⁻¹ ≡ 1 (mod p)

RSA

n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

解き方

1. まずすべての数を n で割った余りに直します。余りは 0 から n − 1 の間です。
2. 最大公約数は、ユークリッドの互除法で割り算を繰り返して求めます。最後の 0 でない余りが最大公約数です。
3. 逆元は拡張ユークリッドの互除法で求め、a の係数を取ります。負なら n を足します。
4. a·x ≡ b は a⁻¹ を掛けて解きます。2 つの合同式は x = r₁ + m₁k とおいて組み合わせます。
5. べき乗では、指数を 2 進数で書いて平方を繰り返します。RSA では d = e⁻¹ mod φ(n)、φ(n) = (p − 1)(q − 1) です。

グラフ理論

握手補題

Σ deg(v) = 2|E|

完全グラフ

|E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n

正則グラフ

|E| = n·k/2

木と森

|E| = n − 1, |E| = n − c

木の葉

L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3

オイラー

閉路：すべての次数が偶数； 路：奇数次数がちょうど 2 つ

K_n のハミルトン閉路

(n − 1)!/2

ダイクストラ法の更新

d(v) = min(d(v), d(u) + w(u, v))

長さ L の歩道

(Mᴸ)_ij

解き方

1. 各頂点の次数を書き出します。次数の総和は辺の数の 2 倍になります。
2. オイラーの問題では、グラフが連結であることを確かめ、奇数次数の頂点を数えます。
3. 木では、辺が n − 1 本であることと握手補題を使います。
4. ダイクストラ法では、暫定距離の表をつくり、毎回、未確定の頂点のうち最小のものを確定します。
5. 最小全域木では、辺を重みの順に並べ、閉路をつくる辺を飛ばす方法（クラスカル法）か、始点から 1 本の木を成長させる方法（プリム法）を使います。

IPv4 サブネット化

サブネットあたりのホスト数

2^{(32 − prefix)} − 2 (/31: 2, /32: 1)

ブロックサイズ

256 − (mask octet)

ネットワークアドレス

IP AND マスク

ブロードキャストアドレス

IP OR (NOT マスク)：ホスト部のビットをすべて 1 にする

n ビット借りたときのサブネット数

2ⁿ