 |
新品価格 |
数学ガール/乱択アルゴリズムを読んだ
マスタカと言えばコンピュータプログラマ
そんなわけでアルゴリズムを勉強しようと思ったところ
本書がオススメされてたので読んでみた
以下、内容
・本書の内容
物語調で話が進む本でとても読みやすい
前半は数学がメインだけど
後半はprocedureで処理が書かれてて
これを数学使って説明していく流れ。
ちらっと見ると緩い感じに見えるけど
内容がガチで結構難しい・・・w
高校数学の復習にもなる
ためになったこと
・2人がサイコロ投げて勝つ確率
6/36で引き分けがあるので
15/36が勝率になる
・封筒問題
1万通の封筒があって
最初に選んだ後に
司会者が9,998通り外れを開けた場合
今のを維持するか交換するか
どっちのあたりの確率が高いか
最初の1通は1/10,000の確率
最後の1通は9,999/10,000の確率
ってことになるので交換した方が良いらしい
・変数の一般化
繰り返す回数がいろいろあって定まらない場合
変数を導入して一般化する
これで計算量を出す
・計算量を出すためにやること
具体例を出して
規則性を見つけて
一般化する
・組み合わせ
nCk
や
|n|
|k|
のような二種類の書き方がある
・パスカルの三角形
(a+b)^nの係数はパスカルの三角形になってる
・確率の意味
公理的確率：公理を満たす確率。現代の確率。ゆがんでないサイコロをモデル化
古典的確率：場合の数の比が確率を表す。ゆがんでないサイコロが議論の前提
統計的確率：発生頻度の確率。交通事故等。サイコロを実際に投げた頻度を前提
・標本空間と確率分布
サイコロの場合
Ω={1,2,3,4,5,6} が標本空間
Pr{1}は1が出る確率
Prは確率分布。関数
・二項分布
nCk*p^k*q^(n-k)
・ハーモニックナンバー
Hn =1/1 + 1/2 + … + 1/n
・O(n)
たかだかnのオーダー
・O記法の仲間
O(f(n))：たかだかf(n)のオーダー
Θ(f(n))：ちょうどf(n)のオーダー
Ω(f(n))：少なくともf(n)のオーダー
・計算量の大きさ
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)
結構難しい本ですが
アルゴリズムの理論は少しつかめたかなぁって感じはしました
コンピュータ関係の人はぜひどうぞ
今後はアルゴリズム関係の難しい本を読んで行こうかなと思います
