計算アルゴリズム【�U】

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 730 名前：デフォルトの名無しさん [2008/10/22(水) 23:39:21 ] ax+by=1を満たす整数x,yが存在する d.hatena.ne.jp/gould2007/20071009 731 名前：デフォルトの名無しさん [2008/10/22(水) 23:41:50 ] そしたら連続する3つ作れればそれ以降、全てつくれるってことだな 732 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 00:01:14 ] その日のうちに答がもらえるとは思わなかった とりあえず列挙できることが分かったので、個数の組はあらかじめ計算して持つようにしよう というか>>729の通り5を足せばいいんじゃん、気づかなかった ありがとうございました 733 名前：デフォルトの名無しさん mailto:sage [2008/10/23(木) 00:50:53 ] どうもおかしいと思った。 ＞最初の5つはこんな感じ 6つあったのねw 734 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:09:36 ] A Small and Fast IP Forwarding Table Using Hashing. これ何度みても計算できねぇ助けて 735 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 01:53:54 ] 一緒に考えてやるからその論文を見る方法を教えろ 736 名前：デフォルトの名無しさん mailto:sage [2008/10/25(土) 02:07:20 ] ttp://cial.csie.ncku.edu.tw/ppt/%5BY200X%5D%5BIEICE%20TRANS%5DA%20Small%20and%20Fast%20IP%20Forwarding%20Table%20Using%20Hashing.ppt ttp://cial.csie.ncku.edu.tw/pdf/%5BY200X%5D%5BIEICE%20TRANS%5DA%20Small%20and%20Fast%20IP%20Forwarding%20Table%20Using%20Hashing.pdf ぐぐった 合ってるかは知らん 737 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 11:10:39 ] >>736 それっすそれっす 738 名前：しろうと [2008/10/26(日) 16:22:55 ] 突然すみません。しろうとです。 バイナリーサーチの計算量はO(log n)ですが、その導き方について。 T(n)=O(1) n<=1 T(n)=T(n/2)+O(1) n>1 以上から、T(n)=T(n/2)+1=T(n/4)+2=T(n/8)+3...=T(n/2^k)+k。 ここまではわかるんだが、解説によると(n/2^k)=1とおいて、T(n)=log n+1 したがってT(n)=O(log n)となっている。なぜ、(n/2^k)=1とおくのでしょうか。 また、(n/2^k)=1をkについて解けばlog nにわかりますがlog n+1の1って何なんでしょうか？ 739 名前：デフォルトの名無しさん [2008/10/26(日) 18:18:41 ] アルゴリズムをよく考えてみ k=１のとき、つまり1回分割したときはn/2 k=2のとき、つまり2回分割したときはn/4 = n/2^2 k=3のとき、つまり3回分割したときはn/8 =n/2^3 といって、求めたいのは、つまりnをk回分割したときの計算量だから k=???のとき、つまりk回分割したときにn/2^k　→ ???を求める為には 数式頼みはよろしくないよ 740 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 18:49:12 ] >>738 ひどい導出だ．O(1) の扱いが雑すぎる． T(n) = O(1) (n <= 1) なんて意味不明すぎる記述． もし本当に本にこう書いてあるなら捨てたほうがいい． 741 名前：くまさん [2008/10/26(日) 18:59:21 ] プログラムの初心者です。 アルゴリズムの流れ図について、自然数ｍ、ｎに対して、 ｍのn乗を計算する効率の良いアルゴリズムのフローチャ ート書くという問題です。 どなたかご教授ください。 742 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 19:37:22 ] 流れ図の問題なんだな？そうなんだよな？ ではまず、効率の良いアルゴリズムを言ってくれ。 743 名前：くまさん [2008/10/26(日) 22:23:58 ] ヒントと書かれていたのはｎ＝64のときは乗算はの回数は6回で済む。 n＾２＊ｎ＾２＊ｎ＾２ これがヒントだそうです。 どうしたら、よろしいのでしょうか？ お願いします。 744 名前：くまさん [2008/10/26(日) 22:44:42 ] ｎの４乗はｎの２乗×ｎの２乗です。　ｎの８乗はｎの２乗×ｎの４乗ですから、展開するとｎの２乗×ｎの２乗×ｎの２乗です。 従い、ｎの６４乗はｎの２乗×ｎの３２乗ですから、ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗×ｎの２乗となります。 の2乗 これを利用して、ｍのｎ乗のアルゴリズムのフローチャートを書くみたいです。 745 名前：デフォルトの名無しさん [2008/10/26(日) 22:45:56 ] よくわからんな、何だろ ビット演算を絡ませたアセンブラ的な問題なのかな？ お前らどうする？これ放置していいん？ 746 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 22:53:29 ] 罠じゃねえの? 説明がデタラメだし。 747 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:18:56 ] >>744 ＞ｎの８乗はｎの２乗×ｎの４乗 ダウト。乗数は足し算です。 n^8 = n^(4+4) = n^4 * n^4 = (n * n * n * n) * (n * n * n * n) ね？ ＞ｎの６４乗はｎの２乗×ｎの３２乗 同様に、ｎの３２乗×ｎの３２乗がｎの６４乗で あえて言うなら（ｎの３２乗）の２乗がｎの６４乗 つまり >>745 問題のヒントが出鱈目だから放置していい。 748 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:20:45 ] >>736の問題助けてくれｗまじでｗ 749 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:27:51 ] 要するに>>736を分かりやすく翻訳してくれって言ってる？ サマリー読む限り、別に問題提起ってわけではなさそうだけど……？ 750 名前：デフォルトの名無しさん mailto:sage [2008/10/26(日) 23:35:16 ] >>749 4bitの集合を考え、具体例として以下で計算した場合 0000, 1100　0011, 0100, 0110, 0111, 1011, 0001. 1100まで計算した場合のV0とV1って V0: 0 0 0 0 V1: 4 3 1 1 になりますかね？ 751 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 00:12:25 ] ４ページのExample 1の話？ 752 名前：デフォルトの名無しさん mailto:sage [2008/10/27(月) 20:28:44 ] うん 753 名前：デフォルトの名無しさん [2008/10/28(火) 20:57:21 ] kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/7885.txt 上記は疑似コードで書かれていますが、アルゴリズム１もアルゴリズム２も 配列の中から最小値を探し出す処理をしているそうですが、アルゴリズム１の ０２行目では配列をどうやってtempにぶちこめるのでしょうか？ 配列Aが例えば {2, 6, 3, 7}だとすると、tempには最初に何が入るのですか？再帰なので、 A[1, 4]を呼び出そうとして、tempに値が入る前にA[1, 3]が呼び出され、やっぱり A[1, 2]が呼び出され、最終的にA[1, 1]になって、A[1]の２が返されて処理が 終了しそうな気がするのですが、間違っているところを教えて下さい。 754 名前：デフォルトの名無しさん mailto:sage [2008/10/28(火) 21:06:35 ] >>753 リンク先は見ていないが、再帰の仕組みを勉強しなおし給え。 要は、a[1]の結果が返されるのはa[1, 2]の呼び出しのtempへの代入なのだろ。 755 名前：デフォルトの名無しさん [2008/10/29(水) 00:57:04 ] 再帰の仕組みって勉強すればなんとかなるもんじゃないだろ 何と言うか、考え方がピンと来るか来ないか、脳みそにマッチするかしないかみたいなもんだ >>753 間違ってない、でも再帰の考え方をそうやって深部に潜ってく物だと考えるのは良くない 君の配列の書き方を使って書くと A[1,4]の最小値は・・・A[1,3]の最小値とA[4]の小さい方！ じゃあA[1,3]の最小値って何さ　→　同じやり方で済むじゃん みたいな考え方を適用すべき 756 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 01:01:16 ] LISP学んだり、フラクタル図形書いてみたり だまし絵とか見に行くといいんじゃないかな 757 名前：755 [2008/10/29(水) 01:09:03 ] >>753 おっと、質問に答えてなかったので答えます 最初にtempに入るのは、A[1,3]の最小値なので2です。 758 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:22:29 ] n個の要素から上位3つを選ぶアルゴリズムで速いのはなんですか？ ソートして先頭3つでやるのはなんかもったいない気がして・・・ 759 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:41:45 ] 端から舐めて上位3個を取り出す方法だろうなぁ 760 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:47:31 ] それだと比較回数3n？ 761 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:50:26 ] ヒープ 762 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 14:53:24 ] 20000個のデータで上位100なら、クイックソートとかしたほうが早いですかね？ 763 名前：デフォルトの名無しさん [2008/10/29(水) 15:30:41 ] >>757 ありがとうございました。 764 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 15:31:13 ] nth_element, partial_sort 765 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:05:02 ] >>762 上から k 個欲しかったらサイズ k のヒープを作って次々に突っ込むのがよい． 計算量は全データ数を n とすれば O(n log k)． k は高々 n なので，計算量はデータ数によらずソートするよりも良い． 実用的にはデータの分布に依存するので，実測しないと何とも． 766 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:16:37 ] >>765 全体ソートするのとオーダーかわらんじゃん 767 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:31:52 ] っ「選択アルゴリズム」 768 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:33:23 ] 選択アルゴリズムはk番目の値しか探せないぞ 769 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:38:05 ] >>768はまったくプログラミングの才能が無いな。 770 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:41:47 ] partial_sort使うのがいいんじゃない？ 771 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:43:47 ] >>770 それ、なんのこと言ってるの? C++前提なの? 772 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 18:50:02 ] 「部分ソート」と呟いておく。 773 名前：デフォルトの名無しさん [2008/10/29(水) 19:03:55 ] たとえば2万個から100個選ぶ場合、値の分布が0点-100点だとして 93点以上が100個程度であるとわかっていれば、93点以上を選べばいい。 774 名前：デフォルトの名無しさん [2008/10/29(水) 19:09:33 ] もしくは、一回目の探索で分布を調べて、100個選ぶにはいくつ以上かを特定する。 次のループでそれ以上を選ぶ。 775 名前：デフォルトの名無しさん mailto:sage [2008/10/29(水) 21:53:17 ] v[0]が4にならねーよ わからねー 776 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 06:19:01 ] >>766 全体ソートは　O(n log n) だから log の値が違う 777 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 13:30:13 ] Nは100〜10000程度で、double x[N]; に適当な数が入っているとします。 任意の数aに最も近いx[k]を知りたいとき、普通はO(N)の時間がかかりますが、 あらかじめx[]をソートしておけば二分法を使ってO(log N)でできます。 ここからが質問なのですが、2次元の座標としてx[N],y[N]があるときに、 任意の直線との距離が最も小さい(x[k],y[k])を知りたいとします。 （与えられたa,bに対してa*x[k]+b*y[k]-1.0 の値が最も小さくなるkが知りたいということ） このときに上の二分法のようなアルゴリズムはあるでしょうか？ 普通にやるとO(N)が必要ですが、O(N)より速い方法を探しています。 778 名前：デフォルトの名無しさん [2008/10/30(木) 13:54:09 ] ないな　O(N)で困る例はなんだよ 779 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 15:30:46 ] >>778 ないこと証明できる？ 困る例なんていくらでも思いつくでしょ。 まさか二分探索は不要だとか主張するつもり？ 780 名前：デフォルトの名無しさん [2008/10/30(木) 15:43:21 ] a,bの存在範囲毎に最小点を計算しておけば定数時間 781 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 16:07:07 ] >>777 i11www.iti.uni-karlsruhe.de/~awolff/pub/dmsw-fpqgc-06.pdf のイントロに書いてあるけど， [CY84]: 前処理 O(n^2)，問い合わせ O(log n) [LC85]: 前処理 O(n^2)，問い合わせ O(log n) [MC95]: 前処理 O(n log n)，問い合わせ O(n^0.695) [Mu03]: 前処理 O(n^1+ε)，問い合わせ O(n^{1/2 + ε}) くらいの結果はあるみたいね． 一通り目を通してみたけど，LC85 は特に簡単．双対変換すると 「直線 l に一番近い点 p」⇔「点 l* の真上にある直線 p*」 という関係になることに注意して，点位置決定問題に帰着するだけ． 782 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 17:50:08 ] >>781 あるんですね。双対変換を使うという発想はなかったです。嬉しいです。 この方法はイメージがついたので、これからちゃんと考えてみます。 追加ですみませんが、 他の方法について、やり方または論文をネット上で見られるものはありますか？ 783 名前：デフォルトの名無しさん [2008/10/30(木) 19:16:37 ] そもそも何に必要なんだよ? 784 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 19:34:27 ] >>782 私の大学からだとCY84以外は契約論文誌なので，Webから取れた． もし必要ならどっかにアップロードするよ． Mu03はciteseerからも取れたので，論文名で検索してみると良い． 785 名前：デフォルトの名無しさん [2008/10/30(木) 19:47:13 ] 前処理って言うのが、一回限りだったら logn < √nだから、はじめので十分では? 786 名前：デフォルトの名無しさん [2008/10/30(木) 19:50:29 ] 最後のやつだとこの辺に関連情報あるぞ scholar.google.com/scholar?q=simplicial+partitions+determine+closest&lr= 787 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 20:04:09 ] >>784 Mu03を見ることができたので、 これまでの材料で頑張ってみます。 ありがとうございました。 >>785 点を一個追加するとか、色々やりたくなるかもしれないので、 いくつかの方法を知っておきたいと思いました。 788 名前：デフォルトの名無しさん mailto:sage [2008/10/30(木) 20:29:11 ] >>785 O(n^2) は大規模なデータを相手にするには重過ぎるという感覚。 n < 2^32 程度でも前処理しきれない。 なので、クエリ時間を増やしても n^2 より安い手法が存在する。 789 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 16:28:46 ] マス目に二種類の記号を置いていった時、 AAA　　　　ABA ABB　　　　ABA AAA　　　　AAA というような回転させたら同じ場面を見つける為にいい方法は無いでしょうか？ 790 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:43:56 ] >>789 問題が不明瞭 マス目に記号が入ったものが二つ与えられたとき、 それが回転で移りあうかどうかをチェックしろということ？ 791 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 17:54:59 ] 簡単な方法はない。 地道に全回転・反転パターン（8通り）を網羅してチェックする。 プログラムが見通しよくなるように工夫がひつようかも。 792 名前：デフォルトの名無しさん [2008/10/31(金) 18:21:54 ] 行同値的を出してそれを比較すれば・・・駄目か 793 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 18:37:25 ] トランザクションメモリの実装 ここでやる夫的に説明してくれよ 794 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 19:41:21 ] 　　　 .　'　　　_ 二二 _ .､ 　　　 　 　 　 ／　　　 /´ -‐…‐- .｀＼ 　　　　　 　 /　　　　 /´　　　 i　　 !｀ヽﾄ､ .　　　 ,ﾍ　 ,' 　 i　 　 !　 !　 |　|i　　|ﾊ　i　ヽ　ｷﾘｯ 　　　/　 ゝ!　 ﾉ|　　! !::__!::ノ ´　￣　 i::.i ｜! 　　　＼　 .|　.:i i :i　i |´　　 ＼　　／　｀!､ﾊ:!　　 　 　 　 ｀ヽi　 从 i　i | ニﾆﾐ　　　 .ﾆニ !:::::|　　 ＜トランザクションメモリの実装 .　　　　 　 | 　ＹﾊｉﾊN　 {r::ﾘ｀　　´{r::ﾘ '::::N　　　　ここでやる夫的に説明してくれよ .　　　　 　 |　　ヽゝ　　 ´´　　　　　｀｀ﾊ!｀　 .　　　　 　 |∧ 　 �Y!　　　 　 　 ′　,':::| 　　　　 　 ｊ/∧　 _!::｝　、　　 ⊂'　..ｲ:::::| 　　　　　 ///∧´ ∨　　｀ 　,.... ィ´ﾞY:::::| .　　　　 /////∧　ヽ　　　　{ﾄ､∧　|::::::! 　　　　 ,＜￣￣∧　 } ｀ヽ　　＞''}　{￣｀ヽ .　　　 / 　 ｀ヽ:::::::::Y´ヽ　　　　　 i´｀∨::::∧ 　　　/　 　 　 ∨:::::| .:: !　　 　 　 i .:.: !::::/　i 　　　　　　　　　　　＿ ＿＿_ 　　　　　　　 ,. :'´: :,.　-―‐-ミ:ヽ、 　　　　　　／: : : :厶ｨ': ´￣￣ヾ : :＼ 　　　　　 /: : : : : :.!: :M: : : : : }､: ヽﾄ､:.＼　　　＜じゃっておｗｗｗ 　　　　　ｉ: : :.!: : : ﾚ‐'　｀￣⌒　⌒" ﾄﾍ:ﾊ! 　　　ﾄ--|: : :.!: : ､|　　ｰ‐'' ´ ｀'ｰ　　}: :.ﾄ 　　ﾐ　ﾐ　ﾐ : :!: : : :!　z=≡　　　≡z.{: :.ﾊ　　　　ﾐ　ﾐ　ﾐ 　/⌒)⌒)⌒.ﾊ :_Nとつ　＼＼＼ C VVﾘ 　　/⌒)⌒)⌒) 　|　/　/　/:弋こ　＼ヽ　＿＿,.　　　}　(⌒)/　/ / /／ 　|　:::::::::::(⌒) : :}＼　　/　　　1　 ／　　ゝ　　:::::::::::/ 　|　　　　　ノくf⌒Y ｀　{_　　_,ﾉイ| 　　　/　　）　　/ 　ヽ　　　　/　 ヽ　ﾍ,､　　_｢　|::!:::::} 　　/　　　　／　　　　 バ 　　|　　　　|　　 l||l　从人 l||l.!::|ｲ:::ヽ_./ l||l 从人 l||l　　バ　　ン 　　ヽ　　　 -一''''''"~~｀`'ー--､/:::::ｲ;　 -一'''''''ー-､　　　　ン 　　　ヽ ＿＿＿＿(⌒)(⌒)⌒)　):::/}　 (⌒＿(⌒)⌒)⌒)) 795 名前：デフォルトの名無しさん mailto:sage [2008/10/31(金) 21:00:10 ] かんなぎは評価されすぎ。 796 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 03:17:29 ] 無向グラフG=(V, E)の隣接リストがGが接続してようとなかろうとO(V+E)であることを証明せよ。 って意味のわかる人教えて下さい。 797 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 06:37:03 ] 意味が分からんな。 「隣接リストが O(V+E)」 ← これはまともな言い方じゃない。 798 名前：796 mailto:sage [2008/11/13(木) 06:40:40 ] >>797 無向グラフG=(V, E)が隣接リストの配列で表現されるとき、Gが接続していようと なかろうとO(V+E)であることを証明せよ。だったらどうですか？ 799 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 07:13:30 ] やはり意味不明。 今度は日本語としてもひどくて、何が O(V+E) なのかが分からん。 800 名前：796 mailto:sage [2008/11/13(木) 07:25:04 ] そうですか。失礼しました。忘れてもらって結構です。 801 名前：796 mailto:sage [2008/11/13(木) 07:31:12 ] 別のやつですが、ダイクストラアルゴリズムは経路に負の数があった場合はうまく動作しない例ってのは 例えばどういうときかわかりますか？ 802 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 07:42:43 ] >>801 G = (V,E) を 3点 a,b,c からなるグラフとし， 頂点間距離を d(a,b) = 0, d(a,c) = 1, d(b,c) = -2 と設定し， 頂点 a から b への最短路を求めようとすると破綻する． 803 名前：796 mailto:sage [2008/11/13(木) 07:49:21 ] なるほど。素早い回答ありがとうございます。 804 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 08:36:21 ] >>802 その例では破綻しないぞ 805 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 11:31:33 ] >>804 kwsk 806 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 21:00:49 ] >>802の例だとd(a, b) = 0で探索終わらね？ 正答が得られないって意味で破綻なんじゃね？ 807 名前：デフォルトの名無しさん [2008/11/14(金) 22:07:03 ] ユークリッド互除法の最悪時間計算量をLameの定理の結果を用いずに解析せよという問題がさっぱりわかりません。 ぜひ解答お願いしたいです。 スレチでしたらすみません。。 808 名前：びぎなぁ mailto:sage [2008/11/16(日) 05:22:26 ] アルゴリズムの勉強を始めたのですが、用語が色々あって混乱しています。 （どの用語がどの用語の中に含まれているのかとか） ヒープと二分ヒープという言葉があるのですが、同じ意味でしょうか？ 木構造--------二分木---------------二分探索木・・・左の子<=親<=右の子 木構造--------二分木---------------二分ヒープ・・・（１）根に最大値がくる、 　　　　　　　　　　　　　　　　　　　　　　　　　 （２）N[a],N[2a],N[2a+1]のデータでは必ずN[a]のデータが一番大きい 木構造--------二分木---------------ヒープ・・・二分ヒープと同義？ 木構造--------多分木 809 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 06:29:55 ] >>808 ヒープとは，木であって各頂点でヒープ条件『自分の値が子の値以上』 を満たすもののことをいう．よって．一般の木上のヒープがありうる． 例えば多分木上のヒープとしてはd分ヒープはたまに使われるし， より一般の木上のヒープとしてはフィボナッチヒープが有名． ただ，最もよく使われるヒープは完全二分木上のヒープで， 何も断らずにヒープと言ったときこれを指す場合も多い． 場合によっては配列実装まで含めてヒープと言う場合もあるけど， フォーマルには構造と実装は別に考えるので， >>808 の二分ヒープの説明は本当はちょっとよろしくない． 810 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 06:53:51 ] >>807 どれくらいの精度で解析すればいいの？ あと，Lameの定理の結果を用いないというのは Lameの定理を証明して用いるのは良いということ？ それとも，フィボナッチ数で抑えること自体が禁止されるの？ 811 名前：デフォルトの名無しさん [2008/11/16(日) 09:19:57 ] >>810 どの程度の制度かまでは問題に書いてないので、わかりません。 Lameの定理を証明してもダメだと思います。 フィボナッチ数を用いても良いかまでもわかりませんが、使わないでできるのなら使わないで解いてもらいたいです。 812 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 11:41:06 ] >>811 互除法のアルゴリズムを gcd(a,b) = if b == 0 then return a else return gcd(b, a mod b) として解析する（mod は割り算の余り）．a, b ≧ 0 の場合のみ考える． 補題． a > b ≧ 0 について，gcd(a,b) が k (≧ 1) ステップで終わるならば a ≧ 1.1^{k+1}, b ≧ 1.1^k が成立する． 証明． k = 1 のときは自明．k-1 まで正しいと仮定． gcd(a,b) が k ステップで終わるとき， gcd(b, a mod b) は k-1 ステップで終わるので帰納法の仮定から b ≧ 1.1^{k-1}, a mod b ≧ 1.1^k，したがって a ≧ 1.1^k + 1.1^{k-1} = 1.1^{k-1}×2.1 ≧ 1.1^{k-1}×1.21 = 1.1^{k+1}． 系． gcd(a,b) のステップ数は O(log min{a,b})． 証明． a > b としてよく，log b = m とおけば補題より O(m) 回以下のステップ数で終わるため． 813 名前：811 mailto:sage [2008/11/16(日) 17:41:20 ] ありがとうございます a ≧ 1.1^{k+1}, b ≧ 1.1^k この式をなぜ持ち出したのかがわかりません。 あと、系の証明が補題より証明できるあたりがいまいちわかりません。 よろしければ教えてください。 814 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 20:51:27 ] >>813 上：なんとなく． 1.1 に必然性はなくて，1.0001^k でも 1.0000000001^k でも何でもいい． (1+ε)^k で示せれば系が示せるので，適当に不等式が成り立ちそうな値にした． 本当に解析しようとしたらギリギリの不等式評価を作るべきなんだけど， この場合にギリギリに評価するとフィボナッチ数が出てしまうので， わざとガバガバに評価しているという事情がある． 下： > できるあたりがいまいちわかりません。 そういうときは具体的にここが分からないとか言うもんだよ． ただ，補題が少し不十分な書き方だったね．補題は 「k (≧ 1) ステップ以上かかるならば」 に置き換えてよい（同じ証明が動く）ので， そう置き替えておいて，対偶を取ると 「a < 1.1^{k+1} もしくは b < 1.1^k ならば k ステップ未満で終わる」 になるので b < 1.1^m なる m を見つけられれば m ステップ未満で終わる． そのような m としては log b (の切り上げ) にでも取れば十分(log は 1.1底)． 815 名前：811 mailto:sage [2008/11/16(日) 21:04:38 ] ありがとうございます。 もう一度問題と向き合って理解を深めたいと思います。 816 名前：びぎなぁ mailto:sage [2008/11/19(水) 07:05:43 ] >>809 返事が遅くなりました。ありがとうございました。 ところで、最小全域木を求めるクラスカル法とプリム法の概要を理解出来たのですが、 計算量のところがウェブ（ウィキとか）で調べてもよく理解できません。 （１）クラスカル法 グラフの中で一番重みの小さい辺をMSTとして加えて行く。ただしその過程でcyclicに なってしまうような辺は加えないようにする。計算量はO(E log E)またはO(E log V) （２）プリム法 MSTに属する頂点とそうでないものの２グループに分け、まだMSTに属していない頂点から 最もコストの安く済む頂点をMSTに付け加えて行く。計算量は３種類あるみたい。 ・隣接行列、探索→O(V^2) ・２分ヒープと隣接リスト→O(E log V)（←これはO((V+E)log(V))より） ・フィボナッチヒープと隣接リスト→O(E+V log (V)) ウェブの説明を読んでもわからないということはここで教えてもらってもわからないかも知れませんが もしわかりやすい説明とかありましたら参考に教えて欲しいです 817 名前：デフォルトの名無しさん mailto:sage [2008/11/19(水) 08:22:57 ] >>816 アルゴリズムの計算量を評価するためには もっと正確にアルゴリズムを述べないといけないんだけど， あなたの説明だと，良く分からない部分が多い． （もちろん「普通の実装」というのがあるのだけれど， 　それがあなたの理解しているものと違う可能性もある） なので，あなたが理解している形で，For やら If やらを使って 手続きが明確に分かるようにアルゴリズムを書いてくれるかな？ その計算量だったら評価するよ． 818 名前：びぎなぁ mailto:sage [2008/11/19(水) 16:22:32 ] >>817 イントロダクショントゥアルゴリズム二版から抜粋です --------------------------------------- MST-クラスカル（G, w） A←0 for each vertex v∈ V[G] do MAKE-SET(v) sort the edges of E into nondecreasing order by weight w for each edge (u, v) ∈ E, taken in nondecreasing order by weight do if FIND-SET(u)≠FIND-SET(v) then A←A∪{(u, v)} UNION(u, v) return A --------------------------------------- MST-プリム(G, w, r) for each u∈V[G] do key[u]←∞ π[u]←NIL key[r]←0 Q←V[G] while Q≠0 do u ← EXTRACT-MIN(Q) for each v∈Adj[u] do if v∈Q and w(u, v) < key[v] then π[v]←u key[v]←w(u, v) --------------------------------------- 819 名前：デフォルトの名無しさん mailto:sage [2008/11/19(水) 21:49:58 ] >>818 その本に計算量の説明が懇切丁寧に書いてあるよ 820 名前：デフォルトの名無しさん mailto:sage [2008/11/19(水) 21:54:24 ] ならし解析ですね分かりません。 821 名前：デフォルトの名無しさん mailto:sage [2008/11/20(木) 00:37:39 ] LC-Treisってどんな木なのですかね？ 822 名前：びぎなぁ mailto:sage [2008/11/20(木) 02:42:41 ] >>819 了解です！ 823 名前：びぎなぁ mailto:sage [2008/11/20(木) 02:46:49 ] 「有向グラフで、開始点から離れて行く辺のweightが全て負の数で、その他の全ての辺が 正の数だった場合、ダイクストラ法は失敗することがあるか？」 あれば例を教えて欲しいです 824 名前：デフォルトの名無しさん mailto:sage [2008/11/20(木) 21:21:36 ] 「開始点から離れて行く辺」の定義が必要なんじゃね？ 825 名前：びぎなぁ mailto:sage [2008/11/20(木) 23:44:17 ] sourceのことだと思います 826 名前：デフォルトの名無しさん mailto:sage [2008/11/24(月) 19:02:46 ] バイナリ木関連のアルゴリズム 詳細に書いてる本ってありますか？ 827 名前：デフォルトの名無しさん mailto:sage [2008/11/24(月) 20:00:17 ] >>826 詳細ってどの程度？ 必要なトピックを具体的にいくつか挙げてください。 828 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 09:34:20 ] トポロジカルソートはなぜグラフがDAGであることが前提なのですか？ サイクリックなグラフでもソート出来ると思うのですが。 829 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 10:13:52 ] >>828 トポロジカルソート（トポロジカルオーダリング）をどう定義してるの？ いくつか流儀があるから君の流儀が分からないと適切には答えられない． 830 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 13:40:19 ] トポロジカルソート： （１）DAGに対して、DFSを実行する。 （２）Finishing timeの大きい順に頂点を並べる。 というものですが、いかがでしょうか。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef