『数学ガール／乱択アルゴリズム』
https://gyazo.com/917c1924117a67fc849c38fe4ff397c7
第1章「絶対に負けないギャンブル」
第2章「愚直な一歩の積み重ね」
ステップ数
見つかる場合
S=1
M=vの位置
見つからない場合
S=0
M=n
4M - 3S + 5
code:jl
function linear_search(A::Vector, n::Int, v) # 1
k = 1 # 1
while k <= n # M + 1 - S
return println("見つかる") # S
end # 0
k += 1 # M - S
end # M - S
return println("見つからない") # 1 - S
end # 1
linear_search(A, 5, 26)
番兵付きリニアサーチ: 48
番兵を置くと場合分けが不要になる
見つからない場合を最後に見つかったにできる
与えられた配列を変える副作用があるあんも.icon
A_copy = copy(A)とでもすれば回避できる
ステップ数
見つかる場合
S=1
M=vの位置
見つからない場合
S=0
M=n
4M - 3S + 7
code:jl
function sentinel_linear_search!(A::Vector, n::Int, v) # 1
push!(A, v) # 番兵を置く # 1
k = 1 # 1
k += 1 # M - S
end # M - S
if k <= n # 1
return println("見つかる") # S
end # 0
return println("見つからない") # 1 - S
end # 1
sentinel_linear_search!(A, 5, 26)
第3章「171億7986万9184の孤独」
アスパラガスの6文字の並べ方: 81
場合の数のキャンセルさせる考え方が汎用性が高くて好きあんも.icon 第4章「確からしさの不確かさ」
サイコロ勝負
code:jl
function dice_game()
a = rand(1:6)
b = rand(1:6)
if a > b
return println("アリスの勝ち")
elseif a < b
return println("ボブの勝ち")
end
return println("引き分け")
end
dice_game()
ルーレット勝負
code:jl
function roulette_game()
r = rand(1:36)
if r <= 15
return println("アリスの勝ち")
elseif r <= 30
return println("ボブの勝ち")
end
return println("引き分け")
end
roulette_game()
公理的確率を定義する: 115
公理的確率
確率の公理によって定める
古典的確率
直観的に定義できて、公理的確率と矛盾しない
統計的確率
発生頻度の比によって定める
出来事の原因を理論的に捉えにくい場合でも利用できる
サイコロを1回投げるときの標本空間
$ \Omega = \large{\{ \char"2680, \char"2681, \char"2682, \char"2683, \char"2684, \char"2685} \}
起こりうる可能性を網羅している
0の目や7の目は出ない
標本空間の各要素が同時に起こることはない
1と2の目が同時に出たりしない
$ Pr(\{\char"2680\}) = \frac{1}{6}, Pr(\{\char"2681\}) = \frac{1}{6}, Pr(\{\char"2682\}) = \frac{1}{6}, Pr(\{\char"2683\}) = \frac{1}{6}, Pr(\{\char"2684\}) = \frac{1}{6}, Pr(\{\char"2685\}) = \frac{1}{6}
標本空間の各要素に対して0以上の値を返す
確率が負になったり、未定義になったりしない
すべての確率を合計して1にならなければならない
1を分布させる関数
偶数の目が出る確率を公理に従って求める
$ Pr(\{\char"2681, \char"2683, \char"2685\}) = Pr(\{\char"2681\}) + Pr(\{\char"2683, \char"2685\}) = \frac{1}{6} + Pr(\{\char"2683\}) + Pr(\{\char"2685\})
公理的確率のうれしさ: 134
標本空間と確率分布を用意するだけで確率を定義できる
歪んだサイコロや縁で立つコインの確率を扱える
第5章「期待値」
すべての目がでるまでの期待値: 170
第6章「とらえがたい未来」
アルゴリズムの実行ステップ数$ T(n) について、入力サイズ$ n が大きくなったときに、スピードがどの程度遅くなるか
$ T(n) = O(n)
ある自然数$ \Bbb{N} と正の数$ C が存在して、$ N 以上のすべての整数$ n について:
$ |T(n)| \leq Cn
$ T(n) の大きさが$ n の定数倍で抑えられる
与える配列は昇順にソートされている
除法に対する床関数は切り捨て除算と同値？あんも.icon floor(Int, (head + tail) / 2)
(head + tail) ÷ 2
code:jl
function binary_search(A::Vector, v)
head = 1
tail = length(A)
while head <= tail
middle = floor(Int, (head + tail) / 2)
return println("見つかる")
head = middle + 1
else
tail = middle - 1
end
end
return println("見つからない")
end
binary_search(A, 77)
$ O(n^2)
2重whileループで$ \frac{n(n+1)}{2} 回程度の比較が行われる
code:jl
function bubble_sort(A::Vector, n::Int)
m = n
while m > 1
k = 1
while k < m
end
k += 1
end
m -= 1
end
return A
end
bubble_sort(A, 5)
与えられた数列のすべての順列を、比較木がもつことができるかを見る
比較木の高さ$ h で表せる順列: $ 2^h
比較階層$ h で表現できる順列
要素数$ n の数列のすべての順列: $ n!
$ 2^h \geq n! \iff h \geq \log_2{n!} であることを確認すればよい
$ \log_2{n!} を下から評価する
$ n=6 について:
$ 6! \geq 6\cdot 5\cdot 4 \geq 3\cdot 3\cdot 3\cdot = 3^3
$ \log{6!} \geq \log{3^3} \iff \log{6!} \geq 3\log{3}
$ \iff \log{6!} \geq \frac{6}{2}\log{\frac{6}{2}}
底を2にして、$ n\geq4 なら一般化できる:
$ \log_2{n!} \geq \frac{n}{2}\log_2{\frac{n}{2}}
$ n\geq4 のとき、$ \log_2{\frac{n}{2}} \geq \frac{1}{2}\log_2{n} であるので:
$ \log_2{n!} \geq \frac{1}{4}n\log_2{n}
ここが$ n\geq4 にしたかった理由？あんも.icon
ゆえに$ \log_2{n!} = \Omega(n\log{n})
第7章「行列」
連立方程式が正則になる条件: 255
逆行列で連立方程式を解く: 267
code:tex
\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}
\begin{pmatrix}
x\\
y
\end{pmatrix}
=
\begin{pmatrix}
s\\
t
\end{pmatrix}
\iff
\begin{pmatrix}
x\\
y
\end{pmatrix}
=
\frac{1}{ad - bc}
\begin{pmatrix}
d & -b\\
-c & a
\end{pmatrix}
\begin{pmatrix}
s\\
t
\end{pmatrix}
行列式で表現する
code:tex
\begin{pmatrix}
x\\
y
\end{pmatrix}
=
\frac{1}{
\begin{vmatrix}
a & b\\
c & d
\end{vmatrix}
}
\begin{pmatrix}
\begin{vmatrix}
s & b\\
t & d
\end{vmatrix}\\
\\
\begin{vmatrix}
a & s\\
c & t
\end{vmatrix}
\end{pmatrix}
$ \begin{pmatrix} a & b\\ c & d \end{pmatrix}^{10} ？: 269
手で実験するとおもしろい
線形変換: 275
第8章「ひとりぼっちのランダムウォーク」
トレースと行列式
第9章「強く、正しく、美しく」
第10章「乱択アルゴリズム」