Introduction to Algorithms 3rd Editionを読むスレ [無断転載禁止]©2ch.net

**デフォルトの名無しさん** · 2017/09/14(木) 20:06:11.31

Introduction to Algorithms 3rd Editionを読むスレ

**デフォルトの名無しさん** · 2017/09/14(木) 20:19:35.01

よし始めてくれ

**デフォルトの名無しさん** · 2017/09/14(木) 20:21:41.61

まずは、

問題解答のページ

http://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html

**デフォルトの名無しさん** · 2017/09/14(木) 20:57:43.48

Excercise 11.1-4が分からないので、
解説をお願いします。

**デフォルトの名無しさん** · 2017/09/15(金) 06:34:18.86

>>3

の

Excercise 11.1-4の解答ですが、こういうのはありんですか？

**デフォルトの名無しさん** · 2017/09/15(金) 13:06:31.11

ッアー

**デフォルトの名無しさん** · 2017/09/15(金) 14:55:33.38

どこがわからないのかがわからんのだけど、
1. doubly linked listを使ってるところなら、これはまったく本質とは関係なくて、
stackとして使うlistっぽいものを2つ用意すればいいだけ
key用とobject用

2. 問題は、huge array Hを元に、(small stack Sを補助として)小さなdictionaryを作れ
ということなので、イメージとしては、H: 英語辞典から、たとえば、
a-zのエントリのみの辞書をつくって、「他のキーに対してはNILを返す」ようにしてください
ということ
HのキーkとSのキーjに対して、S[H[k]]=kとH[S[j]=H[S[j]]=jが成立するようにSを作っていけばいいだけ
Sはキーの管理しかしてないので、同サイズのS'も作ってobjectの管理をすればよろし
これで問題ないことは、init, search, insert, deleteを具体的に示さないといかんのだけど、
簡単だし、たぶん上の解答にかいてあると思う

**デフォルトの名無しさん** · 2017/09/15(金) 15:01:53.76

クオータニオンか

**デフォルトの名無しさん** · 2017/09/15(金) 15:17:15.95

>>7
これってHash TableやTrieを使ったDictionaryに比べて何がうれしいの？

**デフォルトの名無しさん** · 2017/09/15(金) 15:40:26.21

Chap 11. Hash Tables
Sect 1. Direct-address tables
Sect 2. Hash tables
Sect 3. Hash functions
...
という流れのSection 1だから、基本的にHash tableへの前フリ
当然、keyが小さいならHash tableいらなくて、direct-address tablesで
十分ということもふれてあります
Trieについては、上で出した例以外だとあまり関係ないですね
書籍では、もう少し抽象的な扱いなんですが、本質的には簡単な話だということを示す
ために上の例を出しました
なので、Trieは問題を限定しすぎになります

**デフォルトの名無しさん** · 2017/09/15(金) 18:49:15.88

>>3

のExcercise 11.1-4の解答のやり方だと、偶然、ハッシュのスロットが空なのに、空じゃないと
判定されてしまう可能性がないですか？

**デフォルトの名無しさん** · 2017/09/15(金) 19:55:25.26

11章のハッシュ関数のところで、

CHAINED-HASH-DELETE(T, x)

という関数がありますが、なぜ

CHAINED-HASH-DELETE(T, k)

じゃないんですか？

**デフォルトの名無しさん** · 2017/09/15(金) 20:03:32.59

キーって何ですか？イメージがわきません。

**デフォルトの名無しさん** · 2017/09/17(日) 17:10:20.73

Kleinberg & Tardosの本に以下のような内容の記述があります。
でも、 n > 1 のとき、 H が universal になることは決してないですよね。
u = v のとき、常に、 h(u) = h(v) なので、問題の確率は 1 ですから。

--------------------------------------------------
U を要素数の非常に多い有限集合とする。

H を U から {0, 1, ..., n-1} へのすべての写像の集合のある部分集合とする。

u, v ∈ U に対して、ランダムに選んだ h ∈ H が h(u) = h(v) を満たす確率はたかだか 1/n であるとき、
H は universal であるという。

**デフォルトの名無しさん** · 2017/09/17(日) 17:31:03.46

S を #S ≦ n であるような任意の U の部分集合とする。
u を U の任意の要素とする。
X をランダムな選択 h ∈ H に対して、値 #{s ∈ S | h(s) = h(u)} をとるようなランダム変数とする。

このとき、

E[X] ≦ 1

である。

証明：

s ∈ S に対し、
h(s) = h(u) であるならば、 1
h(s) ≠ h(u) であるならば、 0
となるようなランダム変数を X_s とする。

仮定により、 H は universal であるから、
E[X_s] = Pr[Xs = 1] ≦ 1/n

X = Σ X_s だから期待値の線形性により、

E[X] = ΣE[X_s] ≦ #S * (1/n) ≦ 1

**デフォルトの名無しさん** · 2017/09/17(日) 17:34:31.44

この証明は、

u ∈ S であるとき、破綻しますよね。

**デフォルトの名無しさん** · 2017/09/17(日) 17:38:50.10

Kleinbergはネヴァンリンナ賞を受賞した人だそうですが、大丈夫な人なのでしょうか？

**デフォルトの名無しさん** · 2017/09/17(日) 19:04:02.49

Algorithm Designのchap 13のことなら、p.738の(13.22)を導く大前提として、p.736に
distinct elements u, vとかいてあるんだけどね
(13.22)を受けてのuniversalのカジュアルな定義をかいてるだけ

後者については、
let u be any element in U
を
let u be any element in U\S
に読み替えればいいし、これで他の議論になんの影響もないでしょ
どちらも問題の意味理解していればわかる瑣末なこと

formalな定義と議論を知りたいなら
Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis,2ed By Michael Mitzenmacher, Eli Upfal, Cambridge Univ,2017

**デフォルトの名無しさん** · 2017/09/19(火) 16:51:25.50

定理11.1で、

Θ(1 + α)

を n に関して 0 次の項である 1 を消去して、

Θ(α)

と書かないのはなぜですか？

α = n/m です。

**デフォルトの名無しさん** · 2017/09/19(火) 21:26:27.98

証明内や、定理の直前のパラグラフに書いてあるとおり