数学ガール 乱択アルゴリズムを読みました。
はじめに
数学ガールの乱択アルゴリズムを読みました。仕事や趣味でプログラム書くから、他の数学ガールより簡単に読めるかと思いきや、なかなか難しい内容でした。前にアルゴリズムの本を読んで最後まで読みきれなかったことがあるのですが、やはり私にはアルゴリズムが難しいようです。
それでも数学ガールはわかりやすく、順序立てて書かれているので、理解が深まりました。
読んだ感想をまとめます。
リニアサーチ
アルゴリズムと言えばソートというイメージがあったのですが、最初に検索から入っていました。その方が理解しやすいなと感じました。
少しの工夫で実行ステップ数が改善するのが、面白かったです。今まであまり考えたことがなかったのですが、小さな積み重ねが大きな差になるので、これから気をつけないとと思いました。
確率の公理
確率の公理は初めて知りました。高校で習う数学と大学以上の数学での違いは厳密に定義される点だと感じます。
少しの公理に確率の考えが詰まっていると思うと不思議です。
ソート
検索のアルゴリズムは比較的簡単ですが、ソートになると急に難しくなります。前にアルゴリズムの本を読んだときもたくさんのソートアルゴリズムを読んで途中で断念しました。じっくり読むと理解できるのですが、すっとは入ってこないですね。コードを何度も読んだり、実装するのがよいだと思いつつやってないですね。。。
考え方が理解しやすいバブルソートとよく使われているクイックソートが出てきました。
対角行列
私は行列苦手で、特に対角行列がよくわかってなかったのですが、乱択アルゴリズムに対角行列が出てきて理解が深まりました。
対角化することで計算が楽になります。その計算結果を元の行列の計算結果に戻すのも楽なんですね。
P≠NP予想
P問題は多項式時間で解を発見できる問題。
NP問題は多項式時間で正しい解かを判定できる問題。
PならばNPで、その逆は違いそうという雰囲気はわかりますが、証明できてなくて、ミレニアム懸賞問題にもなっています。簡単そうに見えてとても難しい問題なのですね。
乱択アルゴリズム
ランダム性を取り入れて問題を解く方法で、以下のものが紹介されていました。
- 全体を把握するための乱択アルゴリズム。ランダムサンプリングによって少ない手間で全体を見渡す。
- 最悪を避けるための乱択アルゴリズム。固定的な選択によって最悪のケースになりうるとき乱択することによって回避する。
- 多数の証拠を得るための乱択アルゴリズム。おそらくそうであるという解を得る。
失敗確率がいくら以下かという評価を行うことで乱択アルゴリズムの信頼性がきまってくるので、それをしっかり認識していれば、とても実用的な方法だと思いました。
おわりに
乱択アルゴリズムを読んだのをきっかけにアルゴリズムの勉強をもう一度してみようと思いました。
ミレニアム懸賞問題であるP≠NP予想が出てきたことでミレニアム懸賞問題にも興味が出てきました。
本を読むことで興味の幅が広がりますね。でも何でもやりたくなるから、何をやるかの選択が今の課題だと思っています。
