記数法
- 位取り
- 2 進数 2k、8 進数 8k、16 進数 16k
- 10 進数へ
- Σ dk·bk
- 10 進数から
- 基数で割り、余りを下から上へ読む
- 16 進数 ↔ 2 進数
- 16 進数 1 桁 = 4 ビット
- 2 の補数
- ビットを反転して 1 を足す
公式集、全トピックの解法の要点、20 問の演習問題。完全な解答は巻末にあります。
8 ビットのパターン 1100 1001 は、符号付き整数を 2 の補数で表しています。10 進数での値 N はいくつですか?
ビットを 0010 0010 >> 1 の 8 ビットの結果に設定します。結果の値 R は 10 進でいくつですか?
¬(p ∨ ¬p) は恒真式、矛盾、そのどちらでもない式のうちのどれですか? 答えをクリックしてください。
前提 b ∨ c; b、結論 ¬c の論証は妥当ではありません。反例となる真理値表の行をクリックしてください。
カルノー図を使って F(A, B, C, D) = Σm(0, 4, 6, 7, 8, 12, 13, 15) の最小の和積形(POS)を求めてください。和項(因数)N はいくつありますか?
d はドントケア条件を表します。F(A, B, C, D) = Σm(0, 1, 2, 3, 11, 12, 13, 14, 15) + d(4, 9) の最小の SOP 形を求めてください。積項 N はいくつありますか?
オイラーのトーシェント関数 φ(221)、つまり 1 から 221 までの整数のうち 221 と互いに素なものの個数を求めてください。
24x ≡ 48 (mod 56) を解いてください。最小の正の解 x を答えてください。
単純な再帰の階乗関数 fact(n) = n × fact(n − 1) はどれだけのスタック領域を使いますか?
トポロジカルソートが可能なのは、次のどのグラフだけですか?
ダイクストラ法が次に処理する頂点を選ぶために使う抽象データ型はどれですか。
すべての B 木を完全に平衡に保っている性質はどれですか。
木に 次数 3 の頂点が 4 個, 次数 4 の頂点が 2 個, 次数 2 の頂点が 2 個 があり、ほかのすべての頂点は葉(次数 1)です。葉は何枚Lありますか?
ダイクストラ法を使って、重み付きグラフで A から F までの最短経路の長さd(F)を求めてください。
各部署の最高給与を返すクエリはどれですか?
クエリ FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.status = 'paid' が、注文のない顧客を思いがけず落としてしまいます。なぜですか?
「ウェルノウン」ポートとして予約されている TCP/UDP ポート番号の範囲はどれですか?
SYN フラッド攻撃で、攻撃者が枯渇させようとしているリソースは何ですか?
あるサブネットはマスク 255.255.254.0 を使っています。使えるホストアドレスはいくつ H ありますか?
あるホストのアドレスは 10.20.200.214/27 です。そのサブネットで最後に使えるホストアドレスの第 4 オクテット x はいくつですか?
答え: N = −55
位取り記数法:各桁の値は、その数字に基数のべき乗を掛けたものです。2 進数では各桁の重みが 1、2、4、8、16、…、16 進数では 1、16、256、… で、A–F は 10–15 を表します。8 ビットの 2 の補数では、最上位ビットの重みが +128 ではなく −128 になり、こうして負の数を表します。
ほかのビットは通常の正の重みのままです。
答え: R = 17
ビットの設定:各ビットは 2 のべき乗(128、64、…、1)の値をもちます。16 進の 1 桁はちょうど 4 ビットで、8 ビットの 2 の補数では、いちばん左のビットの値は −128 です。ビット演算は、各ビット位置を別々に扱います。
1 だけ右にシフトすると、すべてのビットが 1 桁右へ動きます。右端からはみ出したビットは失われ、左側には 0 が入ります。
答え: 矛盾(恒偽式)
論理的同値: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)。
答え: b = 1, c = 1
量化子と論証:¬∀x P(x) ≡ ∃x ¬P(x)、¬∃x P(x) ≡ ∀x ¬P(x)。否定を内側へ移し、通過する量化子をすべて入れ替え、内側の式は ¬(a → b) ≡ a ∧ ¬b のような命題論理の法則で否定します。論証は、すべての前提が 1 であるどの行でも結論が 1 のとき、妥当です。前提が真で結論が偽になる行が 1 つでもあれば、それは反例であり、その論証が妥当でないことを示します。
この形の論証は妥当な規則のように見えますが、1 行あれば妥当でないことを示せます。
答え: N = 4
カルノー図:セルはグレイコード(00, 01, 11, 10)の順に並んでいるので、端をまたぐものも含め、隣り合うセルはちょうど 1 つの変数だけが異なります。1 を、1, 2, 4, 8, 16 個のセルからなる長方形で、できるだけ大きく、できるだけ少ない数でグループ化し、すべての 1 を覆います。各グループは 1 つの積項で、グループの中で一定のままの変数からなります。2ᵏ 個のセルのグループでは k 個の変数が消えます。ドントケア(X)はグループを大きくするために使えますが、覆う必要はありません。代わりに 0 をグループ化すると、最小の POS 形が得られます。
各グループは 2ᵏ 個のセルからなる長方形です。端のセルは、反対側の端のセルと隣り合っています。
答え: N = 3
カルノー図:セルはグレイコード(00, 01, 11, 10)の順に並んでいるので、端をまたぐものも含め、隣り合うセルはちょうど 1 つの変数だけが異なります。1 を、1, 2, 4, 8, 16 個のセルからなる長方形で、できるだけ大きく、できるだけ少ない数でグループ化し、すべての 1 を覆います。各グループは 1 つの積項で、グループの中で一定のままの変数からなります。2ᵏ 個のセルのグループでは k 個の変数が消えます。ドントケア(X)はグループを大きくするために使えますが、覆う必要はありません。代わりに 0 をグループ化すると、最小の POS 形が得られます。
1 と X からつくれる最大のグループ。
同じ大きさの別のグループ分けもあります。項の数もリテラルの数も同じです。
答え: φ(221) = 192
逆元と合同式: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)。
答え: x = 2
逆元と合同式: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)。
答え: A · O(n)
どれかが戻る前に再帰は n 段の深さになり、各呼び出しにスタックフレームが必要なので、O(n) の領域を使います。
答え: D · 有向非巡回グラフ(DAG)
トポロジカル順序が存在するのは、有向グラフに閉路がない場合に限ります。DFS または Kahn のアルゴリズムで O(V + E) で求められます。
答え: C · 最小優先度付きキュー
最小優先度付きキュー(通常は二分ヒープ)は、未訪問の頂点のうち距離が最小のものを効率よく返します。
答え: B · すべての葉が同じ深さにある
ノードは満杯になると上に向かって分割され、木が高くなるのは根が分割されたときだけなので、すべての葉は常に同じレベルにとどまります。
答え: L = 10
オイラー、ハミルトン、木:連結グラフは、すべての頂点の次数が偶数のときオイラー閉路(すべての辺を 1 回ずつ通って始点に戻る)をもち、ちょうど 2 つの頂点の次数が奇数のとき、閉路でないオイラー路をもちます。その路は、一方の奇数次数の頂点から他方へ通ります。ハミルトン閉路はすべての頂点を 1 回ずつ訪れ、Kn には (n − 1)!/2 個あります。n 個の頂点をもつ木には n − 1 本の辺があり、m 本の辺をもつ連結グラフは、m − n + 1 本の辺を取り除いても全域木が残ります。
近道:次数 d ≥ 3 の頂点について L = 2 + Σ (d − 2) です。
答え: d(F) = 22
最短経路と全域木:ダイクストラ法は毎ラウンド 1 つの頂点を確定します:暫定距離が最小の未確定の頂点です。その距離は最終となり、各隣接頂点 v は d(v) = min(d(v), d(u) + w(u, v)) と更新されます。クラスカル法は、辺を軽い順に取り、閉路をつくる辺を飛ばして最小全域木をつくります。プリム法は、始点から 1 本の木を成長させ、その木から出る最も軽い辺を常に加えます。n 個の頂点の全域木には n − 1 本の辺があります。
各行:確定した頂点、その最終距離、距離が改善される隣接頂点。
答え: C · SELECT dept, MAX(salary) FROM emp GROUP BY dept
GROUP BY dept は部署ごとにグループを作り、MAX(salary) が各グループの最大値を選びます。
答え: C · o に対する WHERE 条件が NULL で埋められた行を除外し、内部結合と同じになるから
一致しない行は o.status が NULL なので、WHERE の判定が TRUE になりません。条件を ON 句に移せば、すべての顧客が残ります。
答え: C · 0–1023
ポート 0–1023 は標準的なサービスのためのウェルノウンポートです。1024–49151 は登録済みポート、49152–65535 は動的またはプライベートポートです。
答え: C · サーバーのハーフオープン接続のテーブル
SYN のたびにサーバーは状態を確保し、来ることのない ACK を待ちます。SYN Cookie は、ハンドシェイクが完了するまで状態を保存しないことでこれを回避します。
答え: H = 510
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).
答え: x = 222
IPv4 サブネット化:アドレスは 32 ビットです。プレフィックス /p は先頭の何ビットがネットワークを表すかを示し、残りの 32 − p ビットでホストを番号付けします。サブネットには 2³²⁻ᵖ 個のアドレスがありますが、最初(ネットワークアドレス)と最後(ブロードキャストアドレス)はホストに割り当てられないため、2³²⁻ᵖ − 2 台のホストが収まります。 例外:/31(ポイントツーポイントリンク、RFC 3021)は 2 つのアドレスを両方ともホストに使い、/32 は単一のアドレス(単一ホストまたはループバック)です。
ExamProblems · examproblems.com/courses/computer-science-fundamentals