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

ビットの設定：各ビットは 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 です。

マルチプレクサ：2ⁿ 対 1 のマルチプレクサは、データ入力の 1 つを出力に通します。選択線を 2 進数として読んだ値が、どれを通すかを決めます。選択線 S₁S₀ = AB の 4 対 1 MUX では、F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃ です。データ入力を 0, 1, C, C′ につなぐと、MUX は A, B, C の任意の関数を出力でき、1 つのチップで論理をつくる一般的な方法です。

フリップフロップとカウンタ：フリップフロップは、有効なクロックエッジでだけ変化します。D は入力をコピーし（Q⁺ = D）、T は T = 1 のときトグルし、JK は 00 で保持、01 でリセット、10 でセット、11 でトグルします。n ビットの 2 進カウンタには 2ⁿ 個の状態があり、2ⁿ を法として数えます。mod-N カウンタは 0, 1, …, N − 1 と数えて 0 に戻り、2ⁿ ≥ N を満たす最小の n 個のフリップフロップが必要です。リップルカウンタの各段は周波数を半分にするので、mod-N カウンタの最後の出力は f_clk/N で動作します。n 個のフリップフロップのジョンソンカウンタには 2n 個の状態があり、リングカウンタには n 個あります。

逆元と合同式：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 本の辺を取り除いても全域木が残ります。

最短経路と全域木：ダイクストラ法は毎ラウンド 1 つの頂点を確定します：暫定距離が最小の未確定の頂点です。その距離は最終となり、各隣接頂点 v は d(v) = min(d(v), d(u) + w(u, v)) と更新されます。クラスカル法は、辺を軽い順に取り、閉路をつくる辺を飛ばして最小全域木をつくります。プリム法は、始点から 1 本の木を成長させ、その木から出る最も軽い辺を常に加えます。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).

経路集約：集約経路 a.b.c.0/p は、最初の p ビットが一致するすべてのネットワークをカバーします。最初と最後のネットワークの異なるオクテットを 2 進数で書きます。共通する先頭のビット数に、それより前のオクテットのビット数を加えたものが最長の集約プレフィックスです。