計算量とグラフ理論に関する本。

　コンピュータサイエンスの分野には、NP困難という計算量に関する用語がある。本日の日記では詳しく書かないが（そもそも私は計算量にまつわる話が苦手なので詳しく書けない）、数学のとても難しい問題である。過去、フェルマーの最終定理が解けたり、ポアンカレ予想が解けたりしたときに大騒ぎになったが、それらと並ぶ難しい問題である。その解説書（入門書？）を本日の日記では紹介する。

最短経路の本

「最短経路の本」という本である。もともとドイツ語で書かれた本のようだが、平易な日本語に訳されている。一貫して、「パソコンの中の謎の人工知能がドイツの女子高生にグラフ理論を教える」という対話形式で書かれている。対話形式で数学を紹介する本には当たり外れがあるが、この本は当たりである。非常に読みやすい。また、口語であるためなのか、日本語とドイツ語の相性がいいのか、訳者の腕がよいのかは分からないが、とにかく翻訳にありがちな無理な日本語もない。

　内容としては、最初に「グラフ理論のグラフとはなんぞや」という話になる。次に、最短経路の話になり、次第に計算量や効率的なアルゴリズムの話へと移り変わっていく。最終的には「効率的なアルゴリズムがあるのかないのかが分からない問題というのが存在する」という話が出てきてNP困難の紹介となっている。専門用語なども（私は専門外なので本当のところは判断できないが）、誤魔化さずに、且つ、分かりやすく説明されているという印象である。

　難易度としては、プログラミングの勉強を始めて三ヶ月くらい経った人にちょうどいいのではないかと思う。C言語などで「素数を求めるプログラム」などの多少数学的なプログラムを書いたことがあると本の内容がよく理解できると思う（擬似コードも数カ所に出てくる）。簡単な文字処理しかしたことがない人にとっては少々厳しいかもしれない。中学一年か二年程度の数学の知識も必要である。

　この本はNP困難を知りたいという人よりも、「なんだか自分の周りで『O(n)』みたいな式で計算量がどうたらこうたらとか話している人がいるけどあれは何？」と思っている人に薦めたい。数学の本というよりは、プログラマのための一般教養の本だと思う。なお、グラフ理論自体に関してはあまり掘り下げられていない印象を受ける。