前提診断 80問

使い方

• 制限時間は 120〜150分。
• 参考資料を見ずに解く。
• 各問1点、合計80点。
• 証明問題は、結論だけでなく理由が書けていれば正答。
• 実装問題は、擬似コードでもPythonでもよい。
• 採点後は assessment/scoring-rubric.md と assessment/recovery-routes.md を使って、領域別に補強する。
• 本体教科書への進行判定は、共通の進行判定ポリシーを正本とする。

判定

68/80は前提診断だけのゲートです。この得点だけで本体教科書への進行可とは判定しません。

A. 集合・論理

Q1. A ⊆ B の定義を、量化記号を使って書け。

Q2. A = {1,2,3}, B = {2,3,4} とする。A ∪ B, A ∩ B, A \ B を求めよ。

Q3. 次の命題を否定せよ。

すべての整数 n について、n が偶数ならば n^2 は偶数である。

Q4. P → Q の対偶を書け。

Q5. 次のうち、P → Q と常に同値なものをすべて選べ。

1. Q → P
2. ¬P → ¬Q
3. ¬Q → ¬P
4. ¬P ∨ Q

Q6. ¬(∀x∈S, P(x)) を、存在量化を使って書き換えよ。

B. 関数・関係

Q7. 関数 f: A → B が単射であることの定義を書け。

Q8. 関数 f: A → B が全射であることの定義を書け。

Q9. A = {1,2,3}, B = {a,b} とする。写像 f: A → B が全単射になれない理由を述べよ。

Q10. 集合 S = {1,2,3,4,5,6} 上の関係 R を、a R b ⇔ a と b を3で割った余りが等しい、と定義する。R が同値関係であるために確認すべき3条件を挙げよ。

Q11. 関係 ≤ が整数集合上の半順序であることを示すために確認すべき性質を挙げよ。

Q12. 同値関係が集合を「分割」する、とはどういう意味か説明せよ。

C. 証明

Q13. 直接証明の基本形を説明せよ。

Q14. 対偶証明が有効な命題の形を説明せよ。

Q15. 背理法の基本形を説明せよ。

Q16. 数学的帰納法で示すべき2つのステップを書け。

Q17. n ≥ 1 について、1 + 2 + ... + n = n(n+1)/2 を証明する場合、帰納法の仮定は何か。

Q18. 「任意の偶数 n について n^2 は偶数である」を直接証明せよ。

Q19. 「n^2 が偶数ならば n は偶数である」を対偶で証明する場合、証明すべき対偶は何か。

Q20. 反例を1つ示せば命題が偽であることを示せる理由を説明せよ。

D. 漸近記法

Q21. f(n) = O(g(n)) の定義を書け。

Q22. 3n^2 + 5n + 7 = O(n^2) を定義から示せ。

Q23. 次を増加率の小さい順に並べよ。

log n, n, n log n, n^2, 2^n

Q24. 次のコード片の時間計算量を Θ 記法で答えよ。

for i = 1 to n:
    print(i)

Q25. 次のコード片の時間計算量を Θ 記法で答えよ。

for i = 1 to n:
    for j = 1 to n:
        print(i, j)

Q26. 次のコード片の時間計算量を Θ 記法で答えよ。

j = 1
while j < n:
    j = 2 * j

E. プログラミング・擬似コード

Q27. 配列 A の長さが n のとき、先頭から順に目的値 x を探す線形探索の擬似コードを書け。

Q28. 二分探索が使える配列の条件を述べよ。

Q29. 次の関数 f(4) の戻り値を求めよ。

def f(n):
    if n == 0:
        return 1
    return n * f(n - 1)

Q30. 上の f(n) が停止する理由を説明せよ。

Q31. ループ不変条件とは何か、短く説明せよ。

Q32. スタックとキューの違いを説明せよ。

F. グラフ

Q33. 無向グラフを、頂点集合と辺集合を使って定義せよ。

Q34. パスと閉路の違いを説明せよ。

Q35. 木の定義を1つ述べよ。

Q36. n 頂点の木の辺数はいくつか。

Q37. BFS と DFS の違いを説明せよ。

Q38. 有向グラフにおける到達可能性とは何か。

Q39. DAG とは何か。

Q40. トポロジカルソートが可能なグラフの条件を述べよ。

G. 組合せと数え上げ

Q41. 長さ n のビット列の個数を求めよ。

Q42. 長さ n のビット列のうち、1 がちょうど k 個であるものの個数を求めよ。

Q43. n 要素集合の部分集合数を求めよ。

Q44. C(n,k)=C(n,n-k) を組合せの意味で説明せよ。

Q45. 1から100までの整数のうち、2または5で割り切れるものの個数を求めよ。

Q46. 鳩ノ巣原理を1文で述べよ。

Q47. 命題変数が n 個あるとき、真理値割当の個数を求めよ。

H. データ構造と基本アルゴリズム

Q48. 抽象データ型と実装の違いを説明せよ。

Q49. ハッシュ表の検索が平均 O(1) で、最悪 O(n) になり得る理由を説明せよ。

Q50. 最小ヒープにおける「最小値を見る」と「最小値を削除する」の計算量を答えよ。

Q51. 隣接行列と隣接リストのメモリ使用量を比較せよ。

Q52. 隣接リスト表現のグラフに対して、BFS の計算量を答えよ。

Q53. 二分探索が O(log n) になる理由を説明せよ。

Q54. 動的計画法における「状態」と「遷移」を説明せよ。

I. 形式言語の入口

Q55. Σ と Σ* の違いを説明せよ。

Q56. ε と ∅ の違いを説明せよ。

Q57. L = {0^n1^n | n >= 0} の要素を短いものから3つ列挙せよ。

Q58. DFA を定義する5つの要素を書け。

Q59. NFA の非決定性がランダムではない理由を説明せよ。

Q60. 判定問題を言語として表すとはどういうことか、短く説明せよ。

J. 確率の基礎

Q61. Pr[A | B] の定義を書け。

Q62. 独立性 A と B の定義を、Pr[A∩B] を使って書け。

Q63. 排反と独立の違いを説明せよ。

Q64. 確率変数を関数として説明せよ。

Q65. 期待値の線形性を式で書け。

Q66. 事象 A の指示変数 I_A について、E[I_A] は何か。

K. 数論・代数の基礎

Q67. gcd(84,30) を求めよ。

Q68. a ≡ b (mod n) の定義を書け。

Q69. mod n で a が逆元を持つ条件を書け。

Q70. 群の4条件を挙げよ。

Q71. 巡回群における生成元とは何か。

L. 線形代数の最小限

Q72. m×n 行列は、どの次元のベクトルをどの次元のベクトルへ写すか。

Q73. 線形独立の定義を書け。

Q74. 行列のランクを直観的に説明せよ。

Q75. F_2 で 1+1 は何か。

Q76. Hamming距離とは何か。

M. 並行性と形式モデルの入口

Q77. 状態遷移システム T=(S, ->, s0) の3要素を説明せよ。

Q78. 非決定性と確率の違いを説明せよ。

Q79. safety と liveness の違いを説明せよ。

Q80. 合意問題の代表的な3条件を挙げよ。

解答概要

A

A1. ∀x (x∈A → x∈B)。

A2. A ∪ B = {1,2,3,4}、A ∩ B = {2,3}、A \ B = {1}。

A3. ある整数 n が存在して、n は偶数であり、かつ n^2 は偶数ではない。

A4. ¬Q → ¬P。

A5. 3 と 4。

A6. ∃x∈S, ¬P(x)。

B

A7. ∀x,y∈A, f(x)=f(y) → x=y。

A8. ∀b∈B, ∃a∈A, f(a)=b。

A9. 全単射なら |A|=|B| が必要だが、|A|=3, |B|=2 で一致しないため。

A10. 反射律、対称律、推移律。

A11. 反射律、反対称律、推移律。

A12. 各要素がちょうど1つの同値類に属し、同値類同士は互いに交わらないこと。

C

A13. 仮定と定義から出発し、論理的推論で結論を導く。

A14. P → Q 型の命題。¬Q → ¬P を証明すればよい。

A15. 否定を仮定し、矛盾を導く。

A16. 基底ステップと帰納ステップ。

A17. 1 + 2 + ... + k = k(k+1)/2 が成り立つ、という仮定。

A18. n=2k とおくと n^2=4k^2=2(2k^2) なので偶数。

A19. n が奇数ならば n^2 は奇数である。

A20. 全称命題は全ての対象で成り立つ必要があるため、1つでも成り立たない例があれば偽。

D

A21. ある正定数 c と n0 が存在して、全ての n≥n0 で 0≤f(n)≤c g(n) が成り立つこと。

A22. n≥1 で 3n^2 + 5n + 7 ≤ 3n^2 + 5n^2 + 7n^2 = 15n^2。よって c=15, n0=1。

A23. log n < n < n log n < n^2 < 2^n。

A24. Θ(n)。

A25. Θ(n^2)。

A26. Θ(log n)。

E

A27. 例:

for i = 0 to n-1:
    if A[i] == x:
        return i
return NOT_FOUND

A28. 配列が探索キーでソート済みであること。

A29. 24。

A30. n が各再帰呼び出しで1ずつ減り、最終的に 0 に到達するため。

A31. ループの各反復の前後で常に成り立つ性質。正しさの証明に使う。

A32. スタックは後入れ先出し、キューは先入れ先出し。

F

A33. G=(V,E)。V は頂点集合、E は V の2要素部分集合からなる辺集合。

A34. パスは頂点を辺でたどる列。閉路は始点と終点が同じパス。

A35. 連結で閉路を持たない無向グラフ。

A36. n-1。

A37. BFS は近い頂点から層状に探索し、DFS は進めるだけ深く進んでから戻る。

A38. 頂点 u から有向辺の向きに従って頂点 v へ到達できること。

A39. Directed Acyclic Graph。有向閉路を持たない有向グラフ。

A40. 有向閉路を持たないこと。

G

A41. 2^n。

A42. C(n,k)。

A43. 2^n。

A44. k 個を選ぶことは、選ばない n-k 個を決めることと一対一に対応するため。

A45. 2の倍数は50個、5の倍数は20個、10の倍数は10個。包除原理により 50+20-10=60。

A46. n+1 個の物を n 個の箱に入れると、少なくとも1つの箱には2個以上入る。

A47. 2^n。

H

A48. 抽象データ型は提供する操作と意味を定めるもの。実装は、それを配列、連結リストなどでどう実現するかである。

A49. ハッシュ値が分散すれば各バケットが小さく平均 O(1)。多数のキーが衝突すれば、同じバケット内を線形に調べるため最悪 O(n)。

A50. 最小値を見るのは O(1)。最小値を削除するのはヒープ条件の回復が必要なので O(log n)。

A51. 隣接行列は O(|V|^2)。隣接リストは O(|V|+|E|)。

A52. O(|V|+|E|)。

A53. 探索範囲を各ステップでほぼ半分にするため、n が1になるまでの回数は log n に比例する。

A54. 状態は部分問題を識別する変数や添字。遷移は小さい状態の答えから別の状態の答えを計算する規則。

I

A55. Σ は記号の集合。Σ* は Σ 上のすべての有限文字列の集合。

A56. ε は長さ0の文字列。∅ は要素を持たない集合。

A57. ε, 01, 0011。

A58. M=(Q,Σ,δ,q0,F)。状態集合、アルファベット、遷移関数、初期状態、受理状態集合。

A59. NFA は確率で遷移を選ぶのではなく、受理経路が少なくとも1つ存在するかで受理を定義するため。

A60. 入力文字列の集合を言語として定義し、入力がその集合に属するかを判定する問題として表すこと。

J

A61. Pr[A | B] = Pr[A∩B] / Pr[B]。ただし Pr[B]>0。

A62. Pr[A∩B] = Pr[A]Pr[B]。

A63. 排反は同時に起きないこと。独立は片方が起きた情報がもう片方の確率を変えないこと。

A64. 確率変数は、標本空間の各結果 ω∈Ω に数値 X(ω) を対応させる関数。

A65. E[aX+bY] = aE[X] + bE[Y]。特に E[X+Y]=E[X]+E[Y]。

A66. E[I_A] = Pr[A]。

K

A67. gcd(84,30)=gcd(30,24)=gcd(24,6)=gcd(6,0)=6。

A68. n | (a-b) が成り立つこと。

A69. gcd(a,n)=1。

A70. 閉性、結合律、単位元の存在、逆元の存在。

A71. その要素のべき乗だけで群の全要素を生成できる要素。

L

A72. n 次元ベクトルを m 次元ベクトルへ写す。

A73. a_1v_1+...+a_kv_k=0 なら、すべての係数が 0 である場合だけ。

A74. 行列に含まれる独立な情報の数。独立な行または列の数。

A75. 0。F_2 では mod 2 で計算するため。

A76. 同じ長さの2つの文字列・ベクトルが異なる位置の数。

M

A77. S は状態集合、-> は遷移関係、s0 は初期状態。

A78. 非決定性は複数の遷移が可能という記述で、確率分布は指定しない。確率では各選択肢に確率が割り当てられる。

A79. safety は悪いことが起きない性質。liveness は良いことがいつか起きる性質。

A80. 一致性、妥当性、終了性。