このページについて
このページでは、計算数理（オートマトンと形式言語）の授業の補足情報を記載します（シラバスと一部かぶりますが）。
ねらい
計算＝計算機でできること、とは何か？という問題は、「人口知能」の可能性が再燃している現代において、改めてその重要性が見直されています。本授業では、オートマトンや形式言語を通じて、計算とその複雑さを深く理解することを目指します。
参考文献
- 丸岡 章, やさしい計算理論―有限オートマトンからチューリング機械まで, サイエンス社
– 最近、出版された入手しやすい本で、コンパクトにまとまっています。基本的にこの内容に従って講義を進める予定です（記述法も）。ただし、必ずしも説明はわかりやすくはないので、他の情報にもあたることをおすすめします。 - Michael Sipser, 計算理論の基礎 [原著第2版] 1.オートマトンと言語, 共立出版
– 本格的でありながら説明が丁寧なので、おすすめしますが、若干価格がお高い。 - J. ホップクロフト, J. ウルマン, R. モトワニ, オートマトン言語理論 計算論〈1〉［第2版］, サイエンス社
– この分野のバイブル的な古典。元々は、数学書的なシンプルでなかなかハードな記述だったが、第2版になって説明にサンプルプログラムが入ったり、かなりイメージチェンジしてわかりやすくなりました。現在、原書では第3版があるが、和訳されていません。 - http://infolab.stanford.edu/~ullman/ialc.html
– オートマトン言語理論 計算論の著者である、スタンフォード大学のウルマン等による講義で使われているスライド・演習等がオンラインで入手できます。イントロダクションを読むだけでも参考になます。 - 高岡 詠子, チューリングの計算理論入門 (ブルーバックス), 講談社
– 比較的最近（2014年）に出版されたもので、歴史的背景や概要をつかむのによいでしょう。直感的な理解には役立ちますが、ちゃんと理解するには適しません。 - 川添 愛, 白と黒のとびら: オートマトンと形式言語をめぐる冒険, 東京大学出版会
– オートマトンと形式言語を物語にしてしまうという意欲的な作品です（2013年）。同著者によるチューリングマシン・人工知能をテーマにした物語もでています。