理論計算機科学を読むための数学・証明・アルゴリズム基礎

統合到達確認テスト 50問

使い方

  • 制限時間は120分。
  • 参考資料を見ずに解く。
  • 各問1点。証明問題は、主要な論理が書けていれば正答。
  • 合計43/50以上、かつ証明問題 Q7〜Q10・Q23・Q49 の3/6以上を満たす。
  • 共通の進行判定ポリシーに従い、対象章別 readiness を含む他の必須ゲートも確認する。
  • 証明問題が2/6以下の場合は、総合点に関係なく第3章へ戻る。

難易度ラベル

  • [A] 基本: 定義を読む・単純計算をする。
  • [B] 標準: 複数の定義を組み合わせる。
  • [C] 発展: 証明・設計・実装の説明が必要。
  • [D] 実装: 実行可能なコードまたは明確な擬似コードが必要。
  • [E] 接続: 本体教科書の概念へ橋渡しする。

A. Core 20問

Q1. A ⊆ B の定義を量化記号で書け。

Q2. ¬(∀x∈S, P(x)→Q(x)) を書き換えよ。

Q3. P→Q と同値な命題を2つ書け。

Q4. 単射の定義を量化記号で書け。

Q5. 同値関係の3条件を挙げよ。

Q6. 半順序と全順序の違いを説明せよ。

Q7. 「任意の奇数 n について n^2 は奇数」を直接証明せよ。

Q8. 「n^2 が偶数ならば n は偶数」を対偶で証明するとき、証明すべき命題を書け。

Q9. 数学的帰納法の基底ステップと帰納ステップを説明せよ。

Q10. 4n^3 + 2n + 9 = O(n^3) を定義から示せ。

Q11. log n, sqrt(n), n, n log n, n^2 を増加率の小さい順に並べよ。

Q12. 次の擬似コードの計算量を答えよ。

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

Q13. 次の擬似コードの計算量を答えよ。

j = n
while j > 1:
    j = floor(j / 2)

Q14. 再帰関数の停止性を説明するときに確認すべき2点を答えよ。

Q15. 線形探索の擬似コードを書け。

Q16. 二分探索の入力条件を述べよ。

Q17. ループ不変条件とは何か。

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

Q19. 構造帰納法が有効な対象を2つ挙げよ。

Q20. 仕様と実装の違いを説明せよ。

B. Standard 15問

Q21. 無向グラフ G=(V,E) を定義せよ。

Q22. パス、閉路、連結性をそれぞれ説明せよ。

Q23. n 頂点の木の辺数を答え、その理由を1文で説明せよ。

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

Q25. 隣接行列と隣接リストのメモリ量を答えよ。

Q26. 長さ n のビット列のうち、1 がちょうど k 個のものはいくつあるか。

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

Q28. 鳩ノ巣原理を使う典型的な場面を1つ説明せよ。

Q29. ADT と実装の違いを説明せよ。

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

Q31. ヒープで最小値削除が O(log n) になる理由を説明せよ。

Q32. Union-Find が解く代表的な問題を述べよ。

Q33. Σ と Σ* を説明せよ。

Q34. DFA の5要素を書け。

Q35. NFA の非決定性が確率ではない理由を説明せよ。

C. Extended 15問

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

Q37. 事象 A, B の独立性を Pr[A∩B] を使って定義せよ。

Q38. 排反と独立が一般に異なる概念である理由を説明せよ。

Q39. 指示変数 I_A の期待値を答えよ。

Q40. gcd(252,105) を Euclid互除法で求めよ。

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

Q42. mod n で a が逆元を持つ条件を述べよ。

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

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

Q45. F_2 で次を計算せよ。

1 + 1 + 1

Q46. Hamming距離を定義せよ。

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

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

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

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

採点表

範囲 問題 推奨最低点
Core Q1-Q20 16/20
Standard Q21-Q35 11/15
Extended Q36-Q50 10/15
合計 Q1-Q50 43/50

証明問題 Q7-Q10、Q23、Q49 は、結論だけでなく理由を書いてください。

領域別の点数は補強先を判断するための推奨最低点です。進行判定は、合計43/50、証明3/6、対象章別 readiness を個別に確認します。

Edit this page on GitHub