章別レビュー問題 採点観点

このページは、章別レビュー問題の採点用メモです。完全な答案例ではありません。 採点時に確認すべき要点を示します。

各章の5項目は、章別レビュー問題の問題1〜5に同じ順序で対応します。証明の途中式、実装コード、境界条件を含む答案全体ではなく、答案を評価するための最小要件として使ってください。

採点方針

• A問題: 定義・記号が正確なら満点。
• B問題: 定義展開、計算過程、論理の向きが正しければ満点。
• C問題: 証明の前提、示すべき命題、結論が明確であること。
• D問題: 正常系だけでなく、境界条件と入力前提を扱うこと。
• E問題: 本体教科書での使われ方へ接続できていること。

第1章 集合と論理

• A⊆B は ∀x(x∈A→x∈B)。
• ¬∀x(P→Q) は ∃x(P∧¬Q)。
• 分配法則は両包含を示す。要素 x を任意に取り、所属条件を論理式として変形する。
• 対偶だけが元の含意と同値。逆・裏は一般に同値でない。
• 計算量クラスは「ある制約を満たす問題の集合」として扱える。

第2章 関数と関係

• 単射: f(a)=f(a')→a=a'。全射: ∀b∈B ∃a∈A f(a)=b。
• 同値関係は反射・対称・推移。半順序は反射・反対称・推移。
• 合同関係は差の整除性で3条件を示す。
• 包含は反射・反対称・推移を満たす。
• DFAは1つの次状態を返し、NFAは次状態集合を返す。

第3章 証明技法

• 証明方法は命題の形で選ぶ。含意は直接・対偶、存在否定は背理法が使いやすい場合がある。
• 偶奇の証明では整数 k を使って n=2k または n=2k+1 と置く。
• 帰納法は基底部と帰納ステップを分離する。
• 構造帰納法では空文字列を基底、1文字追加を帰納ステップにする。
• オートマトンの入力文字列、文法の導出、式の構文木は再帰的構造を持つ。

第4章 漸近記法

• O は上界、Ω は下界、Θ は上下界。
• 成長率は log n < n < n log n < n^2 < 2^n。
• 7n^2+3n+10≤20n^2 など、十分大きい n と定数 c を明示する。
• 二重ループは Σ_{i=1}^n i = Θ(n^2)。
• 正しさは「仕様を満たす」、計算量は「必要資源を抑える」という別主張。

第5章 擬似コードと再帰

• 停止条件がなければ再帰呼び出し列が終わらない。
• 階乗の証明は fact(0)=1 と fact(n)=n fact(n-1) を使う。
• 二分探索は整列済み配列が前提。探索範囲が毎回半分になるため O(log n)。
• 実装では空配列、見つからない場合、境界インデックスを扱う。
• 再帰的数学定義は、基底ケースと再帰ケースがコードの分岐に対応する。

第6章 グラフと木

• グラフは頂点集合と辺集合で定義する。
• 到達可能性はパスの存在で定義する。
• 木の辺数は帰納法、または連結性と閉路なしから示せる。
• BFSはキューを用い、未訪問頂点に距離と親を設定する。
• 到達可能性問題の入力はグラフと2頂点、出力は到達可能かどうかの真偽値。

第7章 組合せと数え上げ

• 和の法則は排他的選択、積の法則は連続選択。
• 1 の位置を k 個選ぶので C(n,k)。
• パスカルの恒等式は、特定要素を含む場合と含まない場合に分ける。
• 2または5で割り切れる個数は ⌊100/2⌋+⌊100/5⌋-⌊100/10⌋。
• 比較ソートは n! 個の順列を決定木の葉で区別する必要がある。

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

• StackはLIFO、QueueはFIFO、Heapは優先度付き、Hash Tableはキー検索。
• 配列はランダムアクセスが定数時間、連結リストは順にたどるため線形時間。
• Union-Findは代表元検索と集合併合を扱う。
• 実装では経路圧縮、union by size/rank、未知要素の扱いを確認する。
• 抽象データ型は仕様、実装はその仕様を満たす具体的表現。

第9章 形式言語の入口

• 言語は文字列集合。
• DFAは状態集合、アルファベット、遷移関数、開始状態、受理状態集合で構成する。
• 「1の個数が偶数」は even/odd の2状態で表せる。
• DFAシミュレータは入力文字を左から読み、遷移表で状態を更新する。
• 言語を集合として扱うと、判定問題を「入力文字列がその集合に属するか」と見られる。

第10章 確率の基礎

• 確率変数は標本空間から値集合への関数。
• Pr[A|B]=Pr[A∩B]/Pr[B]。
• ベイズの定理は Pr[A∩B] の2通りの表現から導く。
• 指示変数 I_i を使い、E[ΣI_i]=ΣE[I_i]=np。
• エントロピーには分布、確率変数、期待値、対数が必要。

第11章 数論・代数の基礎

• a≡b (mod n) は n | (a-b)。
• Euclid互除法: 84=2*30+24, 30=1*24+6, 24=4*6 なので gcdは6。
• 3*5≡1 mod 7 なので逆元は5。
• 群は閉性、結合律、単位元、逆元。整数は加法で0を単位元、-aを逆元に持つ。
• 離散対数問題は g^x=h から x を求める問題。

第12章 線形代数の最小限

• A が m×n, B が n×p のとき AB は定義される。
• F_2 では 1+1=0。
• Hamming距離は異なる座標数。最小距離は異なる符号語間距離の最小値。
• 生成行列はメッセージから符号語を作り、検査行列は誤り検出条件を表す。
• 線形構造を使うと、符号語集合を部分空間として扱え、行列計算で検査できる。

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

• 遷移システムは状態集合、初期状態、遷移関係で表せる。
• 非決定性は仕様上の選択、確率的選択は分布付きの選択。
• safetyは「悪いことが起きない」、livenessは「良いことがいつか起きる」。
• インターリーブでは各プロセスのステップ順序を保ったまま全体順序を組み合わせる。
• 合意問題では、クラッシュ・ビザンチン・同期性などの故障モデルにより可能性が変わる。