計算理論とオートマトン言語理論[第 2 版](ケイサンリロントオートマトンゲンゴリロンダイニハン)

初学者でも読み進められるように証明を含め丁寧に記述し,全面的に見直しを行った著者渾身の改訂版.“なるほど,そういうことか”を繰り返し体験して楽しみながら学ぶことができる.章末問題にはすべて解答をつけた.
第 I 部:計算理論とは／すべては計算から始まる／計算理論のための概念や用語／第 II 部:有限オートマトン,プッシュダウンオートマトン,そして文脈自由文法／有限オートマトン／文脈自由文法／プッシュダウンオートマトン／第 III 部:計算可能性／チューリング機械／チューリング機械の万能性とその限界／第 IV 部:計算の複雑さ／クラス P とクラス NP ／論理回路に基づいた計算時間限定の計算／ NP 完全性

コンピュータにはどこまでのことが計算でき、何が原理的に計算できないのか。この問いに数学の言葉で答えるのが計算理論であり、情報系のカリキュラムで最も抽象度の高い科目の一つです。本書は丸岡章氏によるその定番テキストの第 2 版で、サイエンス社の Information & Computing シリーズの一冊として 2021 年 11 月に刊行されました。全面的な見直しを施した改訂版であることが版元から示されています。

構成は 4 部立てです。計算理論の目的と用語を押さえる導入部から、有限オートマトン・文脈自由文法・プッシュダウンオートマトンを扱う第 II 部、チューリング機械とその万能性・限界を論じる計算可能性の第 III 部、そしてクラス P と NP や NP 完全性に踏み込む計算の複雑さの第 IV 部へと進みます。初学者でも読み進められるよう証明を含めて丁寧に記述する方針が貫かれ、章末問題にはすべて解答が付いています。この解答完備という条件は、講義に頼らず独習する読者には決定的に効きます。

離散数学の初歩、つまり集合や論理の記法に抵抗がなければ読み始められます。学部の講義テキストとしてはもちろん、大学院入試で計算理論を課される受験者や、アルゴリズムの計算量の議論を根本から理解し直したい実務エンジニアが、腰を据えて取り組む価値のある教科書です。