Introduction to Algorithms 3rd Editionを読むスレ

Introduction to Algorithms 3rd Editionを読むスレ at TECH

3:デフォルトの名無しさん
17/09/14 20:21:41.61 VdbIWmI2.net
まずは、
問題解答のページ
URLﾘﾝｸ(sites.math.rutgers.edu)

4:デフォルトの名無しさん
17/09/14 20:57:43.48 VdbIWmI2.net
Excercise 11.1-4が分からないので、
解説をお願いします。

5:デフォルトの名無しさん
17/09/15 06:34:18.86 eHlGtulJ.net
>>3
の
Excercise 11.1-4の解答ですが、こういうのはありんですか？

6:デフォルトの名無しさん
17/09/15 13:06:31.11 M6zHVajf.net
ッアー

7:デフォルトの名無しさん
17/09/15 14:55:33.38 StEXdinN.net
どこがわからないのかがわからんのだけど、
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を具体的に示さないといかんのだけど、
簡単だし、たぶん上の解答にかいてあると思う

8:デフォルトの名無しさん
17/09/15 15:01:53.76 AShrr3bB.net
クオータニオンか

9:デフォルトの名無しさん
17/09/15 15:17:15.95 Xh3vGrxx.net
>>7
これってHash TableやTrieを使ったDictionaryに比べて何がうれしいの？

10:デフォルトの名無しさん
17/09/15 15:40:26.21 StEXdinN.net
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は問題を限定しすぎになります

11:デフォルトの名無しさん
17/09/15 18:49:15.88 eHlGtulJ.net
>>3
のExcercise 11.1-4の解答のやり方だと、偶然、ハッシュのスロットが空なのに、空じゃないと
判定されてしまう可能性がないですか？

12:デフォルトの名無しさん
17/09/15 19:55:25.26 eHlGtulJ.net
11章のハッシュ関数のところで、
CHAINED-HASH-DELETE(T, x)
という関数がありますが、なぜ
CHAINED-HASH-DELETE(T, k)
じゃないんですか？

13:デフォルトの名無しさん
17/09/15 20:03:32.59 eHlGtulJ.net
キーって何ですか？イメージがわきません。

14:デフォルトの名無しさん
17/09/17 17:10:20.73 7slIJ8sy.net
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 であるという。

15:デフォルトの名無しさん
17/09/17 17:31:03.46 7slIJ8sy.net
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

16:デフォルトの名無しさん
17/09/17 17:34:31.44 7slIJ8sy.net
この証明は、
u ∈ S であるとき、破綻しますよね。

17:デフォルトの名無しさん
17/09/17 17:38:50.10 7slIJ8sy.net
Kleinbergはネヴァンリンナ賞を受賞した人だそうですが、大丈夫な人なのでしょうか？

18:デフォルトの名無しさん
17/09/17 19:04:02.49 rjQ9hI/o.net
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

19:デフォルトの名無しさん
17/09/19 16:51:25.50 VId0++Wx.net
定理11.1で、
Θ(1 + α)
を n に関して 0 次の項である 1 を消去して、
Θ(α)
と書かないのはなぜですか？
α = n/m です。

20:デフォルトの名無しさん
17/09/19 21:26:27.98 IqRhss0M.net
証明内や、定理の直前のパラグラフに書いてあるとおり

21:デフォルトの名無しさん
17/09/19 21:52:07.71 VId0++Wx.net
>>20
どういうことですか？

22:デフォルトの名無しさん
17/10/09 18:38:33.45 vbK8I5kP.net
浅野孝夫著『アルゴリズムの基礎とデータ構造』を読んでいます。
「上の挿入ソートの例のように、基本演算回数（比較回数）は入力サイズ n にのみ
依存するとは言えない。そこで、入力サイズ n の入力のうちでアルゴリズムが最も
多くの基本演算を必要とする入力を考えて、それに対する基本演算回数を、本書ではん、
サイズ n の入力に対するアルゴリズムの計算量（time complexity of an algorithm）と
呼ぶ。すなわち、最悪の場合を想定してアルゴリズムの計算量を定めていることになる。
このようにして定められたアルゴリズムの計算量 T はもちろん n にのみ依存する関数で
あるので T(n) と書ける。上の挿入ソートの例では T(n) = n*(n-1)/2 である。」
と書いてあります。
その後、マージソートのところには、
「マージソートの計算量は T(n) = O(n*log(n)) である」
と書いてあります。
T(n) は最悪の場合の計算量ですから、
T(n) = Θ(n*log(n)) が正しいのではないでしょうか？
ちなみに、浅野さんは、この本の最初のほうで O, Ω, Θ を定義しています。
もちろん、 f(n) ∈ Θ(n*log(n)) ⇒ f(n) ∈ O(n*log(n)) ですが。

23:デフォルトの名無しさん
17/10/11 13:39:39.42 rDStqhBV.net
こちらへどうぞ
ｽﾚﾘﾝｸ(tech板)