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

中身について予習せず何となしに手にとったが、ランダム性を上手く活かしての探索の高効率化というメインのテーマが、最近かじったSimulated annealingや量子アニーリングの話題とどんぴしゃりで偶然に驚く。

構成は例によってよく考えられていると感じる。最終目標である、ランダムにピボットを選択する場合のクイックソートの平均ステップ評価を行うのに必要な知識（高校数学の確率や線形変換程度だが）や結果を細分しておき、事前に下ごしらえとして丁寧に扱っておいて、終盤で一気に引っ張ってきたり利用したりして大きな問題を解くことで、カタルシスを感じさせるという流れが、数学のダイジェストな感じで読んでいて楽しい。
前に読んだ不完全性定理の時と違って、今回はお話は主張しすぎず数学の問題をとくための話の流れと無理のない感じで自然に読めた。

全体として、前著よりも更に良い本に仕上がっているように感じた。

一個直ちに分からなかったのが、最後のクイックソートの評価の所で平均ステップ数の漸近評価が分布によらずオーダーn*log(n)というのがあったと思うが、確率分布として端に極端に偏った分布を考えたなら、結果が最長ステップ評価のオーダーn^2に近づきそうな気がしたのだが、この２つのケースはどうつなげば良いのだろうか？　まあそのうち考える。

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

なお完全に余談だが、量子アニーリングの話で読んでいた記事は以下。説明が丁寧で大変わかり易い。

組み合わせ最適化問題と量子アニーリング : 量子断熱発展の理論と性能評価
http://ci.nii.ac.jp/naid/110006830263