数学ガール ゲーデルの不完全性定理/乱択アルゴリズム 結城 浩




数学ガール、シリーズ第3弾は「ゲーテルの不完全性定理」を扱ったもので、第4弾は「乱択アルゴリズム」を扱ったもの。
分野的に興味があるのは「乱択アルゴリズム」のほうだったので、こちらを先に呼んでいたのだけれども、アルゴリズムを扱った分野だからか、シリーズ中一番簡単で手軽に読める本だった。確率、アルゴリズム、計算量、、、それらをつなげて乱択アルゴリズムに持っていく構成が分かりやすい。
この本ではじめて知ったのだけれども、乱択アルゴリズムとは、言葉のとおり乱数をアルゴリズムの中に組み込んだもの。本の例でいえばクイックソートの平均計算量はO(n log n)、最悪の場合(ソート済みの配列にクイックソートを適用するとき)はO(n^2)となるのだけれども、乱択アルゴリズムを採用することで、どんな入力に対しても期待値がO(n log n)になる。これを計算で導き出すのが面白かった。
計算量に関しては今まで知識のみでリニアサーチがO(n)みたいな話は知っていたけど、なぜそうなのかというのは導き出したことがない、まさにこの本に出てくるリサのような人間だったので自分で考えながら読んでいくのが楽しかった。

数学ガール/乱択アルゴリズム
結城 浩
ソフトバンククリエイティブ
売り上げランキング: 888

その一方で「ゲーテルの不完全性定理」のほうは難しくて読むのがキツかった。一応構成としては一歩ずつ処理を進めていくのだけれども、「数学を数学する」内容がなかなか頭に入ってこず。もう一回読み返さないとダメかなー。

数学ガール/ゲーデルの不完全性定理
結城 浩
ソフトバンククリエイティブ
売り上げランキング: 1480


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です