ミニプロジェクト

このページでは、読解だけでなく小さな実装成果物で到達確認できるようにする。各プロジェクトは 2〜6 時間で完了できる粒度にしている。

P1. 関係チェッカー

対象章: 第1章、第2章、第3章

仕様:

• 有限集合 A と二項関係 R ⊆ A × A を入力する。
• 反射律、対称律、反対称律、推移律を判定する。
• 同値関係なら同値類を出力する。
• 半順序なら Hasse 図に必要な cover relation を出力する。

合格条件:

• 空集合、単集合、完全関係、恒等関係でテストしている。
• 反例がある場合、その反例ペアまたは三つ組を返す。
• 判定結果だけでなく、どの定義に基づくかを説明できる。

P2. BFS 到達可能性エクスプローラ

対象章: 第6章、第8章

仕様:

• 隣接リストからグラフを読み込む。
• 始点からの距離、親ポインタ、BFS探索順を出力する。
• 指定した終点までの最短路を復元する。
• 到達不能な頂点を明示する。

合格条件:

• 無向グラフと有向グラフの両方を扱える。
• キューの状態をログ出力できる。
• 「最初に発見した距離が最短距離である」理由を説明できる。

P3. Union-Find による動的連結性

対象章: 第2章、第8章

仕様:

• union(x,y), find(x), connected(x,y) を実装する。
• path compression と union by size/rank を入れる。
• 連結成分を一覧表示する。

合格条件:

• 代表元と同値類の対応を説明できる。
• union の順序が違っても、同じ分割を表せることを確認する。
• 最悪ケースを避ける工夫を説明できる。

P4. DFA シミュレータ

対象章: 第9章

仕様:

• 状態集合、アルファベット、遷移表、初期状態、受理状態を定義する。
• 入力文字列を読み、受理/拒否を返す。
• 遷移表の全域性を検査する。
• 各接頭辞を読んだ後の状態列を出力する。

合格条件:

• 1 の個数が偶数である文字列を受理する DFA を実装する。
• 0*1* など、別の簡単な言語でもテストする。
• 状態が何を記憶しているかを不変条件として書ける。

P5. Hamming距離と単純な誤り検出

対象章: 第10章、第12章

仕様:

• 同じ長さのビット列間の Hamming距離を計算する。
• 符号語集合の最小距離を計算する。
• 受信語から距離が最小の符号語を探索する。

合格条件:

• 最小距離と誤り検出・訂正能力の関係を説明できる。
• 距離が同率最小になる場合を検出できる。
• F_2 上の加算との関係を説明できる。

P6. 合同算術と小さなRSAデモ

対象章: 第11章

仕様:

• Euclid の互除法を実装する。
• 拡張Euclid法で逆元を求める。
• 小さい素数を使って RSA の暗号化・復号の流れを確認する。

合格条件:

• gcd(a,n)=1 でないと逆元が存在しない理由を説明できる。
• toy RSA は教育用であり、実用暗号ではないことを明記する。
• 剰余演算で大きなべき乗を扱うため pow(m, e, n) を使う。

P7. 確率実験と理論値の比較

対象章: 第10章

仕様:

• コイントス、サイコロ、条件付き確率の実験を行う。
• seed を固定して再現可能にする。
• 実験値と理論値を比較する。

合格条件:

• 試行回数を増やすと実験値が理論値へ近づく様子を説明できる。
• 独立と排反の違いを例で説明できる。
• シミュレーションは証明ではないと明記する。

P8. 状態遷移系と safety 検査

対象章: 第13章

仕様:

• 有限状態遷移系を定義する。
• 初期状態から到達可能な状態集合を探索する。
• bad state に到達するかを判定する。
• 到達する場合は反例 trace を出力する。

合格条件:

• 非決定性を set of next states として実装する。
• safety と liveness の違いを説明できる。
• 状態数が組合せ的に増える理由を説明できる。