理論と数学的背景 [GRE CS]

この分野ではいい本が1冊ある。Prentice Hallから出ているDiscrete Mathematics がそれだ。

この本、タイトルこそ「離散数学」という名前だが、内容はもうまさにGREのCS分野「理論と数学的背景」部門をターゲットに書かれたとしか思えないようなもので、狭義の意味での離散数学（数理論理学、集合論、組み合わせ論、グラフ理論）はもちろん、アルゴリズムとその複雑性にも、オートマトンと言語理論にもそれぞれ一章を割き、詳しすぎず簡潔にまとめられており、例も豊富なので「簡潔であるがゆえに具体的なイメージが結びにくい」ということもなく、しかも「具体的な問題を解く手引き」みたいなことも随所で触れられ、GRE CS分野の受験生には必携と言える。

ただ、そうは言っても、リファレンスとして、各領域についてそれなりに細かく書かれたものも手元に置いておくべきだろう。

たとえば、アルゴリズムに関してはThe Design and Analysis of Computer Algorithms （翻訳） 、オートマトンと言語理論に関しては
Introduction to Automata Theory, Languages and Computation （翻訳）なんかが「古典」と呼ぶしかないようなものだけど、他にもこの領域に関してはごまんと本が出ているから、どれでも気に入ったのを選べばいいと思う（ちなみに、「古典」の2冊は古本屋で二束三文で手に入る）。

離散数学に関しては……クヌース大先生のこれ（翻訳）、おれも持ってはいるけど、あんま読んでないんで何とも言い難し。マグロウヒルから出てるこれなんかもよさそうだけど、離散確率とかの項がないんだよな……。



ま、リファレンスはともかく、上述のDiscrete Mathematics さえあれば何とかなると思われます。



総目次めいたところへ