章別レビュー問題

目的

章別レビュー問題は、各章の本文・章末確認・演習を終えた後に、次章へ進む前の理解を確認するための問題です。前提診断よりも章に密着し、統合到達確認テストよりも範囲を限定しています。

採点は ../assessment/scoring-rubric.md と ../assessment/grading-forms.md を併用してください。

各問題の自己採点には章別レビュー問題 採点観点を使います。リンク先は採点時の要点であり、完全解答ではありません。

難易度

第1章 集合と論理

1. [A] A⊆B の定義を量化記号で書け。
2. [A] ¬(∀x∈S, P(x)→Q(x)) を否定記号が量化子の内側に入る形へ変形せよ。
3. [B] A∩(B∪C)=(A∩B)∪(A∩C) を要素追跡で証明せよ。
4. [B] 含意、逆、裏、対偶を具体例で区別せよ。
5. [E] 計算量クラスを集合として扱う、とはどういう意味か説明せよ。

第2章 関数と関係

1. [A] 単射・全射・全単射の定義を書け。
2. [A] 同値関係と半順序の条件を列挙せよ。
3. [B] aRb ⇔ a-b が4で割り切れる、で定義される整数上の関係が同値関係であることを示せ。
4. [B] 集合族上の包含関係 ⊆ が半順序であることを示せ。
5. [E] DFAの遷移関数 δ:Q×Σ→Q とNFAの遷移関数 δ:Q×Σ→P(Q) の型の違いを説明せよ。

第3章 証明技法

1. [A] 直接証明、対偶証明、背理法の使い分けを説明せよ。
2. [B] n^2 が偶数なら n は偶数であることを対偶で証明せよ。
3. [B] 1+3+...+(2n-1)=n^2 を帰納法で証明せよ。
4. [C] 文字列長について |uv|=|u|+|v| を構造帰納法で証明せよ。
5. [E] オートマトンや文法で構造帰納法が自然に現れる理由を説明せよ。

第4章 漸近記法

1. [A] O, Ω, Θ の定義を書け。
2. [A] log n, n, n log n, n^2, 2^n を増加率の小さい順に並べよ。
3. [B] 7n^2+3n+10=O(n^2) を定義から示せ。
4. [B] 二重ループ for i=1..n, for j=1..i の計算量を求めよ。
5. [E] アルゴリズムの正しさと計算量解析が別の主張である理由を説明せよ。

第5章 擬似コードと再帰

1. [A] 再帰関数に停止条件が必要な理由を説明せよ。
2. [B] 階乗関数が n! を返すことを帰納法で証明せよ。
3. [B] 二分探索の前提条件と計算量を説明せよ。
4. [D] 線形探索または二分探索をPythonで実装せよ。
5. [E] 擬似コードと数学的定義がどのように対応するか、再帰を例に説明せよ。

第6章 グラフと木

1. [A] 有向グラフ・無向グラフ・DAG・木を定義せよ。
2. [A] パス、閉路、到達可能性を説明せよ。
3. [B] n 頂点の木の辺数が n-1 であることを証明せよ。
4. [D] 隣接リスト表現のグラフでBFSを実装せよ。
5. [E] 到達可能性問題を、入力・出力を明示して計算問題として定義せよ。

第7章 組合せと数え上げ

1. [A] 和の法則と積の法則を説明せよ。
2. [A] 長さ n のビット列のうち、1がちょうど k 個であるものの個数を求めよ。
3. [B] パスカルの恒等式を組合せ的に説明せよ。
4. [B] 包除原理で、1から100までの整数のうち2または5で割り切れるものを数えよ。
5. [E] 比較ソートの下界に数え上げが使われる理由を説明せよ。

第8章 データ構造と基本アルゴリズム

1. [A] Stack、Queue、Heap、Hash Tableの操作を列挙せよ。
2. [A] 配列と連結リストのアクセス計算量を比較せよ。
3. [B] Union-Findの find と union の役割を説明せよ。
4. [D] Union-Findを実装し、連結成分を返す関数を作れ。
5. [E] 抽象データ型と実装を分けて考える意義を説明せよ。

第9章 形式言語の入口

1. [A] アルファベット、文字列、空文字列、言語を定義せよ。
2. [A] DFAとNFAの構成要素を列挙せよ。
3. [B] 「1の個数が偶数」の言語を受理するDFAを記述せよ。
4. [D] DFAシミュレータを実装せよ。
5. [E] 言語を集合として見ることが、計算可能性や複雑性に接続する理由を説明せよ。

第10章 確率の基礎

1. [A] 標本空間、事象、確率変数を定義せよ。
2. [A] 条件付き確率の定義を書け。
3. [B] ベイズの定理を条件付き確率の定義から導け。
4. [B] 指示変数を使って、コイン n 回投げの表の期待回数を求めよ。
5. [E] エントロピーの定義を読むために必要な確率概念を説明せよ。

第11章 数論・代数の基礎

1. [A] a≡b (mod n) の定義を書け。
2. [A] Euclidの互除法で gcd(84,30) を求めよ。
3. [B] 3 の mod 7 における逆元を求めよ。
4. [B] 群の4条件を列挙し、整数全体が加法で群になる理由を説明せよ。
5. [E] 離散対数問題を暗号の前提問題として説明せよ。

第12章 線形代数の最小限

1. [A] 行列積 AB が定義できる条件を述べよ。
2. [A] F_2 上で 1+1 が何になるか説明せよ。
3. [B] Hamming距離と最小距離を定義せよ。
4. [B] 生成行列と検査行列の役割を説明せよ。
5. [E] 線形符号を線形代数で扱う利点を説明せよ。

第13章 並行性と形式モデル

1. [A] 状態、遷移、遷移システムを定義せよ。
2. [A] 非決定性と確率的選択の違いを説明せよ。
3. [B] safety と liveness の違いを例で説明せよ。
4. [C] 共有カウンタのインターリーブを状態遷移で表せ。
5. [E] 合意問題で故障モデルを明示する必要がある理由を説明せよ。