01 / 読書ガイド
読書ガイド
対象読者
オートマトン入門から理論を広げたい大学院生と上級学部生向け。具体的な計算モデルと消費資源を重視し、回路、記憶を持つ機械、構成上の制約を一つの枠組みで比較する。
前提知識
計算機構成、離散数学、証明への習熟が役立つ。Boolean論理、グラフ、漸近解析、帰納を復習する。算法の基礎があれば計算量と資源交換の議論を追いやすい。
扱う内容
論理回路と記憶付き機械から、オートマトン、計算可能性、代数回路、並列計算へ進む。計算量クラス、回路計算量、時間空間の交換、記憶階層、VLSIも扱う。
使い方
小問題の入力サイズを定め、二つのモデルを比べる。回路や機械状態を描き、そのモデルが測る資源を数える。模倣の議論で余分なコストを示し、下界の仮定とモデル変更の影響を確認する。記憶階層の結果を無制限の機械へ拡張せず、演習で条件の違いを説明する。
版と出典
著者の全電子版は1998年Addison-Wesley刊を訂正したもの。権利は著者へ戻り、2008年7月の電子公開はCC BY-NC-ND 3.0 USと明記する。公開日、初版年、サイト更新日は分ける。
