『数学ガール・乱択アルゴリズム』を読んでみた。

ずっと昔に買ったけど、読まずに積読になっていた『数学ガール・乱択アルゴリズム』を今更ながら読んだので、その感想とか。

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

扱ってる数学

まずは、扱ってる数学について。

出てくる順番に（大雑把に）リストアップすると、

• 確率
• リニアサーチ
• 順列、組合せ、二項定理、指数的爆発
• 公理的確率論
• 確率変数、期待値
• O記法、バイナリサーチ、バブルソート
• 行列と連立一次方程式の関係、線形変換
• ピアノ問題（場合の数）
• 行列のn乗と対角化
• SAT、NP完全、3-SATに対する乱択アルゴリズム
• クイックソートと乱択クイックソート

という感じで、

• アルゴリズム
• 離散数学（順列、組合せ）
• 確率
• 行列

あたりの話を、あっちにふらふら、こっちにふらふらと、それこそランダムウォークするかのように渡り歩きながら、進んでいくw

けど、最後にはそれらが全部まとまりあうような感じで、3-SATに対する乱択アルゴリズムの解析、および、乱択クイックソートの解析に繋がっていく構成は、すごく面白かった。
どの章が欠けてもここには辿り着けないというか、それぞれの数学の繋がりが感じられるのは、とてもいいと思う。

感想とか

一応、専攻が最適化だったので、3-SATに対する乱択アルゴリズムに対する解析以外はだいたいスラスラ読めた感じ。
3-SATに対する乱択アルゴリズムの解析だけは、論文から引っ張ってきてるだけあって、手強い感じだったけど。（というか、ここだけはさらっと眺めただけで、ちゃんとは読んでない）

それにしても、こうやっていろいろな数学が結びついてるんだということを実際に見れるというのは、学生に数学に興味を持ってもらうのにとてもいいと思う。
まるでミステリーを読むかのように、「あぁ、あれはここへの伏線だったんだ！」もとい「あぁ、あの数学はこの数学とこう繋がってたんだ！」という驚きがあって、面白く感じてもらえると思うから。
もっとも、それを味わうには、無味乾燥に思える数式の操作を難なくこなせる数学の基礎体力と、数式の意味を読み取ったり、逆に数式に落とし込んだりする国語力、それに、じっくりと論理を追っていける根気が必要になってくるのだけれど。

思い返してみると、自分が数学に興味を持ったきっかけも、三平方の定理に対する証明で、直角三角形4つを

と組合せたときに、大きな正方形に対する面積から

という数式が得られ、この右辺を計算していくと、

となることから、が導ける、というものを見たときだった。

この「図形の問題が計算で解ける」というのがまず大きな衝撃で、今まで独立したものだと思っていた図形と代数が結びついたことに驚いた。
しかも、その計算も展開の公式を使うものなので、展開の公式がこんなところに繋がってくるんだ、と驚いた記憶がある。

よくよく考えてみると、この証明って

1. 図形の「意味」を数式に落とし込む。
2. 落とし込んだ数式を「意味」を考えずに機械的に計算する。
3. 機械的に計算された数式の結果を、図形の「意味」として読み直す。

ということをやっていて、数学の本質（モデル化とモデル上での計算、およびその解釈）をついてるんだよね。

この辺りの話をすると、作図というのもけっこう面白い話と繋がっていて、コンパスと定木（≠定規。長さは測れないから）で作図できる図形（長さ）は、代数的に四則演算と平方根で表されるものに限る、という話があったり。
作図で掛け算と割り算が出来る、というのも、知らない人には驚きなんじゃないかな。（少なくとも、自分は初めて知ったときに驚いた）
正五角形の作図も黄金比と深い関係があって、黄金比を求めるとなると二次方程式を解くことになり、ここで代数との繋がりが生まれて、正五角形の作図の各ステップが四則演算と平方根をとる計算のどれに対応しているのかというのを眺めていくと、ただの作図に思える正五角形の作図が、非常に興味深いものになってくる。
他にも、作図と代数の関係の話は三大作図問題の不可能性の話と繋がっていて、特に円積問題はが超越数である（＝有理係数の代数方程式の解にならない）という話と繋がっていたり。

ちなみに、自分が中学のときに読んだ作図の本は、次の本。

定木とコンパスで挑む数学―四則演算から作図不能問題まで (ブルーバックス)

まだ売ってるのか分からないけど、非常に面白いのでオススメ。

そういえば、中学の頃の自分は、正五角形が作図できることに喜んで、正十二面体を薄く輪切りにしていったときの各断面を作図し（微分！）、各断面を厚紙で切り抜いて重ね合わせて（積分！）、中身の詰まった正十二面体のサイコロを作って喜んでたw
我ながら変な中学生だw

連立方程式、グラフ、ベクトル、行列、行列式、線形変換

閑話休題。

各数学の繋がり、という話でいくと、連立方程式、グラフ、ベクトル、行列、行列式、線形変換の繋がりというのがちゃんと書かれているのは、すごくいいと思った。

高校の頃、行列は習ったけど、やるのは計算だけでそれが何を意味しているのかということについては習わなかったので、結局、この行とか列っていうのは何なんだろう？というのが抜けなかった。（それが分かったのは大学に入って線形代数をちゃんと勉強してから）
けど、こうしてちゃんとそれぞれの数学との繋がりが説明されていると、すごく分かりやすいと思う。
高校でもちゃんとこうやって教えてくれればよかったのに。（もっとも、今は行列自体が外されちゃってるみたいだけど）

乱択アルゴリズム

恥ずかしながら、乱択アルゴリズムの話は初めて読んだ。
けど、非常に面白いアイディアだなぁ、と。

思い返してみると、変種オセロをSwiftに移植してみた。（その10） - いものやま。で書いた「上限値のある乱数」を得るためのアルゴリズムも、ある種の乱択アルゴリズムになっている気がする。
というのも、1回の試行では失敗する可能性があって、ただし、その失敗する確率を上から押さえられるので、何度か繰り返すことで、失敗する確率を十分に小さい値に抑えることが出来る、としているから。

最適化ェ・・・

欲を出せば、最適化の話も出てきてくれると嬉しかったなぁ、と。
自分が専攻していた分野なのでw

でも実際、線形計画法が取り上げられれば、行列と凸多面体との関係とかも出てくるだろうし、凸多面体の凸性の話から、二次関数で最小値を求めるのがなんで嬉しいのか（凸性が局所最適性を全体最適性まで押し広げてくれる）という話にも繋がっていく。

線形計画法を解くためのアルゴリズムである単体法を追えば、それぞれの操作が凸多面体上で何をやっているのかという話になって、面白いと思う。
それに、単体法が常に多項式時間で終わるピボット規則が存在するかどうかは、未解決問題だし。

さらに、NP困難な問題に対する別のアプローチとして、近似アルゴリズムというのも存在する。
こちらは、常に多項式時間で終わって、最適値の倍で抑えられる近似解（最小化問題の場合）を得るというアルゴリズムで、面白いのは、「最適値は正確に分からないのに、でも、必ず最適値の倍以下の近似解を得られる」ということ。
そんなこと可能なのか？と思うけど、そこで出てくるのが線形計画法で、その双対定理を使うことでこの保証が得られたりする。

他にも、人工知能の話なんかにも繋がっていく（ニューラルネットワークなら最急降下法やニュートン法、サポートベクターマシンなら二次計画法、強化学習（モデルあり）だと動的計画法）ので、非常に面白いと思うんだけど、まぁ、紙面にも限りがあるしね・・・

誰か『最適化ガール』書かないかなw

今日はここまで！

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)