アルゴリズムの導論の第5章の総括
2362 ワード
応募者をランダムに並べるステップがあれば、ランダムアルゴリズム(random algorithm)、いいえ、確率分析(probability analysis)です.
ランダム配列を実現する2つのアルゴリズム:PREMUTE-BY-Sorting(A)とRANDOM-IN-PLACE.
PREMUTE-BY-Sortingアルゴリズムは、優先度を測定するために、応募者ごとに乱数シーケンスを生成するものとみなされます.生成された乱数シーケンスが重複しない確率は(1−1/n)以上であるが、任意に重複する可能性がある.RANDOM-IN-PLACEではこのような問題はありません.
The birthday paradox:
確率で導くには,1+x<=e^xという不等式の役割に注意する.
確率をランダム変数で計算する場合,数学的期待E[X]=k(k−1)/2 nを最後に算出して1以上とすればよい.
不等式k(k−1)>=2 nを解く場合,ルート式を用いてk=28を算出することができる.
Balls and bins:
5つの箱があり,試験回数は幾何学的分布に合致した.
成功確率(a hit)k回目の試験方が成功する確率が期待されるまで
1. 1 1 1
2. 4/5 (1/5)^(k-1)*(4/5) 5/4
3. 3/5 (2/5)^(k-1)*(3/5) 5/3
4. 2/5 (3/5)^(k-1)*(2/5) 5/2
5. 1/5 (4/5)^(k-1)*(1/5) 5
幾何学的分布の特徴から算出できることが望ましい:E[X]=1/p
Streaks:見終わっていません.
Online hiring:
応募者を4つのセグメントに分けて考えることができます.
A[1..k],A[k+1..i-1],A[i],A[i+1..n]
best-qualifiedアプリケーションが最初の配列にある場合、私たちは彼に応募する確率が0なので、
Pr{S}= .
本の上でBとOは関係がないと言って、あまり分かりません.このように考えると、Pr{Oi}=k/(i-1)、Pr{Bi}=1/n、Pr{Si}=Pr{Oi}*Pr{Bi}=k/(n*(i-1))となり、Pr{S}を再計算すればよい.ここでA.12式を使います.この式はFigure A.1を見て、筆算をすれば証明できます.最終的に
k/n(lnn-lnk)<=Pr{S}<=k/n(ln(n-1)-ln(k-1))を求め、1/n(lnn-lnk-1)、1/n(lnn-lnk-1)=0のときの関数は極大値、すなわちlnk=lnn-1=ln(n/e)、k=n/3のとき、best-qualifiedへの応募に成功する確率が最大であり、最大確率は1/e未満ではない.
ランダム配列を実現する2つのアルゴリズム:PREMUTE-BY-Sorting(A)とRANDOM-IN-PLACE.
PREMUTE-BY-Sortingアルゴリズムは、優先度を測定するために、応募者ごとに乱数シーケンスを生成するものとみなされます.生成された乱数シーケンスが重複しない確率は(1−1/n)以上であるが、任意に重複する可能性がある.RANDOM-IN-PLACEではこのような問題はありません.
The birthday paradox:
確率で導くには,1+x<=e^xという不等式の役割に注意する.
確率をランダム変数で計算する場合,数学的期待E[X]=k(k−1)/2 nを最後に算出して1以上とすればよい.
不等式k(k−1)>=2 nを解く場合,ルート式を用いてk=28を算出することができる.
Balls and bins:
5つの箱があり,試験回数は幾何学的分布に合致した.
成功確率(a hit)k回目の試験方が成功する確率が期待されるまで
1. 1 1 1
2. 4/5 (1/5)^(k-1)*(4/5) 5/4
3. 3/5 (2/5)^(k-1)*(3/5) 5/3
4. 2/5 (3/5)^(k-1)*(2/5) 5/2
5. 1/5 (4/5)^(k-1)*(1/5) 5
幾何学的分布の特徴から算出できることが望ましい:E[X]=1/p
Streaks:見終わっていません.
Online hiring:
ON-LINE-MAXIMUM(k, n)1 bestscore ← -∞2 for i ← to k3 do if score(i) > bestscore4 then bestscore ← score(i)5 for i ← k + 1 to n6 do if score(i) > bestscore7 then return i8 return n 応募者を4つのセグメントに分けて考えることができます.
A[1..k],A[k+1..i-1],A[i],A[i+1..n]
best-qualifiedアプリケーションが最初の配列にある場合、私たちは彼に応募する確率が0なので、
Pr{S}= .
本の上でBとOは関係がないと言って、あまり分かりません.このように考えると、Pr{Oi}=k/(i-1)、Pr{Bi}=1/n、Pr{Si}=Pr{Oi}*Pr{Bi}=k/(n*(i-1))となり、Pr{S}を再計算すればよい.ここでA.12式を使います.この式はFigure A.1を見て、筆算をすれば証明できます.最終的に
k/n(lnn-lnk)<=Pr{S}<=k/n(ln(n-1)-ln(k-1))を求め、1/n(lnn-lnk-1)、1/n(lnn-lnk-1)=0のときの関数は極大値、すなわちlnk=lnn-1=ln(n/e)、k=n/3のとき、best-qualifiedへの応募に成功する確率が最大であり、最大確率は1/e未満ではない.