章末確認チェック

使い方

各章を読んだ後、該当する確認問題を解いてください。各章10点満点です。8点以上を通過、6〜7点を要復習、5点以下を再学習とします。

解答は短くてよいですが、定義を問う問題では用語だけでなく条件まで書いてください。

第1章 集合と論理

1. A ⊆ B の定義を量化記号で書け。
2. A = {1,2,3}, B = {3,4} のとき A∪B, A∩B, A\B を求めよ。
3. ¬(P∧Q) を書き換えよ。
4. ¬(∀x∈S, P(x)) を書き換えよ。
5. P→Q の対偶を書け。
6. P→Q と Q→P が同値ではない例を作れ。
7. 全称命題を反例で否定できる理由を説明せよ。
8. ∅ と {∅} の違いを説明せよ。
9. 冪集合 P({a,b}) を列挙せよ。
10. P→Q が偽になる真理値の組を答えよ。

通過条件: 量化の否定と対偶で誤りがないこと。

第2章 関数と関係

1. 関数 f:A→B の定義域と終域を答えよ。
2. 単射の定義を書け。
3. 全射の定義を書け。
4. 全単射が存在するために有限集合では何が必要か。
5. 同値関係の3条件を挙げよ。
6. 半順序の3条件を挙げよ。
7. aRb ⇔ a-b が偶数、は整数上の同値関係か。
8. 同値類とは何か。
9. 半順序と全順序の違いを説明せよ。
10. 到達可能性が一般に同値関係でない理由を述べよ。

通過条件: 同値関係と半順序の条件を混同しないこと。

第3章 証明技法

1. 直接証明の型を書け。
2. 対偶証明で証明する命題の形を書け。
3. 背理法の型を書け。
4. 数学的帰納法の2ステップを書け。
5. 強い帰納法を使う場面を説明せよ。
6. 構造帰納法を使う対象を1つ挙げよ。
7. 「偶数の平方は偶数」を直接証明せよ。
8. 「n^2 が偶数なら n は偶数」を対偶で証明せよ。
9. 1+...+n=n(n+1)/2 の帰納法の仮定を書け。
10. 反例が全称命題を否定する理由を説明せよ。

通過条件: 証明が例示だけで終わっていないこと。

第4章 漸近記法

1. f(n)=O(g(n)) の定義を書け。
2. f(n)=Ω(g(n)) の定義を書け。
3. f(n)=Θ(g(n)) の定義を書け。
4. 5n^2+3n+1 = O(n^2) を定義から示せ。
5. log n, n, n log n, n^2, 2^n を小さい順に並べよ。
6. 単一ループ 1..n の時間計算量を答えよ。
7. 二重ループ 1..n, 1..n の時間計算量を答えよ。
8. j=1; while j<n: j=2j の時間計算量を答えよ。
9. 二分探索が O(log n) である理由を説明せよ。
10. O(n) と Θ(n) の違いを説明せよ。

通過条件: 定義で c と n0 を落とさないこと。

第5章 擬似コードと再帰

1. 線形探索の擬似コードを書け。
2. 二分探索が使える入力条件を述べよ。
3. 階乗再帰の基底条件を書け。
4. 再帰関数が停止するために必要な2条件を述べよ。
5. ループ不変条件とは何か。
6. 配列とリストの違いを説明せよ。
7. スタックとキューの違いを説明せよ。
8. 再帰呼び出しでスタックが増える理由を説明せよ。
9. return の役割を説明せよ。
10. 仕様と実装の違いを説明せよ。

通過条件: 停止性を「いつか止まる」ではなく、減少量と基底条件で説明すること。

第6章 グラフと木

1. 無向グラフを G=(V,E) で定義せよ。
2. 有向グラフでは辺集合をどう表すか。
3. パスと閉路の違いを説明せよ。
4. 木の定義を1つ述べよ。
5. n 頂点の木の辺数を答えよ。
6. 連結性とは何か。
7. 到達可能性とは何か。
8. BFS と DFS の違いを説明せよ。
9. DAG とは何か。
10. トポロジカルソート可能な条件を述べよ。

通過条件: グラフを図ではなく集合で説明できること。

第7章 組合せと数え上げ

1. 積の法則を説明せよ。
2. 和の法則を説明せよ。
3. 長さ n のビット列の個数を答えよ。
4. n 要素集合の部分集合数を答えよ。
5. 1 がちょうど k 個の長さ n ビット列の個数を答えよ。
6. C(n,k)=C(n,n-k) を説明せよ。
7. 鳩ノ巣原理を述べよ。
8. 包除原理を2集合の場合で書け。
9. 命題変数 n 個の真理値割当数を答えよ。
10. 状態数を数えるときに重複を避ける方法を説明せよ。

通過条件: 重複あり・なしの区別を説明できること。

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

1. ADT と実装の違いを説明せよ。
2. スタックの代表操作を2つ書け。
3. キューの代表操作を2つ書け。
4. ハッシュ表の平均検索が O(1) になる理由を説明せよ。
5. ヒープで最小値削除が O(log n) になる理由を説明せよ。
6. 隣接行列のメモリ量を答えよ。
7. 隣接リストのメモリ量を答えよ。
8. BFS の計算量を隣接リスト前提で答えよ。
9. Union-Find が扱う代表的な問題を説明せよ。
10. 動的計画法の状態と遷移を説明せよ。

通過条件: データ構造の操作仕様と内部実装を混同しないこと。

第9章 形式言語の入口

1. アルファベット Σ とは何か。
2. Σ* とは何か。
3. ε と ∅ の違いを説明せよ。
4. 言語とは何か。
5. L={0^n1^n | n≥0} の要素を3つ挙げよ。
6. DFA の5要素を書け。
7. DFA の遷移関数の型を書け。
8. NFA の非決定性が確率でない理由を説明せよ。
9. 文法における非終端記号とは何か。
10. 判定問題を言語として表すとは何か。

通過条件: ε と ∅ を混同しないこと。

第10章 確率の基礎

1. 標本空間とは何か。
2. 事象とは何か。
3. Pr[A|B] の定義を書け。
4. 独立性を Pr[A∩B] で定義せよ。
5. 排反と独立の違いを説明せよ。
6. 確率変数を関数として説明せよ。
7. 期待値の線形性を書け。
8. 指示変数 I_A の期待値を答えよ。
9. 二項分布が現れる条件を述べよ。
10. Markov不等式の直観を述べよ。

通過条件: 条件付き確率と独立性を混同しないこと。

第11章 数論・代数の基礎

1. gcd(84,30) を求めよ。
2. a≡b (mod n) の定義を書け。
3. mod n における逆元の定義を書け。
4. 逆元が存在する条件を述べよ。
5. Euclid互除法の停止理由を説明せよ。
6. 群の4条件を挙げよ。
7. 巡回群とは何か。
8. 生成元とは何か。
9. 体とは何か。
10. 離散対数問題の形を説明せよ。

通過条件: 合同算術を通常の等式と混同しないこと。

第12章 線形代数の最小限

1. m×n 行列が写すベクトル空間の次元を答えよ。
2. 行列積 AB が定義できる条件を書け。
3. 単位行列の役割を説明せよ。
4. 線形写像とは何か。
5. 線形独立の定義を書け。
6. ランクを説明せよ。
7. F_2 で 1+1 を計算せよ。
8. Hamming距離を定義せよ。
9. 生成行列の役割を説明せよ。
10. 検査行列の役割を説明せよ。

通過条件: 次元の整合性を確認できること。

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

1. 状態遷移システム T=(S,→,s0) の3要素を説明せよ。
2. 非決定性と確率の違いを説明せよ。
3. trace とは何か。
4. safety を説明せよ。
5. liveness を説明せよ。
6. invariant を説明せよ。
7. 共有メモリモデルの特徴を述べよ。
8. メッセージパッシングモデルの特徴を述べよ。
9. happens-before の直観を説明せよ。
10. 合意問題の3条件を挙げよ。

通過条件: safety と liveness を反例の形で区別できること。