良いと思った本

色んな本をちょくちょく読んできましたが, それぞれの感想について述べていきます (全部読んだわけではないのですが, パパッと読んで思ったことについて簡単に書きます)

Computational Complexity (S. Arora, B. Barak)

• 茶色い本
• チューリング機械の定義からちゃんと書いてある.
• 説明がすごく丁寧.
• 例が多くて分かりやすい.
• 演習問題は難しめ.

Computational Complexity (O. Goldreich)

• 表紙がカッコイイ.
• トピックが広い.
• 書いてあることは分かる(証明とかも追える)が, Arora本と比べると分かりにくい.
• そういえばSATを3-彩色問題に帰着する証明が面白かった.

近似アルゴリズム (V. V. ヴァジラーニ; 浅野 孝夫 訳)

• 一つ一つの章が短めで読みやすい.
• アルゴリズムのアイデアなどを直感的に説明していて分かりやすい.
• 演習問題も教育的.
• LPに基づく近似アルゴリズム(ラウンディングやプライマルデュアルなど)を, 集合カバー問題を軸にして分かりやすく解説してある.

Introduction to Random Graph (A. Frieze)

• ランダムグラフを全く知らなくても読める.
• 測度論的確率論はほとんど用いられないので, その辺も知らなくても大丈夫.
• 20, 21章を簡単に目を通してから1章とかを読むと良いと思う.
• 2015年の著作なので, 分野の最新の進展が分かる.
• 2015年の著作なので,  (Web上で公開されてるものは)タイポとかミスが多い.

グラフ理論 (R. ディーステル; 根上 生也, 太田 克弘 訳)

• かなり有名な本.
• イメージとしては「広く浅く」グラフ理論をカバーしている.
• グラフ理論を初めて学ぶ人(かつしっかり学びたい人)は少なくとも1,2章はしっかりと読むべきだと思う.

組合せ論シリーズ :数え上げの手法, グラフの構造, グラフの不変数, 集合論的グラフ理論 (L. ロヴァース; 秋山 仁, 榎本 彦衛 訳)

• 演習問題しかない.
• 問題が羅列してあって, そのヒントと解答がすぐ下にちゃんと書いてあるのは親切.
• 問題はそこそこ難しいものもあり, 1問解くのに数時間かかることはザラにある.
• しかし解いていくと力がついていくので, 「時間があったらちゃんと読みたい(解きたい)本ランキング」はぶっちぎりの一位.
• というか書いたいけど(古本含め)どこにも売ってない...