https://orsj-ml.org/orwiki/wiki/index.php?action=history&feed=atom&title=%E3%83%A9%E3%83%B3%E3%83%80%E3%83%9E%E3%82%A4%E3%82%BC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3
ランダマイゼーション - 版の履歴
2026-06-22T19:25:27Z
このウィキのこのページに関する変更履歴
MediaWiki 1.35.3
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%A9%E3%83%B3%E3%83%80%E3%83%9E%E3%82%A4%E3%82%BC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3&diff=9705&oldid=prev
Imahori: 基礎編と用語編のマージ
2008-03-23T08:39:42Z
<p>基礎編と用語編のマージ</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年3月23日 (日) 08:39時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【らんだまいぜーしょん (randomization)】'''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【らんだまいぜーしょん (randomization)】'''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">=== 概要 ===</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>ランダマイゼーションは, アルゴリズムの中にランダムな要素を導入し, それにより最悪の場合にとらわれない簡単で実際に速いアルゴリズムを構成しようという手法である. ランダマイゼーションすることによって得られるアルゴリズムをランダム化アルゴリズムと呼ぶ. ランダマイゼーションは, アルゴリズムに対する入力に確率分布を仮定して計算時間を平均的に評価するとかいうのではない. 代表的な手法に, ランダム抽出法, ランダム順添加法などがある.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>ランダマイゼーションは, アルゴリズムの中にランダムな要素を導入し, それにより最悪の場合にとらわれない簡単で実際に速いアルゴリズムを構成しようという手法である. ランダマイゼーションすることによって得られるアルゴリズムをランダム化アルゴリズムと呼ぶ. ランダマイゼーションは, アルゴリズムに対する入力に確率分布を仮定して計算時間を平均的に評価するとかいうのではない. 代表的な手法に, ランダム抽出法, ランダム順添加法などがある.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">詳しくは</del>[[<del class="diffchange diffchange-inline">《ランダマイゼーション》</del>|<del class="diffchange diffchange-inline">基礎編：ランダマイゼーション</del>]]<del class="diffchange diffchange-inline">を参照</del>.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">=== 詳説 ===</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> ランダマイゼーション(randomization)は, アルゴリズムの中にランダムな要素を導入し, それにより最悪の場合にとらわれない簡単で実際に速いアルゴリズムを構成しようという手法である. ランダマイザーションすることによって得られるアルゴリズムをランダム化アルゴリズムとよぶ. メタヒューリスティックスのシミュレーティッド・アニーリングから素数判定のランダム化数論アルゴリズムまで幅広く用いられている. ランダマイゼーションは, アルゴリズムに対する入力になんらかの確率分布を仮定して計算時間を平均的に評価するとかいうのではない. 教科書も既にあり, </ins>[<ins class="diffchange diffchange-inline">2] は全般的なアルゴリズムについて, </ins>[<ins class="diffchange diffchange-inline">3] は計算幾何のアルゴリズムについて詳しい. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 本項では, 計算幾何の問題に対するランダマイゼーションの代表的手法についてまとめる. 代表的手法としては次の2つのものがあり, 以下その説明をする. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''ランダム抽出(random sampling)''' ランダムに選ぶことにより全体を反映した部分集合を定め, その抽出した部分集合の情報をフルに活用するもの</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''ランダム順添加法(randomized incremental method)''' アルゴリズムの構成のもっとも簡単なパラダイムである逐次添加法において, 添加順をランダム化する方法で, 添加法の実用性を示すものでもある. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''(a) ランダム抽出''' ランダム抽出法の目指すところは, 部分で全体を表すということである. そうできると, 部分を計算するだけで情報がある程度得られるという計算量の観点からの利点がある. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 代表的な例で, 平面上の<math>n\, </math>個の点の集合<math>S\, </math>の<math>\epsilon\, </math>-近似<math>T\, </math>を考える. 任意の<math>\epsilon\ge0\, </math>に対して, <math>S\, </math>の部分集合<math>T\, </math>が<math>\epsilon\, </math>近似である}とは, 任意の半平面<math>h\, </math>に対して次式が成り立つことをいう. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><math>\left</ins>| <ins class="diffchange diffchange-inline">{|S\cap h|\over|S|}-{|T\cap h|\over |T|}\right|</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">\le\epsilon\, </math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"></center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 任意の<math>\epsilon\, </math>に対して, <math>T=S\, </math>とすればそれは<math>\epsilon\, </math>近似になっているから, このような<math>\epsilon\, </math>近似の存在は保証されるので, <math>T\, </math>のサイズをどこまで小さくできるかがポイントである. ランダム抽出の理論を適用すると, 次の定理が成り立つ( [1] 参照). </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''定理.''' 任意の<math>\epsilon,\ \delta>0\, </math>に対して, 点集合<math>S\, </math>から少なくとも</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"><math>m\ge{16\over\epsilon^2}\left(3\ln{48\over\epsilon^2}+\ln{4\over\delta}\right)\, </math></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"></center></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">なる<math>m\, </math>点をランダムかつ独立に選んで得られる集合<math>T\, </math>は, 少なくとも<math>1-\delta\, </math>の確率で<math>S\, </math>の<math>\epsilon\, </math>-近似である. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> この定理より, 任意の<math>\epsilon>0\, </math>に対して, <math>\delta\, </math>を1に近付けても, ある確率で<math>\epsilon\, </math>近似が単純なサンプリングで求められということがわかる. 確率が正ならその事象が存在するので, ほぼ定理のサイズの<math>\epsilon\, </math>-近似の存在定理も導かれる. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> このように<math>\epsilon\, </math>-近似は全体の点数に関係のない点数の部分集合で, 半平面に含まれる点数に関する近似を与えており, 部分によって全体を表現できている. このようなランダム抽出に関する定理は, アルゴリズム構成面で自然と分割統治に使えて有用である. さらに理論の観点からは, 各ニューロンが単純な線形しきい値関数である場合のニューラルネットでの学習能力と関係している. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''(b) ランダム順添加法''' ランダム順添加法も有用な方法である. これは, アルゴリズム設計のパラダイムの1つである逐次添加法 (incremental method)をもとにするものである. 従来の逐次添加法は, <math>n\, </math>要素の問題を解くときに, 最初は定数個(例えば2,3)の要素の部分問題に対する解から始めて, <math>i\, </math>個の要素の部分問題の解があるとき, <math>i+1\, </math>番目の要素をそこに加えて<math>i+1\, </math>個の要素の部分問題に対する解をつくり, これを<math>n\, </math>個全体に対する解が得られるまで繰り返す方法である. このとき, <math>i\, </math>個の要素の部分問題に対する解がわかっていれば, 通常それに1個加えた<math>i+1\, </math>個の部分問題に対する解は, ゼロからその<math>i+1\, </math>個の問題を解くのに比べて, はるかに効率よく求めることができるということが, 高速アルゴリズムを得るために役立つ. たとえば, 挿入ソートなどは, この典型例である. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> ランダム順添加法では, ランダマイゼーションにより要素をランダム順に並べ, その順に逐次添加を行なっていく. それによって, 最悪の場合を考えたとき, 単に与えられた順で添加していくと, たいてい逐次添加法にとっては都合の悪い順番が存在し, その場合の計算量が最悪計算時間となってしまうことが多いのに対し, ランダマイゼーションによってそれを避けることができる. これは, 入力になんらかの分布を仮定して平均計算時間を評価するのと近く, ただ複雑な問題では入力の分布として妥当なものを考えることが難しいので, 作為的な入力分布を仮定するより, アルゴリズムの中でランダマイゼーションした方がより汎用的な成果が得られる. また, ランダマイゼーションアルゴリズムといっても, もし, 入力の分布に関して, そう悪い例が出てこなさそうであれば, 実際には単に与えられた順で添加をしていけばよいのである. このランダム順添加法は, 低次元線形計画や凸包構成など幅広く適用されている. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">----</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''参考文献'''</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[1] 今井浩, 今井桂子, 『計算幾何学』, 共立出版, 1994.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[2</ins>] <ins class="diffchange diffchange-inline">R. Motwani and P. Raghavan, ''Randomized Algorithms,'' Cambridge University Press, 1995.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[3</ins>] <ins class="diffchange diffchange-inline">K. Mulmuley, ''Computational Geometry: An Introduction Through Randomized Algorithms,'' Prentice-Hall, 1994</ins>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[[Category:計算幾何|らんだまいぜーしょん]]</ins></div></td></tr>
</table>
Imahori
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%A9%E3%83%B3%E3%83%80%E3%83%9E%E3%82%A4%E3%82%BC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3&diff=8352&oldid=prev
2007年8月8日 (水) 12:17にKanda.kによる
2007-08-08T12:17:02Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年8月8日 (水) 12:17時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >2行目:</td>
<td colspan="2" class="diff-lineno">2行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>ランダマイゼーションは, アルゴリズムの中にランダムな要素を導入し, それにより最悪の場合にとらわれない簡単で実際に速いアルゴリズムを構成しようという手法である. ランダマイゼーションすることによって得られるアルゴリズムをランダム化アルゴリズムと呼ぶ. ランダマイゼーションは, アルゴリズムに対する入力に確率分布を仮定して計算時間を平均的に評価するとかいうのではない. 代表的な手法に, ランダム抽出法, ランダム順添加法などがある.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>ランダマイゼーションは, アルゴリズムの中にランダムな要素を導入し, それにより最悪の場合にとらわれない簡単で実際に速いアルゴリズムを構成しようという手法である. ランダマイゼーションすることによって得られるアルゴリズムをランダム化アルゴリズムと呼ぶ. ランダマイゼーションは, アルゴリズムに対する入力に確率分布を仮定して計算時間を平均的に評価するとかいうのではない. 代表的な手法に, ランダム抽出法, ランダム順添加法などがある.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">詳しくは[[《ランダマイゼーション》|基礎編：ランダマイゼーション]]を参照.</ins></div></td></tr>
</table>
Kanda.k
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%A9%E3%83%B3%E3%83%80%E3%83%9E%E3%82%A4%E3%82%BC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3&diff=6617&oldid=prev
Orsjwiki: "ランダマイゼーション" を保護しました。 [edit=sysop:move=sysop]
2007-07-20T01:13:30Z
<p>"ランダマイゼーション" を保護しました。 [edit=sysop:move=sysop]</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<tr class="diff-title" lang="ja">
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">2007年7月20日 (金) 01:13時点における版</td>
</tr><tr><td colspan="2" class="diff-notice" lang="ja"><div class="mw-diff-empty">(相違点なし)</div>
</td></tr></table>
Orsjwiki
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%A9%E3%83%B3%E3%83%80%E3%83%9E%E3%82%A4%E3%82%BC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3&diff=2249&oldid=prev
122.17.2.240: 新しいページ: ''''【らんだまいぜーしょん (randomization)】''' ランダマイゼーションは, アルゴリズムの中にランダムな要素を導入し, それにより最...'
2007-07-09T13:10:05Z
<p>新しいページ: ''''【らんだまいぜーしょん (randomization)】''' ランダマイゼーションは, アルゴリズムの中にランダムな要素を導入し, それにより最...'</p>
<p><b>新規ページ</b></p><div>'''【らんだまいぜーしょん (randomization)】'''<br />
<br />
ランダマイゼーションは, アルゴリズムの中にランダムな要素を導入し, それにより最悪の場合にとらわれない簡単で実際に速いアルゴリズムを構成しようという手法である. ランダマイゼーションすることによって得られるアルゴリズムをランダム化アルゴリズムと呼ぶ. ランダマイゼーションは, アルゴリズムに対する入力に確率分布を仮定して計算時間を平均的に評価するとかいうのではない. 代表的な手法に, ランダム抽出法, ランダム順添加法などがある.</div>
122.17.2.240