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

**デフォルトの名無しさん転載ダメ©2ch.net** · 2016/06/19(日) 14:47:29.63

このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。

　　　　　　　　　　　　　　　　　　京都大学霊長類研究所

データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
http://echo.2ch.net/test/read.cgi/tech/1362301811/

【関連スレ】
3Dアルゴリズム全般
http://toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
http://toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
http://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

**デフォルトの名無しさん** · 2017/06/05(月) 21:17:56.80

>>352

今、グラフ理論の本を読んでいるのですが、その演習問題の
答えを計算機で計算したいと思いプログラムを作っています。

手計算でできる問題なので計算量とかは無問題です。

情報、ありがとうございました。

**デフォルトの名無しさん** · 2017/06/08(木) 13:28:45.57

>>352
thx

**デフォルトの名無しさん** · 2017/06/10(土) 01:09:12.89

セジウィックのアルゴリズムCはコルメン他の本とは対極にあるような本だね。
どっちもどっち。

**デフォルトの名無しさん** · 2017/06/10(土) 22:49:54.03

セジウィックのアルゴリズムCは言葉足らず。

**デフォルトの名無しさん** · 2017/06/11(日) 08:24:40.56

セジウィックのアルゴリズムＣは定義がダメダメ。

例：
連結グラフの極大木とは、すべての頂点を含む部分グラフであって、
木である限りできるだけ多くの辺をもつものをいう。

この定義だと連結グラフに極大木が常に存在するというのが定理になってしまう。
が、証明せずに、この事実を以下で使っている。

**デフォルトの名無しさん** · 2017/06/11(日) 11:00:58.83

セジウィックのアルゴリズムＣは、訳も最低。

**デフォルトの名無しさん** · 2017/06/16(金) 18:04:24.35

浅野孝夫著『アルゴリズムの基礎とデータ構造数理とCプログラム』（近代科学社）

ポインタを使えるCでアルゴリズムを実装しておきながらポインタを使わず、
配列を使ってポインタの機能を実現するという面倒なことをしています。

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

**デフォルトの名無しさん** · 2017/06/16(金) 18:08:47.36

javaの逆ポートだろう

**デフォルトの名無しさん** · 2017/06/16(金) 18:30:17.58

浅野孝夫著『アルゴリズムの基礎とデータ構造数理とCプログラム』（近代科学社）

の公式ページからソースコードをダウンロードできます。

たくさんのソースコードがあるのですが、こういうのを実行するときってみなさんは
どうしていますか？

Visual Studio を使っているのですが、一つのソースファイルに対して、いちいち
プロジェクトを作っていると面倒なんですが、どうすればいいですか？

**デフォルトの名無しさん** · 2017/06/16(金) 18:31:46.91

コマンドプロンプトからコマンドを実行してコンパイルをしたりする原始的なやり方
は避けたいです。

**デフォルトの名無しさん** · 2017/06/16(金) 18:47:18.97

なんだ
ステマか

**デフォルトの名無しさん** · 2017/06/16(金) 20:42:10.07

原始的なやり方×
基本的なやり方〇

**デフォルトの名無しさん** · 2017/06/16(金) 20:54:00.90

探せば学習用のC言語インタプリタとかあるんじゃない

**デフォルトの名無しさん** · 2017/06/16(金) 21:27:28.11

ちょっとサンプルコードを走らせるかって程度なら
Online IDEとか使えばよいのに

**デフォルトの名無しさん** · 2017/06/16(金) 21:42:24.80

そもそも何でファイルごとにわざわざプロジェクト作るような原始的なことやってるの

**デフォルトの名無しさん** · 2017/06/16(金) 22:44:29.43

mainの数だけプロジェクトが必要だから？

**デフォルトの名無しさん** · 2017/06/17(土) 15:06:03.16

プロセス増えるだけだからプロジェクトは増やさなくてもいいんじゃね

**デフォルトの名無しさん** · 2017/06/17(土) 18:14:18.11

アルゴリズムとデータ構造の本のソースコードを見ると、よくグローバル変数を
多用していて非常に分かりにくいことが多いです。

グローバル変数を使うのは良くないというのをよく目にしますが、なぜ、
コンピュータサイエンスのプロであるはずのアルゴリズムとデータ構造の本の
著者がそんなプログラムを書くのでしょうか？

**デフォルトの名無しさん** · 2017/06/17(土) 18:18:02.53

例えば、

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

という本のソースプログラムが分かりにくいです。

拡張子が「.h」のファイルにグローバル変数を定義して使いまわしています。

さらに、その拡張子が「.h」のファイル内で「emaxsize」というのがありますが
それが何なのかが書いてありません。

その拡張子が「.h」のファイルを利用するファイル内で、「emaxsize」を設定しています。

こういうのはありなんでしょうか？

あちこちいろいろなファイルを見ないと、全体が分かりません。

**デフォルトの名無しさん** · 2017/06/17(土) 18:18:09.88

サンプルだから

**デフォルトの名無しさん** · 2017/06/17(土) 18:19:41.47

>>371
Javaしか使ったことない人が知ったかぶりでCの本出すからそうなる
捨てろ

**デフォルトの名無しさん** · 2017/06/17(土) 18:19:49.58

全然、プログラム作りの参考になりません。

ただ、例外もあります。

セジウィックの『Algorithms』という赤い本は、参考になります。

**デフォルトの名無しさん** · 2017/06/17(土) 18:21:15.46

>>373

でも、コード自体は非常に巧妙で優れています。

**デフォルトの名無しさん** · 2017/06/17(土) 20:50:11.36

そういえば、茨木俊秀の本のプログラムもひどかったような。

**デフォルトの名無しさん** · 2017/06/17(土) 22:37:25.92

グローバル変数を避けようとかはソフトウェア工学の話で、コンピューター科学とは別の分野なんだよ。

**デフォルトの名無しさん** · 2017/06/17(土) 23:06:32.77

ソフトウェア工学の基本すら知らないんですかね？

**デフォルトの名無しさん** · 2017/06/18(日) 00:34:44.62

グローバル変数を使った方が、説明しやすいとか、
ソースコードがわかりやすいとか

本の目的が、アルゴリズムの説明だから、
グローバル変数を使って、わかりやすく説明するのも、OK

物事には強弱・重要度があるから、
重要な事を説明する際、重要でない事は無視してもよい

これを、TPO と言って、強弱を付けられる人は、空気を読める

ちょっとしたプログラミングに、型チェックする、Javaなどを使わず、
Rubyで書くのもそう。
ラフな会合に、盛装して行かないのもそう

**デフォルトの名無しさん** · 2017/06/18(日) 12:26:58.32

掲示板のTPO弁えない人にTPO語ってもしょうがないよ

**デフォルトの名無しさん** · 2017/06/18(日) 12:39:15.20

グローバル変数を明らかに、分かりにくいやり方で使っています。

何の利点もないと思います。

**デフォルトの名無しさん** · 2017/06/18(日) 13:30:23.31

もしかして、理論ばかりに興味があり、プログラムを作ったことがないんですかね？

**デフォルトの名無しさん** · 2017/06/18(日) 14:37:44.92

プログラム教本ではなくアルゴリズム解説本だからでしょ
擬似言語で書いている場合のが多いと思うけど

**デフォルトの名無しさん** · 2017/06/18(日) 15:37:30.01

最初から完成してたらおまいらの仕事無くなっちゃうだろ

**デフォルトの名無しさん** · 2017/06/18(日) 18:10:10.06

楽器やってるひとがいってたよ。自分がつかえる技術を全部つかうわけじゃない

**デフォルトの名無しさん** · 2017/06/18(日) 20:13:26.60

浅野孝夫の本。

ちょっと説明が足りないところがある。
完成度がやや低い。
他の日本人の本よりはまし。

プログラムは巧妙。

**デフォルトの名無しさん** · 2017/06/18(日) 20:48:27.00

こんなところに日記書く人って、相当追い詰められてるんだろうな。

**デフォルトの名無しさん** · 2017/06/19(月) 04:29:40.16

こんなところだから何書いてもいいよ

**デフォルトの名無しさん** · 2017/06/19(月) 09:50:06.41

ステマよりグロい

**デフォルトの名無しさん** · 2017/06/19(月) 12:02:27.97

浅野孝夫の本。

深さ優先探索とか幅優先探索の説明を言葉で長々としています。
そんなことするより、コードを見せたほうがいいと思うんですよね。
コードを見れば一目で分かりますよね。

**デフォルトの名無しさん** · 2017/06/19(月) 12:05:01.80

もうおめーが執筆しろよ

**デフォルトの名無しさん** · 2017/06/19(月) 13:13:41.68

コードはあくまで例なので解説が先

**デフォルトの名無しさん** · 2017/06/21(水) 10:56:36.24

http://imgur.com/9QGwvmM.jpg
http://imgur.com/j3Dp32V.jpg
http://imgur.com/iJhKoqM.jpg

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

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

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

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

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

**デフォルトの名無しさん** · 2017/06/21(水) 11:00:57.46

訂正します：

http://imgur.com/9QGwvmM.jpg
http://imgur.com/j3Dp32V.jpg
http://imgur.com/iJhKoqM.jpg

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

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

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

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

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

**デフォルトの名無しさん** · 2017/06/21(水) 11:11:21.29

商品の説明
内容紹介
ネットワーク・人工知能の基礎となるグラフ・ネットワークを学ぶ

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

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

この出版社は、「世界標準MIT教科書」などとタイトルに書いたり、売るためには
手段を選ばない出版社ですね。

**デフォルトの名無しさん** · 2017/06/21(水) 12:35:50.38

>>395
自分の想像力の欠如で批判しないほうがいいよ

**デフォルトの名無しさん** · 2017/06/21(水) 12:37:14.26

外国には「たのしいRuby」が無い

日本人が20時間で勉強できることを、何十時間も掛けて勉強して、なおかつ理解できない。
だから、MIT に頼る

外人でも知っている人は、Ruby でツールを作る。
Chef, Vagrant, SASS とか

Homebrew もRubyで作られているのだから、
Apple は、もっとRubyに力を入れるべき

**デフォルトの名無しさん** · 2017/06/21(水) 12:53:00.17

>>394
幅優先探索わかる？

**デフォルトの名無しさん** · 2017/06/21(水) 12:54:37.96

>>394
３枚目は補木辺があって２部グラフではないので、
別におかしくないのでは

**デフォルトの名無しさん** · 2017/06/21(水) 13:14:54.71

>>399

「同じ深さの点を結ぶ補木辺がないときは、この色の割当てが実際に2彩色になっている。」

3枚目の画像には同じ深さの点を結ぶ補木辺がありません。
ですが、2彩色ではありません。

**デフォルトの名無しさん** · 2017/06/21(水) 13:31:42.95

松坂君のアスペ日記３

Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net
http://rio2016.2ch.net/test/read.cgi/math/1497007079/

**デフォルトの名無しさん** · 2017/06/21(水) 13:33:59.73

要するに、↓が間違っているわけです。

「補木辺は、同じ深さの点を結んでいるか、あるいは深さが 1 異なる点を結んでいることに注意しよう。」

**デフォルトの名無しさん** · 2017/06/21(水) 13:55:32.90

ここじゃなくて著者なり出版社なりに連絡しなよ
その方がちゃんと議論できるだろうし修正されればあとから読む人の為になるよ

**デフォルトの名無しさん** · 2017/06/21(水) 14:30:39.96

>>400
幅優先で探索木作ったら同じ深さを結ぶ補木辺ができるから二部グラフでないことがわかる

**デフォルトの名無しさん** · 2017/06/21(水) 16:12:29.38

>394
三枚目の図は、反例になっていない。
あなたが幅優先探索を理解できていないだけで、書籍の記述は間違っていないよ。
根でない2つの頂点は、どちらも、根から辺が張られていて、根と隣接しているのだから、同じ深さの位置にある。

**デフォルトの名無しさん** · 2017/06/21(水) 18:57:35.69

あ、勘違いしました。

無向グラフでしたね。

**デフォルトの名無しさん** · 2017/06/21(水) 19:28:34.24

教科書だって間違いはいくらでもある。
だからといって、間違いらしきものを見つけて喜々としてあげつらうのではなく、
自分の解釈ではこうだが違うのだろうかという態度で質問しておけばよかったね。

**デフォルトの名無しさん** · 2017/06/21(水) 22:04:49.64

何がいんだろ

**デフォルトの名無しさん** · 2017/06/23(金) 09:05:15.05

>>393-394
他人の誤りを指摘するときに
自分でも誤るとか恥ずかしくないか

**デフォルトの名無しさん** · 2017/06/23(金) 13:07:58.26

間違いを恐れるな

**デフォルトの名無しさん** · 2017/06/23(金) 13:38:13.56

馬鹿、アスペを恐れるな

**デフォルトの名無しさん** · 2017/06/23(金) 19:23:07.84

KIZLA7]]]

%≒72%,M,L,TO"JYOJA"

**デフォルトの名無しさん** · 2017/06/26(月) 15:07:57.81

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）ですが、この
本には強連結成分分解のアルゴリズムは書いてあるのですが、その正しさについて
の説明がありません。

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

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

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

**デフォルトの名無しさん** · 2017/06/26(月) 15:09:29.86

あ、よくみたら解答がありました。

**デフォルトの名無しさん** · 2017/06/26(月) 15:14:33.33

強連結成分分解のアルゴリズムはグラフ理論的な観点からは興味深いですが、
応用についてはあまりないようですね。

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

**デフォルトの名無しさん** · 2017/06/26(月) 15:27:14.29

ステマ乙としか

**デフォルトの名無しさん** · 2017/06/26(月) 15:32:39.93

ところで、LEDAというライブラリはお勧めですか？

**デフォルトの名無しさん** · 2017/06/26(月) 16:23:39.69

病人が粘着してる

**デフォルトの名無しさん** · 2017/06/27(火) 13:16:02.75

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

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

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

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

**デフォルトの名無しさん** · 2017/06/27(火) 14:05:21.18

NGにしてほしいんじゃね

**デフォルトの名無しさん** · 2017/06/27(火) 14:08:46.74

勉強しなきゃいいのに

**デフォルトの名無しさん** · 2017/06/27(火) 15:22:28.20

馬鹿のアスペの気持ちなんか分からん

**デフォルトの名無しさん** · 2017/06/27(火) 17:51:10.93

本人だったりして

**デフォルトの名無しさん** · 2017/06/27(火) 19:32:13.18

あ、その後の有向無閉路ネットワークの最長パスを求めるアルゴリズムで
トポロジカルラベリングが使われていました。

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

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

**デフォルトの名無しさん** · 2017/06/27(火) 19:34:40.25

有向無閉路ネットワークという制限が強すぎますね。

でもこの制限のおかげでちょっと面白いトポロジカルラベリングの応用例が見れたわけですね。

**デフォルトの名無しさん** · 2017/06/27(火) 21:47:11.43

プログラミング・コンテスト・チャレンジブック、第2版、2012

ほとんど全てのアルゴリズムを網羅。
問題数も多く、パズル感覚で楽しめる。
AIやシミュレーションゲームの参考になる

**デフォルトの名無しさん** · 2017/06/27(火) 21:55:21.79

>>426

網羅からはほど遠いと思います。

**デフォルトの名無しさん** · 2017/06/27(火) 21:58:43.82

>>426

それとアルゴリズムの正当性のまともな説明がありません。

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

**デフォルトの名無しさん** · 2017/06/27(火) 22:34:26.12

一から百まで説明しないとダメな奴、すなわち無能

**デフォルトの名無しさん** · 2017/06/28(水) 02:20:53.63

入門データ構造とアルゴリズム、2013、オライリー
Narasimha Karumanchi(インド人) 著

アルゴリズムなら、セジウィックでも読めば？

プログラミング・コンテスト・チャレンジブックは、
コンテストの問題を集めた本だから、便利

一々、ウェブサイトの問題を見なくても良いから、楽

**デフォルトの名無しさん** · 2017/06/28(水) 05:10:12.09

>>430

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

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

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

**デフォルトの名無しさん** · 2017/06/28(水) 05:17:01.98

D40

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

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

**デフォルトの名無しさん** · 2017/06/28(水) 06:24:05.46

>>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 であるような連結なグラフは木であるから、そうような部分グラフは木である。

**デフォルトの名無しさん** · 2017/06/28(水) 06:52:24.02

>>432

ヒントとして、「T - AB は2成分からなる森である」と書いてあるのですが、
このヒントを利用した解答はどうなるのでしょうか？

**デフォルトの名無しさん** · 2017/06/28(水) 10:22:23.33

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

↓は、ある点から各点への最長パスを求めるプログラムのメイン関数です。
「出発点を入力してください」などと出力していますが、出発点は 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;
}

**デフォルトの名無しさん** · 2017/06/28(水) 10:54:52.65

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

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

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とする
■■■■■■■■}
■■■■}
}

**デフォルトの名無しさん** · 2017/06/28(水) 10:57:07.89

366 :nobodyさん 2017/05/29(月) 16:07:39.16 ID:6v4UcGhE
今回の民法改正、ソフトウェア受託開発の場合、(検収後ではなく)バグ発見後１年瑕疵担保責任があるということで、地獄かよ、と思ったが、
元々問題が起きがちな受託案件がビジネス的に成立しなくなることで強制的に業界再編につながるなら良いことかもと思うようになった。
一部で地獄を見ても。
https://twitter.com/yukihiro_matz/status/869061879389343744

367 :nobodyさん 2017/05/29(月) 16:28:06.55 ID:6v4UcGhE
ニュース - 改正民法が成立、「瑕疵担保責任」などシステム開発契約に影響大：ITpro
http://b.hatena.ne.jp/entry/itpro.nikkeibp.co.jp/atcl/news/17/052601508/

372 :nobodyさん2017/05/29(月) 19:10:37.12 ID:???
Railsでシステム作って納品する
↓
Railsはマイナー、メジャーのアップデートが半年以内に必ずある
↓
客がアップデートする。アップデートによるエラーやバグ、動作の不具合に気づく
↓
気づいてから1年以内に通知すれば、5年間無料保証ゲット
↓
つまりRailsがアップデートするたびに、無償の修正作業を発生するということかな

376 :nobodyさん2017/05/30(火) 09:20:20.09 ID:L5po86sS
>>378>>379>>375
客が瑕疵担保責任法の法改正を知ってくると思うから、今後5年無償保証をお願いされるだろう
営業がそれでも仕事を取ってこれるか？たぶん無理だろう。無限の直していたら赤字になる。
こういう保守に弱い言語、ころころ仕様が変わる言語は仕事として発生しなくなってくる。
これは変わり目だ。お前らも早く逃げたほうがいいぞ。RubyやPHPなど動的言語は確実に廃れる。
保守に強い言語のみ生き残れる。

**デフォルトの名無しさん** · 2017/06/28(水) 11:02:48.67

↑の for 文は j = 1 から始まっています。

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

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

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

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

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

正しくは、

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

**デフォルトの名無しさん** · 2017/06/28(水) 11:19:51.44

あ、もう一つバグがありました↑

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

となっていますが、

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

でなければなりません。

**デフォルトの名無しさん** · 2017/06/28(水) 12:31:24.06

>>438
>インデックスが 0 の要素は初期化すらしていません

配列[0] を使わないのなら、初期化する必要はない

**デフォルトの名無しさん** · 2017/06/28(水) 12:34:24.00

>>440

そうですが、

for(j = 1;

とすると

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

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

**デフォルトの名無しさん** · 2017/06/28(水) 12:37:24.37

有向無閉路ネットワークの最長パスをトポロジカルラベリングを利用して、
求めるアルゴリズムって他の本に載っていますか？

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

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

**デフォルトの名無しさん** · 2017/06/28(水) 13:17:27.40

>>426

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

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

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

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

**デフォルトの名無しさん** · 2017/06/28(水) 14:35:33.86

外部変数は0で初期化される。

**デフォルトの名無しさん** · 2017/06/28(水) 15:46:50.33

j=1で始まってんのに意図せず配列[0]を参照するの意味がわからん

**デフォルトの名無しさん** · 2017/06/28(水) 16:26:43.89

それでも馬鹿のアスペの荒らしをスルーできない

**デフォルトの名無しさん** · 2017/06/28(水) 18:29:25.09

>>444

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

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

**デフォルトの名無しさん** · 2017/06/28(水) 18:29:51.34

訂正します：

>>445

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

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

**デフォルトの名無しさん** · 2017/06/28(水) 18:33:38.48

さらに、

v == tporder[1] == 1 です。

**デフォルトの名無しさん** · 2017/06/29(木) 11:58:28.12

http://imgur.com/A84Qz1i.jpg
http://imgur.com/NsXCsS1.jpg
http://imgur.com/Bm7ANHm.jpg
http://imgur.com/iSqMNes.jpg

↑は浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）です。
1枚目と2枚目の画像が連結な有向オイラーグラフの一筆書きを求めるアルゴリズムです。
3枚目と4枚目の画像がそのアルゴリズムの正しさの証明です。

「連結グラフ G が一筆書きできるための必要十分条件は、 G がオイラーであることである。」

という定理の証明において、十分性は、↑の3枚目と4枚目の画像の定理5.3により分かるということが書いてあります。

↑の3枚目と4枚目の画像を読めば分かりますが、十分性について証明されていないように思います。

どうでしょうか？

**デフォルトの名無しさん** · 2017/06/29(木) 12:19:34.40

むしろ、十分性が成り立つことを前提にしてアルゴリズムの正しさを証明しているように思います。

**デフォルトの名無しさん** · 2017/06/30(金) 09:51:08.15

粘着