形式言語・オートマトン・計算量理論 オススメ動画・本まとめ 計算理論の基本を学ぶ

いいソフトウェアを作るには計算理論の知識は欠かせないと思います。

普通のプログラマーは専門家になる必要はありませんが、基本的なことは知っておかなければいけません。

形式言語やオートマトンの知識はコンパイラを作るのにも必要になりますし、アルゴリズムの設計などを考える場合には計算量理論の知識も必要になります。

オートマトンやチューリングマシンについては、youtubeに講義動画がありますのでまずそれを見るのがいいと思います。

Formal Languages and Automata 2013 - Week 02

同じ人の計算量理論の講義動画もありますので、そちらもオススメです。

Computational Complexity Theory 2009 - Week 01

福井大学での授業のようです。比較的分かりやすい方なので取り敢えずこの動画を見ることをお薦めします。

また計算理論やアルゴリズム設計、分散・並列アルゴリズムなどはnaist(奈良先端大学院大学)にもあります。

NAISTにはいろいろな講義があるので探してみるといいと思います。

library.naist.jp

数学的な議論をする分野ですので、というか数学なのでまずは講義動画を見てから本を読む方が理解が早いと思います。

オートマトン・言語理論の基礎

オートマトン・言語理論の基礎

オートマトン、チューリングマシンの入門書としては多分１番分かりやすいと思います。

１番最初に読む本としては最適でしょう。

内容も基本的なところはちゃんと押さえてあるので、これを読んでおけばオートマトンの基本はわかっているといえると思います。

この分野は有名な計算理論の基礎という本がありますがそれと同じぐらい良くできています。

このあとに計算量理論の本を読む必要があります。

計算理論の基礎

計算理論の基礎 [原著第2版] 1.オートマトンと言語

計算理論の基礎 [原著第2版] 2.計算可能性の理論

第三巻が計算量理論です。

この分野では最も有名な本で、計算理論をやるなら取り敢えず読んでおけ、といわれる本です。

かなり分かりやすくかかれているのでそこまで苦労せずに理解できると思います。

全部読むと結構量があるので、時間がかかりますが読む価値のある本です。

白と黒のとびら

白と黒のとびら: オートマトンと形式言語をめぐる冒険

読み物です。

オートマトンや形式言語の基本的な概念を理解できるようにはなると思いますが、好き嫌いのある書き方です。

なんか逆に読みづらいと私は感じましたがまあひとによるでしょう。

川添氏の本はどれもこの調子でして、たぶん数学ガールと一緒でテイストに馴染める人にとってはいい本なんだと思います。

こういうのが苦手な人は普通のテキストで学びましょう。

他にもいろいろな本を書かれていますので好きな人は全部読むといいと思います。

働きたくないイタチと言葉がわかるロボット 人工知能から考える「人と言葉」
自動人形の城(オートマトンの城): 人工知能の意図理解をめぐる物語
精霊の箱 上: チューリングマシンをめぐる冒険
精霊の箱 下: チューリングマシンをめぐる冒険

この分野はどこまでやるべきかはなかなか難しいのですが、アルゴリズムを専門的にやっていきたい人は計算量理論はちゃんとやっておくべきでしょう。

普通のプログラマーは計算理論の基礎にかかれていることがわかっていれば十分な気がします。

他の分野

他の分野に興味がある人はこちらをどうぞ

www.neuralsparrow.com
www.neuralsparrow.com
www.neuralsparrow.com
www.neuralsparrow.com
www.neuralsparrow.com