記数法
- 位取り
- 2 進数 2k、8 進数 8k、16 進数 16k
- 10 進数へ
- Σ dk·bk
- 10 進数から
- 基数で割り、余りを下から上へ読む
- 16 進数 ↔ 2 進数
- 16 進数 1 桁 = 4 ビット
- 2 の補数
- ビットを反転して 1 を足す
公式集、全トピックの解法の要点、20 問の演習問題。完全な解答は巻末にあります。
8 ビットの 2 の補数で −60 を格納するようにビットを設定します。符号なしの数として読むと、このパターンの値 U はいくつですか?
あるシステムで、2422 個の項目それぞれに同じ長さの固有の 2 進コードを割り当てます。必要なビット数 b は最小でいくつですか?
¬(a → c) と論理的に同値な論理式はどれですか? クリックしてください。
真理値表の 16 行のうち、((¬q ∧ p) ∧ (r → ¬s)) ↔ ((¬r → p) ∧ q) が真になるのは何行ですか? この数を N とします。
カルノー図を使って F(A, B, C, D) = Σm(0, 1, 2, 5, 7, 12, 13, 15) の最小の和積形(POS)を求めてください。和項(因数)N はいくつありますか?
d はドントケア条件を表します。F(A, B, C, D) = Σm(1, 3, 5, 9, 13, 15) + d(7, 8, 10, 12) の最小の SOP 形を求めてください。リテラル L はいくつ含まれますか?
オイラーのトーシェント関数 φ(1715)、つまり 1 から 1715 までの整数のうち 1715 と互いに素なものの個数を求めてください。
メッセージ m = 233 を RSA 公開鍵 (n, e) = (407, 7) で暗号化してください。暗号文 c を求めてください。
安定(stable)なソートアルゴリズムはどれですか?
一部の辺の重みが負のとき、ダイクストラ法が誤った結果を出すことがあるのはなぜですか?
ある道路網には 100,000 の交差点があり、それぞれが約 4 つの他の交差点とつながっています。最も適した表現はどれですか。
n 要素の二分最小ヒープで任意のキーを探索するのにどれだけ時間がかかりますか。
木に 次数 3 の頂点が 2 個, 次数 5 の頂点が 4 個 があり、ほかのすべての頂点は葉(次数 1)です。葉は何枚Lありますか?
ダイクストラ法を使って、重み付きグラフで A から F までの最短経路の長さd(F)を求めてください。
HAVING について正しい記述はどれですか?
ダーティリードは防ぐが、ノンリピータブルリードは依然として許す分離レベルはどれですか?
TLS は HTTPS にどのようなセキュリティ特性を提供しますか?
SYN フラッド攻撃で、攻撃者が枯渇させようとしているリソースは何ですか?
ある部署では、1 つのサブネット内に 224 個のホストアドレスが必要です。十分な大きさとなる最長のプレフィックス長 p(最小のサブネット)はいくつですか?
あるルータは次のネットワークへの経路をもっています:10.132.80.0/24, 10.132.81.0/24, 10.132.82.0/24, 10.132.83.0/24, 10.132.84.0/24, 10.132.85.0/24, 10.132.86.0/24, 10.132.87.0/24。それらすべてをカバーする 1 つの集約経路の最長のプレフィックス長 p はいくつですか?
答え: U = 196
ビットの設定:各ビットは 2 のべき乗(128、64、…、1)の値をもちます。16 進の 1 桁はちょうど 4 ビットで、8 ビットの 2 の補数では、いちばん左のビットの値は −128 です。ビット演算は、各ビット位置を別々に扱います。
答え: b = 12 bit
位取り記数法:各桁の値は、その数字に基数のべき乗を掛けたものです。2 進数では各桁の重みが 1、2、4、8、16、…、16 進数では 1、16、256、… で、A–F は 10–15 を表します。8 ビットの 2 の補数では、最上位ビットの重みが +128 ではなく −128 になり、こうして負の数を表します。
答え: a ∧ ¬c
論理的同値: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 = 7
真理値表:n 個の異なる変数をもつ論理式には、真理値のすべての組み合わせに対応する 2ⁿ 行があります(1 = 真、0 = 偽)。内側から順に進め、部分式ごとに列を用意します。¬a は値を反転させ、a ∧ b は両方が 1 のときだけ 1、a ∨ b は両方が 0 のときだけ 0、a → b は a = 1 かつ b = 0 のときだけ 0、a ↔ b は両辺が等しいとき 1 です。
答え: N = 4
カルノー図:セルはグレイコード(00, 01, 11, 10)の順に並んでいるので、端をまたぐものも含め、隣り合うセルはちょうど 1 つの変数だけが異なります。1 を、1, 2, 4, 8, 16 個のセルからなる長方形で、できるだけ大きく、できるだけ少ない数でグループ化し、すべての 1 を覆います。各グループは 1 つの積項で、グループの中で一定のままの変数からなります。2ᵏ 個のセルのグループでは k 個の変数が消えます。ドントケア(X)はグループを大きくするために使えますが、覆う必要はありません。代わりに 0 をグループ化すると、最小の POS 形が得られます。
各グループは 2ᵏ 個のセルからなる長方形です。端のセルは、反対側の端のセルと隣り合っています。
同じ大きさの別のグループ分けもあります。項の数もリテラルの数も同じです。
答え: L = 6
カルノー図:セルはグレイコード(00, 01, 11, 10)の順に並んでいるので、端をまたぐものも含め、隣り合うセルはちょうど 1 つの変数だけが異なります。1 を、1, 2, 4, 8, 16 個のセルからなる長方形で、できるだけ大きく、できるだけ少ない数でグループ化し、すべての 1 を覆います。各グループは 1 つの積項で、グループの中で一定のままの変数からなります。2ᵏ 個のセルのグループでは k 個の変数が消えます。ドントケア(X)はグループを大きくするために使えますが、覆う必要はありません。代わりに 0 をグループ化すると、最小の POS 形が得られます。
1 と X からつくれる最大のグループ。
同じ大きさの別のグループ分けもあります。項の数もリテラルの数も同じです。
答え: φ(1715) = 1176
逆元と合同式: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)。
答え: c = 381
冪剰余と 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 で行います。
答え: D · マージソート
マージソートは、値が等しいときに左半分から先に取り出すようにマージすれば安定です。インプレースのクイックソート、ヒープソート、選択ソートは通常安定ではありません。
答え: A · 頂点は取り出された時点で確定するが、後の負の辺によってより短い経路が得られる可能性があるから
貪欲なステップは、取り出した距離が確定するように重みが非負であることに依存しています。重みが負になりうる場合はベルマン-フォード法を使います。
答え: C · 隣接リスト
行列では 1010 個のセルが必要になり、そのほとんどが空です。隣接リストなら約 400,000 個の辺の項目だけを格納すれば済みます。
答え: D · O(n)
ヒープには、どちらの部分木にキーが含まれるかについての規則がないので、最悪の場合すべてのノードを調べなければなりません。すばやく見つけられるのは最小値だけです。
答え: L = 16
オイラー、ハミルトン、木:連結グラフは、すべての頂点の次数が偶数のときオイラー閉路(すべての辺を 1 回ずつ通って始点に戻る)をもち、ちょうど 2 つの頂点の次数が奇数のとき、閉路でないオイラー路をもちます。その路は、一方の奇数次数の頂点から他方へ通ります。ハミルトン閉路はすべての頂点を 1 回ずつ訪れ、Kn には (n − 1)!/2 個あります。n 個の頂点をもつ木には n − 1 本の辺があり、m 本の辺をもつ連結グラフは、m − n + 1 本の辺を取り除いても全域木が残ります。
近道:次数 d ≥ 3 の頂点について L = 2 + Σ (d − 2) です。
答え: d(F) = 20
最短経路と全域木:ダイクストラ法は毎ラウンド 1 つの頂点を確定します:暫定距離が最小の未確定の頂点です。その距離は最終となり、各隣接頂点 v は d(v) = min(d(v), d(u) + w(u, v)) と更新されます。クラスカル法は、辺を軽い順に取り、閉路をつくる辺を飛ばして最小全域木をつくります。プリム法は、始点から 1 本の木を成長させ、その木から出る最も軽い辺を常に加えます。n 個の頂点の全域木には n − 1 本の辺があります。
各行:確定した頂点、その最終距離、距離が改善される隣接頂点。
答え: D · 集約関数を使ってグループを絞り込むことができる
HAVING は集約の後でグループを絞り込み、集約関数を参照できます。WHERE ではそれができません。
答え: B · Read committed
Read committed は未コミットの変更を隠します。Repeatable read はノンリピータブルリードも防ぎ、Serializable はファントムも防ぎます。
答え: B · 機密性、完全性、サーバー認証
TLS はトラフィックを暗号化し、改ざんを検出し、証明書によってサーバーを認証します(任意でクライアントも認証します)。
答え: A · サーバーのハーフオープン接続のテーブル
SYN のたびにサーバーは状態を確保し、来ることのない ACK を待ちます。SYN Cookie は、ハンドシェイクが完了するまで状態を保存しないことでこれを回避します。
答え: p = 24
IPv4 サブネット化:アドレスは 32 ビットです。プレフィックス /p は先頭の何ビットがネットワークを表すかを示し、残りの 32 − p ビットでホストを番号付けします。サブネットには 2³²⁻ᵖ 個のアドレスがありますが、最初(ネットワークアドレス)と最後(ブロードキャストアドレス)はホストに割り当てられないため、2³²⁻ᵖ − 2 台のホストが収まります。 例外:/31(ポイントツーポイントリンク、RFC 3021)は 2 つのアドレスを両方ともホストに使い、/32 は単一のアドレス(単一ホストまたはループバック)です。
答え: p = 21
経路集約:集約経路 a.b.c.0/p は、最初の p ビットが一致するすべてのネットワークをカバーします。最初と最後のネットワークの異なるオクテットを 2 進数で書きます。共通する先頭のビット数に、それより前のオクテットのビット数を加えたものが最長の集約プレフィックスです。
集約経路:10.132.80.0/21
ExamProblems · examproblems.com/courses/computer-science-fundamentals