Part II 計算理論
このパートは、本書の中核です。Part I でそろえた計算モデルと言語の視点を使って、「解ける問題と解けない問題」「解けるとしてどの程度の資源が要るか」「個々のアルゴリズムをどう評価するか」を連続した問いとして整理します。
このパートで得るもの
- 決定可能性・還元・複雑性クラスの基本的な読み方
- 不可能性の証明と効率性の議論を混同せずに読むための枠組み
- 第7章以降で使う計算量解析の共通言語
通し例: 安全なメッセージ配送基盤
このパートでは、安全なメッセージ配送基盤に対して「仕様チェックをどこまで自動化できるか」「配送制約や資源配分をどこまで効率よく最適化できるか」を考えます。通し例を置くと、第4章の限界、第5章の困難さ、第6章の解析手法が同じ系の別問題としてつながります。
なぜこの順番か
- 第4章で「計算の限界」を示し、万能な自動化が存在しないことを押さえる
- 第5章で「解ける問題どうしの難しさ」を比較し、計算資源の観点を導入する
- 第6章で個々のアルゴリズムへ降り、設計手法と解析手法を具体的に結びつける
第4章と第5章が全体の地図、第6章が設計現場で使う読解力という役割分担です。
読み飛ばしの目安
- 実務寄りにアルゴリズム解析を急ぎたい場合でも、第4章の還元と第5章の複雑性クラスの骨格は先に押さえる方が、第6章の位置づけを誤読しにくくなります
- 逆に、理論の限界に関心が強い読者は、第4章と第5章を丁寧に読み、第6章は必要な設計手法から拾い読みにして構いません
- いずれの場合も、Part II は本書後半を読む際の判断軸になるため、完全に飛ばす構成は推奨しません
章の役割
- 第4章 計算可能性理論: 何が原理的に判定できないかを明確にする
- 第5章 計算複雑性理論: 解ける問題の困難さを資源制約の下で比較する
- 第6章 アルゴリズムの数学的解析: 設計した手続きを定量的に評価する
次のパートへの接続
Part II を終えると、問題の難しさとアルゴリズムの性能を評価する尺度がそろいます。Part III ではその尺度を持ったまま、データ構造・グラフ・形式的手法といった、より具体的な対象へ理論を落とし込みます。