数学に萌える。。。一応理系だけど学生時代は萌えたことなかったな。この数学ガールは学生時代に出会いたかった本の一つだ。小学生の息子が中学に入ったら４冊セットで贈りたいと思う。てか、その頃には５、６冊になってるのかも（汗）
４作目の今回は「乱択アルゴリズム」をテーマとして取り上げている。前作に比べてテーマが比較的簡単（？）で、自分がＳＥでアルゴリズムに馴染みがあったこともあってか楽に読めた。それでも少し進んではちょっと戻って、といった感じで読了までには随分と時間がかかった。まぁ、楽しめる時間が長いってことでお得な１冊だと思う。
過去3作のレビューはこちら
第1作 数学ガール - zakky's report
第2作 数学ガール/フェルマーの最終定理 - zakky's report
第3作 数学ガール ゲーデルの不完全性定理 - zakky's report
（「BOOK」データベースより）
確率とコンピュータの深くて不思議な関係とは?「僕」と四人の少女が、乱択アルゴリズムの世界に挑む魅惑の数学物語。
んで、今回のテーマとなっている「乱択アルゴリズム」とはなんぞや？ 読むまでは乱数生成のアルゴリズムだと思っていた。そうではなくて無作為選択を前提としたアルゴリズムといったところか。 ソートでも探索でもなんでもいいんだが、そのアルゴリズムを進める上で選択するところに無作為性を取り込む。そうすることで最悪ケースを回避したり、失敗の確率を減らしたりできるという考え。
例えばすごく大きな数が素数かどうかを判定するには、その数より小さい素数で割ってみて割り切れたら素数ではないと判定できる。まぁ、全ての素数についてやればいいんだけど、小さい順とか大きい順とか、ある規則に従うとヒットまでに時間がかかってしまう可能性がある。ここで乱択アルゴリズムで無作為に選択することによりヒットまでの時間を短縮し、効率よく判定できるという考え方だ。さらに最悪ケースを切ることで効率化を計ることもできる。例えば一定時間内に素数ではないと判定できなかった場合は「素数の可能性がある」という判定にし、より詳細な素数判定に回せばいい。
というわけで乱数生成のアルゴリズムではないんですね。そこは期待と違って残念だったけど、内容は非常に充実していた。登場する数学的題材は多岐に渡るが、これが最後に一つにまとまるのは素晴らしい。じっくり落ち着いて読むと本当に深い。
初っ端からモンティ・ホール問題とかが出てきたりして、ワクワクしてしまった。モンディ・ホール問題については映画『ラスベガスをぶっつぶせ
さて、この物語にはたくさんの萌えっ娘さん達が登場する。主人公の同級生の才媛ミルカさん、後輩の元気少女テトラちゃん、中学生の従妹のユーリ、そしてさらに今回から登場する無口なコンピュータ少女リサ。よくもまぁこんだけ数学萌えっ娘さんを集めたもんだ。そういえば最初は妹系だと思ってたテトラちゃんも最近はすっかりお姉さんになってきた。と、完全におっさん的視点で見てしまっている。
んで、この４人の女の子と主人公の僕が数学についてあれこれ談義していくという展開は毎度おなじみだ。数学の深い考察はもちろんだけど、例えば行列の向きの覚え方に漢字の形を利用するといったちょいネタなんかも多い。順序を意識して列にするのが順列、とかも教科書に載せて欲しいちょいネタだ。
あとちょいネタで面白かったのは、宇宙の広さは２の２８０乗立方ｃｍで、つまり２８０ビットあれば宇宙全体を一辺が１cmのサイコロ型に区切って、その一つ一つに番号をつけることができるという話。うーむ、ハルヒに出てくる情報統合思念体の存在も否定できんな。
そして、この作品のいいところは彼らを通して、数学に向かう姿勢なんかも学べるというところ。「例示は理解の試金石」とか本当に当たり前だけど重要なことだ。それに主人公が中学生のユーリに、一般化することの意義は「やってみればわかる」状態から「やらなくてもわかる」状態にすることであり、さらに自分が手を動かした経験がないと公式のありがたみや適用するポイントが分かりにくいことなどを説いている。ユーリじゃないけどなるほどににゃあ、と思わされるわけだ。
特に圧巻だったのが第７章。中学で習う連立一次方程式と高校で習う行列の積和計算の関係が出てきたり、行列（１、１、１、０）の累乗がフィボナッチ数列の漸化式になるなんてのは本当に興味深い。
そして第９章ではいよいよ本題ともいうべき充足可能性問題（ＳＡＴ）が登場する。ユーリの淡い恋から出てきた「強正優美」問題が３つのリテラルを持つ論理式を充足する割り当てが存在するかどうかを調べる充足可能性問題（３－ＳＡＴ）だった。この３－ＳＡＴを解く単純なアルゴリズムは全ての割り当てをしらみつぶしにチェックする方法、ブルートフォースだ。これだと変数がｎ個の場合、２のｎ乗のチェックが必要となり、指数関数のオーダーとなってしまう。乱択アルゴリズムを使うことでこのオーダーを２よりも小さくしようというのがこの章の課題だ。
主人公はコイン投げのランダムウォーク、表が出たら目的地に一歩近づき裏が出たら一歩遠ざかるランダムウォークを手がかりにオーダーを１．５に下げる、つまり高々１．５のｎ乗であることを証明する。これだけでもスゴイと思ったが、ミルカさんは論文に書かれていた１．３３４のｎ乗となる評価方法を紹介する。直前の第８章で出てきたピアノ問題の一般解を使うという何ともうまい流れ。
そして最終となる第１０章では、クイックソートに乱択アルゴリズムを用いた乱択クイックソートについての考察となる。クイックソートはその名の通り確かに早いソートアルゴリズムだ。しかし、それは入力が一様分布である場合という条件付きだ。例えば既にソート済みの入力の場合は最悪ケースとなってしまうように、入力の確率分布が任意である場合には効果を発揮しない。そこで出てくるのが乱択アルゴリズムだ。入力が一様でないのなら、選択時にその任意性を取り除くというところか。
普通のクイックソートの平均実行ステップ数は、一様分布に従う入力に対して高々ｎｌｏｇｎのオーダーになるのに対し、乱択アルゴリズムはどんな入力に対してもｎｌｏｇｎのオーダーとなる。それにしてもここでインディケータが出てくるとは。。。二要素間ではたかだか１回しか比較が行われない、というのは言われてみれば確かにそうなんだけど、それに気づくのは本当に難しい。
そしていよいよテトラちゃんの講義だ。えっと、何がいよいよかというとなんかストーリー的な展開でテトラちゃんが中学生向けの数学講義をするという話になっており、そんなこんなでいよいよなのだ。テトラちゃん、最初は緊張からか資料を落としてしまい言葉もうまく出なかったりと、こっちまでハラハラドキドキ。そこに来ないと思っていたミルカさんが登場。リサの手助けもあって何とか仕切りなおし、最後は拍手喝采。感動。
そして、、、
・例示は理解の試金石
・あたりまえのことから始めるのは良いこと
・変数の導入による一般化
・前提条件を明確にした定量的評価
といった数学ガールのエッセンスがこのテトラちゃんの講義で分かる仕組みになっているのはさすがだ。
さらにテトラちゃん、ライプニッツは二進法を研究した１７世紀の数学者。彼は現代のコンピュータを知らないけれど、彼の研究のおかげで現代のコンピュータが存在している。「数学は時を越える」と。。。
結城さん、素晴らしい本をありがとう。
