Python実装ノート
この教材の Python 例は、理論概念を実装で検査するための補助である。ライブラリは原則として標準ライブラリだけを使う。NumPy などは線形代数の理解を補助するが、前提教材では行列演算を手で追えることを優先する。
実装方針
| 方針 | 理由 |
|---|---|
| 標準ライブラリ中心 | 環境差分を減らす |
| 小さい入力を使う | 状態・不変条件を目で追えるようにする |
| 型ヒントを付ける | 集合・関数・関係の型を明示する |
| assert を使う | 定義と実装の対応を検査する |
| 乱数を使う場合は seed を固定する | 結果の再現性を確保する |
実行方法
リポジトリ直下で次を実行する。
python examples/python/tests.py
個別の例を動かす場合:
python examples/python/bfs_layers.py
python examples/python/dfa_simulator.py
python examples/python/state_transition.py
理論と実装の対応
| 理論概念 | Python表現 | 注意点 |
|---|---|---|
| 集合 | set[T] |
順序を持たない |
| 関数 | dict[A, B] または callable |
全域性を検査する必要がある |
| 関係 | set[tuple[A, A]] |
反射律・対称律・推移律を検査可能 |
| グラフ | dict[V, set[V]] |
有向・無向を明確にする |
| DFA | 遷移表 dict[(state, symbol), state] |
遷移関数は全域でなければならない |
| 確率分布 | dict[outcome, probability] |
合計が1か検査する |
| 状態遷移系 | state -> next states |
非決定性を集合で表す |
禁止したい実装
前提補強教材では、次の実装は避ける。
- 定義を検査せずに、サンプル入力だけで「正しい」と判断する。
- グローバル変数で状態を暗黙に持つ。
- ランダム性に依存して、再現不能な説明をする。
- アルゴリズムの計算量を、測定時間だけで判断する。
- 例外処理で仕様違反と実装バグを混同する。