データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3

1 名前：デフォルトの名無しさん mailto:sageteoff [2016/06/19(日) 14:47:29.63 ID:5KvSKdL/.net] このスレッドは天才チンパンジー「アイちゃん」が 言語訓練のために立てたものです。 アイと研究員とのやり取りに利用するスレッドなので、 関係者以外は書きこまないで下さい。 　　　　　　　　　　　　　　　　　　京都大学霊長類研究所 データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2 echo.2ch.net/test/read.cgi/tech/1362301811/ 【関連スレ】 3Dアルゴリズム全般 toro.2ch.net/test/read.cgi/tech/1164171086/ ＜集大成＞アルゴリズム大辞典 toro.2ch.net/test/read.cgi/tech/1086272325/ アルゴリズム総合スレ in ム板 toro.2ch.net/test/read.cgi/tech/1217773415/ アルゴリズムとデータ構造 - Kaneko Lab. ttp://www.kkaneko.com/adp/algo/index.html アルゴリズムとデータ構造 - ソースコード探険隊 ttp://www.codereading.com/algo_and_ds/ 各種アルゴリズムの C++ による実装 - Spaghetti Source ttp://www.prefield.com/algorithm/ アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP ttp://vipprog.net/wiki/algo_and_data_const.html 152 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 17:37:02.75 ID:ic0p/3Yf.net] 長さn� 153 名前：ﾌ整数からなる列(a_1 ,a_2, ..., a_n) があるとして、列の大きさを |a_1|+...+|a_n|で定義します。、 大きさがmの任意の列を大きさm-1の列の中の一つの値だけ1違う 列一つに対応させたいんですけど 対応のさせ方がわかりません、教えてください。 例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する長さ2の列は (0 ,-1 ,1), (1,0,1),(1,-1,1),(1,-1,0)とかあるので一つには定まってません。 なのでその対応をする関数をおしえてください。 [] [ここ壊れてます] 154 名前：間違ってたので直します mailto:sage [2016/12/19(月) 17:39:59.34 ID:ic0p/3Yf.net] 長さnの整数からなる列(a_1 ,a_2, ..., a_n) があるとして、列の大きさを |a_1|+...+|a_n|で定義します。、 大きさがmの任意の列を大きさm-1の列の中の一つの値だけ1違う 列一つに対応させたいんですけど 対応のさせ方がわかりません、教えてください。 例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する大きさ2の列は (0 ,-1 ,1), (1,0,1),(1,-1,0)とかあるので一つには定まってません。 なのでその対応をする関数をおしえてください。 155 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 17:48:27.12 ID:z9XVuDpo.net] (1,-1,1)の長さが2? 156 名前：デフォルトの名無しさん [2016/12/19(月) 17:53:09.70 ID:yHCszZUX.net] ＞なのでその対応をする関数をおしえてください。 意味不明です。 157 名前：デフォルトの名無しさん [2016/12/19(月) 17:55:40.11 ID:yHCszZUX.net] (a_1, a_2, ..., a_i, ..., a_n) a_i > 0 のときには、 (a_1, a_2, ..., a_i-1, ..., a_n) a_i < 0 のときには、 (a_1, a_2, ..., a_i+1, ..., a_n) a_i = 0 のときには、 (a_1, a_2, ..., a_i±1, ..., a_n) を返せばいいのでは？ 158 名前：デフォルトの名無しさん [2016/12/19(月) 17:57:14.37 ID:yHCszZUX.net] (a_1, a_2, ..., a_i, ..., a_n) a_i > 0 のときには、 (a_1, a_2, ..., a_i-1, ..., a_n) a_i < 0 のときには、 (a_1, a_2, ..., a_i+1, ..., a_n) を返せばいいのでは？ a_i = 0 のときには、条件を満たす列は存在しないね。 159 名前：デフォルトの名無しさん [2016/12/19(月) 17:58:07.65 ID:yHCszZUX.net] >>150 何がやりたいのかが不明確。 160 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 17:58:17.41 ID:hSWjQy3F.net] >>149 列の最初の数字だけ1足すなり引くなりして返せばいいだけじゃないの？ 161 名前：デフォルトの名無しさん [2016/12/19(月) 18:01:17.72 ID:yHCszZUX.net] ＞例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する大きさ2の列は ＞(0 ,-1 ,1), (1,0,1),(1,-1,0)とかあるので一つには定まってません。 ＞なのでその対応をする関数をおしえてください。 一つに定まらないから、すべての結果を返したいのか、 任意の一つの結果を返したいのか？ 162 名前：デフォルトの名無しさん [2016/12/19(月) 18:02:09.41 ID:yHCszZUX.net] 明らかに、 (0, 0, ..., 0) に対しては条件を満たす結果は存在しないね。 163 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 18:50:37.10 ID:ic0p/3Yf.net] ０はスタート地点なので 164 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 18:57:02.98 ID:ic0p/3Yf.net] >>154 a_2を1としたとき(-1, 1)のとき(-1,0)を返し a_1を-1としたとき　(-1,1)は(0,1)をかえすことになるので 一つに定まりません 165 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 19:06:19.22 ID:ic0p/3Yf.net] >>157 大きさn>0の任意の列aにたいしてf(a)=bでbがn-1の大きさでaと列の中の値が1だけ違う 列を出力する関数fを求めるということです。 166 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 19:13:51.38 ID:ic0p/3Yf.net] >>156 初めはそんな風に考えてる時期もありました もう2か考えてるけれど全然わからないのでここで質問してみました 167 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 19:16:05.63 ID:hSWjQy3F.net] >>161 問題文を鸚鵡返しするんじゃなくて、質問者の質問に答えたら？ 168 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 19:23:49.64 ID:ic0p/3Yf.net] >>163 fの出力は列の集合じゃないから普通わかりますよね 169 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 19:31:58.40 ID:hSWjQy3F.net] >>164 fが返すのは集合じゃないってのはどこに書いてある？ 170 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 19:34:42.99 ID:ic0p/3Yf.net] >>165 14行上に書いてあります 171 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 19:47:31.40 ID:hSWjQy3F.net] >>166 Mateだと>>156って書いてあるわ 自分の中ではこれは当然みたいな条件がいろいろあるんだろうけど、それを人に説明するのが下手なんじゃね 172 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 20:02:25.40 ID:ic0p/3Yf.net] 改行コードの数を数えてますか？ 文の折り返しと改行とは違いますよ？ 173 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 20:17:02.98 ID:2q/Y95iw.net] こりゃまたひどい質問者だな 174 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 20:18:06.39 ID:Xx/umGft.net] 課題の丸投げ、しかも「日本語」が 175 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 20:25:56.12 ID:ic0p/3Yf.net] 課題という証拠はありますか？ 実際課題じゃなくプログラミングしていたら出てきた問題なので 全然課題じゃないです 176 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 20:33:03.53 ID:ic0p/3Yf.net] >>170 あなたには誤った文を訂正する能力がないんですか？ それでは人間ではなくコンパイラーと同じですよ 177 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 20:37:51.17 ID:ic0p/3Yf.net] >>169 面白い問題とつまらない問題を区別する能力が数学的推測には 一番必要なんんです この問題がつまらないと思うのなら解かないでいいです 178 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 20:50:46.99 ID:2q/Y95iw.net] 問題をきちんと記述する能力に欠けている 179 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 20:52:23.54 ID:2q/Y95iw.net] あと、面白い問題だと思うなら、それこそ自分で解くのが楽しいのでは ここで聞かずに 180 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 21:27:51.26 ID:ic0p/3Yf.net] >>175 楽しいものは独り占めるのではなく分け与えようと習わなかったのでは？ 181 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 21:44:43.60 ID:ic0p/3Yf.net] >>174 今読み返してみましたがキチンと書かれてますよ どこがキチンと書かれてないのか言ってくれたら それは理解力の無さなので説明してもいいです 182 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 22:34:08.82 ID:2q/Y95iw.net] 十分楽しんだからあとは一人で楽しんでくれていいよ 183 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 22:53:51.02 ID:Xx/umGft.net] >>172 馬鹿乙 184 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 23:04:39.12 ID:L2gIhLeK.net] 先頭から非0を探して、はじめの要素が正なら1ひく、負なら1足す これで終わりじゃないの？ 185 名前：デフォルトの名無しさん mailto:sage [2016/12/19(月) 23:45:15.82 ID:Xx/umGft.net] アルゴリズムは自分で考えるじゃ、ボケ 186 名前：デフォルトの名無しさん mailto:sage [2016/12/20(火) 13:05:59.52 ID:lAXr92yw.net] >>171 茶か尿かもう判らんって意見があるけど 検出時のガスクロのデータ見直したら判るはずという話がある 仮にそれでお茶だとしてももう発表はないだろう 187 名前：デフォルトの名無しさん [2016/12/21(水) 18:35:54.54 ID:UR5SKYPV.net] 数列 1, 2, 3, … すなわち、 数列 {a_n} = {n} を考える。 {a_n} の任意の連続する有限部分列を a_k, a_(k+1), …, a_l（k ≦ l）とする。 各 i（k ≦ i ≦ l）に対して、0以上の整数 b_i を以下で定義する： 「2^(b_i) は a_i を割り切るが、 2^(b_i+1) は a_i を割り切らない」 このとき、 #{m | k ≦ i ≦ l である任意の i に対して、 b_i ≦ b_m} = 1 であることを示せ。 また、有限部分列 a_k, a_(k+1), …, a_l（k ≦ l）が与えられたとき、 k ≦ i ≦ l である 任意の i に対して、 b_i ≦ b_m となるような m を求めるプログラムを作れ。 188 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 18:45:01.91 ID:trArLuj5.net] お断りいたします 189 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 18:49:10.92 ID:IT3zLaEf.net] 俺も断るわ 190 名前：デフォルトの名無しさん [2016/12/21(水) 19:41:25.65 ID:UR5SKYPV.net] 早くも降参宣言か。 191 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 19:55:05.40 ID:RIWp4Ngq.net] mなんていくらでもあるんじゃないの？ なんで#{m}=1？ 192 名前：デフォルトの名無しさん [2016/12/21(水) 20:06:55.96 ID:UR5SKYPV.net] >>187 一意的です。そこがちょっと面白いところです。 反例を作ろうと思ってもできないはずです。 193 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 20:09:57.40 ID:trArLuj5.net] >>183 分からない問題はここに書いてね421 [無断転載禁止]©2ch.net rio2016.2ch.net/test/read.cgi/math/1480771004/493 194 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 20:12:10.26 ID:RIWp4Ngq.net] k=1, l=2で、{m}={2,4,6,8,...} k=l=1で、{m}=自然数の集合 じゃないの？ 195 名前：デフォルトの名無しさん [2016/12/21(水) 20:16:47.08 ID:UR5SKYPV.net] >>190 {a_n} の任意の＊連続する＊有限部分列を a_k, a_(k+1), …, a_l（k ≦ l）とする。 196 名前：デフォルトの名無しさん [2016/12/21(水) 20:18:48.11 ID:UR5SKYPV.net] k=1, l=2で、{m}={2,4,6,8,...} k=l=1で、{m}=自然数の集合 じゃないの？ a_1, a_2 = 1, 2 なので、 b_1, b_2 = 0, 1 です。 なので、 {m} = {2} です。 197 名前：デフォルトの名無しさん [2016/12/21(水) 20:19:15.67 ID:UR5SKYPV.net] >>191 は勘違いです。 198 名前：デフォルトの名無しさん [2016/12/21(水) 20:20:14.23 ID:UR5SKYPV.net] a_1 = 1 なので、 b_1 = 0 です。 なので、 {m} = {1} です。 199 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 20:21:17.66 ID:RIWp4Ngq.net] k=1, l=2も、k=l=1も、当然連続する部分列でしょ {b_i}を10個ぐらい挙げてみてよ 200 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 20:22:42.50 ID:RIWp4Ngq.net] mの条件が足りないんじゃないの？ 201 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 20:24:46.75 ID:RIWp4Ngq.net] b_i ≦ b_mさえ満たせばいいんならmなんていくらでもあるでしょ 202 名前：デフォルトの名無しさん [2016/12/21(水) 20:32:03.58 ID:UR5SKYPV.net] b_m は b_i の最大値です。 その最大値となる b_m の m が一意的であるということです。 203 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 20:32:36.28 ID:El82f3CE.net] k≦m≦lという条件が抜けているっぽいね 204 名前：デフォルトの名無しさん [2016/12/21(水) 20:34:06.08 ID:UR5SKYPV.net] テレンス・タオ ルベーグ積分入門 テレンス タオ 固定リンク: amzn.asia/8KaL6NK 「日本の理工系学部ではルベーグ積分は3年次程度の必修相当科目なので、」 ↑これっておかしくないですか？ 普通、ルベーグ積分なんてやるのは数学科かせいぜい物理学科くらいじゃないですか？ 205 名前：デフォルトの名無しさん [2016/12/21(水) 20:34:58.70 ID:UR5SKYPV.net] >>199 各 i（k ≦ i ≦ l）に対して、0以上の整数 b_i を以下で定義する： 206 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 20:39:27.31 ID:RIWp4Ngq.net] 不完全な問題出しておいて>>186はないよね 207 名前：デフォルトの名無しさん [2016/12/21(水) 20:41:22.47 ID:UR5SKYPV.net] >>202 不完全なところはありません。 よく問題文を読んでください。 208 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 20:42:06.97 ID:trArLuj5.net] >>200 力学･解析力学part2 rio2016.2ch.net/test/read.cgi/sci/1284697460/479 209 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 20:43:41.56 ID:trArLuj5.net] マルチ小僧ｗ 210 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 20:44:49.22 ID:RIWp4Ngq.net] >>203 mがkからlの間なんて一言もないんだから不完全 211 名前：デフォルトの名無しさん [2016/12/21(水) 20:47:08.96 ID:UR5SKYPV.net] >>206 >>183 各 i（k ≦ i ≦ l）に対して、0以上の整数 b_i を以下で定義する 212 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 20:52:23.64 ID:RIWp4Ngq.net] そうだとして、わざと誤読を誘おうとしている悪問だね でO(log k)のアルゴリズム思いついたから俺は降りるね 213 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 20:53:06.55 ID:RIWp4Ngq.net] O(log l)だった 214 名前：デフォルトの名無しさん [2016/12/21(水) 20:55:14.58 ID:UR5SKYPV.net] >>183 の解答は以下です。 imgur.com/rAnp3Ga.jpg 赤線を引いたところは「odd」が正しいですね。 215 名前：デフォルトの名無しさん [2016/12/21(水) 21:27:34.73 ID:UR5SKYPV.net] 実は、この問題には続きがあります。 m, n を m < n を満たす正の整数とします。 このとき、 1/m + 1/(m+1) + … + 1/n は整数にはならないことを証明せよ。 216 名前：デフォルトの名無しさん [2016/12/21(水) 21:29:28.61 ID:UR5SKYPV.net] ちょっとアルゴリズム的な問題からは離れますが。 217 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 21:31:37.14 ID:xYX0mlO/.net] 提出日はいつですか？ 218 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 22:14:54.89 ID:auJA5Ak8.net] またバカな質問者が暴れてるのか 219 名前：デフォルトの名無しさん mailto:sage [2016/12/21(水) 23:45:05.79 ID:mNaBBYjZ.net] qiitaでやれ 220 名前：デフォルトの名無しさん mailto:sage [2016/12/23(金) 00:59:54.04 ID:gOElNe3R.net] >>183 そのような m が 2 個ある m1 < m2 とする m1 の下位ビット 0 〜 n-1 までは 0で、 ビット n が 1 とする m2 も同様になる（すなわち b_m1 = b_m2 = n ） m3 = m1 + ( 2 の n 乗 ) と定義すると m1 < m3 <= m2 であるが、b_m3 > n となって矛盾 221 名前：デフォルトの名無しさん mailto:sage [2016/12/23(金) 01:37:11.09 ID:gOElNe3R.net] >>211 1/m + 1/(m+1) + … + 1/n = P = 整数 だとする L = ∏ r ; r = m…n を両辺に掛ける L/m + L/(m+1) + … + L/n = LP すべての項は整数。 b_LP ( LP の連続する下位ビット 0 の個数 ) >= Σ b_r ; r = m…n m <= x <= n は b_x を最大にするもの 左辺の L/x だけ連続する下位ビット 0 の個数は他より少ない よって b_左辺 = b_x で矛盾 222 名前：デフォルトの名無しさん [2017/01/01(日) 00:15:18.27 ID:VtFWW7J2.net] ダイクストラのアルゴリズムの正しさの証明が載っている本で 一番分かりやすい本を教えてください。 223 名前：デフォルトの名無しさん [2017/01/02(月) 07:40:19.35 ID:03PPbeGI.net] 『アルゴリズムイントロダクション』について質問です。 この本での実数の集合には、 ∞, -∞ が含まれるのでしょうか？ 最短路問題の説明で、 実数 a が a≠∞のとき、 a + -∞ = -∞ 実数 a が a≠-∞のとき、 a + ∞ = ∞ という記述があるために質問します。 224 名前：デフォルトの名無しさん [2017/01/02(月) 08:09:15.65 ID:03PPbeGI.net] 実数 a が a≠∞のとき、 a + -∞ = -∞ 実数 a が a≠-∞のとき、 a + ∞ = ∞ -∞ + -∞ = -∞ ∞ + ∞ = ∞ という等式を含めたいからこのような書き方になったのでしょうか？ 225 名前：デフォルトの名無しさん mailto:sage [2017/01/02(月) 09:29:22.45 ID:J77W/v0L.net] それは実無限派の書き方だが，世の趨勢は可能無限 ほどほどに相手をするだけでいいよ 226 名前：デフォルトの名無しさん [2017/01/02(月) 11:22:57.42 ID:03PPbeGI.net] >>221 ということは、『アルゴリズムイントロダクション』での実数の集合の定義には、 ∞、-∞ が含まれるというk十ですね。 227 名前：デフォルトの名無しさん [2017/01/02(月) 11:23:39.72 ID:03PPbeGI.net] 頂点の数が n のグラフで、任意の頂点間に辺が存在するようなものを考える。 ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を求めよ。 228 名前：デフォルトの名無しさん [2017/01/02(月) 11:26:14.49 ID:03PPbeGI.net] 頂点の数が n（≧2） のグラフで、任意の頂点間に辺が存在するようなものを考える。 ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を a_n とする。 このとき、 (n-1)! ≧ a_n ≧ (n-2)! が成り立つことを示せ。 229 名前：デフォルトの名無しさん mailto:sage [2017/01/02(月) 12:08:43.26 ID:GdcUHK9D.net] 宿題は宿題スレへ 230 名前：デフォルトの名無しさん mailto:sage [2017/01/02(月) 12:09:56.00 ID:GdcUHK9D.net] 宿題は宿題スレへ 231 名前：デフォルトの名無しさん [2017/01/02(月) 12:22:39.27 ID:03PPbeGI.net] 宿題ではないのです。 ある本に、頂点 s から t への最短経路を計算する方法として、 s から ｔ へのあらゆる経路の長さを考えて、最小の経路を選ぶとすると、 経路の数が O(n!) だから現実的ではない という話が書いてあります。 ところが、計算してみると、 O(n!) は荒い評価であって、 O((n-1)!) とできますね。 232 名前：デフォルトの名無しさん [2017/01/02(月) 12:24:22.04 ID:03PPbeGI.net] もっといい評価はありますでしょうか？ 233 名前：デフォルトの名無しさん mailto:sage [2017/01/02(月) 12:28:36.72 ID:GdcUHK9D.net] 判ってるなら効くな 234 名前：デフォルトの名無しさん [2017/01/02(月) 14:08:15.59 ID:03PPbeGI.net] ダイクストラ法の正しさの証明で分かりやすい証明を思いつきました。 発表しましょうか？ 235 名前：デフォルトの名無しさん mailto:sage [2017/01/02(月) 14:21:37.12 ID:w6ZCrhsc.net] どうぞどうぞ 236 名前：デフォルトの名無しさん mailto:sage [2017/01/02(月) 14:27:23.53 ID:yIXUnWg3.net] >>227 オーダーについてあんま良くわかってないんだろうけどO((n-1)!) なんて書き方はないよ もし書いたとして、それはO(n!)と同じもの 237 名前：デフォルトの名無しさん mailto:sage [2017/01/02(月) 17:55:38.72 ID:J77W/v0L.net] >>222 実無限はいろいろ破綻するから可能無限にしておいたほうがいいよ 実数の定義に∞, -∞は入らない というか，そもそも -∞ というのがおかしい存在 つリーマン球面 238 名前：デフォルトの名無しさん [2017/01/02(月) 19:04:30.86 ID:03PPbeGI.net] なんか正しさの証明を書いてみると簡単なことなのに長くなりますね。 もし、間違っていたら指摘してください。 imgur.com/PDx2vmZ.jpg imgur.com/DbMiSz5.jpg ダイクストラのアルゴリズムは↑のものとします。 239 名前：デフォルトの名無しさん [2017/01/02(月) 19:05:18.10 ID:03PPbeGI.net] 節点 s から、ある節点 i への最短経路が存在するとき、その長さを td(i) で表わすことにする。 i への経路、したがって最短経路が存在しないときには、 td(i) = ∞ とする。 ステップ(1)で選ばれる節点 v ∈ V - S に対して、 d(v) = td(v) が成り立つことを数学的帰納法により、以下で証明する。 最初にステップ(1)が実行されるときを考える。 明らかに、 d(s) = td(s) = 0 が成り立つ。 k ≧ 1 とする。 第 1 回目から第 k 回目にステップ(1)が実行されるときに、いつもステップ(1)で選ばれる節点 v ∈ V - S に対して、 d(v) = td(v) が成り立つと仮定する。 240 名前：デフォルトの名無しさん [2017/01/02(月) 19:05:35.40 ID:03PPbeGI.net] 第 (k+1) 回目にステップ(1)が実行されるときを考える。 このとき、明らかに #S = k であり、 ∀i ∈ S に対して、 d(i) = td(i) が成り立つ。 第 (k+1) 回目にステップ(1)が実行されるときに選ばれる節点を v ∈ V - S とする。 d(v) = ∞ である場合と d(v) ≠ ∞ である場合で場合分けして考える。 (1) d(v) = ∞ である場合。 td(v) ≠ d(v) = ∞ と仮定して矛盾を導く。 td(v) ≠ ∞ であるから、節点 s から節点 v への経路 s = v_0 → v_1 → … → v_(l-1) → v_l = v が存在する。 明らかに、 td(v_0), td(v_1), …, td(v_(l-1)), td(v_l) ≠ ∞ である。 v_0 ∈ S, v_l ∈ V - S であるから、 v_i ∈ S, v_(i+1) ∈ V - S となるような i が存在する。 ∀j ∈ V - S に対して、 d(j) = ∞ であるから、 d(v_(i+1)) = ∞ である。また、 v_i ∈ S であるから、 d(v_i) = td(v_i) ≠ ∞ が成り立つ。 v_i がステップ(2)で S に追加されたときのことを考えれば分かるように、 (v_i, v_(i+1)) ∈ E かつ v_(i+1) ∈ V - S であるから、 d(v_(i+1)) = ∞ ということはない。これは矛盾である。 よって、 d(v) = td(v) = ∞ が成り立つ。 241 名前：デフォルトの名無しさん [2017/01/02(月) 19:05:51.66 ID:03PPbeGI.net] (2) d(v) ≠ ∞ である場合。 td(v) ≠ d(v) と仮定して矛盾を導く。 ステップ(2)を考えれば明らかなように、 d(v) ≠ ∞ であるから、節点 s から節点 v への 最短経路 s = v_0 → v_1 → … → v_(l-1) → v_l = v が存在する。 よって、 td(v) ≠ ∞ である。 仮定により、 td(v) ≠ d(v) であるから、 td(v) < d(v) が成り立つ。 v_0 ∈ S, v_l ∈ V - S であるから、 v_i ∈ S, v_(i+1) ∈ V - S となるような i が存在する。 td(v_(i+1)) < d(v_(i+1)) である。なぜなら、もし、そうでないと仮定すると、 d(v_(i+1)) = td(v_(i+1)) であるが、 td(v_(i+1)) ≦ td(v) < d(v) であるから、 d(v_(i+1)) < d(v) � 242 名前：ﾆなってしまい、ステップ(1)での v の 選ばれ方に矛盾するからである。 v_i ∈ S であるから、 d(v_i) = td(v_i) である。 v_i がステップ(2)で S に追加されたときのことを考えれば分かるように、 (v_i, v_(i+1)) ∈ E かつ v_(i+1) ∈ V - S であるから、 d(v_i) + a_(v_i v_(i+1)) ≧ d(v_(i+1)) である。 一方、明らかに、 td(v_i) + a_(v_i v_(i+1)) = td(v_(i+1)) であるから、 td(v_(i+1)) = td(v_i) + a_(v_i v_(i+1)) = d(v_i) + a_(v_i v_(i+1)) ≧ d(v_(i+1)) となるが、これは矛盾である。 よって、 td(v) = d(v) が成り立つ。 [] [ここ壊れてます] 243 名前：デフォルトの名無しさん [2017/01/02(月) 19:06:08.41 ID:03PPbeGI.net] 以上より、第 (k+1) 回目にステップ(1)が実行されるときにも、ステップ(1)で選ばれる節点 v ∈ V - S に対して、 d(v) = td(v) が成り立つ。 S に追加される節点はすべて、ステップ(1)で選ばれた 節点 v ∈ V - S であり、一度 S に追加された節点 v の d(v) はそれ以後、 変更されないから、ステップ(1)でアルゴリズムが終了したとき、 ∀i ∈ S = V に対して、 d(i) = td(i) が成り立つ。 244 名前：デフォルトの名無しさん [2017/01/02(月) 19:26:36.14 ID:03PPbeGI.net] >>232 ある本では、 正定数 c, n0 が存在して、 n ≧ n0 のとき、 T(n) ≦ c*f(n) であるなら、 T(n) は O(f(n)) であるという と定義されています。 T(n) = n! f(n) = n! g(n) = (n-1)! とします。 このとき、明らかに、 T(n) は O(f(n)) ですが、 T(n) は O(g(n)) ではありません。 245 名前：デフォルトの名無しさん [2017/01/02(月) 19:29:54.44 ID:03PPbeGI.net] したがって、 O(f(n)) と O(g(n)) は異なります。 246 名前：デフォルトの名無しさん mailto:sage [2017/01/03(火) 08:33:06.09 ID:3o9M4oho.net] この狂人ヤバいなｗ 247 名前：デフォルトの名無しさん [2017/01/03(火) 08:50:16.82 ID:hCDXc7Qp.net] >>224 >>227 閉路を含まないから、各点を高々1回しか通らない。（端点も） 直通の経路が　１ 途中でｋ個所を通過する経路が 　(n-2)(n-3)･････(n-k-1) = (n-2)!/(n-k-2)! だけある。ただし、k≦n-2 よって a_n = (n-2)!｛1 + 1/1! + 1/2! + … + 1/(n-2)!}, n ≧ 2 のとき、 (n-2)! ≦ (n-2)! * (1 + 1/1! + 1/2! + … + 1/(n-2)!) ≦ e * (n-2)! したがって、 a_n = Θ((n-2)!) である。 248 名前：デフォルトの名無しさん [2017/01/03(火) 08:52:54.04 ID:hCDXc7Qp.net] >>234-238 のダイクストラのアルゴリズムの正しさの証明に間違いはないという ことでOKですか？ 249 名前：デフォルトの名無しさん [2017/01/03(火) 11:39:58.60 ID:hCDXc7Qp.net] Erik DemaineはMITの歴史上最年少で教授になったという天才だそうですね。 今、そのErik Demaineの2005年のダイクストラのアルゴリズムについての講義を見ています。 見終わったら、講義の要約について書きます。 250 名前：デフォルトの名無しさん [2017/01/03(火) 13:47:58.01 ID:hCDXc7Qp.net] ダイクストラのアルゴリズム： 01: d[s] ← 0 02: for each v ∈ V - {s}: 03: ■■d[v] ← ∞ 04: S ← Φ 05: Q ← V 06: while Q ≠ Φ: 07: ■■u ← ExtractMin(Q) 08: S ← S ∪ {u} 09: for each v ∈ Adj[u]: 10: ■■if d[v] > d[u] + w(u, v): 11: ■■■■d[v] ← d[u] + w(u, v) 251 名前：デフォルトの名無しさん [2017/01/03(火) 13:49:29.21 ID:hCDXc7Qp.net] Correctness I: d[v] の初期化の直後、およびLine 11の直後において、 すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が 成り立つ。 証明： d[v] の初期化の直後には、 d[s] = 0 かつすべての v ∈ S - {v} に対して、d[v] = ∞ が成り立っている。 δ(s, s) = 0 かつすべての v ∈ S に対して、 δ(s, v) ≦ ∞ であるから、d[v] の初期化の直後には、 すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が確かに 成り立っている。 252 名前：デフォルトの名無しさん [2017/01/03(火) 13:49:56.08 ID:hCDXc7Qp.net] Line 11の直後において、すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が成り立つことを背理法により示す。 Line 11の直後において、 d[v] ≧ δ(s, v) が 成り立たないような v ∈ V が存在するとする。 v をそのような点の中で、最初の点とする。 d[v] < δ(s, v) d[v] < δ(s, v) ≦ ∞ であるから、 ダイクストラのアルゴリズムのLine 11は少なくとも1回は 実行されているはずである。そのような最後の実行を d[v] ← d[u] + w(u, v) とすると、 d[u] + w(u, v) = d[v] < δ(s, v) が成り立つ。 一方、 d[u] ≧ δ(s, u) であるから、 d[u] + w(u, v) ≧ δ(s, u) + w(u, v) ≧ δ(s, u) + δ(u, v) ≧ δ(s, v) が成り立つが、これは矛盾である。

---

---

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

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