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

ビットの設定：各ビットは 2 のべき乗（128、64、…、1）の値をもちます。16 進の 1 桁はちょうど 4 ビットで、8 ビットの 2 の補数では、いちばん左のビットの値は −128 です。ビット演算は、各ビット位置を別々に扱います。

ビットの設定：各ビットは 2 のべき乗（128、64、…、1）の値をもちます。16 進の 1 桁はちょうど 4 ビットで、8 ビットの 2 の補数では、いちばん左のビットの値は −128 です。ビット演算は、各ビット位置を別々に扱います。

論理的同値：2 つの論理式は、真理値表のすべての行で同じ値をとるとき同値（≡）です。恒真式（トートロジー）はすべての行で 1、矛盾（恒偽式）はすべての行で 0、どちらでもないものは充足可能な非恒真式です。役に立つ法則：ド・モルガンの法則 ¬(a ∧ b) ≡ ¬a ∨ ¬b と ¬(a ∨ b) ≡ ¬a ∧ ¬b、a → b ≡ ¬a ∨ b ≡ ¬b → ¬a（対偶）、¬(a → b) ≡ a ∧ ¬b、そして分配法則 a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)。

真理値表：n 個の異なる変数をもつ論理式には、真理値のすべての組み合わせに対応する 2ⁿ 行があります（1 = 真、0 = 偽）。内側から順に進め、部分式ごとに列を用意します。¬a は値を反転させ、a ∧ b は両方が 1 のときだけ 1、a ∨ b は両方が 0 のときだけ 0、a → b は a = 1 かつ b = 0 のときだけ 0、a ↔ b は両辺が等しいとき 1 です。

ブール代数：式を簡単にする規則は、X + X′ = 1 と X·X′ = 0、X + X = X、吸収則 X + X·Y = X、結合則 X·Y + X·Y′ = X、X + X′Y = X + Y、そしてコンセンサス定理 XY + X′Z + YZ = XY + X′Z です。ド・モルガンの法則は (X·Y)′ を X′ + Y′ に、(X + Y)′ を X′·Y′ に変えます。カルノー図はこれらの規則を図で適用するものです：隣り合う 2 つのセルのグループは、XY + XY′ = X を 1 回使うことに当たります。

カルノー図：セルはグレイコード（00, 01, 11, 10）の順に並んでいるので、端をまたぐものも含め、隣り合うセルはちょうど 1 つの変数だけが異なります。1 を、1, 2, 4, 8, 16 個のセルからなる長方形で、できるだけ大きく、できるだけ少ない数でグループ化し、すべての 1 を覆います。各グループは 1 つの積項で、グループの中で一定のままの変数からなります。2ᵏ 個のセルのグループでは k 個の変数が消えます。ドントケア（X）はグループを大きくするために使えますが、覆う必要はありません。代わりに 0 をグループ化すると、最小の POS 形が得られます。

逆元と合同式：a が n を法として逆元をもつのは、gcd(a, n) = 1 のときに限ります。拡張ユークリッドの互除法で 1 = s·n + t·a と書くと、a⁻¹ ≡ t (mod n) です。gcd(a, n) = 1 のとき、合同式 a·x ≡ b (mod n) の解は x ≡ a⁻¹·b です。法が互いに素な 2 つの合同式 x ≡ r₁ (mod m₁) と x ≡ r₂ (mod m₂) には、m₁·m₂ を法として 1 つの解があります（中国の剰余定理）。オイラーの φ(n) は、1 から n までの数のうち n と互いに素なものの個数です：φ(n) = n·∏(1 − 1/p)。

冪剰余と RSA：aᵏ mod n は反復二乗法で計算します：k を 2 進数で書き、二乗し、毎回簡約し、ビットが 1 の冪を掛けます。フェルマー：素数 p が a を割り切らないとき aᵖ⁻¹ ≡ 1 (mod p) なので、指数は p − 1 を法として簡約できます。RSA：素数 p と q を選び、n = p·q、φ(n) = (p − 1)(q − 1) とします。公開指数 e は φ(n) と互いに素で、秘密指数は d = e⁻¹ mod φ(n) です。暗号化は c = mᵉ mod n、復号は m = cᵈ mod n で行います。

オイラー、ハミルトン、木：連結グラフは、すべての頂点の次数が偶数のときオイラー閉路（すべての辺を 1 回ずつ通って始点に戻る）をもち、ちょうど 2 つの頂点の次数が奇数のとき、閉路でないオイラー路をもちます。その路は、一方の奇数次数の頂点から他方へ通ります。ハミルトン閉路はすべての頂点を 1 回ずつ訪れ、K_n には (n − 1)!/2 個あります。n 個の頂点をもつ木には n − 1 本の辺があり、m 本の辺をもつ連結グラフは、m − n + 1 本の辺を取り除いても全域木が残ります。

次数：頂点の次数は、その頂点に接する辺の数です。どの辺にも端が 2 つあるので、次数の和は辺の数の 2 倍になります：Σ deg(v) = 2|E|（握手補題）。したがって、奇数次数の頂点の数は偶数です。K_n には n(n − 1)/2 本の辺があり、n 個の頂点をもつ k 正則グラフには nk/2 本、n 個の頂点をもつ木には n − 1 本の辺があります。

IPv4 subnetting: an address has 32 bits. The prefix /p says how many leading bits identify the network; the remaining 32 − p bits number the hosts. A subnet has 2³²⁻ᵖ addresses, but the first (network address) and last (broadcast address) cannot be given to hosts, so 2³²⁻ᵖ − 2 hosts fit. Exceptions: a /31 (point-to-point link, RFC 3021) uses both of its 2 addresses for hosts, and a /32 is one single address (a single host or a loopback).

IPv4 サブネット化：アドレスは 32 ビットです。プレフィックス /p は先頭の何ビットがネットワークを表すかを示し、残りの 32 − p ビットでホストを番号付けします。サブネットには 2³²⁻ᵖ 個のアドレスがありますが、最初（ネットワークアドレス）と最後（ブロードキャストアドレス）はホストに割り当てられないため、2³²⁻ᵖ − 2 台のホストが収まります。 例外：/31（ポイントツーポイントリンク、RFC 3021）は 2 つのアドレスを両方ともホストに使い、/32 は単一のアドレス（単一ホストまたはループバック）です。