計算理論とオートマトン おすすめの参考書

計算理論とオートマトンは「コンピュータで何が計算できるのか、そしてそれを効率よく行うにはどうすればいいか」という問いを数学的に研究する、コンピュータサイエンスの最も根幹をなす学問分野です。

本記事では、おすすめの参考書とさらに最先端の研究が発表されているトップカンファレンスを紹介します。

おすすめ参考書

計算理論の基礎

入門から標準レベルの教科書としては、計算理論の基礎がおすすめです。世界的な標準テキストです。アメリカの教科書ということもあり、演習問題などの回答が英語ですが、Web上ですが探せば出てくるということもおすすめの理由です。英語の教科書は非常に分厚いので、日本語版では３分冊となっています。

英語の原著はこちらになります。

計算理論とオートマトン言語論

日本の大学の講義でもよく使われる一冊です。エッセンスが凝縮されており、独学でも体系的に学びやすい構成です。

計算理論のトップカンファレンス

理論計算機科学の分野では、以下の会議が世界最高峰とされています。

STOC(ACM Symposium on Theory of Computing), FOCS(IEEE Symposium on Foundations of Computer Science)という会議がトップカンファレンスです。最先端の研究が気になる方はこちらを参考に更なる勉強をしてみてください。