数学ガール乱択アルゴリズム(結城浩)

作者: 結城浩
出版社/メーカー: SBクリエイティブ
発売日: 2011/02/26
メディア: 単行本
購入: 19人クリック: 779回
この商品を含むブログ (103件) を見る

数学ガール/乱択アルゴリズム

「数学ガール」の第4巻。昨年3月の発売のすぐ後に読み終えていたのだが、感想を書くのが今になってしまった。

以前のエントリでも書いたのだが、純粋な(?)数学の話ではなくてプログラミングに関係の深そうなテーマになるとは意外だった。各章のタイトルと、補足として章の内容の要約を書くと以下のようになる。

第1章絶対に負けないギャンブル
サイコロ、コイン、宝くじ、モンティ・ホール問題

第2章愚直な一歩の積み重ね
リニアサーチ、実行ステップ数

第3章 171億7986万9184の孤独
順列・組み合わせ、二項定理

第4章確からしさの不確からしさ
確率の種類、確率の公理

第5章期待値
確率分布、期待値、二項分布

第6章とらえがたい未来
オーダー、サーチアルゴリズム、ソートアルゴリズム

第7章行列
行列、行列式、行列による線型変換

第8章ひとりぼっちのランダムウォーク
行列の対角化、固有値・固有方程式・固有ベクトル

第9章強く、正しく、美しく
充足可能性問題、P≠NP予想、乱択アルゴリズムとラウンド数の評価

第10章乱択アルゴリズム
 クイックソート、乱択クイックソート

特に勉強になったのは以下の3つ。

とかく直感でとらえにくい「確率」を公理系で定義すること
「無限個」と同じく、しょせん直感では理解し得ないものだということがわかった気がする。
「オーダー」のちゃんとした考え方、定義
今までいい加減に使っていた。おまけにもっぱらO記法だけで、ΘやΩは使ってなかったし。
乱択アルゴリズム
探索のアルゴリズムに確率や乱数を導入するというのは興味深い。

全体的に、前3巻に比べて難易度は下がったが胸キュン度は増した感じ。彼女たち(特にミルカさん)がどうなっていくのかにも目が離せない。

乱択アルゴリズムはとても興味深かったのだが、コンピュータのアルゴリズムでしかも失敗も見越したもの(ただし失敗の確率を小さく抑えられていることがポイント)となると、急に現実世界に引き戻された印象はある。次はまた純粋な数学の世界を冒険するようなテーマがいいな... と思っていたら、次巻はガロア理論だとのこと。