数学ガール４・乱択アルゴリズム　感想・レビュー

基本情報

著者：結城浩

出版社：ソフトバンククリエイティブ

初版発行：2011年3月10日

ページ数：465ページ

全体の感想

数学ガールシリーズを読むのは2冊目。まず、代数に興味を持って、「数学ガール５・ガロア理論」を図書館で借りて読んだのだが面白かったので次にこちらを読んでみた。
本書の内容の中では個人的には特に第９章の３SAT問題の乱択アルゴリズムによる解法が丁寧に解説されているのが面白かった。アルゴリズムの解析はアメリカ人の計算機科学者であるクヌース先生が始めた学問で、著者はその内容を多いに参考にしているみたいだった。（私自身は読んだことはない）

あと印象に残ったところとしては「確率変数は標本空間から実数への関数」という理解がとても興味深かった。

数学ガールは先に読んだガロア理論のものもレビューしているのだが、この本も同じように数学の公理などを用いてばっちり抑えながら、具体例豊富に解説されていてとても面白かった。

章立てについての考察

他の数学ガールシリーズ同様、この本でも最終的に主題である「乱択アルゴリズム」の説明をするためにさまざまな準備がなされている。特に今回は２つの大きな柱、「確率論」と「アルゴリズム」の部分の二本の流れから最後の２章で「乱択アルゴリズム」に挑むという章立ての流れを感じたのでそれを登場人物を踏まえながらまとめてみる。

各章の数学的内容まとめ

第１章　絶対に負けないギャンブル

数学的内容：コイン投げ、モンティ・ホール問題
登場人物：僕、ユーリ

第２章　愚直な一歩の積み重ね

数学的内容：リニアサーチアルゴリズム、アルゴリズムの解析
登場人物：僕、リサ、テトラ、ミルカ

第３章　171億7986万9184の孤独

数学的内容：順列、組み合わせ、二項定理
登場人物：僕、ユーリ、テトラ、ミルカ

第4章　確からしさの不確かさ

数学的内容：確率の公理
登場人物：僕、ユーリ、リサ、テトラ、ミルカ

第5章　期待値

数学的内容：確率変数、期待値、インディケータ確率変数、二項分布、クーポン収集問題
登場人物：僕、テトラ、ミルカ

第6章　とらえがたい未来

数学的内容：バイナリサーチ、バブルソート、比較ソート、比較木
登場人物：僕、リサ、テトラ、ミルカ

第7章　行列

数学的内容：行列、線形変換
登場人物：僕、ユーリ、リサ、テトラ、ミルカ

第8章　ひとりぼっちのランダムウォーク

数学的内容：ランダムウォーク（放浪問題）
登場人物：僕、ユーリ、テトラ

第9章　強く、正しく、美しく

数学的内容：3-SAT、NP完全、3-SATに対する乱択アルゴリズム（RANDOM-WALK-3-SAT）
登場人物：僕、ユーリ、リサ、テトラ、ミルカ

第１０章　乱択アルゴリズム

数学的内容：クイックソート、クイックソートに対する乱択アルゴリズム（RANDOMIZED-QUICKSORT)
登場人物：僕、ユーリ、リサ、テトラ、ミルカ

各章ごとの関係

今作は二本の大きな柱があるようなのでその関係を章と合わせて図にしてみた。

基本的には確率論とアルゴリズムの二本立てになっていて、それを合わせて１０章でクイックソートの乱択アルゴリズムの解析を行うのが目標になっている。
ただ、プログラマーとしてアルゴリズムを扱っているので、個人的には第９章のRANDOMIZED-WALK-3-SATのほうが馴染みが薄く、難しく感じた。

また、まとめてみて気づいたが、第７章の行列の説明は第８章の放浪問題を解く際に必要だからというだけの理由で用意されていて、作者の苦心が感じられた。