X



Introduction to Algorithms 3rd Editionを読むスレ [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん2017/09/14(木) 20:06:11.31ID:VdbIWmI2
Introduction to Algorithms 3rd Editionを読むスレ
0003デフォルトの名無しさん2017/09/14(木) 20:21:41.61ID:VdbIWmI2
まずは、

問題解答のページ

http://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html
0004デフォルトの名無しさん2017/09/14(木) 20:57:43.48ID:VdbIWmI2
Excercise 11.1-4が分からないので、
解説をお願いします。
0005デフォルトの名無しさん2017/09/15(金) 06:34:18.86ID:eHlGtulJ
>>3



Excercise 11.1-4の解答ですが、こういうのはありんですか?
0007デフォルトの名無しさん2017/09/15(金) 14:55:33.38ID:StEXdinN
どこがわからないのかがわからんのだけど、
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を具体的に示さないといかんのだけど、
簡単だし、たぶん上の解答にかいてあると思う
0010デフォルトの名無しさん2017/09/15(金) 15:40:26.21ID:StEXdinN
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は問題を限定しすぎになります
0011デフォルトの名無しさん2017/09/15(金) 18:49:15.88ID:eHlGtulJ
>>3

のExcercise 11.1-4の解答のやり方だと、偶然、ハッシュのスロットが空なのに、空じゃないと
判定されてしまう可能性がないですか?
0012デフォルトの名無しさん2017/09/15(金) 19:55:25.26ID:eHlGtulJ
11章のハッシュ関数のところで、

CHAINED-HASH-DELETE(T, x)

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

CHAINED-HASH-DELETE(T, k)

じゃないんですか?
0013デフォルトの名無しさん2017/09/15(金) 20:03:32.59ID:eHlGtulJ
キーって何ですか?イメージがわきません。
0014デフォルトの名無しさん2017/09/17(日) 17:10:20.73ID:7slIJ8sy
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 であるという。
0015デフォルトの名無しさん2017/09/17(日) 17:31:03.46ID:7slIJ8sy
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
0016デフォルトの名無しさん2017/09/17(日) 17:34:31.44ID:7slIJ8sy
この証明は、

u ∈ S であるとき、破綻しますよね。
0017デフォルトの名無しさん2017/09/17(日) 17:38:50.10ID:7slIJ8sy
Kleinbergはネヴァンリンナ賞を受賞した人だそうですが、大丈夫な人なのでしょうか?
0018デフォルトの名無しさん2017/09/17(日) 19:04:02.49ID:rjQ9hI/o
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
0019デフォルトの名無しさん2017/09/19(火) 16:51:25.50ID:VId0++Wx
定理11.1で、

Θ(1 + α)

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

Θ(α)

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

α = n/m です。
0020デフォルトの名無しさん2017/09/19(火) 21:26:27.98ID:IqRhss0M
証明内や、定理の直前のパラグラフに書いてあるとおり
0021デフォルトの名無しさん2017/09/19(火) 21:52:07.71ID:VId0++Wx
>>20

どういうことですか?
0022デフォルトの名無しさん2017/10/09(月) 18:38:33.45ID:vbK8I5kP
浅野孝夫著『アルゴリズムの基礎とデータ構造』を読んでいます。

「上の挿入ソートの例のように、基本演算回数(比較回数)は入力サイズ 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)) ですが。
0024デフォルトの名無しさん2018/05/23(水) 21:35:13.59ID:Au5e7VGg
僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法 モニアレフヌノ』

SZ9P6
0025デフォルトの名無しさん2018/07/05(木) 00:24:18.40ID:RfoszcD2
OTQ
■ このスレッドは過去ログ倉庫に格納されています

ニューススポーツなんでも実況