「計算理論の基礎」を(一応)読み終わった

以前欲しいと書いた「計算理論の基礎」を読み終えた。
一応と書いたのは、面倒くさい所は読み流す程度ですませたから。問題が付いているけど全然解いていないし。

内容を少しメモしておく。

本自体

内容自体はそれなりに難しいけど、話の流れは日本の教科書とは違い計算理論の目的とかが説明してあってコンピュータの世界の位置づけがかなり分かりやすい。
作りとしては、各章の最初で目的や役割を述べて内容を理解するために例題とそれを証明していく。最後には問題を読者が解いていくという形式。解答は問題のあとに書いてある方式。日本の本では、本の最後に纏めて解答を書いているパターンが多いけどこれはお国柄の違いかな?

1巻

計算理論に必要な数学の基礎知識から始まって、定番のオートマトン、正規言語、文脈自由言語が対象。
この辺りの知識は結構プログラミングでも役に立つのでプログラマ必須の知識だけど、改めて勉強して個人的には収穫が結構有った。

2巻

1巻はコンピュータの機能制限版のオートマトンが対象だったけど、コンピュータと同等のチューリングマシンから話が始まる。
その後はアルゴリズムの定義、判定可能性等などへと話が移っていく。
プログラミングで直接役に立つのは判定可能性以降かな。解きたい問題を見つけてもプログラミングしても解決できるかどうかとかの判定等に係わる重要な話。

3巻

ここは複雑さの判定、クラスP、NP(NP完全性等)とかが含まれる。
プログラミングでももちろん役立つんだけどどっちかといえばより数学寄りの理論の話へ移って行きます。まあ余裕が有れば読んでおきたい内容と言った感じです。
NP完全性とか卒研以来に聞いたな。

全体を通しての印象は計算理論なだけあってかなり数学よりでプログラミンマとしてはイメージはかなり沸き辛いです。
今ではへたれなりに経験、知識がある程度あるので理解出来るけど、大学の時はここの内容は何に役立つのかさっぱりだったのは仕方がない。
例えばオートマトンが良く使われるのは正規表現だけど、分かりやすいプログラムを書く場合にも重宝する。
文脈自由言語なんかコンパイラやインタプリンタを作るのに必要な知識だけど、当時はコンパイラの中身はとても想像出来なかったし。
まあ久しぶりにこういう勉強も大切ですね。

あとAmazonのイメージだけでTAOCPぐらいの結構大きなイメージが有ったんだけど、そんなことはなくさほど厚くは無いサイズ。厚さはラノベでも通りそうなぐらい。1冊200ページちょっと程だしね。