ホーム » 計算数理:オートマトンと形式言語

計算数理:オートマトンと形式言語

このページについて

このページでは、計算数理(オートマトンと形式言語)の授業の補足情報を記載します(シラバスと一部かぶりますが)。

ねらい

計算=計算機でできること、とは何か?という問題は、「人口知能」の可能性が再燃している現代において、改めてその重要性が見直されています。本授業では、オートマトンや形式言語を通じて、計算とその複雑さを深く理解することを目指します。

参考文献

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

category

archive