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

公式集、全トピックの解法の要点、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 ビットの 2 の補数で −92 を格納するようにビットを設定します。符号なしの数として読むと、このパターンの値 U はいくつですか？

N = −928 bit

U =

2.記数法むずかしい

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

1000 1101AND1101 1000

R =

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

p → (q ∨ r) を背理法によって証明しようとしています。最初に仮定する主張はどれですか？クリックしてください。

p → (q ∨ r)

1¬p ∧ ¬(q ∨ r)
2¬p → ¬(q ∨ r)
3¬p ∧ (q ∨ r)
4p ∧ ¬(q ∨ r)

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

否定を最も内側まで移したとき、¬∀x (A(x) → ∃y R(x, y)) と同値な主張はどれですか？クリックしてください。

¬∀x (A(x) → ∃y R(x, y))

1∃x (A(x) → ∀y ¬R(x, y))
2∀x (A(x) ∧ ∀y ¬R(x, y))
3∃x (A(x) ∧ ∀y ¬R(x, y))
4∃x (¬A(x) ∧ ∃y R(x, y))

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

カルノー図を使って F(A, B, C, D) = Σm(0, 8, 9, 11, 13, 14, 15) の最小の和積形（POS）を求めてください。和項（因数）N はいくつありますか？

F(A, B, C, D) = Σm(0, 8, 9, 11, 13, 14, 15)

N =

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

d はドントケア条件を表します。F(A, B, C, D) = Σm(2, 3, 9, 11, 15) + d(4, 6, 10, 12) の最小の SOP 形を求めてください。積項 N はいくつありますか？

F(A, B, C, D) = Σm(2, 3, 9, 11, 15) + d(4, 6, 10, 12)

N =

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

オイラーのトーシェント関数 φ(351)、つまり 1 から 351 までの整数のうち 351 と互いに素なものの個数を求めてください。

n = 351 = 3³·13

φ(351) =

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

8x ≡ 10 (mod 74) を解いてください。最小の正の解 x を答えてください。

8x ≡ 10 (mod 74)

x =

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

標準的な 3 重ループで 2 つの n × n 行列を掛ける時間計算量は何ですか？

AO(n² log n)
BO(n²)
CO(n)
DO(n³)

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

巡回セールスマン問題はどのように分類されますか？

A決定版は NP 完全で、最適化版は NP 困難である
Bダイクストラ法がすべての都市を 1 回ずつ訪れて解くので、P に属する
C決定不能である
D決定版は P に属するが、最適化版は NP 完全である

11.データ構造ふつう

二分探索木を中間順（in-order）でたどると、キーはどの順序で訪問されますか。

A昇順
Bレベル順
C常に降順
D挿入順

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

単純一様ハッシュの仮定の下で、n 個のキーと m 個のバケットをもつチェイン法のハッシュテーブルの探索の期待時間はどれですか。

AO(log n)
Bα = n / m として O(1 + α)
CO(m)
DO(n)

13.グラフ理論ふつう

木に次数 3 の頂点が 2 個, 次数 4 の頂点が 3 個, 次数 5 の頂点が 3 個, 次数 2 の頂点が 2 個があり、ほかのすべての頂点は葉（次数 1）です。葉は何枚Lありますか？

2 × deg 33 × deg 43 × deg 52 × deg 2

L =

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

重み付きグラフの最小全域木の重みの合計 W を求めてください。

|V| = 7|E| = 11

W =

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

customers テーブルの異なる都市の数を返すクエリはどれですか？

ASELECT DISTINCT COUNT(city) FROM customers
BSELECT COUNT(DISTINCT city) FROM customers
CSELECT SUM(DISTINCT city) FROM customers
DSELECT COUNT(city) FROM customers GROUP BY city

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

SELECT dept, name, COUNT(*) FROM emp GROUP BY dept が標準 SQL で無効なのはなぜですか？

Aname はグループ化も集約もされておらず、グループごとに 1 つの値を持たないから
BCOUNT(*) は GROUP BY と一緒に使えないから
Cdept は集約関数の中に入れなければならないから
DGROUP BY にはテーブルのすべての列を並べなければならないから

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

分散型サービス拒否（DDoS）攻撃の特徴はどれですか？

A攻撃者が近くの車から、暗号化されていない Wi-Fi のトラフィックを読む
Bウイルスが 1 台の PC のファイルを削除する
C1 人の攻撃者がユーザーのパスワードを推測する
D乗っ取られた多数のマシンが標的にトラフィックを大量に送りつける

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

無限カウント問題はどの種類のルーティングプロトコルで起こり、何がその対策になりますか？

Aリンクステート型。リンク更新のフラッディング
Bスタティックルーティング。デフォルトルートの追加
Cパスベクター型。より長い AS パス
Dディスタンスベクター型。スプリットホライズンとポイズンリバース

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

ネットワーク 10.118.8.0/22 を、プレフィックス /25 の等しいサブネットに分割します。サブネットはいくつ N ありますか？

10.118.8.0/22/25

N =

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

あるルータは次のネットワークへの経路をもっています：10.126.235.0/24, 10.126.236.0/24, 10.126.237.0/24, 10.126.238.0/24, 10.126.239.0/24。それらすべてをカバーする 1 つの集約経路の最長のプレフィックス長 p はいくつですか？

10.126.235.0/24 … 10.126.239.0/24

p =

3溶液

1.記数法

答え: U = 164

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

反転して 1 を足す

92 = 0101 1100

反転後: 1010 0011

+1 → 1010 0100

符号なしとして読む

1010 0100₂ = 256 − 92 = 164

答え

U = 164

2.記数法

答え: R = 136

ビットごとに

AND は、両方のビットが 1 のところだけ 1 になります。

1000 1101

AND 1101 1000

= 1000 1000

結果の値

1000 1000₂ = 136

答え

R = 136

3.命題論理と証明

答え: p ∧ ¬(q ∨ r)

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

含意の各部分

a = p, b = q ∨ r

含意の否定

¬(a → b) ≡ a ∧ ¬b = p ∧ ¬(q ∨ r)

答え

p ∧ ¬(q ∨ r)

仮定から矛盾が導かれるなら、その含意は真でなければなりません。

4.命題論理と証明

答え: ∃x (A(x) ∧ ∀y ¬R(x, y))

量化子と論証：¬∀x P(x) ≡ ∃x ¬P(x)、¬∃x P(x) ≡ ∀x ¬P(x)。否定を内側へ移し、通過する量化子をすべて入れ替え、内側の式は ¬(a → b) ≡ a ∧ ¬b のような命題論理の法則で否定します。論証は、すべての前提が 1 であるどの行でも結論が 1 のとき、妥当です。前提が真で結論が偽になる行が 1 つでもあれば、それは反例であり、その論証が妥当でないことを示します。

否定を内側へ移す

¬∀x (A(x) → ∃y R(x, y)) ≡ ∃x (A(x) ∧ ∀y ¬R(x, y))

答え

∃x (A(x) ∧ ∀y ¬R(x, y))

ほかの選択肢は、量化子がそのままになっているか、量化子の順序が変わっているか、内側の式の否定が間違っているかのどれかです。

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

答え: N = 4

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

0 をグループ化する

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

(B + C′ + D)

(B′ + C + D)

(A + D′)

(A + C′)

最小の POS 形

F = (B + C′ + D)(B′ + C + D)(A + D′)(A + C′)

N = 4

答え

N = 4

同じ大きさの別のグループ分けもあります。項の数もリテラルの数も同じです。

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

答え: N = 3

主項

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

B′C, A′CD′, ACD, AB′D

最小被覆

F = B′C + ACD + AB′D

N = 3

答え

N = 3

7.整数論と合同式

答え: φ(351) = 216

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

素因数

351 = 3³·13

トーシェント関数

φ(351) = φ(27)·φ(13) = 18·12 = 216

答え

φ(351) = 216

8.整数論と合同式

答え: x = 29

gcd で割る

gcd(8, 74) = 2

4x ≡ 5 (mod 37)

簡約した合同式を解く

4⁻¹ ≡ 28 (mod 37) → x ≡ 29 (mod 37)

74 を法とする解

x ∈ {29, 66}

木の握手補題

L + 37 = 2(L + 10) − 2

L = 19

答え

L = 19

近道：次数 d ≥ 3 の頂点について L = 2 + Σ (d − 2) です。

14.グラフ理論

答え: W = 41

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

クラスカル法

BD (1): 取る

AB (3): 取る

DE (5): 取る

BC (9): 取る

D · ディスタンスベクター型。スプリットホライズンとポイズンリバース

19.IPv4 サブネット化

答え: N = 8

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).

借りたビット

25 − 22 = 3

サブネット数

N = 2³ = 8

答え

N = 8

各 /25 サブネットには 2⁷ − 2 = 126 個の使えるホストがあります。

20.IPv4 サブネット化

答え: p = 21

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

ビットを比べる

235 = 11101011

239 = 11101111

共通する先頭のビット：5

プレフィックス長

p = 16 + 5 = 21

答え

p = /21

集約経路：10.126.232.0/21 （リストにない 3 個のネットワークもカバーします）。

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