結城浩『数学ガール…

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

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

JRF 2017年10月18日

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

JRF 2017年10月18日

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

JRF 2017年10月18日

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

JRF 2017年10月18日

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

JRF 2017年10月18日

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

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

JRF 2017年10月18日

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

JRF 2017年10月18日

Trackbacks:

《cocolog:89482767》 from JRF のひとこと
http://jrf.cocolog-nifty.com/statuses/2018/06/post-4e04.html

結城浩『数学ガール ガロア理論』と『数学ガール ポアンカレ予想』を読んだ。「阿弥陀」の名を冠したアミダクジから作る群のケイリーグラフが「易双六」の盤に似ているのを知ったのが最大の収穫かな。... 

受信： 2018-06-29 14:34:05 (JST)

《cocolog:89225672》 from JRF のひとこと
http://jrf.cocolog-nifty.com/statuses/2018/04/post-4e04.html

結城浩『数学ガール』と『数学ガール フェルマーの最終定理』を読んだ。ライトノベル風に数学を紹介できたら間口も広がるだろう。そういう小説をかけたら…と思った者は幾人もいただろう。しかし、それをモノにして「売れた」のは著者ぐらいで、スゴイと思う。... 

受信： 2018-06-29 14:35:37 (JST)