CLRS Chapter5 - 壊れた計算機

アルゴリズムイントロダクション/Introduction to Algorithms

Exercise 5.1-1

遷移律が満たされないとすると、a < b, b < c , c < aとなるa,b,cが取れる。このとき、a,b,cの出現順によって採用する人が変わるので矛盾。
反対称律と反射律は問題からして自明
全員比較される可能性があるので完全律もOK

Exercise 5.1-2

lg(ceil(a-b))の長さの二進符号を作りa-bに対応させる。Random(0,1)の結果を見ていって、a-bに当てはまらない符号があったらもういっかい籤をひく。
$\frac{m2^m}{(b-a)} \;(m=\lg \lceil b - a \rceil)$

Exercise 5.1-3

def unbiased ()
   a <- biased()
   b <- biased()
   if a == 1 and b == 0
      return 1
   else if a == 0 and b == 1
      return 0
   else
      return unbiased()

Exercise 5.2-1

1/n
1/n!

Exercise 5.2-3

(7/2)n

Exercise 5.2-4

Exercise 5.2-5

n(n-1)/4

Exercise 5.3-1

0だけ特別視

Exercise 5.3-2

No.
1,2,3
から
1,3,2
みたいな配列が作り出せない。

Exercise 5.3-3

No.
乱数の出方はn^n通りあるが、順列はn!通りである。
n^nはn!の倍数ではないことがある(n=3など)ので、このアルゴリズムでn!通りが一様に出てくることはない。

Exercise 5.3-4

証明略
n通りしか出てこないので間違いだ

Exercise 5.3-5

(1-1/n^3)(1 - 2/n^3)...を近似をつかって評価する

Exercise 5.3-6

同じものが出たら最初からやり直す。

Exercise 5.3-7

帰納法で簡単に示せる

Exercise 5.4-1

250人くらい
650人くらい

Exercise 5.4-2

解いていない。状態遷移図をかけば解けそう

Exercise 5.4-3

考えていない

Exercise 5.4-4

40人くらい

Exercise 5.4-5

nPk/n^k
分母が5.4-4などの場合
分子が5.4-1などの場合
大きさが直感に反して違うのでパーティーのパラドックスが生じる

Exercise 5.4-6 5.4-7

解いていない

Problem 5-1

a

1回のIncrementで期待値が1上がることを確認した。

b

解いていない

Problem 5-2

a

略

b c d

T = n/k (k >= 1) , n lg(n) (k = 0)

e f g

averageは、n/(k+1) (k >= 1), n (k = 0)
worstはn

h

expected : n/(k+1)
worst : n

i

SCRAMBLE-SEARCHを選ぶ。
RANDOM-SEARCHは期待計算量が多すぎる
DETERMINISTRIC-SEARCHの平均計算量と、SCRAMBLE-SEARCHの期待計算量は同じだが、SCRAMBLE-SEARCHの方は計算量の分散が確定するので安心できる。