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

公式集、全トピックの解法の要点、20 問の演習問題。完全な解答は巻末にあります。

新しい問題科目に戻る

印刷ウィンドウで「PDF として保存」を選ぶと、コピーを端末に保存できます。

1公式と解法

記数法

位取り: 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

解き方

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

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

基本ゲート: 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（とドントケアは X として）を、行と列がグレイコード 00, 01, 11, 10 のカルノー図に書き込みましょう。
1 を、1, 2, 4, 8, 16 個のセルからなる、できるだけ少なくできるだけ大きなグループで、端をまたぎながら覆いましょう。各グループは、一定のままの変数からなる 1 つの積項です。POS 形には 0 をグループ化します。
フリップフロップとカウンタでは、各有効クロックエッジで入力を読み取り、エッジごとの状態を書き出し、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

解き方

まずすべての数を n で割った余りに直します。余りは 0 から n − 1 の間です。
最大公約数は、ユークリッドの互除法で割り算を繰り返して求めます。最後の 0 でない余りが最大公約数です。
逆元は拡張ユークリッドの互除法で求め、a の係数を取ります。負なら n を足します。
a·x ≡ b は a⁻¹ を掛けて解きます。2 つの合同式は x = r₁ + m₁k とおいて組み合わせます。
べき乗では、指数を 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

解き方

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

IPv4 サブネット化

サブネットあたりのホスト数: 2^{(32 − prefix)} − 2 (/31: 2, /32: 1)
ブロックサイズ: 256 − (mask octet)
ネットワークアドレス: IP AND マスク
ブロードキャストアドレス: IP OR (NOT マスク)：ホスト部のビットをすべて 1 にする
n ビット借りたときのサブネット数: 2ⁿ

2演習問題

1.記数法ふつう

8 ビットのパターン 1001 0011 は、符号付き整数を 2 の補数で表しています。10 進数での値 N はいくつですか？

1001 00118 bit

N =

2.記数法むずかしい

ビットを 1000 0110 OR 0101 0111 の 8 ビットの結果に設定します。結果の値 R は 10 進でいくつですか？

1000 0110OR0101 0111

R =

3.命題論理と証明ふつう

q ↔ ¬q は恒真式、矛盾、そのどちらでもない式のうちのどれですか？答えをクリックしてください。

q ↔ ¬q

1恒真式
2矛盾（恒偽式）
3恒真でも矛盾でもない式

4.命題論理と証明むずかしい

真理値表の 16 行のうち、¬(s ∨ ¬r) ↔ ((s ∧ p) → q) が真になるのは何行ですか？この数を N とします。

¬(s ∨ ¬r) ↔ ((s ∧ p) → q)

N =

5.デジタル論理：ゲート・カルノー図・フリップフロップふつう

カルノー図を使って F(A, B, C) = Σm(2, 3, 5) の最小の積和形（SOP）を求めてください。積項 N はいくつありますか？

F(A, B, C) = Σm(2, 3, 5)

N =

6.デジタル論理：ゲート・カルノー図・フリップフロップむずかしい

d はドントケア条件を表します。F(A, B, C, D) = Σm(3, 4, 10, 13, 15) + d(1, 8, 12) について、必須主項の個数 N を求めてください。

F(A, B, C, D) = Σm(3, 4, 10, 13, 15) + d(1, 8, 12)

N =

7.整数論と合同式ふつう

x ≡ 1 (mod 5) かつ x ≡ 5 (mod 6) を満たす最小の正の整数 x を求めてください。

x ≡ 1 (mod 5)x ≡ 5 (mod 6)

x =

8.整数論と合同式むずかしい

6x ≡ 15 (mod 75) は、{0, 1, …, 74} の中にいくつ解 N をもちますか？

6x ≡ 15 (mod 75)

N =

9.アルゴリズムと計算量ふつう

ある関数は n 回反復するループを 1 つ実行し、その後別に n 回反復するループをもう 1 つ実行します。時間計算量は何ですか？

AO(2ⁿ)
BO(n)
CO(log n)
DO(n²)

10.アルゴリズムと計算量むずかしい

最短単純路は多項式時間で見つけられます。一般のグラフで 2 頂点間の最長単純路を見つけることについて、何が知られていますか？

A決定不能である
B重みの符号を反転すればダイクストラ法で解ける
C常に O(V + E) で解ける
DNP 困難である

11.データ構造ふつう

二分ヒープに新しい要素はどのように挿入されますか。

Aより大きい要素をすべて 1 つ右にずらして、ソートされた位置に挿入する
Bヒープ全体を一から作り直す
C根に置き、下へ移動させる（sift down）
D配列の末尾に置き、ヒープ性に反している間は上へ移動させる（sift up）

12.データ構造むずかしい

n 個の数の配列に対するフェニック木（Binary Indexed Tree）が O(log n) でサポートする操作はどれですか。

A接頭辞和のクエリと単一要素の更新
B配列のソートと二分探索
C任意の位置への要素の挿入
DO(1) での中央値の検索

13.グラフ理論ふつう

連結グラフに 13 個の頂点と 16 本の辺があります。全域木にするには、辺を何本k取り除く必要がありますか？

|V| = 13|E| = 16

k =

14.グラフ理論むずかしい

ダイクストラ法を使って、重み付きグラフで A から F までの最短経路の長さd(F)を求めてください。

始点：A終点：F

d(F) =

15.データベースと SQLふつう

SELECT COALESCE(phone, 'unknown') FROM customers は、phone が NULL の顧客について何を返しますか？

ANULL
Bエラー
C'unknown'
D空文字列

16.データベースと SQLむずかしい

WHERE YEAR(order_date) = 2025 を含むクエリが order_date のインデックスを使わないことがあるのはなぜですか？

A列に関数を適用すると、単純なインデックス範囲検索ができなくなるから
BYEAR は有効な SQL ではないから
Cインデックスは日付では決して機能しないから
Dorder_date のインデックスは ORDER BY 句にしか使われず、WHERE には決して使われないから

17.コンピュータネットワークふつう

VLAN の主な目的は何ですか？

A1 つの物理的なスイッチネットワークを別々のブロードキャストドメインに分けること
Bすべてのスイッチポートの速度を上げること
C各デバイスにグローバル IP アドレスを与えること
D他の部署が読めないよう、スイッチ間のすべてのトラフィックを暗号化すること

18.コンピュータネットワークむずかしい

IPv6 のフラグメンテーションは IPv4 と比べてどう違いますか？

AIPv6 では 576 バイトより大きいパケットは許されない
BIPv6 ルーターは、転送する前に 64 バイトより大きいすべてのパケットをフラグメント化する
CIPv6 はトランスポート層で TCP の内部でフラグメント化する
Dルーターは IPv6 パケットを決してフラグメント化せず、パス MTU 探索を使って送信元だけがフラグメント化できる

19.IPv4 サブネット化ふつう

ある部署では、1 つのサブネット内に 1537 個のホストアドレスが必要です。十分な大きさとなる最長のプレフィックス長 p（最小のサブネット）はいくつですか？

1537 hosts

p =

20.IPv4 サブネット化むずかしい

あるホストのアドレスは 10.20.117.88/26 です。そのサブネットのブロードキャストアドレスの最後の数（第 4 オクテット）x はいくつですか？

10.20.117.88/26

x =

3溶液

1.記数法

答え: N = −109

位取り記数法：各桁の値は、その数字に基数のべき乗を掛けたものです。2 進数では各桁の重みが 1、2、4、8、16、…、16 進数では 1、16、256、… で、A–F は 10–15 を表します。8 ビットの 2 の補数では、最上位ビットの重みが +128 ではなく −128 になり、こうして負の数を表します。

重みを合計する

ほかのビットは通常の正の重みのままです。

−128 + 16 + 2 + 1 = −109

答え

N = −109

2.記数法

答え: R = 215

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

ビットごとに

OR は、少なくとも一方のビットが 1 のところで 1 になります。

1000 0110

OR 0101 0111

= 1101 0111

結果の値

1101 0111₂ = 215

答え

R = 215

3.命題論理と証明

答え: 矛盾（恒偽式）

論理的同値：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)。

真理値表を行ごとに見る

q = 1: ¬q = 0, q ↔ ¬q = 0

q = 0: ¬q = 1, q ↔ ¬q = 0

分類

q ↔ ¬q: 0, 0

すべての行で 0：矛盾です。

答え

矛盾（恒偽式）

4.命題論理と証明

答え: N = 6

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

列

¬r; s ∨ ¬r; ¬(s ∨ ¬r); s ∧ p; (s ∧ p) → q; ¬(s ∨ ¬r) ↔ ((s ∧ p) → q)

p で分ける

p = 1: 4

p = 0: 2

N = 4 + 2 = 6

答え

N = 6

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

答え: N = 2

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

1 をグループ化する

各グループは 2ᵏ 個のセルからなる長方形です。端のセルは、反対側の端のセルと隣り合っています。

A′B

AB′C

最小の SOP 形

F = A′B + AB′C

N = 2

答え

N = 2

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

答え: N = 4

主項

1 と X からつくれる最大のグループ。

BC′D′, A′B′D, AB′D′, ABD, ABC′

必須主項

BC′D′, A′B′D, AB′D′, ABD

N = 4

答え

N = 4

7.整数論と合同式

答え: x = 11

逆元と合同式：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)。

1 番目の合同式

x = 1 + 5k

2 番目の合同式

1 + 5k ≡ 5 (mod 6) → 5k ≡ 4 (mod 6)

k ≡ 5·4 ≡ 2 (mod 6)

結果

x = 1 + 5·2 = 11

x = 11

確認: 11 mod 5 = 1, 11 mod 6 = 5

答え

x = 11

8.整数論と合同式

答え: N = 3

gcd で割る

gcd(6, 75) = 3

2x ≡ 5 (mod 25)

簡約した合同式を解く

2⁻¹ ≡ 13 (mod 25) → x ≡ 15 (mod 25)

75 を法とする解

x ∈ {15, 40, 65}

全域木の辺

13 − 1 = 12

取り除く辺

k = 16 − 12 = 4

答え

k = 4

14.グラフ理論

答え: d(F) = 10

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

ダイクストラ法をラウンドごとに

各行：確定した頂点、その最終距離、距離が改善される隣接頂点。

A (0): B: 1, C: 10

B (1): D: 3, G: 9

D (3): E: 9, F: 16

E (9): F: 10

G (9)

C (10)

F (10)

最短経路

A → B → D → E → F

必要なホストビット数

2¹⁰ − 2 = 1022 < 1537

2¹¹ − 2 = 2046 ≥ 1537 → h = 11

プレフィックス長

p = 32 − 11 = 21

答え

p = /21

20.IPv4 サブネット化

答え: x = 127

ブロックサイズ

2⁶ = 64

このホストのサブネット

ネットワーク: ⌊88/64⌋·64 = 64

ブロードキャスト: 64 + 64 − 1 = 127

使えるホスト: 65 … 126

答え

x = 127

ExamProblems · examproblems.com/courses/computer-science-fundamentals