cocolog:88278251

結城浩『数学ガール 乱択アルゴリズム』を読んだ。わかりやすい。情報工学科を卒業して、こんな基本的なこともわかってなかったか…と恥ずかしくなる。 (JRF 7071)

JRF 2017年10月18日 (水) Tweet

『数学ガール 乱択アルゴリズム』(結城 浩 著, ソフトバンク クリエイティブ株式会社, 2011年)
https://www.amazon.co.jp/dp/479736100X
http://7net.omni7.jp/detail/1106006546

JRF2017/10/183316

『数学ガール』シリーズを(まだ)1巻からすべて読んでいるわけではないが、3巻となる『数学ガール ゲーデルの不完全性定理』を少し前に読んで([cocolog:88125718])、おもしろかったので、この 4巻目を買って読んだ。

JRF2017/10/189047

今回は、クイックソートのピヴォットの選び方をランダムにする乱択クイックソートが最後のトピックとなる。不完全性定理にくらべれば楽だが、ハードな内容であることに変わりはない。

JRF2017/10/186415

クイックソートの平均実行時間のオーダーが O(n log n) であることの証明とか、私は大学は情報工学科卒なので、習ったことがあるかもしれないが、ここまで「わかった」と思えるような理解の仕方はしていなかった。

JRF2017/10/188232

乱択クイックソートのアイデアは、確か習ってないが、おのころ、独力で思い付いていたように思う。入力が一様に分布してなくても乱択のおかげで、速さが平均化されるだろうとは思っていた。でも、その証明ができていたわけではない。ここには証明があり、それはすばらしいことだ。(それとも、先輩とかから習ったのかな？) 逆にこんな基本的なことを私は知らなかったのかと思うと恥ずかしくもある。

JRF2017/10/186742

3-SAT については、読めはするが今いち理解が完璧ではない感じ。難しかった。

しかし、こういう確率とアルゴリズムの絡みあいって、昔、カッコイイと思って憧れたことはあったよな…と思い出す。そこを深く追うことはその後なかったんだけど。

JRF2017/10/185018

行列と連立方程式の話、ad - bc の話は深い話を知れたと思う。『数学ガール』はこういう発見が多いね。シリーズの他の本も読んでみたくなる。

JRF2017/10/182375