◎正当な理由による書き込みの削除について:      生島英之とみられる方へ:

Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net ->画像>6枚


動画、画像抽出 || この掲示板へ 類似スレ 掲示板一覧 人気スレ 動画人気順

このスレへの固定リンク: http://5chb.net/r/math/1497007079/
ヒント:5chスレのurlに http://xxxx.5chb.net/xxxx のようにbを入れるだけでここでスレ保存、閲覧できます。

1132人目の素数さん
2017/06/09(金) 20:17:59.42ID:qUOneyKn
Daniel Marcus Graph Theory を読む。
2◆2VB8wsVUoo
2017/06/09(金) 20:19:04.83ID:XVb2Gvc9
■■■馬鹿板を続けたらオツムがスポンジ脳になるのでサッサと足を洗うべき。■■■

3132人目の素数さん
2017/06/09(金) 20:19:21.11ID:qUOneyKn
https://github.com/for-2ch/for-2ch/blob/master/Chapter_B.ipynb
https://github.com/for-2ch/for-2ch/blob/master/Chapter_C.ipynb
https://github.com/for-2ch/for-2ch/blob/master/Chapter_D.ipynb
4132人目の素数さん
2017/06/09(金) 20:20:05.44ID:qUOneyKn
Graph Theory: A Problem Oriented Approach (Maa Textbooks)
by Daniel A. Marcus
https://www.amazon.com/dp/0883857723
5◆2VB8wsVUoo
2017/06/09(金) 20:20:39.44ID:XVb2Gvc9
★★★数学徒は馬鹿板をしない生活を送り、日頃から真面目に学問に精進すべき。★★★

6132人目の素数さん
2017/06/09(金) 21:15:38.28ID:0mal/2rX
305 名前:132人目の素数さん[] 投稿日:2017/06/07(水) 11:16:58.13 ID:54f7ZpML
あ、簡単でしたね。

https://anaconda.org/for_2ch/chapter-c/notebook

306 名前:132人目の素数さん[] 投稿日:2017/06/07(水) 12:44:01.61 ID:54f7ZpML
Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net	->画像>6枚

与えられた次数列をもつ2部グラフが存在するかどうかの問題です。

解答をお願いします。

307 名前:132人目の素数さん[] 投稿日:2017/06/07(水) 12:52:53.09 ID:54f7ZpML
>>306

これは試行錯誤するしかないっぽいですね。

308 名前:132人目の素数さん[] 投稿日:2017/06/07(水) 12:56:32.29 ID:54f7ZpML
C26

(a)

次数をすべて足すと = 42
42 / 2 = 21

次数列を構成している次数はすべて偶数だから2部グラフは存在しない。

311 名前:132人目の素数さん[] 投稿日:2017/06/07(水) 19:37:58.59 ID:54f7ZpML
>>310

ありがとうございます。

https://github.com/for-2ch/for-2ch/blob/master/Chapter_C.ipynb

314 名前:132人目の素数さん[] 投稿日:2017/06/07(水) 21:25:35.66 ID:54f7ZpML
Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net	->画像>6枚

↑の問題C28の意味が分かりません。

どういう解答を期待しているのでしょうか?

(4, 3, 3, 3, 3, 3, 3, 2, 2)

という次数列だけからでは、2部補グラフがどのような次数列を持つかが
分からないように思います。

321 名前:132人目の素数さん[] 投稿日:2017/06/07(水) 22:17:21.49 ID:54f7ZpML
>>314

2部補グラフを考えることにより、問題が簡単になるようには思えません。
7◆2VB8wsVUoo
2017/06/10(土) 04:34:02.27ID:fALuLzXC
8◆2VB8wsVUoo
2017/06/10(土) 04:34:20.75ID:fALuLzXC
9◆2VB8wsVUoo
2017/06/10(土) 04:34:39.84ID:fALuLzXC
10◆2VB8wsVUoo
2017/06/10(土) 04:34:57.24ID:fALuLzXC
11◆2VB8wsVUoo
2017/06/10(土) 04:35:15.65ID:fALuLzXC
12◆2VB8wsVUoo
2017/06/10(土) 04:35:34.69ID:fALuLzXC
13◆2VB8wsVUoo
2017/06/10(土) 04:35:54.18ID:fALuLzXC
14◆2VB8wsVUoo
2017/06/10(土) 04:36:11.87ID:fALuLzXC
15◆2VB8wsVUoo
2017/06/10(土) 04:36:16.76ID:fALuLzXC
16◆2VB8wsVUoo
2017/06/10(土) 04:36:35.93ID:fALuLzXC
17132人目の素数さん 転載ダメ©2ch.net
2017/06/12(月) 16:44:47.61ID:0ito7mL9
759 名前:デフォルトの名無しさん[] 投稿日:2017/06/12(月) 15:07:56.32 ID:yuw+moiO
グローバル変数の net というのは、関数の中で呼び出されている関数の中でも
使えるんですか?

760 名前:デフォルトの名無しさん[] 投稿日:2017/06/12(月) 15:09:49.85 ID:yuw+moiO
あ、できますね↓

glvar = "abc"

def myfunc1():
■■■■myfunc2()

def myfunc2():
■■■■print(glvar)

myfunc1()

761 名前:デフォルトの名無しさん[] 投稿日:2017/06/12(月) 15:11:05.87 ID:yuw+moiO
しかし、この斎藤っていう人、こんあひどいコードをよく恥ずかしげもなく公開できますね。

762 名前:デフォルトの名無しさん[] 投稿日:2017/06/12(月) 15:11:58.06 ID:yuw+moiO
なんでこの斎藤っていう人の本は高評価なんですか?

こんなひどいコード見たことがないです。正直言って。

763 名前:デフォルトの名無しさん[] 投稿日:2017/06/12(月) 15:12:31.37 ID:yuw+moiO
意図的に人を混乱に陥れようとしているかのようです。

764 名前:デフォルトの名無しさん[] 投稿日:2017/06/12(月) 15:22:22.17 ID:yuw+moiO
18◆2VB8wsVUoo
2017/06/12(月) 16:53:34.70ID:Lt75QqGT
■■■馬鹿板をスルと菅官房長官みたいな嘘吐きになります。そやし止めなさい。■■■

19◆2VB8wsVUoo
2017/06/12(月) 18:07:37.75ID:Lt75QqGT
20◆2VB8wsVUoo
2017/06/12(月) 18:07:56.27ID:Lt75QqGT
21◆2VB8wsVUoo
2017/06/12(月) 18:08:13.29ID:Lt75QqGT
22◆2VB8wsVUoo
2017/06/12(月) 18:08:33.89ID:Lt75QqGT
23◆2VB8wsVUoo
2017/06/12(月) 18:08:54.23ID:Lt75QqGT
24◆2VB8wsVUoo
2017/06/12(月) 18:09:12.26ID:Lt75QqGT
25◆2VB8wsVUoo
2017/06/12(月) 18:09:32.25ID:Lt75QqGT
26◆2VB8wsVUoo
2017/06/12(月) 18:09:35.51ID:Lt75QqGT
27◆2VB8wsVUoo
2017/06/12(月) 18:09:55.88ID:Lt75QqGT
28◆2VB8wsVUoo
2017/06/12(月) 18:10:13.90ID:Lt75QqGT
29◆2VB8wsVUoo
2017/06/12(月) 18:10:34.03ID:Lt75QqGT
30132人目の素数さん 転載ダメ©2ch.net
2017/06/12(月) 21:00:03.50ID:bgpySfsf
346 名前:デフォルトの名無しさん[] 投稿日:2017/06/12(月) 18:38:21.92 ID:yuw+moiO
↓このプログラムですが、ひどすぎないですか?
斎藤康毅のディープラーニングの本のコードです。

def softmax(x):
■■■■if x.ndim == 2:
■■■■■■■■x = x.T
■■■■■■■■x = x - np.max(x, axis=0)
■■■■■■■■y = np.exp(x) / np.sum(np.exp(x), axis=0)
■■■■■■■■return y.T

■■■■x = x - np.max(x) # オーバーフロー対策
■■■■return np.exp(x) / np.sum(np.exp(x))

def cross_entropy_error(y, t):
■■■■if y.ndim == 1:
■■■■■■■■t = t.reshape(1, t.size)
■■■■■■■■y = y.reshape(1, y.size)
■■■■■■■■
■■■■# 教師データがone-hot-vectorの場合、正解ラベルのインデックスに変換
■■■■if t.size == y.size:
■■■■■■■■t = t.argmax(axis=1)
■■■■■■■■■■■■
■■■■batch_size = y.shape[0]
■■■■return -np.sum(np.log(y[np.arange(batch_size), t])) / batch_size

347 名前:デフォルトの名無しさん[] 投稿日:2017/06/12(月) 18:39:18.66 ID:yuw+moiO
def numerical_gradient(f, x):
■■■■h = 1e-4 # 0.0001
■■■■grad = np.zeros_like(x)
■■■■
■■■■it = np.nditer(x, flags=['multi_index'], op_flags=['readwrite'])
■■■■while not it.finished:
■■■■■■■■idx = it.multi_index
■■■■■■■■tmp_val = x[idx]
■■■■■■■■x[idx] = float(tmp_val) + h
■■■■■■■■fxh1 = f(x) # f(x+h)
■■■■■■■■
■■■■■■■■x[idx] = tmp_val - h
■■■■■■■■fxh2 = f(x) # f(x-h)
■■■■■■■■grad[idx] = (fxh1 - fxh2) / (2*h)
■■■■■■■■
■■■■■■■■x[idx] = tmp_val # 値を元に戻す
■■■■■■■■it.iternext()
■■■■■■■■
■■■■return grad
31132人目の素数さん
2017/06/13(火) 00:40:36.30ID:o0PC5jwG
 素人向けだと言っているだろ!
あまりの初心者むけに評判がいいんだよ!
32◆2VB8wsVUoo
2017/06/14(水) 05:31:37.26ID:6+DmjjrM
33◆2VB8wsVUoo
2017/06/14(水) 05:31:56.47ID:6+DmjjrM
34◆2VB8wsVUoo
2017/06/14(水) 05:32:16.45ID:6+DmjjrM
35◆2VB8wsVUoo
2017/06/14(水) 05:32:37.08ID:6+DmjjrM
36◆2VB8wsVUoo
2017/06/14(水) 05:32:56.70ID:6+DmjjrM
37◆2VB8wsVUoo
2017/06/14(水) 05:33:15.82ID:6+DmjjrM
38◆2VB8wsVUoo
2017/06/14(水) 05:33:33.65ID:6+DmjjrM
39◆2VB8wsVUoo
2017/06/14(水) 05:33:52.15ID:6+DmjjrM
40◆2VB8wsVUoo
2017/06/14(水) 05:34:11.48ID:6+DmjjrM
41◆2VB8wsVUoo
2017/06/14(水) 05:34:31.61ID:6+DmjjrM
42132人目の素数さん 転載ダメ©2ch.net
2017/06/17(土) 16:48:09.00ID:seT4nJ+a
似非爺の説教
43◆2VB8wsVUoo
2017/06/17(土) 17:22:58.27ID:x2f6D4gs
44132人目の素数さん 転載ダメ©2ch.net
2017/06/21(水) 13:30:21.63ID:qFl3BEr/
393 名前:デフォルトの名無しさん[] 投稿日:2017/06/21(水) 10:56:36.24 ID:CsbvaOkp
Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net	->画像>6枚
Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net	->画像>6枚
Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net	->画像>6枚

↑は浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)です。

重大な誤りを発見しました。

G が二部グラフであるための必要十分条件は、G を幅優先探索したときに同じ深さの補木辺がないことであると書かれていますが、
完全な誤りです。

具体的に言うと、「同じ深さの点を結ぶ補木辺がないときは、この色の割当てが実際に2彩色になっている。」と書かれていますが、
間違っています。

反例は3枚目の画像を参照してください。

394 名前:デフォルトの名無しさん[] 投稿日:2017/06/21(水) 11:00:57.46 ID:CsbvaOkp
訂正します:

Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net	->画像>6枚
Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net	->画像>6枚
Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net	->画像>6枚

↑は浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)です。

重大な誤りを発見しました。

G が二部グラフであるための必要十分条件は、G を幅優先探索したときに同じ深さの点を結ぶ補木辺がないことであると書かれていますが、完全な誤りです。

具体的に言うと、「同じ深さの点を結ぶ補木辺がないときは、この色の割当てが実際に2彩色になっている。」と書かれていますが、
間違っています。

反例は3枚目の画像を参照してください。

395 名前:デフォルトの名無しさん[] 投稿日:2017/06/21(水) 11:11:21.29 ID:CsbvaOkp
商品の説明
内容紹介
ネットワーク・人工知能の基礎となるグラフ・ネットワークを学ぶ

アマゾンに商品説明として、↑のように書かれています。

人工知能とグラフ・ネットワーク理論に何の関係があるのでしょうか?

この出版社は、「世界標準MIT教科書」などとタイトルに書いたり、売るためには
手段を選ばない出版社ですね。
45◆2VB8wsVUoo
2017/06/21(水) 13:59:16.27ID:cGYdNhEa
★★★数学徒は論理的な考察により客観的に暮らし、日頃から深い学術を志すべき。★★★

46◆2VB8wsVUoo
2017/06/21(水) 17:47:02.48ID:cGYdNhEa
47◆2VB8wsVUoo
2017/06/21(水) 17:47:24.68ID:cGYdNhEa
48◆2VB8wsVUoo
2017/06/21(水) 17:47:44.67ID:cGYdNhEa
49◆2VB8wsVUoo
2017/06/21(水) 17:48:06.71ID:cGYdNhEa
50◆2VB8wsVUoo
2017/06/21(水) 17:48:27.01ID:cGYdNhEa
51◆2VB8wsVUoo
2017/06/21(水) 17:48:46.12ID:cGYdNhEa
52◆2VB8wsVUoo
2017/06/21(水) 17:49:05.45ID:cGYdNhEa
53◆2VB8wsVUoo
2017/06/21(水) 17:49:23.75ID:cGYdNhEa
54◆2VB8wsVUoo
2017/06/21(水) 17:50:01.08ID:cGYdNhEa
55◆2VB8wsVUoo
2017/06/21(水) 17:50:21.07ID:cGYdNhEa
56132人目の素数さん 転載ダメ©2ch.net
2017/06/26(月) 16:31:09.67ID:gJHwrh/s
413 名前:デフォルトの名無しさん[] 投稿日:2017/06/26(月) 15:07:57.81 ID:wjem+ipT
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)ですが、この
本には強連結成分分解のアルゴリズムは書いてあるのですが、その正しさについて
の説明がありません。

「アルゴリズムの正当性については演習問題とする。」などと書かれているだけです。
そして、解答がありません。

解答をつけないほど簡単な問題でしょうか?

エイホ、ホップクロフト、ウルマン著『データ構造とアルゴリズム』に分かりやすい説明がありました。

414 名前:デフォルトの名無しさん[] 投稿日:2017/06/26(月) 15:09:29.86 ID:wjem+ipT
あ、よくみたら解答がありました。

415 名前:デフォルトの名無しさん[] 投稿日:2017/06/26(月) 15:14:33.33 ID:wjem+ipT
強連結成分分解のアルゴリズムはグラフ理論的な観点からは興味深いですが、
応用についてはあまりないようですね。

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)の「はじめに」に
「強連結成分分解はシステムの故障診断や効率的解析への応用があると言われている。」
などと書かれいます。浅野さん自身は応用について具体的な詳細を知らないと宣言して
いるようなものですね。

417 名前:デフォルトの名無しさん[] 投稿日:2017/06/26(月) 15:32:39.93 ID:wjem+ipT
ところで、LEDAというライブラリはお勧めですか?
57◆2VB8wsVUoo
2017/06/26(月) 16:33:18.63ID:dYpMJpMg
★★★忖度と処世術に汚染された日本人:権威主義的な支配と損したくない人達★★★
  ~~~芳雄氏が言う『研究者としての基本的態度』とは一体何だろうか~~~

佐藤幹夫:自分自身の素朴な疑問に真剣に耳を傾ける。⇒不滅の金字塔を打ち立てる。
糞父芳雄:人間関係を駆使し他人を操り根回しを行う。⇒ハリボテお教授として君臨。

隠蔽の財務省、嘘吐きの文科省、そして問答無用に屈服させる官邸。コレでも先進国?

(佐藤師がしてたのは本物の研究だ。だが)芳雄氏がしてたのはケケケ、ケンキュウ。
外見を繕って偉そう見せさえすれば何でもヨロシ。ほんで教授になりさえすれば研究の
中身なんて何でもヨロシ。そもそも論文なんてモンは、外国の権威ある雑誌に掲載され
さえすれば、その中身のギロンなんて何でもヨロシ。そやし適当に書いてしまえ~~~
中身がダメだと知ってて、ソレでもSTAP論文を外国に投稿して受理される。発覚したら
適当に言い逃れる醜い態度。オツムのダメな大学院生に「虚偽の良品ラベル」を貼って
世間に出荷するハリボテ大学は詐欺行為そのもの。世間に媚びを売って客商売に徹し、
『売れさえすれば学生の脳の質なんて何でもヨロシ』と居直る大学。そしてブランド名
だけを見て仕入れる世間。●●は一流大学やさかい、きっと優秀なエリートやろwww

中身を何も説明しないで、問答無用に上から押し付ける。ソレをイチャモンで騒いで、
そして邪魔して潰そうとする周囲の下々。大学教員も国会議事堂も、そして馬鹿板人の
遣ってる事も皆同じだ。日本人はバカ民族であり、今は外国にもちゃんとバレてるので
海外からも軽蔑されるだけであり、そのうちにどの国からも信用されなくなるだろう。

近視眼的で打算的な人生観を息子に押し付ける父親と、大脳に栄養が足りてない連中が
跋扈する永田町や霞が関に支配される国に住む不幸、一体どうしてくれるというのか。

■■■馬鹿板を続けたらオツムがスポンジ脳になるのでサッサと足を洗うべき。■■■

58132人目の素数さん
2017/06/26(月) 16:53:58.21ID:x1JD94Dw
このハゲー
おまえがいけ
おまえがちゃんとあやまってこり

これいじょうわたしをおこらせるな!
102 :
右や左の名無し様
2017/06/26(月) 16:51:43.50 ID:DV/Fl9ZZ
このハゲー ちゃうだろ!
おなじことをいわせるな

はげてるんですううううう

すみません スミマンセン スミマセン
59◆2VB8wsVUoo
2017/06/26(月) 17:12:46.84ID:dYpMJpMg
■■■馬鹿板をスルのは頭の悪い行為であり、そやし数学徒が行ってはならない。■■■

60◆2VB8wsVUoo
2017/06/26(月) 18:54:11.44ID:dYpMJpMg
61◆2VB8wsVUoo
2017/06/26(月) 18:54:31.20ID:dYpMJpMg
62◆2VB8wsVUoo
2017/06/26(月) 18:54:51.09ID:dYpMJpMg
63◆2VB8wsVUoo
2017/06/26(月) 18:55:10.68ID:dYpMJpMg
64◆2VB8wsVUoo
2017/06/26(月) 18:55:30.45ID:dYpMJpMg
65◆2VB8wsVUoo
2017/06/26(月) 18:55:51.47ID:dYpMJpMg
66◆2VB8wsVUoo
2017/06/26(月) 18:56:10.97ID:dYpMJpMg
67◆2VB8wsVUoo
2017/06/26(月) 18:56:35.40ID:dYpMJpMg
68◆2VB8wsVUoo
2017/06/26(月) 18:56:54.18ID:dYpMJpMg
69◆2VB8wsVUoo
2017/06/26(月) 18:57:12.74ID:dYpMJpMg
70132人目の素数さん 転載ダメ©2ch.net
2017/06/27(火) 21:19:57.73ID:lcYLIs+q
419 名前:デフォルトの名無しさん[] 投稿日:2017/06/27(火) 13:16:02.75 ID:NGLAHv1W
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)を読んでいます。

G のトポロジカルラベリングについては説明があるのですが、トポロジカルソートの応用例が
全く書かれていません。

勉強するモチベーションが全くありません。

著者は一体何を考えているのでしょうか?

424 名前:デフォルトの名無しさん[] 投稿日:2017/06/27(火) 19:32:13.18 ID:NGLAHv1W
あ、その後の有向無閉路ネットワークの最長パスを求めるアルゴリズムで
トポロジカルラベリングが使われていました。

なかなか面白い応用ですね。

この本、説明にちょっと粗雑なところもありますが、見せ場があって楽しいですね。

425 名前:デフォルトの名無しさん[] 投稿日:2017/06/27(火) 19:34:40.25 ID:NGLAHv1W
有向無閉路ネットワークという制限が強すぎますね。

でもこの制限のおかげでちょっと面白いトポロジカルラベリングの応用例が見れたわけですね。
71132人目の素数さん 転載ダメ©2ch.net
2017/06/28(水) 11:03:25.62ID:28hknpW0
431 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 05:10:12.09 ID:6P8PW2pA
>>430

そのインド人の本は、アルゴリズムの正当性のまともな説明がありません。

計算量の評価についてもまともな説明がありmせん。

セジウィックのAlgorithms 4th Editionはいい本ですが、計算量の評価については
まともな説明がないように思います。

432 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 05:17:01.98 ID:6P8PW2pA
D40

T をグラフ G の全域木とする。
C を G のサイクルとする。
AB を C および T に含まれる辺とする。

このとき、 T から AB を除去し、辺 UV を追加したときに、
依然として G の全域木であるような辺 UV が C の中に
含まれることを示せ。

433 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 06:24:05.46 ID:6P8PW2pA
>>432


T は木であるからサイクルを含まない。
よって、 C には T に含まれないような辺が少なくとも一つは存在する。
T は全域木であるから、そのような辺の両端点を結ぶ T の辺のみからなる(一意的な)パスが存在する。

仮に、 T に含まれないような C の辺たちの両端点を結ぶ T の辺のみからなるパスたちがすべて AB を含まない
と仮定すると、 A から B への T の辺のみからなるパスで辺 AB を含まないようなものが存在することになる。
A, B という A から B へのパスは、辺 AB を含み T の辺のみからなる。よって、 A から B への T の辺のみから
なるパスが2つ以上存在することになるが、これは木の性質に反する。

よって、 T に含まれないような C の辺たちの両端点を結ぶ T の辺のみからなるパスたちの中には、 AB を含む
ようなものが存在する。そのようなパスを U, …, A, B, …, V とする。 T から AB を除去し、辺 UV を追加し
たときにできる部分グラフは明らかに T と同じ数の辺をもち、依然として連結なままである。点の数が v で
辺の数が v - 1 であるような連結なグラフは木であるから、そうような部分グラフは木である。
72132人目の素数さん 転載ダメ©2ch.net
2017/06/28(水) 11:05:10.30ID:28hknpW0
435 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 10:22:23.33 ID:6P8PW2pA
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)を読んでいます。

↓は、ある点から各点への最長パスを求めるプログラムのメイン関数です。
「出発点を入力してください」などと出力していますが、出発点は 1 でないとダメです。
なぜかというと depth_first() 関数がかならず 1 から深さ優先探索を開始するからです。
↓を見ると、あたかも、出発点に選択の余地があるかのようです。なぜ、こんなことを
しているのか意味不明です。

int main(void){
■■■■directed_network_input();
■■■■// 有向ネットワークの辺数m,点数n,各辺の始点,終点,長さが決定される
■■■■dicomp_incidence_list_construct(); // 接続辺リストが構成される
■■■■printf("出発点を入力してください\n");
■■■■scanf("%d", &s);
■■■■printf("出発点 = %d \n", s); // sからすべての点が到達可能であることを仮定
■■■■depth_first(); // 深さ優先探索をして後行順ラベルを求める
■■■■tpsort(); // トポロジカルソートを行う(tporder[1]==sとなることを仮定)
■■■■longestpath_from(s);// sからの到達可能な点への最長パスが計算される
■■■■longestpath_output();// sからの到達可能な点への最長パスが出力される
■■■■return 0;
}
73132人目の素数さん 転載ダメ©2ch.net
2017/06/28(水) 11:05:37.33ID:28hknpW0
436 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 10:54:52.65 ID:6P8PW2pA
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)を読んでいます。

ひどいバグを発見しました。

void longestpath_from(int s){// sからの到達可能な点への最長パスを計算する関数
■■■■int a, j, v, w;
■■■■dmax[s]=0; // sからsへの最長パスの長さは0である
■■■■path[s]=0; // sからの到達可能な点への最長パス木の根がsである
■■■■for (j = 1; j <= n; j++) {// トポロジカルソートに基づいて
■■■■■■■■v= tporder[j];
■■■■■■■■// sからvまでの最長パスの長さdmax[v]とパス上でvの直前の点path[v]の計算
■■■■■■■■a=revedgefirst[v]; // vを終点とする辺のリストの先頭の辺がaである
■■■■■■■■w=tail[a]; // wはaの始点
■■■■■■■■if(j == 1) printf("v = %2d, a = %2d, w = %2d", v, a, w); //debug
■■■■■■■■dmax[v]=dmax[w]+length[a]; // 式(4.2)に基づくdmax[v]の初期設定
■■■■■■■■path[v]=w; // 式(4.2)に基づくpath[v]の初期設定
■■■■■■■■a=revedgenext[a]; // aの次の辺をaとする
■■■■■■■■while (a != 0) {// vを終点とする辺のリストの末尾の辺になるまで繰り返す
■■■■■■■■■■■■w=tail[a]; // wはaの始点
■■■■■■■■■■■■if (dmax[v] < dmax[w]+length[a]){// wを経由したほうがより長いとき
■■■■■■■■■■■■■■■■dmax[v] = dmax[w]+length[a]; // wを経由するほうに更新する
■■■■■■■■■■■■■■■■path[v]=a; // aに更新する
■■■■■■■■■■■■}
■■■■■■■■■■■■a=revedgenext[a]; // aの次の辺をaとする
■■■■■■■■}
■■■■}
}
74132人目の素数さん 転載ダメ©2ch.net
2017/06/28(水) 11:38:19.15ID:28hknpW0
438 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 11:02:48.67 ID:6P8PW2pA
↑の for 文は j = 1 から始まっています。

v == tporder[1] == 1 です。
a == revedgefirst[1] == 0 です。

ところが、この本では配列のインデックスは 1 からしか利用していません。
インデックスが 0 の要素は初期化すらしていません。
どうも配列を初期化しないと値は不定だそうですが、実際には 0 で初期化されることが
多いようです。

仕様では不定であるはずの

tail[0]
dmax[0]
length[0]

がたまたま 0 で初期化されるため、偶然、問題なく動作しています。

正しくは、

for 文は j = 2 から始めなくては駄目です。

439 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 11:19:51.44 ID:6P8PW2pA
あ、もう一つバグがありました↑

path[v]=w; // 式(4.2)に基づくpath[v]の初期設定

となっていますが、

path[v]=a; // 式(4.2)に基づくpath[v]の初期設定

でなければなりません。
75132人目の素数さん 転載ダメ©2ch.net
2017/06/28(水) 14:16:38.06ID:EQaFJu//
441 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 12:34:24.00 ID:6P8PW2pA
>>440

そうですが、

for(j = 1;

とすると

意図せず配列[0]を使うことになってしまいます。

この値がたまたま 0 で初期化されていて、かつ 0 であれば正しく動くため、
問題が表面化していないだけです。

442 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 12:37:24.37 ID:6P8PW2pA
有向無閉路ネットワークの最長パスをトポロジカルラベリングを利用して、
求めるアルゴリズムって他の本に載っていますか?

あまりにも特殊すぎて載っていないのではないかと推測しますが。

この本は、鮮やかに解けるように問題を特殊化して見せ場を作っていますね。

443 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 13:17:27.40 ID:6P8PW2pA
>>426

その本を読むのでしたら、

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)

のほうがCプログラムも載っていますし、面白いと思いますよ。

オイラーグラフの一筆書きのプログラムがあったりします。
76132人目の素数さん
2017/06/28(水) 14:36:40.94ID:wBz59QIa
番組冒頭、伊集院は豊田氏による元秘書への暴言を録音した模様を、テレビが
短時間に何度も流すことに言及していた。元秘書の男性が運転中に録音した
ボイスレコーダーには、豊田氏とみられる女性の声で「このハゲーー!!」
違うだろ!!」などと罵倒するほか、この男性を殴ったとみられる打撃音も
収められている。

伊集院は「『ハゲーー!!』ってところを3~5分のニュースで4回くらい
オンエアするんだよね。多くない?」と疑問を口にする。続けて、
精神的苦痛を受ける人も世間にいると伊集院は持論を展開し「ハゲてる人
はこたえてると思うよ、相当ね」「あと、ああいう圧に耐えながら仕事
している人は、怖ぇと思うんだけどな」と指摘したのだった。
77◆2VB8wsVUoo
2017/06/28(水) 22:30:46.21ID:A63zUC8I
78◆2VB8wsVUoo
2017/06/28(水) 22:31:16.23ID:A63zUC8I
79◆2VB8wsVUoo
2017/06/28(水) 22:31:35.90ID:A63zUC8I
80◆2VB8wsVUoo
2017/06/28(水) 22:31:57.00ID:A63zUC8I
81◆2VB8wsVUoo
2017/06/28(水) 22:32:17.12ID:A63zUC8I
82◆2VB8wsVUoo
2017/06/28(水) 22:32:36.64ID:A63zUC8I
83◆2VB8wsVUoo
2017/06/28(水) 22:32:55.68ID:A63zUC8I
84◆2VB8wsVUoo
2017/06/28(水) 22:33:16.22ID:A63zUC8I
85◆2VB8wsVUoo
2017/06/28(水) 22:33:36.05ID:A63zUC8I
86◆2VB8wsVUoo
2017/06/28(水) 22:33:55.20ID:A63zUC8I
87◆2VB8wsVUoo
2017/06/28(水) 22:34:13.90ID:A63zUC8I
88132人目の素数さん 転載ダメ©2ch.net
2017/06/29(木) 12:56:04.43ID:CtSdz1EQ
439 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 11:19:51.44 ID:6P8PW2pA
あ、もう一つバグがありました↑
path[v]=w; // 式(4.2)に基づくpath[v]の初期設定
となっていますが、
path[v]=a; // 式(4.2)に基づくpath[v]の初期設定
でなければなりません。
441 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 12:34:24.00 ID:6P8PW2pA
>>440
そうですが、
for(j = 1;
とすると
意図せず配列[0]を使うことになってしまいます。

この値がたまたま 0 で初期化されていて、かつ 0 であれば正しく動くため、
問題が表面化していないだけです。

442 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 12:37:24.37 ID:6P8PW2pA
有向無閉路ネットワークの最長パスをトポロジカルラベリングを利用して、
求めるアルゴリズムって他の本に載っていますか?

あまりにも特殊すぎて載っていないのではないかと推測しますが。

この本は、鮮やかに解けるように問題を特殊化して見せ場を作っていますね。

443 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 13:17:27.40 ID:6P8PW2pA
>>426

その本を読むのでしたら、

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)

のほうがCプログラムも載っていますし、面白いと思いますよ。

オイラーグラフの一筆書きのプログラムがあったりします。

447 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 18:29:25.09 ID:6P8PW2pA
>>444

このプログラムだけ見てももちろん分からないと思います。

a == revedgefirst[1] == 0 なので、 tail[a] == tail[0] です。

448 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 18:29:51.34 ID:6P8PW2pA
訂正します:

>>445

このプログラムだけ見てももちろん分からないと思います。

a == revedgefirst[1] == 0 なので、 tail[a] == tail[0] です。

449 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 18:33:38.48 ID:6P8PW2pA
さらに、

v == tporder[1] == 1 です。
89◆2VB8wsVUoo
2017/06/29(木) 15:54:39.97ID:0RPSduFk
90◆2VB8wsVUoo
2017/06/29(木) 15:55:08.96ID:0RPSduFk
91◆2VB8wsVUoo
2017/06/29(木) 15:55:29.12ID:0RPSduFk
92◆2VB8wsVUoo
2017/06/29(木) 15:55:50.47ID:0RPSduFk
93◆2VB8wsVUoo
2017/06/29(木) 15:56:11.19ID:0RPSduFk
94◆2VB8wsVUoo
2017/06/29(木) 15:56:28.88ID:0RPSduFk
95◆2VB8wsVUoo
2017/06/29(木) 15:56:51.36ID:0RPSduFk
96◆2VB8wsVUoo
2017/06/29(木) 15:57:09.38ID:0RPSduFk
97◆2VB8wsVUoo
2017/06/29(木) 15:57:35.83ID:0RPSduFk
98◆2VB8wsVUoo
2017/06/29(木) 15:57:55.94ID:0RPSduFk
99132人目の素数さん 転載ダメ©2ch.net
2017/07/01(土) 10:23:15.92ID:H85bg2CR
456 名前:デフォルトの名無しさん[] 投稿日:2017/07/01(土) 09:37:54.54 ID:OLSj8alI
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)
ホップクロフト - カープのアルゴリズムのところを読んでいます。


do {// マッチされていない左端点からマッチされていない右端点へのパスがある限り
■■■■levelgraph(); // レベルグラフの構成
■■■■if (t_found != n+2) augmentation(); // パスがあるときにはマッチングの更新
} while (t_found != n+2);

などというコードがあります。

do {// マッチされていない左端点からマッチされていない右端点へのパスがある限り
■■■■levelgraph(); // レベルグラフの構成
■■■■if (t_found == n+2) break;
■■■■else augmentation(); // パスがあるときにはマッチングの更新
} while (1);

と書いた方が分かりやすいですよね。

augmentation() 内では、グローバル変数 t_found の値は変更されません。
なので、以下のように書くのが標準的だと思います。

levelgraph();
while(t_found != n + 2){
■■■■augmentation();
■■■■levelgraph();
}
100132人目の素数さん 転載ダメ©2ch.net
2017/07/01(土) 10:23:45.90ID:H85bg2CR
457 名前:デフォルトの名無しさん[] 投稿日:2017/07/01(土) 09:42:20.68 ID:OLSj8alI
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)を読んでいます。

a = edgefirst[v1];
while(a != 0){
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
a = edgenext[a];
}

などというコードが本書のソースコードのいたるところで使われています。

↓のように書くべきですよね。

for(a = edgefirst[v1]; a != 0; a = edgenext[a]){
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
}

458 名前:デフォルトの名無しさん[] 投稿日:2017/07/01(土) 09:46:11.85 ID:OLSj8alI
茨木俊秀さんの本でも感じましたが、ひどいコードを書く人が多いですよね。

一番、驚いたのが野崎昭弘さんの本です。

goto 文を使わなくていいところで常用しています。

461 名前:デフォルトの名無しさん[] 投稿日:2017/07/01(土) 09:59:03.29 ID:OLSj8alI
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)
ホップクロフト - カープのアルゴリズムのところを読んでいます。

for (v = 1; v <= n; v++) parent[v] = unvisited;

というコードがあります。

点 v の親の処理ですが、深さ優先探索で使う定数である unvisited == -1 を流用しています。
親は訪問するものではないにもかかわらずです。
単に -1 という値が使いたいだけです。

ひどいコードです。
101◆2VB8wsVUoo
2017/07/02(日) 13:58:15.18ID:mFP5+etN
102◆2VB8wsVUoo
2017/07/02(日) 13:58:34.31ID:mFP5+etN
103◆2VB8wsVUoo
2017/07/02(日) 13:58:54.38ID:mFP5+etN
104◆2VB8wsVUoo
2017/07/02(日) 13:59:14.06ID:mFP5+etN
105◆2VB8wsVUoo
2017/07/02(日) 13:59:33.57ID:mFP5+etN
106◆2VB8wsVUoo
2017/07/02(日) 13:59:51.96ID:mFP5+etN
107◆2VB8wsVUoo
2017/07/02(日) 14:00:09.99ID:mFP5+etN
108◆2VB8wsVUoo
2017/07/02(日) 14:00:32.51ID:mFP5+etN
109◆2VB8wsVUoo
2017/07/02(日) 14:00:52.12ID:mFP5+etN
110◆2VB8wsVUoo
2017/07/02(日) 14:01:09.93ID:mFP5+etN
111132人目の素数さん
2018/06/24(日) 09:44:36.43ID:CiX9DLBe
111
112132人目の素数さん
2018/07/28(土) 21:09:32.60ID:Tc6OBNZE
微積分ばかり読んで馬鹿アスペは大丈夫な人なのでしょうか?
113132人目の素数さん
2018/07/29(日) 20:59:50.92ID:MefUqIVV
お前にはプログラムの才能はない(笑)
114132人目の素数さん
2018/08/03(金) 18:40:09.51ID:7nSNATAS
ミルカちゃん
115132人目の素数さん
2018/08/04(土) 10:46:34.73ID:1ZWGxFZ0
に電気アンマされたい
116132人目の素数さん
2018/08/06(月) 19:58:12.92ID:msOD46p7
Graph Minor Theorem まで読み終わった
117132人目の素数さん
2020/10/04(日) 22:37:52.35ID:3NNl8xHn
真田重雄は地獄へ落ちて幾十年だな
この世と地獄では時の流れが違うだろうけど

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



lud20250816130000
このスレへの固定リンク: http://5chb.net/r/math/1497007079/
ヒント:5chスレのurlに http://xxxx.5chb.net/xxxx のようにbを入れるだけでここでスレ保存、閲覧できます。

TOPへ TOPへ  

このエントリをはてなブックマークに追加現在登録者数177 ブックマークへ


全掲示板一覧 この掲示板へ 人気スレ | Youtube 動画 >50 >100 >200 >300 >500 >1000枚 新着画像

 ↓「Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net ->画像>6枚 」を見た人も見ています:
【Bloomberg】Japan minister says higher "cultural standard" helped beat virus [マスク着用のお願い★]
「The Telegraph」「Tech Radar」などのGOTYが発表、「ゼルダの伝説 BotW」が80個目の栄冠
「つばきファクトリー 10th Anniversary Live Tour 2025 Spring ~OUR DAYS GO ON~」FC先行受付のお知らせ ★2
【トランプ大統領】Happy Birthday to Melania, our great First Lady! [ちーたろlove&peace★]
Griffiths-Harris, Principles of Algebraic Geometry.
Animelo Summer Live 2019 -STORY-26th
Happy Mary Christmas
SEVENTH DARK セブンスダーク Part35【Laplace】
Welcome to the new 'nida' board!
Donald E. Knuth The Art of Computer Programming を読む。
Animelo Summer Live 2025 “ThanXX!” DAY5
Animelo Summer Live 2025 “ThanXX!” DAY1
Animelo Summer Live 2025 “ThanXX!” DAY2
THE IDOLM@STER CINDERELLA GIRLS Shout out Live!!! Day2 Part2 [転載禁止★]
THE MAD CAPSULE MARKETS 17
【Netflix】MCU marvel作品総合【ディフェンダー】
【実況】ラブライブ!虹ヶ咲学園スクールアイドル同好会 UNIT LIVE & FAN MEETING vol.4 R3BIRTH ~First DELIGHT~ ☆2
【音楽】Mrs.GREEN APPLE「もはや別人」紅白初出場の3人組バンド 活動休止→再開からの激的イメチェンにファン困惑 [Ailuropoda melanoleuca★]
Canon EOS 6D Mark II part15
Canon EOS 5D Mark Ⅳ part21
Canon EOS 7D Mark II part23
Canon EOS 5D Mark Ⅳ part27
Canon EOS 5D Mark Ⅳ part33
ヤフオクでポンコツ買うDaniel Kitty 爺 Part.2
Inter-universal geometry と ABC予想 否定派
Canon EOS 5D markII part 51
Canon EOS 7D Mark II part22
Canon EOS 6D Mark II part17
Canon EOS 5D Mark Ⅳ part32
Canon EOS 5D Mark Ⅳ part30
Canon EOS 5D Mark Ⅳ part25
Canon EOS 5D Mark Ⅳ part24
Canon EOS 5D Mark Ⅳ part38
【ハイルドライバー】Mark&Daniel【大理石】
NITRO MICROPHONE UNDERGROUND Part.32
「number theory → arithmetic」みたいなカッコつけ
CorelDRAW Graphics Suite X5
Inter-universal geometry と ABC予想 31
Inter-universal geometry と ABC予想 35
Inter-universal geometry と ABC予想 29
Inter-universal geometry と ABC予想 18
Intel HD Graphics 総合スレッド★2
Inter-universal geometry と ABC予想 34
Inter-universal geometry と ABC予想 28
Inter-universal geometry と ABC予想 21
Inter-universal geometry と ABC予想 16
CUBOT kingkong mini Part2
Intel Iris Plus Graphicsでゲームしたらどうなんの?教えて
HTT (Higher Topos Theory) について
Intel HD Graphics 総合スレッド★3
Daniel Craig's Wife【霊長】Rachel Weisz
Inter-universal geometry と ABC予想 41
Inter-universal geometry と ABC予想 37
Inter-universal geometry と ABC予想 40
Inter-universal geometry と ABC予想 14
Dies irae PANTHEON 総合スレ Part.4 ©bbspink.com
In a sandwich, the cucumber being between the bread is why people eat them.
【音楽】『LIVE the SPEEDSTAR』に斉藤和義、GRAPEVINE、UA、矢野顕子が出演決定 [湛然★]
■AMD RX 6000 Series Graphics Cards■実況会場 10/28(水)25:00(日本時間)
【米国】安倍首相、米アーリントン国立墓地で献花 (動画のみ AFP, USA Military Channel 2件)
Canon EOS R5 MarkII Part5
Canon EOS R6 MarkII Part1
Canon EOS 6D Mark II part9
Canon EOS 7D Mark II part7
Canon EOS 6D Mark II part4

人気検索: child porn 無撫 teen 2016 チア 35 キャミ Sex pedo little girls 和日曜ロリ Daisy Kids
04:17:10 up 137 days, 5:15, 1 user, load average: 18.25, 18.42, 20.12

in 0.075160980224609 sec @0.075160980224609@0b7 on 090117