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

[表示 : 全て最新50 1-99 101- 201- 301- 401- 501- 601- 701- 801- 901- 1001- 2ch.scのread.cgiへ]
Update time : 02/03 08:19 / Filesize : 282 KB / Number-of Response : 1020
[このスレッドの書き込みを削除する]
[＋板最近立ったスレ＆熱いスレ一覧 : ＋板最近立ったスレ／記者別一覧] [類似スレッド一覧]


↑キャッシュ検索、類似スレ動作を修正しました、ご迷惑をお掛けしました

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
308 名前：デフォルトの名無しさん mailto:sage [2017/01/08(日) 22:51:13.67 ID:Qw43e7Zm.net]: ここはプログラミング問題集書評のスレなの？
309 名前：デフォルトの名無しさん [2017/01/09(月) 06:08:00.57 ID:JOAqSyBk.net]: >>301
うむ
日本語下手なのはもちろん英語も下手みたいだな
310 名前：デフォルトの名無しさん mailto:sage [2017/01/09(月) 06:09:36.68 ID:cSodeH17.net]: 頭の使い方が下手というかそもそも頭が不自由なんだろう
311 名前：デフォルトの名無しさん [2017/01/09(月) 10:59:50.63 ID:TqLncjlX.net]: アルゴリズムイントロダクションの練習問題15.1-3の解答って以下であっていますか？

BOTTOM-UP-CUT-ROD(p, c, n)
1 r[0..n] を新しい配列とする
2 r[0] = 0
3 for j = 1 to n
4 ■■q = -∞
5 ■■for i = 1 to j-1
6 ■■■■q = maxx(q, p[i] + r[j-i] - c)
7 ■■q = max(q, p[j])
8 ■■r[j] = q
9 return r[n]
312 名前：デフォルトの名無しさん [2017/01/09(月) 11:02:45.57 ID:TqLncjlX.net]: 15.1-2

反例

p[1] = 1
p[2] = 5
p[3] = 7
313 名前： []: [ここ壊れてます]
314 名前：デフォルトの名無しさん [2017/01/09(月) 13:21:16.77 ID:TqLncjlX.net]: F_0 = 0
F_1 = 1
F_i = F_(i-1) + F_(i-2) (i≧2)

F_n を O(n) 時間で計算する動的計画アルゴリズムを設計せよ。
対応する部分問題グラフを描け。
このグラフにはいくつの頂点と辺が存在するか？

↑はアルゴリズムイントロダクションの練習問題15.1-5なんですけど、
なんか簡単すぎるようにみえるんですけど、落とし穴があるんですかね？

なんでΘ(n)じゃなくてO(n)と書いてあるんですかね？
315 名前：デフォルトの名無しさん [2017/01/09(月) 13:34:48.26 ID:TqLncjlX.net]: 配列を使わないとDPとは言えないですか？
配列いらないですよね。
でもi = 0～nに対して、F[i]が求まるという意味はありますね。

F[0] = 0
F[1] = 1
for i = 2 to n
■■F[n] = F[n-1] + F[n-2]

明らかにΘ(n)ですよね。

部分問題グラフは以下ですよね：

imgur.com/WUQMG8R.jpg

#V = n + 1
#E = 2*(n - 1)

ですね。
316 名前：デフォルトの名無しさん [2017/01/09(月) 13:37:23.94 ID:TqLncjlX.net]: あ、ひっかけがありましたね。
訂正します：

n > 0 のとき、

#V = n + 1
#E = 2*(n - 1)

n = 0 のとき

#V = n + 1
#E = 0

ですね。
317 名前：デフォルトの名無しさん [2017/01/09(月) 15:27:31.58 ID:TqLncjlX.net]: アルゴリズムイントロダクションに、以下の事実を1955年にRobbinsが発見したと書いてあります。

--------------------------------------------
すべての n ≧ 1 に対して

n! = sqrt(2*π*n) * (n/e)^n * exp(α_n)

と書ける。

ただし、 1/(12*n+1) < α_n < 1/(12*n)
--------------------------------------------

本当にこんな比較的簡単にみえる結果が1955年という比較的最近になって発見された
のでしょうか？
318 名前：デフォルトの名無しさん [2017/01/09(月) 15:37:47.20 ID:4OeNzyzM.net]: >>308
フィボナッチだろ
√5が出て来る公式
O(1)になるかも試練が
319 名前：デフォルトの名無しさん mailto:sage [2017/01/09(月) 15:46:27.18 ID:FSSb8O2Z.net]: >>311
　　　　　　r　‐､
　　　　　　| ○ | 　　　　　　　　r‐‐､
　　　　　_,;ﾄ - ｲ、　　　　　　∧l☆│∧ 　良い子の諸君！
　　　（⌒`　　　 ⌒ヽ　　　/,､,,ﾄ.-ｲ/,､ l 　
　　　　|ヽ　 ~~⌒γ ⌒ ）　r'⌒　｀!´ `⌒）よく頭のおかしい数学者気取りのバカが
　　　│　ヽー―'^ー-'　（ ⌒γ ⌒~~　/　「誰も気付かなかった事を発見したことを発表」とほざくが
　　　│　　〉　　　 |│　　|｀ー^ｰ― r'　| 大抵それは「先人が思いついたけどあえて発表しなかった」ことだ
　　　│　/───|　|　　|/　| 　l　　ﾄ､ | 　王道が何故面白いか理解できない人間に面白い話は
　　　|　 irｰ-､ｰ　,}　|　　　 / 　　　　i　作れないぞ！
　　　| /　　　｀X´　ヽ　　 / 　入　　|
320 名前：デフォルトの名無しさん [2017/01/10(火) 20:16:10.65 ID:Zd0v4023.net]: アルゴリズムイントロダクションが難しいという人がいますけど、
この本は馬鹿丁寧に書かれていますよね。

いわゆる「書きすぎ」ですね。

「書きすぎ」れば分かりやすくなると思い込んでいますね、著者らは。
321 名前：デフォルトの名無しさん mailto:sage [2017/01/10(火) 20:19:42.26 ID:kxFYGz06.net]: hissi.org/read.php/tech/20160614/U2lCYS9zNTM.html

マジ基地だな。壊れたレコードかよ。
322 名前：デフォルトの名無しさん mailto:sage [2017/01/13(金) 21:58:42.65 ID:wiy2qrIv.net]: プログラミング言語のパーサーってどういう仕組みで動いてるんですか？
文字列をトークンの配列に分ける
特定のパターンにマッチするトークンの部分集合をひとまとめにして新しいトークンに置き換える
再帰的に同じ事を繰り返す
こんな感じ？
323 名前：デフォルトの名無しさん mailto:sage [2017/01/13(金) 22:37:46.17 ID:+ExxsU2F.net]: >>316
Java 再帰下降構文解析超入門
qiita.com/7shi/items/64261a67081d49f941e3

ビジュアル構文解析
www.csg.ci.i.u-tokyo.ac.jp/~ichikawa/visual_parsing.pdf
324 名前：デフォルトの名無しさん mailto:sage [2017/01/14(土) 00:10:28.40 ID:H4kTcvBH.net]: >>317
これ考えた奴は天才だな
325 名前：デフォルトの名無しさん mailto:sage [2017/01/16(月) 17:57:37.27 ID:YH2Bx58z.net]: Lisperか
BNF
326 名前：デフォルトの名無しさん mailto:sage [2017/01/19(木) 09:40:05.52 ID:uhfgjGGl.net]: https://chrome.google.com/webstore/detail/%E3%81%AF%E3%81%A6%E3%81%AAng/mbgdnfmdelffjdhkdggilmphfdihnmcj?hl=ja
327 名前：デフォルトの名無しさん mailto:sage [2017/05/14(日) 13:16:07.97 ID:SQILU9sh.net]: 類似スレ検索とかのアルゴリズムって何がいいのかな？
編集距離とか数字部分のマスキングくらいしか浮かばない
形態素解析して要素の一致率とかもあるみたいだけど、スレタイみたいな短い文字じゃ弱そう
328 名前：デフォルトの名無しさん mailto:sage [2017/05/14(日) 13:20:48.12 ID:SQILU9sh.net]: むしろ短くて重要な単語が多いスレタイこそ一致率うまく働きそうか
毎回評価してたら検索速度悪そうだけど
329 名前：デフォルトの名無しさん mailto:sage [2017/05/14(日) 13:56:17.84 ID:CjOSHdvj.net]: Baka ha sinanakya
Naoranai
Fucky ou
330 名前：デフォルトの名無しさん [2017/05/26(金) 14:08:00.89 ID:fOPo0M5r.net]: アルゴリズムイントロダクション

当たり前のことを定理などとよんで回りくどく証明していますね。

なんなんですか？この本。

例えば、p.506定理22.9とか。
331 名前：デフォルトの名無しさん [2017/05/26(金) 19:39:06.33 ID:GnitEmTF.net]: 当たり前のことを2chで指摘して回りくどくdisっていますね。
なんなんですか？あなた。
例えば、 >>324 とか。
332 名前：デフォルトの名無しさん mailto:sage [2017/05/26(金) 21:10:54.45 ID:ovKX6RUR.net]: >>324
当たり前が何故当たり前なのかを知るのは割と重要だが。
333 名前：デフォルトの名無しさん [2017/05/26(金) 22:50:21.07 ID:fOPo0M5r.net]: >>324

しかも「証明」が長い。当たり前のことを長々と書いている。
その「証明」自体も意外性ゼロ。
334 名前：デフォルトの名無しさん [2017/05/26(金) 22:52:14.04 ID:fOPo0M5r.net]: しかも徹底していない。

ある命題は明らかで済ませている。
その一方である命題には長々と「証明」をつけている。

基準がさっぱりわからない。
335 名前：デフォルトの名無しさん mailto:sage [2017/05/26(金) 22:52:58.46 ID:ovKX6RUR.net]: 初級アルゴリズム本持ち出して何なんですか言われてもねぇ。。。
物足りなかったら上のクラスの本買えば？
336 名前：デフォルトの名無しさん [2017/05/26(金) 23:04:15.09 ID:fOPo0M5r.net]: とにかくしつこい本。

この著者らの感性は、おかしいと思う。

丁寧というよりしつこい。

クヌースの本は丁寧という感じ。

結局、教科書の書き手として優れていない。
337 名前：デフォルトの名無しさん [2017/05/27(土) 03:04:18.64 ID:V3ffhZkY.net]: きっとアスペなんだろう
338 名前：デフォルトの名無しさん mailto:sage [2017/05/27(土) 03:30:20.38 ID:6GQ16ypm.net]: アルゴリズムでは、セジウィックが有名。他に、

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

プログラミング・コンテスト・チャレンジブック、第2版、2012
339 名前：デフォルトの名無しさん mailto:sage [2017/05/27(土) 05:56:26.58 ID:0xIYYFUk.net]: hissi.org/read.php/tech/20160422/cGVtVmVaYUg.html
hissi.org/read.php/tech/20160612/YkttemlBQ3Y.html
hissi.org/read.php/tech/20160614/U2lCYS9zNTM.html
hissi.org/read.php/tech/20160619/NUt2U0tkTC8.html
hissi.org/read.php/tech/20170526/Zk9QbzBNNXI.html

壊れかけの脳味噌。
340 名前：デフォルトの名無しさん [2017/05/27(土) 08:08:34.68 ID:tcRpjIho.net]: 浅野孝夫の新しく出た2冊の本はどうですか？
341 名前：デフォルトの名無しさん [2017/05/27(土) 11:29:04.28 ID:tcRpjIho.net]: アルゴリズムイントロダクションは訳もひどいね。

意味不明だと思って原著を調べるといつも誤訳。

今読んでいるところにも誤訳を見つけた。

本当に理解して訳しているか？
342 名前：デフォルトの名無しさん [2017/05/27(土) 11:54:19.85 ID:tcRpjIho.net]: Let v be the first vertex to be discovered in c, and let (u, v) be the preceding edge in c.

の訳が、

c の中で最初に発見される頂点を v, c において v に向かう辺を (u, v) とする。
（したがって、 u は c における v の先行点である。）

日本語としてまずおかしいし、 u は v の先行点では、もちろんない。
343 名前：デフォルトの名無しさん mailto:sage [2017/05/27(土) 13:19:03.94 ID:olQh0zw8.net]: >>333
徳永乙
344 名前：デフォルトの名無しさん mailto:sage [2017/05/27(土) 14:45:49.59 ID:m5ivKvT+.net]: 本ばかり読んでコードも書かない典型だな
345 名前：デフォルトの名無しさん mailto:sage [2017/05/31(水) 19:10:09.21 ID:uNlt1YRD.net]: 今扱ってるライブラリのコンストラクタとか生成系のメソッドとかの引数が多すぎるんで何とかしたいんだがビルダーパターンぐらいしかないのかな
今は引数用の構造体を用意して成のメソッドの呼び出し時に構造体を参照させるようにしてるんだが、お前らどう思う？
346 名前：デフォルトの名無しさん mailto:sage [2017/05/31(水) 19:13:07.12 ID:uNlt1YRD.net]: >>339
s/成のメソッド/生成のメソッド
347 名前：デフォルトの名無しさん mailto:sage [2017/05/31(水) 22:35:13.68 ID:NSe5u++m.net]: クラスを作りまくって引数を減らすんだよ
348 名前：デフォルトの名無しさん mailto:sage [2017/06/01(木) 07:33:57.31 ID:9lL7NugS.net]: まあ、ファクトリかビルダだろうな

引数をオーバーライドメソッドでなるべく少なくなる工夫しつつ
349 名前：デフォルトの名無しさん [2017/06/01(木) 07:40:31.13 ID:PJoLYMb9.net]: グラフ理論のアルゴリズムを実装したときに、正しいかどうか
チェックするのって、グラフを用意しなきゃならなくて大変だけど
サンプルのグラフってどこかに公開されていないの？
350 名前：デフォルトの名無しさん mailto:sage [2017/06/01(木) 08:27:11.96 ID:RM67mdjD.net]: >>341
>>342
やっぱそれぐらいしかないか
レスさんくす
351 名前：デフォルトの名無しさん mailto:sage [2017/06/01(木) 09:01:58.44 ID:dZ2VO+v4.net]: >343

Knuth先生のThe Stanford Graphbase

www-cs-staff.stanford.edu/~knuth/sgb.html
352 名前：デフォルトの名無しさん mailto:sage [2017/06/01(木) 09:26:44.84 ID:bUIwnMhK.net]: ダイクストラなどのグラフは、Python
353 名前：デフォルトの名無しさん [2017/06/05(月) 16:05:46.39 ID:gPC56aZq.net]: 2つのグラフが同型かどうか判定するアルゴリズムを教えてください。
354 名前：デフォルトの名無しさん mailto:sage [2017/06/05(月) 18:35:40.61 ID:Vm0ObO74.net]: ちょっと手間を減らすなら、次数でソートしたりゴニョゴニョできるけど、NPだからあとは力技
355 名前：デフォルトの名無しさん mailto:sage [2017/06/05(月) 19:30:33.86 ID:SUt02FhH.net]: 最終的に力業になることが分かってる問題って悲しいよね。
356 名前：デフォルトの名無しさん mailto:sage [2017/06/05(月) 20:28:56.86 ID:gPC56aZq.net]: >>348-349

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

基本的で重要な問題なのにアルゴリズムの本で見かけなかったのは効率的な
アルゴリズムが存在しないからだったんですね。

効率的なアルゴリズムが存在しない場合でも、小さい問題は解けるわけですから、
それなりの工夫でもいいから、教科書に載せてほしいです。
357 名前：デフォルトの名無しさん mailto:sage [2017/06/05(月) 20:36:06.74 ID:gPC56aZq.net]: >>348-349

グラフが同型かどうかくらいならプログラムを誰でも作れると思います。

効率的なアルゴリズムが存在しない問題の場合、教科書にはアルゴリズムが
載っていないことが多いと思います。自分で力任せのプログラムを書ける場合
はいいですが、力不足で力任せのプログラムすら書けない場合って困りますね。
358 名前：デフォルトの名無しさん mailto:sage [2017/06/05(月) 21:01:13.00 ID:sad0uPoZ.net]: >347
networkXっていうPythonのグラフアルゴリズムのライブラリに、グラフ同型判定の関数があるよ。
is_isomorphic()
ソースコードも見れるから、実装の参考にしては。
VF2アルゴリズムというのを使っているらしい。どういうのかは、知らない。。
359 名前：デフォルトの名無しさん mailto:sage [2017/06/05(月) 21:17:56.80 ID:gPC56aZq.net]: >>352

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

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

情報、ありがとうございました。
360 名前：デフォルトの名無しさん mailto:sage [2017/06/08(木) 13:28:45.57 ID:oPuedIYN.net]: >>352
thx
361 名前：デフォルトの名無しさん [2017/06/10(土) 01:09:12.89 ID:yRjB/26o.net]: セジウィックのアルゴリズムCはコルメン他の本とは対極にあるような本だね。
どっちもどっち。
362 名前：デフォルトの名無しさん [2017/06/10(土) 22:49:54.03 ID:bkNNwNFI.net]: セジウィックのアルゴリズムCは言葉足らず。
363 名前：デフォルトの名無しさん [2017/06/11(日) 08:24:40.56 ID:7PvmoOJK.net]: セジウィックのアルゴリズムＣは定義がダメダメ。

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

この定義だと連結グラフに極大木が常に存在するというのが定理になってしまう。
が、証明せずに、この事実を以下で使っている。
364 名前：デフォルトの名無しさん [2017/06/11(日) 11:00:58.83 ID:7PvmoOJK.net]: セジウィックのアルゴリズムＣは、訳も最低。
365 名前：デフォルトの名無しさん [2017/06/16(金) 18:04:24.35 ID:ixzzoI9b.net]: 浅野孝夫著『アルゴリズムの基礎とデータ構造数理とCプログラム』（近代科学社）

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

著者は何を考えているのでしょうか？
366 名前：デフォルトの名無しさん [2017/06/16(金) 18:08:47.36 ID:1eQLQexT.net]: javaの逆ポートだろう
367 名前：デフォルトの名無しさん [2017/06/16(金) 18:30:17.58 ID:ixzzoI9b.net]: 浅野孝夫著『アルゴリズムの基礎とデータ構造数理とCプログラム』（近代科学社）

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

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

Visual Studio を使っているのですが、一つのソースファイルに対して、いちいち
プロジェクトを作っていると面倒なんですが、どうすればいいですか？
368 名前：デフォルトの名無しさん [2017/06/16(金) 18:31:46.91 ID:ixzzoI9b.net]: コマンドプロンプトからコマンドを実行してコンパイルをしたりする原始的なやり方
は避けたいです。
369 名前：デフォルトの名無しさん [2017/06/16(金) 18:47:18.97 ID:1eQLQexT.net]: なんだ
ステマか
370 名前：デフォルトの名無しさん mailto:sage [2017/06/16(金) 20:42:10.07 ID:1imKhLwB.net]: 原始的なやり方×
基本的なやり方〇
371 名前：デフォルトの名無しさん mailto:sage [2017/06/16(金) 20:54:00.90 ID:RYT773NB.net]: 探せば学習用のC言語インタプリタとかあるんじゃない
372 名前：デフォルトの名無しさん mailto:sage [2017/06/16(金) 21:27:28.11 ID:vP51FB3m.net]: ちょっとサンプルコードを走らせるかって程度なら
Online IDEとか使えばよいのに
373 名前：デフォルトの名無しさん mailto:sage [2017/06/16(金) 21:42:24.80 ID:SNTjPZEm.net]: そもそも何でファイルごとにわざわざプロジェクト作るような原始的なことやってるの
374 名前：デフォルトの名無しさん mailto:sage [2017/06/16(金) 22:44:29.43 ID:e6Uo8nQP.net]: mainの数だけプロジェクトが必要だから？
375 名前：デフォルトの名無しさん mailto:sage [2017/06/17(土) 15:06:03.16 ID:SdcHR0BJ.net]: プロセス増えるだけだからプロジェクトは増やさなくてもいいんじゃね
376 名前：デフォルトの名無しさん [2017/06/17(土) 18:14:18.11 ID:DtePX3I4.net]: アルゴリズムとデータ構造の本のソースコードを見ると、よくグローバル変数を
多用していて非常に分かりにくいことが多いです。

グローバル変数を使うのは良くないというのをよく目にしますが、なぜ、
コンピュータサイエンスのプロであるはずのアルゴリズムとデータ構造の本の
著者がそんなプログラムを書くのでしょうか？
377 名前：デフォルトの名無しさん [2017/06/17(土) 18:18:02.53 ID:DtePX3I4.net]: 例えば、

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

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

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

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

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

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

あちこちいろいろなファイルを見ないと、全体が分かりません。
378 名前：デフォルトの名無しさん mailto:sage [2017/06/17(土) 18:18:09.88 ID:n14YEU6w.net]: サンプルだから
379 名前：デフォルトの名無しさん mailto:sage [2017/06/17(土) 18:19:41.47 ID:n14YEU6w.net]: >>371
Javaしか使ったことない人が知ったかぶりでCの本出すからそうなる
捨てろ
380 名前：デフォルトの名無しさん [2017/06/17(土) 18:19:49.58 ID:DtePX3I4.net]: 全然、プログラム作りの参考になりません。

ただ、例外もあります。

セジウィックの『Algorithms』という赤い本は、参考になります。
381 名前：デフォルトの名無しさん [2017/06/17(土) 18:21:15.46 ID:DtePX3I4.net]: >>373

でも、コード自体は非常に巧妙で優れています。
382 名前：デフォルトの名無しさん [2017/06/17(土) 20:50:11.36 ID:DtePX3I4.net]: そういえば、茨木俊秀の本のプログラムもひどかったような。
383 名前：デフォルトの名無しさん mailto:sage [2017/06/17(土) 22:37:25.92 ID:tNCJKlzg.net]: グローバル変数を避けようとかはソフトウェア工学の話で、コンピューター科学とは別の分野なんだよ。
384 名前：デフォルトの名無しさん [2017/06/17(土) 23:06:32.77 ID:L9yKSdqC.net]: ソフトウェア工学の基本すら知らないんですかね？
385 名前：デフォルトの名無しさん mailto:sage [2017/06/18(日) 00:34:44.62 ID:o43mtcr6.net]: グローバル変数を使った方が、説明しやすいとか、
ソースコードがわかりやすいとか

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

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

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

ちょっとしたプログラミングに、型チェックする、Javaなどを使わず、
Rubyで書くのもそう。
ラフな会合に、盛装して行かないのもそう
386 名前：デフォルトの名無しさん mailto:sage [2017/06/18(日) 12:26:58.32 ID:HTlYPuIB.net]: 掲示板のTPO弁えない人にTPO語ってもしょうがないよ
387 名前：デフォルトの名無しさん [2017/06/18(日) 12:39:15.20 ID:4GAQ5Lgy.net]: グローバル変数を明らかに、分かりにくいやり方で使っています。

何の利点もないと思います。
388 名前：デフォルトの名無しさん [2017/06/18(日) 13:30:23.31 ID:4GAQ5Lgy.net]: もしかして、理論ばかりに興味があり、プログラムを作ったことがないんですかね？
389 名前：デフォルトの名無しさん mailto:sage [2017/06/18(日) 14:37:44.92 ID:7v+ppDWb.net]: プログラム教本ではなくアルゴリズム解説本だからでしょ
擬似言語で書いている場合のが多いと思うけど
390 名前：デフォルトの名無しさん [2017/06/18(日) 15:37:30.01 ID:xPH4G83l.net]: 最初から完成してたらおまいらの仕事無くなっちゃうだろ
391 名前：デフォルトの名無しさん [2017/06/18(日) 18:10:10.06 ID:L/LJrXI/.net]: 楽器やってるひとがいってたよ。自分がつかえる技術を全部つかうわけじゃない
392 名前：デフォルトの名無しさん [2017/06/18(日) 20:13:26.60 ID:4GAQ5Lgy.net]: 浅野孝夫の本。

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

プログラムは巧妙。
393 名前：デフォルトの名無しさん mailto:sage [2017/06/18(日) 20:48:27.00 ID:wscBwMor.net]: こんなところに日記書く人って、相当追い詰められてるんだろうな。
394 名前：デフォルトの名無しさん mailto:sage [2017/06/19(月) 04:29:40.16 ID:+M9YR/5M.net]: こんなところだから何書いてもいいよ
395 名前：デフォルトの名無しさん mailto:sage [2017/06/19(月) 09:50:06.41 ID:JRZAs/i8.net]: ステマよりグロい
396 名前：デフォルトの名無しさん [2017/06/19(月) 12:02:27.97 ID:0IiK5rsw.net]: 浅野孝夫の本。

深さ優先探索とか幅優先探索の説明を言葉で長々としています。
そんなことするより、コードを見せたほうがいいと思うんですよね。
コードを見れば一目で分かりますよね。
397 名前：デフォルトの名無しさん mailto:sage [2017/06/19(月) 12:05:01.80 ID:TXA5MC9f.net]: もうおめーが執筆しろよ
398 名前：デフォルトの名無しさん mailto:sage [2017/06/19(月) 13:13:41.68 ID:YgkoP+sD.net]: コードはあくまで例なので解説が先
399 名前：デフォルトの名無しさん [2017/06/21(水) 10:56:36.24 ID:CsbvaOkp.net]: imgur.com/9QGwvmM.jpg
imgur.com/j3Dp32V.jpg
imgur.com/iJhKoqM.jpg

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

重大な誤りを発見し�
400 名前：ﾜした。 G が二部グラフであるための必要十分条件は、G を幅優先探索したときに同じ深さの補木辺がないことであると書かれていますが、 完全な誤りです。 具体的に言うと、「同じ深さの点を結ぶ補木辺がないときは、この色の割当てが実際に2彩色になっている。」と書かれていますが、 間違っています。 反例は3枚目の画像を参照してください。 []: [ここ壊れてます]
401 名前：デフォルトの名無しさん [2017/06/21(水) 11:00:57.46 ID:CsbvaOkp.net]: 訂正します：

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

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

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

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

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

反例は3枚目の画像を参照してください。
402 名前：デフォルトの名無しさん [2017/06/21(水) 11:11:21.29 ID:CsbvaOkp.net]: 商品の説明
内容紹介
ネットワーク・人工知能の基礎となるグラフ・ネットワークを学ぶ

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

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

この出版社は、「世界標準MIT教科書」などとタイトルに書いたり、売るためには
手段を選ばない出版社ですね。
403 名前：デフォルトの名無しさん mailto:sage [2017/06/21(水) 12:35:50.38 ID:TkpRSZSL.net]: >>395
自分の想像力の欠如で批判しないほうがいいよ
404 名前：デフォルトの名無しさん mailto:sage [2017/06/21(水) 12:37:14.26 ID:L1LFWazB.net]: 外国には「たのしいRuby」が無い

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

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

Homebrew もRubyで作られているのだから、
Apple は、もっとRubyに力を入れるべき
405 名前：デフォルトの名無しさん mailto:sage [2017/06/21(水) 12:53:00.17 ID:TkpRSZSL.net]: >>394
幅優先探索わかる？
406 名前：デフォルトの名無しさん mailto:sage [2017/06/21(水) 12:54:37.96 ID:Y4WM7moX.net]: >>394
３枚目は補木辺があって２部グラフではないので、
別におかしくないのでは
407 名前：デフォルトの名無しさん [2017/06/21(水) 13:14:54.71 ID:CsbvaOkp.net]: >>399

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

3枚目の画像には同じ深さの点を結ぶ補木辺がありません。
ですが、2彩色ではありません。
408 名前：デフォルトの名無しさん mailto:sage [2017/06/21(水) 13:31:42.95 ID:srnzKpaS.net]: 松坂君のアスペ日記３

Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net
rio2016.2ch.net/test/read.cgi/math/1497007079/
409 名前：デフォルトの名無しさん [2017/06/21(水) 13:33:59.73 ID:CsbvaOkp.net]: 要するに、↓が間違っているわけです。

「補木辺は、同じ深さの点を結んでいるか、あるいは深さが 1 異なる点を結んでいることに注意しよう。」
410 名前：デフォルトの名無しさん mailto:sage [2017/06/21(水) 13:55:32.90 ID:BP6mUhEj.net]: ここじゃなくて著者なり出版社なりに連絡しなよ
その方がちゃんと議論できるだろうし修正されればあとから読む人の為になるよ
411 名前：デフォルトの名無しさん mailto:sage [2017/06/21(水) 14:30:39.96 ID:TkpRSZSL.net]: >>400
幅優先で探索木作ったら同じ深さを結ぶ補木辺ができるから二部グラフでないことがわかる
412 名前：デフォルトの名無しさん mailto:sage [2017/06/21(水) 16:12:29.38 ID:e3wPbus7.net]: >394
三枚目の図は、反例になっていない。
あなたが幅優先探索を理解できていないだけで、書籍の記述は間違っていないよ。
根でない2つの頂点は、どちらも、根から辺が張られていて、根と隣接しているのだから、同じ深さの位置にある。
413 名前：デフォルトの名無しさん [2017/06/21(水) 18:57:35.69 ID:CsbvaOkp.net]: あ、勘違いしました。

無向グラフでしたね。
414 名前：デフォルトの名無しさん mailto:sage [2017/06/21(水) 19:28:34.24 ID:TkpRSZSL.net]: 教科書だって間違いはいくらでもある。
だからといって、間違いらしきものを見つけて喜々としてあげつらうのではなく、
自分の解釈ではこうだが違うのだろうかという態度で質問しておけばよかったね。
415 名前：デフォルトの名無しさん mailto:sage [2017/06/21(水) 22:04:49.64 ID:GPdgYp3Z.net]: 何がいんだろ
416 名前：デフォルトの名無しさん [2017/06/23(金) 09:05:15.05 ID:0OdP20aK.net]: >>393-394
他人の誤りを指摘するときに
自分でも誤るとか恥ずかしくないか
417 名前：デフォルトの名無しさん mailto:sage [2017/06/23(金) 13:07:58.26 ID:IBCt0Ik9.net]: 間違いを恐れるな
418 名前：デフォルトの名無しさん mailto:sage [2017/06/23(金) 13:38:13.56 ID:8e+v7 ]: [ここ壊れてます]
419 名前：OlS.net mailto: 馬鹿、アスペを恐れるな []: [ここ壊れてます]
420 名前：デフォルトの名無しさん [2017/06/23(金) 19:23:07.84 ID:vbPiU/7d.net]: KIZLA7]]]

%≒72%,M,L,TO"JYOJA"
421 名前：デフォルトの名無しさん [2017/06/26(月) 15:07:57.81 ID:wjem+ipT.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）ですが、この
本には強連結成分分解のアルゴリズムは書いてあるのですが、その正しさについて
の説明がありません。

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

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

エイホ、ホップクロフト、ウルマン著『データ構造とアルゴリズム』に分かりやすい説明がありました。
422 名前：デフォルトの名無しさん [2017/06/26(月) 15:09:29.86 ID:wjem+ipT.net]: あ、よくみたら解答がありました。
423 名前：デフォルトの名無しさん [2017/06/26(月) 15:14:33.33 ID:wjem+ipT.net]: 強連結成分分解のアルゴリズムはグラフ理論的な観点からは興味深いですが、
応用についてはあまりないようですね。

浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）の「はじめに」に
「強連結成分分解はシステムの故障診断や効率的解析への応用があると言われている。」
などと書かれいます。浅野さん自身は応用について具体的な詳細を知らないと宣言して
いるようなものですね。
424 名前：デフォルトの名無しさん [2017/06/26(月) 15:27:14.29 ID:H+izVTcm.net]: ステマ乙としか
425 名前：デフォルトの名無しさん [2017/06/26(月) 15:32:39.93 ID:wjem+ipT.net]: ところで、LEDAというライブラリはお勧めですか？
426 名前：デフォルトの名無しさん mailto:sage [2017/06/26(月) 16:23:39.69 ID:xVfkWcpc.net]: 病人が粘着してる
427 名前：デフォルトの名無しさん [2017/06/27(火) 13:16:02.75 ID:NGLAHv1W.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

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

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

著者は一体何を考えているのでしょうか？
428 名前：デフォルトの名無しさん mailto:sage [2017/06/27(火) 14:05:21.18 ID:41er5Tk4.net]: NGにしてほしいんじゃね
429 名前：デフォルトの名無しさん mailto:sage [2017/06/27(火) 14:08:46.74 ID:7kGXm9Ae.net]: 勉強しなきゃいいのに
430 名前：デフォルトの名無しさん mailto:sage [2017/06/27(火) 15:22:28.20 ID:LAkf1Hly.net]: 馬鹿のアスペの気持ちなんか分からん
431 名前：デフォルトの名無しさん mailto:sage [2017/06/27(火) 17:51:10.93 ID:LqFx/Quf.net]: 本人だったりして
432 名前：デフォルトの名無しさん [2017/06/27(火) 19:32:13.18 ID:NGLAHv1W.net]: あ、その後の有向無閉路ネットワークの最長パスを求めるアルゴリズムで
トポロジカルラベリングが使われていました。

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

この本、説明にちょっと粗雑なところもありますが、見せ場があって楽しいですね。
433 名前：デフォルトの名無しさん [2017/06/27(火) 19:34:40.25 ID:NGLAHv1W.net]: 有向無閉路ネットワークという制限が強すぎますね。

でもこの制限のおかげでちょっと面白いトポロジカルラベリングの応用例が見れたわけですね。
434 名前：デフォルトの名無しさん mailto:sage [2017/06/27(火) 21:47:11.43 ID:i+35CN1y.net]: プログラミング・コンテスト・チャレンジブック、第2版、2012

ほとんど全てのアルゴリズムを網羅。
問題数も多く、パズル感覚で楽しめる。
AIやシミュレーションゲームの参考になる
435 名前：デフォルトの名無しさん [2017/06/27(火) 21:55:21.79 ID:NGLAHv1W.net]: >>426

網羅からはほど遠いと思います。
436 名前：デフォルトの名無しさん [2017/06/27(火) 21:58:43.82 ID:NGLAHv1W.net]: >>426

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

計算量の評価についてもまともな説明はありません。
437 名前：デフォルトの名無しさん mailto:sage [2017/06/27(火) 22:34:26.12 ID:Tdvy+2PR.net]: 一から百まで説明しないとダメな奴、すなわち無能
438 名前：デフォルトの名無しさん mailto:sage [2017/06/28(水) 02:20:53.63 ID:W36D2Opo.net]: 入門データ構造とアルゴリズム、2013、オライリー
Narasimha Karumanchi(インド人) 著

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

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

一々、ウェブサイトの問題を見なくても良いから、楽
439 名前：デフォルトの名無しさん [2017/06/28(水) 05:10:12.09 ID:6P8PW2pA.net]: >>430

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

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

セジウィックのAlgorithms 4th Editionはいい本ですが、計算量の評価については
まともな説明がないように思います。
440 名前：デフォルトの名無しさん [2017/06/28(水) 05:17:01.98 ID:6P8PW2pA.net]: D40

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

このとき、 T から AB を除去し、辺 UV を追加したときに、
依然として G の全域木であるような辺 UV が C の中に
含まれることを示せ。
441 名前：デフォルトの名無しさん [2017/06/28(水) 06:24:05.46 ID:6P8PW2pA.net]: >>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 であるような連結なグラフは木であるから、そうような部分グラフは木である。
442 名前：デフォルトの名無しさん [2017/06/28(水) 06:52:24.02 ID:6P8PW2pA.net]: >>432

ヒントとして、「T - AB は2成分からなる森である」と書いてあるのですが、
このヒントを利用した解答はどうなるのでしょうか？
443 名前：デフォルトの名無しさん [2017/06/28(水) 10:22:23.33 ID:6P8PW2pA.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

↓は、ある点から各点への最長パスを求めるプログラムのメイン関数です。
「出発点を入力してください」などと出力していますが、出発点は 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;
}
444 名前：デフォルトの名無しさん [2017/06/28(水) 10:54:52.65 ID:6P8PW2pA.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

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

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とする
■■■■■■■■}
■■■■}
}
445 名前：デフォルトの名無しさん mailto:sage [2017/06/28(水) 10:57:07.89 ID:+O8L6XqQ.net]: 366 :nobodyさん 2017/05/29(月) 16:07:39.16 ID:6v4UcGhE
今回の民法改正、ソフトウェア受�
446 名前：J発の場合、(検収後ではなく)バグ発見後１年瑕疵担保責任があるということで、地獄かよ、と思ったが、 元々問題が起きがちな受託案件がビジネス的に成立しなくなることで強制的に業界再編につながるなら良いことかもと思うようになった。 一部で地獄を見ても。 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など動的言語は確実に廃れる。 保守に強い言語のみ生き残れる。 []: [ここ壊れてます]
447 名前：デフォルトの名無しさん [2017/06/28(水) 11:02:48.67 ID:6P8PW2pA.net]: ↑の for 文は j = 1 から始まっています。

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

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

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

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

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

正しくは、

for 文は j = 2 から始めなくては駄目です。
448 名前：デフォルトの名無しさん [2017/06/28(水) 11:19:51.44 ID:6P8PW2pA.net]: あ、もう一つバグがありました↑

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

となっていますが、

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

でなければなりません。
449 名前：デフォルトの名無しさん [2017/06/28(水) 12:31:24.06 ID:W36D2Opo.net]: >>438
>インデックスが 0 の要素は初期化すらしていません

配列[0] を使わないのなら、初期化する必要はない
450 名前：デフォルトの名無しさん [2017/06/28(水) 12:34:24.00 ID:6P8PW2pA.net]: >>440

そうですが、

for(j = 1;

とすると

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

この値がたまたま 0 で初期化されていて、かつ 0 であれば正しく動くため、
問題が表面化していないだけです。
451 名前：デフォルトの名無しさん [2017/06/28(水) 12:37:24.37 ID:6P8PW2pA.net]: 有向無閉路ネットワークの最長パスをトポロジカルラベリングを利用して、
求めるアルゴリズムって他の本に載っていますか？

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

この本は、鮮やかに解けるように問題を特殊化して見せ場を作っていますね。
452 名前：デフォルトの名無しさん [2017/06/28(水) 13:17:27.40 ID:6P8PW2pA.net]: >>426

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

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

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

オイラーグラフの一筆書きのプログラムがあったりします。
453 名前：デフォルトの名無しさん mailto:sage [2017/06/28(水) 14:35:33.86 ID:itdARVty.net]: 外部変数は0で初期化される。
454 名前：デフォルトの名無しさん mailto:sage [2017/06/28(水) 15:46:50.33 ID:7M5wzg7m.net]: j=1で始まってんのに意図せず配列[0]を参照するの意味がわからん
455 名前：デフォルトの名無しさん mailto:sage [2017/06/28(水) 16:26:43.89 ID:mp82Jtm6.net]: それでも馬鹿のアスペの荒らしをスルーできない
456 名前：デフォルトの名無しさん [2017/06/28(水) 18:29:25.09 ID:6P8PW2pA.net]: >>444

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

a == revedgefirst[1] == 0 なので、 tail[a] == tail[0] です。
457 名前：デフォルトの名無しさん [2017/06/28(水) 18:29:51.34 ID:6P8PW2pA.net]: 訂正します：

>>445

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

a == revedgefirst[1] == 0 なので、 tail[a] == tail[0] です。
458 名前：デフォルトの名無しさん [2017/06/28(水) 18:33:38.48 ID:6P8PW2pA.net]: さらに、

v == tporder[1] == 1 です。
459 名前：デフォルトの名無しさん [2017/06/29(木) 11:58:28.12 ID:df4uIsIb.net]: imgur.com/A84Qz1i.jpg
imgur.com/NsXCsS1.jpg
imgur.com/Bm7ANHm.jpg
imgur.com/iSqMNes.jpg

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

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

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

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

どうでしょうか？
460 名前：デフォルトの名無しさん [2017/06/29(木) 12:19:34.40 ID:df4uIsIb.net]: むしろ、十分性が成り立つことを前提にしてアルゴリズムの正しさを証明しているように思います。
461 名前：デフォルトの名無しさん mailto:sage [2017/06/30(金) 09:51:08.15 ID:pDIkSJMf.net]: 粘着
462 名前：デフォルトの名無しさん [2017/06/30(金) 13:39:18.75 ID:8CLI6C9V.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）

ホップクロフト - カープのアルゴリズムのところを読んでいます。

段々、面白いアルゴリズムが登場してきていますね。

日本語のアルゴリズムの本は本当に初歩的な本が多いですが、なぜなのでしょうか？

例えば、ホップクロフト - カープのアルゴリズムが載っている本はあるでしょうか？

日本語の本に載っているのは、

リスト、ハッシュ、ヒープ、2分探索木、平衡木、ソート、最短経路、文字列

とかそんなもんだけですよね。
463 名前：デフォルトの名無しさん mailto:sage [2017/06/30(金) 19:08:50.27 ID:OVGL+Zaw.net]: 初歩的な問題すら理解できずにドヤ顔で間違った反例晒すやつがいるからだよ
464 名前：デフォルトの名無しさん mailto:sage [2017/06/30(金) 20:21:27.99 ID:QJcLAte5.net]: それ以上の難解アルゴリズムに挑戦する頭脳があれば英語の習得は容易いので、結果すでにある英語本を買うようになると予想
465 名前：デフォルトの名無しさん [2017/07/01(土) 09:37:54.54 ID:OLSj8alI.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。

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();
}
466 名前：デフォルトの名無しさん [2017/07/01(土) 09:42:20.68 ID:OLSj8alI.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

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

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

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

for(a = edgefirst[v1]; a != 0; a = edgenext[a]){
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
}
467 名前：デフォルトの名無しさん [2017/07/01(土) 09:46:11.85 ID:OLSj8alI.net]: 茨木俊秀さんの本でも感じましたが、ひどいコードを書く人が多いですよね。

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

goto 文を使わなくていいところで常用しています。
468 名前：デフォルトの名無しさん mailto:sage [2017/07/01(土) 09:53:17.51 ID:w5457acR.net]: 粗さがしが得意みたいだから、出版社で校正でもやったら良いのでは？
469 名前：デフォルトの名無しさん mailto:sage [2017/07/01(土) 09:55:39.01 ID:PrUYVLVg.net]: 伏字かと思ったらインデントかよ。
これが見やすいと思ったんだろうか？ここに辿り着くまでの思考過程を見てみたいわ。
470 名前：デフォルトの名無しさん [2017/07/01(土) 09:59:03.29 ID:OLSj8alI.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。

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

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

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

ひどいコードです。
471 名前：デフォルトの名無しさん mailto:sage [2017/07/01(土) 12:24:50.45 ID:HZmJrzKI.net]: >>460
基地外の思考過程なんて見たらSAN値下がるぞ。
472 名前：デフォルトの名無しさん [2017/07/01(土) 12:35:14.71 ID:OLSj8alI.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。

このプログラムですが、意味不明に冗長なところがあるので超分かりにくいです。

もし、この本を読む人は、注意した方がいいです。

分かりやすい等価なコードにすこしずつ変えながら読んでいます。
473 名前：デフォルトの名無しさん [2017/07/01(土) 20:40:17.40 ID:OLSj8alI.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。

プログラムに、非常に非効率な部分を発見しました。

深さ優先探索で最短パスを探す部分があるのですが、一つの最短パスを
発見した後も、うろうろと探索を続けています。 return 文で呼び出し元へと
遡って戻るべき箇所です。

具体的にいうと、p.95の void bipartite_dfs(int) 関数内の

bipartite_dfs(w1);

は、

bipartite_dfs(w1);
if(pathfound) return;

とすべきです。
474 名前：デフォルトの名無しさん mailto:sage [2017/07/01(土) 22:15:24.31 ID:fqWBe1B0.net]: 俺様のアスペ日記
475 名前：デフォルトの名無しさん [2017/07/01(土) 23:27:45.18 ID:OLSj8alI.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）

のHopcroft-Karpのアルゴリズムのプログラムを一切変更を加えずに使用して、
Aizu Online Judgeの2部グラフのマッチングの問題を解かせてみたら、
1問目から正しい結果が得られませんでした。

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

では一つの例に対して、プログラムをチェックしているだけです。
その例に対しては正しい結果が得られます。

著者はおそらく他の例についてはチェックしていないと思われます。

これから原因を究明しようと思います。

ちなみに

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

での例ですが、この著者の旧著でも全く同じ例を使っています。

使いまわしですね。他の例は一度もチェックしていないようです。 👀
Rock54: Caution(BBR-MD5:0be15ced7fbdb9fdb4d0ce1929c1b82f)
476 名前：デフォルトの名無しさん [2017/07/01(土) 23:59:37.67 ID:OLSj8alI.net]: あ、勘違いでした。

入力のフォーマットが会津と浅野の本で違いました。
477 名前：デフォルトの名無しさん [2017/07/02(日) 12:42:08.55 ID:KDfMECXZ.net]: マッチングといっても、いろいろな問題があるんですね。

安定マッチングと最大マッチングは互いに何の関係もない全く異なる問題ですね。

↓の講義は、安定マッチングについてですが、簡単ですね。

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-7-matching-problems/#vid_related

MITの微分積分の講義を見ると学生のレベルが低いという印象ですが、この講義を見ると
そうでもないような印象です。
478 名前：デフォルトの名無しさん [2017/07/02(日) 13:22:29.16 ID:KDfMECXZ.net]: >>468

なんか明らかなことをダラダラと証明していますね。
479 名前：デフォルトの名無しさん [2017/07/03(月) 08:45:45.65 ID:b174092u.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）

を読んでいます。

定理：
G のマッチング M に対して、 M が最大マッチングであるための必要十分条件は M に
関する増加パスが存在しないことである。

という定理が書いてあります。

十分性の証明が長すぎます。見た目はちょっとすっきりとしていていいのですが、長くて
素朴な証明法ではありません。
480 名前：デフォルトの名無しさん [2017/07/03(月) 08:46:22.05 ID:b174092u.net]: 以下のような証明が素朴なよい証明だと思います。

G のマッチング M に対して、 M が最大マッチングであるための必要十分条件は M に関する増加パスが存在しないことである。

必要性は明らかである。

十分性について証明する。

G は連結である場合に証明できれば、 G が連結でない場合にも、明らかに定理は成り立つ。
そのため、 G は連結であると仮定する。

G には、 M に関する増加パスが存在しないと仮定する。
M の辺に接続されていない点をFreeな点と呼ぶことにする。

G にFreeな点が2点以上存在することはないことを背理法によって証明しよう。
a, b を G の任意のFreeな2点とする。 G は連結だから、 a, b を結ぶ単純なパスが存在する。
a = a_1, …, a_k = b をその単純なパスとする。
このとき、　a_1, …, a_i に含まれるFreeな点の数が 2 であるような i ≧ 2 が存在することは明らかである。
単純なパス a_1, …, a_i は明らかに増加パスである。
これは、 G には、 M に関する増加パスが存在しないという仮定に反する。

よって、 G にFreeな点が2点以上存在することはない

G にFreeな点が1点存在する場合には、 G の点の数は、奇数であり、明らかに M は最大マッチングである。
G にFreeな点が1点も存在しない場合には、 G の点の数は、偶数であり、明らかに M は最大マッチングである。
481 名前：デフォルトの名無しさん [2017/07/03(月) 08:55:27.46 ID:b174092u.net]: なんか他の本を調べてみても、

>>471

のような素朴な証明法が載っていませんね。

ソートするアルゴリズムが存在することを示せ

という問題があったとして、答えとして、バブルソートをあげれば十分であるにもかかわらず、
ヒープソートをあげるようなもんですね。
482 名前：デフォルトの名無しさん mailto:sage [2017/07/03(月) 12:01:19.36 ID:2KgtUC+G.net]: >471

頂点a b c d eがあって、
辺が、
a b
a c
a d のとき、
Mとして
a bを選べば、増加パスはないけど、
cとdはFreeな頂点になるのでは？
483 名前：デフォルトの名無しさん [2017/07/03(月) 12:17:16.61 ID:b174092u.net]: >>473

ありがとうございます。

>>471
は間違いですね。
484 名前：デフォルトの名無しさん mailto:sage [2017/07/03(月) 22:09:21.73 ID:d7TtC2S/.net]: >>474

ズコーッ
485 名前：デフォルトの名無しさん [2017/07/03(月) 23:57:03.23 ID:kWtGcdOg.net]: >>474

ヽ(･ω･)/ｽﾞｺｰ
486 名前：デフォルトの名無しさん mailto:sage [2017/07/06(木) 14:52:18.01 ID:MPcf+VnS.net]: 松坂君はおつむ弱いなー
487 名前：デフォルトの名無しさん [2017/07/07(金) 10:19:21.25 ID:LuN3QDVY.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。

ネットワークフローについてですが、
ソースから流出する総フローが、
シンクに流入する総フローに
等しいということを自明のこととして、
証明していません。

これはOKなのでしょうか？
488 名前：デフォルトの名無しさん mailto:sage [2017/07/07(金) 10:33:49.72 ID:Hkhwo5qO.net]: おつむが弱いアスペ参上
489 名前：デフォルトの名無しさん [2017/07/07(金) 11:03:27.05 ID:LuN3QDVY.net]: やはり証明は必要なんですね。
↓の本に証明が載っていました。

組合せ数学入門 II (共立全書)
C.L.リウ
https://www.amazon.co.jp/dp/4320005422
490 名前：デフォルトの名無しさん [2017/07/07(金) 11:04:16.11 ID:LuN3QDVY.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）

は、計算量の評価の説明がひどすぎます。

ほとんど結果しか書いていません。
491 名前：デフォルトの名無しさん [2017/07/07(金) 11:53:23.95 ID:LuN3QDVY.net]: >>478

少し後のところで、
ソースから流出する総フローが、
シンクに流入する総フローに
等しいという結果を特別な場合として
含むような結果を示していました。

ソースから流出する総フローが、
シンクに流入する総フローに
等しいということが自明なことならば、
そのより一般化された結果も自明です。

著者の態度は矛盾していますね。
492 名前：デフォルトの名無しさん mailto:sage [2017/07/07(金) 13:13:44.59 ID:G2hd19q1.net]: 僕の肛門から流出するソースの総フローがシンクに流入します
493 名前：デフォルトの名無しさん [2017/07/07(金) 17:37:48.39 ID:LuN3QDVY.net]: 今、ウィルソンのグラフ理論の本を見てみたのですが、内容がスカスカですね。

アルゴリズム的なグラフ理論の本のほうが分かりやすいし、面白いですね。
494 名前：デフォルトの名無しさん [2017/07/07(金) 19:30:12.19 ID:LchmZiK1.net]: 「29歳既婚、2年前に会社を辞めた。ボードゲーム作りを始めて3700万円を
売り上げたけど何か聞きたいことはある？」回答いろいろ
labaq.com/archives/51880196.html
日本ボードゲーム界の異端児に聞く！ボードゲームデザイナーとして生きていくには？
https://bodoge.hoobby.net/columns/00013
カードゲームを自作する1　【自宅でカード印刷】
tanishi.org/?p=801
100円ショップでボードゲームを自作しよう
https://sites.google.com/site/jun1sboardgames/blog/makeyourbg
ノーアイデアでボードゲームを作ろう第1回「100円ショップで物を買う」
boardgamelove.com/archives/boardgame-make-1/
ボードゲーム市場がクラウドファンディングの出現で急成長を遂げ市場規模を拡大中
gigazine.net/news/20150820-board-game-crowdfunding/
自作ゲーム即売会「ゲームマーケット」に１万人超
www.nikkansports.com/general/nikkan/news/1750500.html
ボードゲームの展示イベント「ゲームマーケット」の成長記録からこれからの
市場に必要なことを妄想してみた。6年間の来場者数推移（2016年4月時点調べ）
https://bodoge.hoobby.net/columns/00001
495 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 06:00:28.99 ID:h3/vqusb.net]: >>484
あ？　スカトロが何だって？
496 名前：デフォルトの名無しさん [2017/07/08(土) 09:51:52.03 ID:bx7kaphQ.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）の
Ford - Fulkerson　のアルゴリズムのプログラムを読んでいます。

ひどいプログラムです。

たとえば、深さ優先探索を行う関数を見てください↓

void dfs(int v, int path[]){// vからの深さ優先探索
■■■■int afwd, abk, w;
■■■■afwd = edgefirst[v];
■■■■while (afwd != 0 && rescap[afwd] == 0) afwd = edgenext[afwd];
■■■■while (t_found == false && afwd != 0) {// 増加パスはまだ発見されいない限り
■■■■■■■■w = head[afwd];
■■■■■■■■if (path[w] == unvisited) {// wが未訪問であったらwへ前進
■■■■■■■■■■■■abk = afwd+1; // abkはafwdの逆向きの辺
■■■■■■■■■■■■if (afwd % 2 ==0) abk = afwd-1;
■■■■■■■■■■■■path[w] = abk; // afwdの逆向きの辺abkをpath[w]に記憶する
■■■■■■■■■■■■if (w != t) dfs(w,path); // wからの深さ優先探索へ進む
■■■■■■■■■■■■else {// w == t なので増加パスPが見つかった
■■■■■■■■■■■■■■■■t_found=true; // dfs(v,path)の強制終了へ
■■■■■■■■■■■■}
■■■■■■■■}
■■■■■■■■if (t_found == false) { // dfs(v,path)が強制終了になっていないときのみ
■■■■■■■■■■■■ afwd = edgenext[afwd]; //次の辺に移る
■■■■■■■■■■■■ while (afwd != 0 && rescap[afwd] == 0) afwd = edgenext[afwd];
■■■■■■■■}
■■■■}
}
497 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 10:04:34.97 ID:gbIBpGm+.net]: 基地外こえーな
498 名前：デフォルトの名無しさん [2017/07/08(土) 10:07:07.69 ID:bx7kaphQ.net]: ↓は、↑と等価なプログラムです。

すっきりとしていて分かりやすいですね。↓

void dfs(int v, int path[]){
■■■■int afwd, abk, w;
■■■■afwd = edgefirst[v];
■■■■for(afwd = edgefirst[v]; afwd != 0; afwd = edgenext[afwd]){
■■■■■■■■if(rescap[afwd] == 0) continue;
■■■■■■■■w = head[afwd];
■■■■■■■■if(path[w] == unvisited){
■■■■■■■■■■■■if(afwd % 2 == 0){
■■■■■■■■■■■■■■■■abk = afwd - 1;
■■■■■■■■■■■■}else{
■■■■■■■■■■■■■■■■abk = afwd + 1;
■■■■■■■■■■■■}■■■■■■■■
■■■■■■■■■■■■path[w] = abk;
■■■■■■■■■■■■if(w != t){
■■■■■■■■■■■■■■■■dfs(w, path);
■■■■■■■■■■■■}else{
■■■■■■■■■■■■■■■■t_found = true;
■■■■■■■■■■■■■■■■return;
■■■■■■■■■■■■}
■■■■■■■■}
■■■■}
}
499 名前：デフォルトの名無しさん [2017/07/08(土) 10:10:00.82 ID:bx7kaphQ.net]: 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）のプログラムは
すべて↑こんな感じなので、いちいち自分でまともな等価なプログラムに改善してから
読む必要に迫られます。
500 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 10:29:14.58 ID:W4vGtvme.net]: 海苔弁プログラムと呼ぶことにしよう
501 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 10:35:19.17 ID:dHGGPCH1.net]: アホのアスペ日記
502 名前：デフォルトの名無しさん [2017/07/08(土) 14:20:34.28 ID:bx7kaphQ.net]: for-2ch-codes/FlowLibrary.h

↓こちらが浅野さんの Ford - Fulkerson のアルゴリズムのソースコードです：
for-2ch-codes/asano_fordfulkerson.c

↑なぜ、こんな分かりにくいコードを書けるのか不思議です。
アルゴリズムの研究者なのに、プログラミングをしたことがないのでしょうか？

↓こちらが浅野さんのコードを読みやすくした等価なコードです：
for-2ch-codes/my_fordfulkerson.c
503 名前：デフォルトの名無しさん [2017/07/08(土) 14:21:50.45 ID:bx7kaphQ.net]: https://github.com/for-2ch/for-2ch-codes/blob/master/FlowLibrary.h

↓こちらが浅野さんのソースコードです：
https://github.com/for-2ch/for-2ch-codes/blob/master/asano_fordfulkerson.c

↑なぜ、こんな分かりにくいコードを書けるのか不思議です。
アルゴリズムの研究者なのに、プログラミングをしたことがないのでしょうか？

↓こちらが浅野さんのコードを読みやすくした等価なコードです：
https://github.com/for-2ch/for-2ch-codes/blob/master/my_fordfulkerson.c
504 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 14:46:01.89 ID:shVOEDs/.net]: ■■■■■■■■■■■■■
■■このスレ闇が深すぎ■■
■■■■■■■■■■■■■
505 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 15:34:28.51 ID:/nxmjkTk.net]: すみません、松坂くんて誰ですか
506 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 16:30:54.37 ID:/Hl6yXpd.net]: >>496
教科書の荒さがして著者をdisることを生きがいとしてる厨房

ID:bx7kaphQ

Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net
rio2016.2ch.net/test/read.cgi/math/1497007079/
507 名前： ◆QZaw55cn4c mailto:sage [2017/07/08(土) 18:49:23.91 ID:/o9ObF5e.net]: >>497
高等な趣味だと思うよ，よく頑張っているね
508 名前：デフォルトの名無しさん mailto:sage [2017/07/08(土) 19:37:28.26 ID:ICTsGxtb.net]: 馬鹿アスペ同士仲良く
509 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 17:28:01.51 ID:X4hx0gz3.net]: お前ら、ちゃんと次スレ立ててやれよ？
隔離スレさえあればこっちに被害は及ばないからな
510 名前：デフォルトの名無しさん mailto:sage [2017/07/09(日) 17:29:01.52 ID:ZR+XIVIQ.net]: お前がやれよ
511 名前：デフォルトの名無しさん mailto:sage [2017/07/10(月) 01:48:04.10 ID:LYhH/bN3.net]: よし、今日からワイがM坂だ！
512 名前：デフォルトの名無しさん [2017/07/10(月) 10:06:36.48 ID:BQfNYjN8.net]: 比較によるソートの比較回数の下限についての議論で決定木が登場します。

決定木の葉の数が n! 以上だという記述があるのですが、ちょうど n! ではないのでしょうか？

意味不明です。
513 名前：デフォルトの名無しさん [2017/07/10(月) 13:49:55.16 ID:BQfNYjN8.net]: そもそも決定木って何ですか？
514 名前：デフォルトの名無しさん [2017/07/10(月) 14:01:08.40 ID:BQfNYjN8.net]: 例えば、決定木の内部ノードに 1: 2 というのノードにおいて、
a_1 ≧ a_2 であるか a_1 < a_2 であるかを計算しますが、
その計算結果を捨ててしまってもいいんですよね？
515 名前：デフォルトの名無しさん [2017/07/10(月) 14:02:15.57 ID:BQfNYjN8.net]: 例えば、決定木の内部ノードに 1: 2 というノードがあったとすると、そのノードにおいて、
a_1 ≧ a_2 であるか a_1 < a_2 であるかを計算しますが、その計算結果を捨ててしまっ
て以後利用しなくてもいいんですよね？
516 名前：デフォルトの名無しさん [2017/07/10(月) 17:02:14.26 ID:BQfNYjN8.net]: imgur.com/XyDXq0t.jpg

↑は普通の決定木です。

imgur.com/zqlLVWW.jpg

↑のような決定木はどう扱うのでしょうか？
517 名前：デフォルトの名無しさん mailto:sage [2017/07/10(月) 17:11:43.87 ID:OAwCY67i.net]: どこでもたちまち糞日記スレにしてしまう恐ろしさ
518 名前：デフォルトの名無しさん mailto:sage [2017/07/10(月) 17:39:12.62 ID:S+vnKcL6.net]: 他にも被害スレが？
519 名前：デフォルトの名無しさん [2017/07/10(月) 18:34:52.99 ID:BQfNYjN8.net]: 段々、言いたいことが分かってきました。

a1, a2, a3, a4 を比較によってソートするあるアルゴリズムがあるとします。

そのアルゴリズムには対応する決定木 T が存在します。

深さ k の決定木の葉の数の最大値は明らかに 2^k です。（深さ k の完全2分木の場合）

a1, a2, a3, a4 の大小関係の可能性は、以下の 4! = 24 通りあります。

a1 < a2 < a3 < a4
a1 < a2 < a4 < a3
…
a4 < a3 < a2 < a1

そのすべての可能性に対してそのアルゴリズムはソートしなければならないので、
T の葉の数はちょうど 24 であるはずです。

深さ 1 の決定木はただ一つ存在し、葉の数は 2 です。
24 ≠ 2 なので、 T の深さは 1 ではありません。

深さ 2 の決定木の葉の数の最大値は 2^2 = 4 です。

24 ≦ 4 ではないため深さ 2 の決定木では、 24 個の葉を収容できません。

深さ 3 の決定木の葉の数の最大値は 2^3 = 8 です。

24 ≦ 8 ではないため深さ 3 の決定木では、 24 個の葉を収容できません。
520 名前：デフォルトの名無しさん [2017/07/10(月) 18:37:08.78 ID:BQfNYjN8.net]: 深さ 4 の決定木の葉の数の最大値は 2^4 = 16 です。

24 ≦ 16 ではないため深さ 4 の決定木では、 24 個の葉を収容できません。

深さ 5 の決定木の葉の数の最大値は 2^5 = 32 です。

24 ≦ 32 であるため深さ 5 の決定木には、 24 個の葉を収容可能です。

以上から、決定木 T の葉の深さは最低でも 5 である必要があります。
521 名前：デフォルトの名無しさん [2017/07/10(月) 18:52:50.18 ID:BQfNYjN8.net]: a_1, a_2, …, a_n を比較によってソートするあるアルゴリズムがあるとします。

そのアルゴリズムには対応する決定木 T が存在します。

深さ k の決定木の葉の数の最大値は明らかに 2^k です。（深さ k の完全2分木の場合）

a_1, a_2, …, a_n の大小関係の可能性は、以下の n! 通りあります。

a_1 < a_2 < … a_(n-1) < a_n
a_1 < a_2 < … a_n < a_(n-1)
…
a_n < a_(n-1) < … < a_1

そのすべての可能性に対してそのアルゴリズムはソートしなければならないので、
T の葉の数はちょうど n! であるはずです。

n! 個の葉を収容するためには、 T の深さを k とすると、

n! ≦ 2^k

が成り立たなければなりません。

よって、

lg(n!) ≦ lg(2^k) = k*lg(2) = k

が成り立たなければなりません。
522 名前：デフォルトの名無しさん [2017/07/10(月) 18:53:05.24 ID:BQfNYjN8.net]: lg(n!) = Θ(n*lg(n)) ですので、

Θ(n*lg(n)) ≦ k

が成り立ちます。

以上より、比較によってソートする最高速度のアルゴリズムでも、その決定木の深さは
少なくとも Θ(n*lg(n)) の深さがあります。

よって、その最高速度のアルゴリズムにとって最悪のデータ a_1, a_2, …, a_n を与えた場合、
少なくとも Θ(n*lg(n)) 回の比較が必要です。
523 名前：デフォルトの名無しさん [2017/07/10(月) 18:57:08.74 ID:BQfNYjN8.net]: 訂正します：

lg(n!) = Ω(n*lg(n)) ですので、

Ω(n*lg(n)) ≦ k

が成り立ちます。

以上より、比較によってソートする最高速度のアルゴリズムでも、その決定木の深さは
少なくとも Ω(n*lg(n)) の深さがあります。

よって、その最高速度のアルゴリズムにとって最悪のデータ a_1, a_2, …, a_n を与えた場合、
少なくとも Ω(n*lg(n)) 回の比較が必要です。
524 名前：デフォルトの名無しさん [2017/07/10(月) 19:00:21.22 ID:BQfNYjN8.net]: なんか非常に大雑把な議論で Ω(n*lg(n)) という評価を得ているのに、
ヒープソートやマージソートのような O(n*lg(n)) のアルゴリズムが存在する
というところが不思議ですね。
525 名前：デフォルトの名無しさん mailto:sage [2017/07/10(月) 19:15:23.77 ID:wVcu7osF.net]: この人DHAだろ
526 名前：デフォルトの名無しさん mailto:sage [2017/07/10(月) 19:19:20.07 ID:TpSxkkBl.net]: マグロの目？
527 名前：デフォルトの名無しさん [2017/07/10(月) 20:08:22.69 ID:BQfNYjN8.net]: アマゾンってダメダメですね。

【全品10%ポイント還元】マンガ・雑誌など本全品がお買い得
7/10 18:00～7/11 23:59のプライムデー限定で全ての商品が10%ポイント還元中！＞今すぐチェック

ヤフーショッピングとかで買えば実質30%引きくらいで買えるときもありますよね。
528 名前：デフォルトの名無しさん mailto:sage [2017/07/10(月) 20:27:20.96 ID:Di3Z2y8c.net]: >>516
ＡＤＨＤ？唯の馬鹿のアスペだと思う
529 名前：デフォルトの名無しさん [2017/07/11(火) 02:13:19.92 ID:kTultHtx.net]: URLとかファイルパスとかコマンドとかをクッソ汚い文字列として
文字列処理で結合したり変数埋込みしたり正規表現使ったり
するコードとか、
エンコードされたり、エスケープ混じりのぐちゃぐちゃな文字列とか
とにかく汚くて長くて改行されてない文字列処理にも
データ構造やデザインパターンて適用できるの？
またはデータ構造やデザインパターンでソースをきれいに
整形できたりする？
530 名前：デフォルトの名無しさん mailto:sage [2017/07/11(火) 10:51:23.09 ID:GFhKOZAg.net]: 文字列処理っつってもいろいろあんだろ
どういう処理がしたいのかもわからんのにデザパタ適用もクソもあるかよ
531 名前：デフォルトの名無しさん mailto:sage [2017/07/11(火) 11:15:39.29 ID:oEYLH8ZM.net]: Stringというデータ構造
532 名前：デフォルトの名無しさん mailto:sage [2017/07/11(火) 19:00:22.76 ID:XmA15/s4.net]: クッソ汚いもぐちゃぐちゃも個人の感想だから伝わらない
533 名前：デフォルトの名無しさん mailto:sage [2017/07/11(火) 21:26:37.33 ID:rybeffro.net]: おう、松坂！
次スレな

俺は賢い、ディープラーニング教えて [無断転載禁止]©2ch.net
https://mevius.2ch.net/test/read.cgi/tech/1498636978/l50
534 名前：デフォルトの名無しさん mailto:sage [2017/07/12(水) 14:44:43.08 ID:sNyzU/qO.net]: 著者名NGに入れて連鎖あぽーんですっきりするな
535 名前：デフォルトの名無しさん [2017/07/12(水) 18:59:57.68 ID:BkmceXb8.net]: 繁野麻衣子著『ネットワーク最適化とアルゴリズム』を読んでいます。

imgur.com/RI1TvXi.jpg

部分グラフの定義がおかしいです。

こんな基礎的なところで間違いを犯しているというのが信じられません。
536 名前：デフォルトの名無しさん [2017/07/12 ]: [ここ壊れてます]
537 名前：(水) 19:25:04.11 ID:BkmceXb8.net mailto: あ、グラフになっていないと部分グラフとは言わないからOKなんですね。

でも分かりにくい表現ですね。 []: [ここ壊れてます]
538 名前：デフォルトの名無しさん [2017/07/12(水) 19:35:27.04 ID:BkmceXb8.net]: A' が空集合の場合はどうするんですかね？
539 名前：デフォルトの名無しさん [2017/07/12(水) 19:40:24.94 ID:BkmceXb8.net]: 空写像って何ですか？
540 名前：デフォルトの名無しさん mailto:sage [2017/07/12(水) 19:50:43.67 ID:sNyzU/qO.net]: 中学生？
541 名前：デフォルトの名無しさん mailto:sage [2017/07/13(木) 01:49:26.96 ID:dTYbVLC2.net]: ただの基地外だろう。
542 名前：デフォルトの名無しさん [2017/07/16(日) 19:13:54.39 ID:jm8THNZB.net]: D40
imgur.com/i8hq9mG.jpg

↑この問題に対する解答ですが、

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

の解答であっていますか？

2週間くらい前に書いたものですが、理解ができません。

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

↑ここが理解できません。
543 名前：デフォルトの名無しさん [2017/07/16(日) 19:22:48.15 ID:jm8THNZB.net]: あー理解できました。

ここは分かりやすく書き直したほうがいいですね。
544 名前：デフォルトの名無しさん [2017/07/16(日) 19:35:47.89 ID:jm8THNZB.net]: 仮に、 T に含まれないような C の辺たちの両端点を結ぶ T の辺のみからなる
パスたちがすべて辺 AB を含まないと仮定します。

A_1 := A
A_n ;= B

とします。

サイクル C が以下であるとします：

A_1 → … → A_n → A_1

もしも、

辺 A_i → A_(i+1) が T に含まれないときには、

サイクル C の A_i → A_(i+1) の部分を A_i から A_(i+1) への（一意的な） T の辺のみから
なるパスに置き換えます。

すると、 A から B への T の辺のみからなるパスで辺 AB を含まないようなパスが構成できます。

これは A から B への T の辺のみからなるパスが一意的であるという木の性質に反します。
（ほかに A → B
545 名前： という T の辺のみからなる長さ 1 のパスが存在することに注意。） []: [ここ壊れてます]
546 名前：デフォルトの名無しさん mailto:sage [2017/07/16(日) 19:54:31.53 ID:oSRVjDnX.net]: 糞日記

分からない問題はここに書いてね428 [無断転載禁止]©2ch.net
rio2016.2ch.net/test/read.cgi/math/1498222858/749
547 名前：デフォルトの名無しさん mailto:sage [2017/07/19(水) 22:52:51.73 ID:W3gBCwo8.net]: データ構造とアルゴリズムを勉強するときに、プログラム作成の言語は何がおすすめでしょうか？

なぜ、いまだにC++が幅を利かせているのでしょうか？
548 名前： ◆QZaw55cn4c mailto:sage [2017/07/20(木) 01:30:17.29 ID:NeFB4pBD.net]: >>536
C/C++が基本だから
549 名前：デフォルトの名無しさん mailto:sage [2017/07/20(木) 07:32:28.47 ID:JPSYgWUy.net]: JAVAやC#はなぜ主流じゃないんですか？
550 名前：デフォルトの名無しさん mailto:sage [2017/07/20(木) 08:06:18.81 ID:VwfBeboA.net]: 遅いから。
でも、JAVAはアルゴリズムの教科書でも使われていることあるよ。
551 名前：デフォルトの名無しさん mailto:sage [2017/07/20(木) 13:39:20.43 ID:+UhdLUtU.net]: Golangは爆速やで～
552 名前：デフォルトの名無しさん [2017/07/21(金) 05:47:07.66.net]: Foo foo; と
Foo foo = new Foo();
は何が違うの?

あるクラス内で
private String field; のとき

public String method(String field){
return field;
}
と、
public String method(){
return this.field;
}
は何が違うの?
553 名前： ◆QZaw55cn4c mailto:sage [2017/07/21(金) 08:00:44.54.net]: >>541
>Foo foo; と
>Foo foo = new Foo();
C/C++ か、それとも C#/Java か、はっきりさせよ
554 名前：デフォルトの名無しさん mailto:sage [2017/07/21(金) 08:35:20.75.net]: 命名規約的にJavaだろ
555 名前：デフォルトの名無しさん mailto:sage [2017/07/21(金) 10:31:24.26.net]: >>541
Foo foo; // 参照型変数fooを宣言
Foo foo = new Foo(); // さらに、メモリのヒープ領域ってとこにFoo型のインスタンスを作成し、その場所を代入

コンストラクタとかでよく見ることになると思うけど
Foo(String name) {
this.name = name;
}
これは想像どおりの挙動をしてくれる
引数とフィールドに同じ名前があったとき
フィールドのものを使いたいときあえてthisつける
Foo() {
String name = "bar";
this.name = name;
}
みたいなときも同じ
名前が被ったとき、フィールド側の変数を選ぶのがthis
556 名前：デフォルトの名無しさん mailto:sage [2017/07/21(金) 19:57:34.85 ID:+Ec9GEX5.net]: >>539
著者はズレてるよな。
557 名前：デフォルトの名無しさん mailto:sage [2017/07/21(金) 20:06:52.80 ID:+Ec9GEX5.net]: データ構造、アルゴリズムはCで勉強して、デザパタはC++で勉強するのがいいな。
558 名前：デフォルトの名無しさん [2017/07/22(土) 13:37:57.58 ID:S+qzOSdo.net]: 本当はGoやRuby Python JavaScript Kotlinあたりやりたいのに、
本格的なプログラミングとか設計勉強しようとすると
必ずJava, C, C++ あたりで解説されるから覚えざるを得ないというジレンマ。
559 名前：デフォルトの名無しさん mailto:sage [2017/07/22(土) 13:46:49.67 ID:0HjhMGYw.net]: おらLispやれLispゥ！
560 名前：デフォルトの名無しさん mailto:sage [2017/07/22(土) 18:31:48.46 ID:Yr9CVNZl.net]: >>547
インプレイス、という概念を植えつけられない言語でアルゴリズムをやるのは問題
でも Java が使われるのは疑問
561 名前：デフォルトの名無しさん [2017/07/22(土) 19:09:29.77 ID:3d/mUXex.net]: Javaだと問題があるのでしょうか？

セジウィックの本の第4版がJavaですが。
562 名前：デフォルトの名無しさん mailto:sage [2017/07/22(土) 19:10:22.08 ID:fXxiASxC.net]: >>547
GoやRuby Python JavaScript Kotlinあたりに入門ちゃんと済ませて、これから本格的なプログラミングとか設計を勉強していくぞって人なら
具体例の説明に使われる程度のJavaやCなんて、無勉でもある程度は読めるでしょ
563 名前：デフォルトの名無しさん [2017/07/22(土) 19:12:56.74 ID:3d/mUXex.net]: 例えば、Pythonだとソートとかハッシュとかリストとかが用意されていますが、
データ構造を学ぶ上では高級すぎるのではないでしょうか？
564 名前：デフォルトの名無しさん mailto:sage [2017/07/22(土) 19:21:52.44 ID:fJRG67nz.net]: Sedgwick のアルゴリズムの教科書は、C++版やJava版があるよね。
C++版はちょっと古くて、C++11以降のモダンな書き方で改訂版を出してほしい。

自分は、アルゴリズムの教科書は疑似コードのみを示すの（MITのCormenの）で勉強したんだけど、失敗だったと思っている。
疑似コードを真似してそのまま実装してたから、一文字変数あまりまえ、クラスや構造体を定義することはなく、何でもかんでも配列で済ませるというクセがついてしまった。
もうちょっと、オブジェクト指向とかを勉強してからにすればよかったのかも。
565 名前：デフォルトの名無しさん [2017/07/23(日) 11:49:40.37 ID:cZonGhlD.net]: Javaとか連想配列使うだけでもいちいちnewとかキャストとか
鬱陶しい。
566 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 14:58:46.77 ID:CNTwKpOF.net]: アルゴリズムは抽象的で、言語仕様とは切り離されたものであるべきなのだ。
そうは言っても手続き型を意識したものになりがちで、これを関数型に書き直せと言われても一目難しいものがままある
567 名前：デフォルトの名無しさん [2017/07/23(日) 15:44:19.76 ID:G5QCCj7S.net]: アルゴリズムイントロダクションを読んでいます。

imgur.com/xbuAPtJ.jpg

↑は、 ω 記法についてです。

「if the limit exists」

と書かれていますが、なぜこんなことを書いているのでしょうか？

意味不明です。
568 名前：デフォルトの名無しさん [2017/07/23(日) 15:46:31.20 ID:G5QCCj7S.net]: g(n) が漸近的に正であるような関数であれば、

f(n) = ω(g(n))

⇔

lim f(n) / g(n) = ∞

ではないでしょうか？

「if the limit exists」などと書いてある理由が分かりません。
569 名前：デフォルトの名無しさん [2017/07/23(日) 15:51:14.63 ID:G5QCCj7S.net]: アルゴリズムイントロダクションって結構いい加減ですよね。

やっぱりクヌースの本を読んだ方がいいのかもしれませんね。
570 名前：デフォルトの名無しさん [2017/07/23(日) 15:54:26.92 ID:G5QCCj7S.net]: 漸近的に正である関数
漸近的に非負である関数

について説明がありますが、

なぜ、漸近的に正である関数だけを考えないのでしょうか？

漸近的に非負である関数などこの本で登場する機会はあるのでしょうか？
571 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 15:55:21.76 ID:p86Uodim.net]: 松坂君の夏休みの糞日記
572 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 16:03:03.18 ID:I43wPtVl.net]: >>556-559
この基地外が人様を害さないことを祈るばかりだ。
573 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 16:05:04.45 ID:7bD+iXj9.net]: >>555
現実問題、アルゴリズムを書くコードはC、C++に限られる。
Fortran、Java、Python、C#など他の言語はそれで書かれたライブラリを呼ぶだけだ。
574 名前：デフォルトの名無しさん [2017/07/23(日) 16:09:19.74 ID:cZonGhlD.net]: 機械のパフォーマンスを追求するあまりに
人間時間のパフォーマンスを際限なく犠牲にする池沼
575 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 18:48:09.61 ID:wW+3pobQ.net]: >>563
それはお前みたいな業務プログラマの視点
576 名前：デフォルトの名無しさん [2017/07/23(日) 19:06:54.73 ID:cZonGhlD.net]: >>564
何だよ業務プログラマって
俺は人に使役されてないし、インフラも構築できるし、
人工知能や数学もやってるんだぞ。
お前みたいなパフォーマンスオタクのほうが頭おかしいから。
577 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 20:44:29.00 ID:Js688EZT.net]: >Javaとか連想配列使うだけでもいちいちnewとかキャストとか
>鬱陶しい。
笑
578 名前：デフォルトの名無しさん [2017/07/23(日) 20:46:56.02 ID:LRxsFVvF.net]: >>565
なんでそんなに必死なの?
579 名前：デフォルトの名無しさん mailto:sage [2017/07/23(日) 21:10:16.48 ID:7eA3s3Ch.net]: >>562
Youがライブラリ作ってもいいんだぞ
580 名前：デフォルトの名無しさん [2017/07/23(日) 23:45:48.25 ID:G5QCCj7S.net]: アルゴリズムイントロダクションを読んでいます。

「関数 n^(1 + sin(n)) の指数部の値は 0 と 2 の間で振動し、その中間にあるすべての値をとる」

などと書かれていますが、明らかに間違っていますよね。

sin(n) = 1/sqrt(2) となるような自然数 n は存在しません。

何を考えているのでしょうか？
581 名前：デフォルトの名無しさん [2017/07/23(日) 23:54:11.92 ID:G5QCCj7S.net]: n と書いておきながら n が R を動くと仮定しているとかそんなことはないですよね？
582 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 00:08:11.63 ID:1mGhcU0l.net]: 原文なの？　IT関係の翻訳は誤訳だらけだよ。
583 名前：デフォルトの名無しさん [2017/07/24(月) 00:10:01.69 ID:dw4Kx5PQ.net]: オリジナルのほうにも、

p.52
the value of the exponent in n^(1 + sin(n)) oscillates between 0 and 2, taking on all values in between

と書いてあります。
584 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 00:21:28.79 ID:BT4s6Lxv.net]: >557
0<=c g(n) < f(n)

って書いてあるのだから、（0 < c g(n) でなく、0 <= c g(n) であることに注意）
g(n) = 0, if n > 3
1, if n <= 3
とかなら、
f(n)/g(n) の極限は存在しないよ。
だから、もし極限が存在すれば、という限定をつけたのだと思うよ。
585 名前：デフォルトの名無しさん [2017/07/24(月) 00:25:53.48 ID:dw4Kx5PQ.net]: >>573

それだと、

極限が存在するかしないか以前に、

f(n) / g(n) は n ≦ 3 に対してしか定義されませんよね。

lim f(n) / g(n) と書いた以上は

∃n0 s.t. n ≧ n0 ⇒ g(n) ≠ 0

でないといけないと思います。
586 名前：デフォルトの名無しさん [2017/07/24(月) 00:27:22.94 ID:dw4Kx5PQ.net]: たとえば、

関数 h(n) の定義域が {0, 1, 2, 3} のときに、

lim h(n) などそもそも考えられないわけです。
587 名前：デフォルトの名無しさん [2017/07/24(月) 00:31:02.81 ID:dw4Kx5PQ.net]: >>573

まず、

0 <= c g(n)

となっているのが問題だと考えます。

g(n) は漸近的に正であるような関数でなければならないはずです。
588 名前：デフォルトの名無しさん [2017/07/24(月) 00:32:17.21 ID:dw4Kx5PQ.net]: このあたりのところを4人の著者のうち誰が書いたのか知りませんが、
非常に出来が悪いですね。

世界標準とはとてもいえないと思います。
589 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 00:33:52.43 ID:1mGhcU0l.net]: 書いてあるとおりにしか取れない。キミの解釈がむしろ分らない。
the value of the exponent って(1 + sin(n)) だよな。それは between 0 and 2で、taking on all values in betweenだよな。

nが自然数なのかは知らんけど、sin(n) = 1/sqrt(2) という解釈はどこから？
590 名前：デフォルトの名無しさん [2017/07/24(月) 00:36:55.54 ID:dw4Kx5PQ.net]: 「if the limit exists」と書いてある理由について考えられる唯一の可能性があります。

それは以下の可能性です。

f(n) = ω(g(n)) の定義では、 n は N を動くと考えている。

一方、

lim f(n) / g(n) = ∞

という式の n は R を動くと考えている。
591 名前：デフォルトの名無しさん [2017/07/24(月) 00:41:44.60 ID:dw4Kx5PQ.net]: >>578

例としてそのような値を考えたということです。

0 < 1 + 1/sqrt(2) < 2

ですが、

1 + sin(n) = 1 + 1/sqrt(2) となるような n ∈ N は明らかに存在しません。

1 + sin(n) = 0
1 + sin(n) = 2

となるような n ∈ N も明らかに存在しませんが、 in between というのが

0 と 2 を含まない可能性を考えて、↑のような例にしました。
592 名前：デフォルトの名無しさん [2017/07/24(月) 00:51:03.16 ID:dw4Kx5PQ.net]: やっぱりクヌースの本の完成度は群を抜いていますね。
593 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 01:21:19.59 ID:1mGhcU0l.net]: > the value of the exponent in n^(1 + sin(n)) oscillates between 0 and 2, taking on all values in between

書いてあるそのままの意味で、これは数学的に真で、
1 + sin(n) = 1 + 1/sqrt(2) を満たす自然数nが存在するなんてどこにも書いてないし、言ってない。
直前にnは自然数と定義してるならそれも引用してもらわないと判断のしようがない。おそらくnumberの略だろう。変数n。
594 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 01:46:14.40 ID:1mGhcU0l.net]: もっと本質的な勘違いか。
AならばBはA=Bではないし、AならばBは、BならばAでもないぞ。
言ってるのはthe value, taking on all values in between だけだからな。
595 名前：デフォルトの名無しさん [2017/07/24(月) 03:48:35.95 ID:qy6/mYOI.net]: >>582

n については何も記述がありません。

そもそも、普通なら関数について書くときには、定義域を書くはずですが、
書いてありません。

習慣として、 n と書けば自然数の集合を動く変数ということになりますので、
そう解釈するのが妥当です。

1 + sin(n) が 0 と 2　の間のすべての値をとるのであれば、当然、

0 < 1 + 1/sqrt(2) < 2 ですので、値 1 + 1/sqrt(2) もとります。
596 名前：デフォルトの名無しさん [2017/07/24(月) 03:58:43.71 ID:qy6/mYOI.net]: 念のため、公式ページの正誤表を見てみましたが、書いてありませんでした。

かなり売れている本だと思いますが、飛ばし読みしている人ばかりなのでしょうか？
597 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 04:32:03.26 ID:1mGhcU0l.net]: 数学の世界ならそうだろうが、数学本じゃなくてプログラミングの本なんだろ？
sin(n)　と書いてあればプログラマはたいてい n をfloat型かdouble型の変数だと解釈する。
=　一つとっても大抵のプログラミング言語は等式ではなく、代入演算子と定義している。
分野が違うのだから論理的におかしいと思ったらまずは定義を疑う。数学だってブール代数で1+1=1って書く場合もあるだろう。
今のプログラミング言語は+や-の演算子すら再定義できるのだ。

仮に自然数だとしても、次に本質的な論理問題。>>583 これ。

> 0 と 2　の間のすべての値をとる

これも怪しい。take on All Value なので、on　～の上にという意味で、日本語にするならば結果がその範囲内に収まるだろう。
All values in between take the valueではないのだ。AはBのとき、BはAか？もちろん偽。
つまり1 + sin(n) = 1 + 1/sqrt(2)を保証する記述ではない。
598 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 09:36:19.03 ID:yBhCO73J.net]: 馬鹿のアスペにかまうな
599 名前：デフォルトの名無しさん mailto:sage [2017/07/24(月) 15:13:09.34 ID:BdqEvISL.net]: >>569
>「関数 n^(1 + sin(n)) の指数部の値は 0 と 2 の間で振動し、その中間にあるすべての値をとる」

指数部の値は 0 と 2 の間で振動し、その中間にあるすべての値をとるんじゃね？
600 名前：デフォルトの名無しさん mailto:sage [2017/07/25(火) 00:02:25.50 ID:6PSqyxlH.net]: nが自然数か何かも書いてないのに勝手に自然数だと勘違いして発狂するとか何考えてんでしょうね
601 名前：デフォルトの名無しさん mailto:sage [2017/07/25(火) 08:35:49.61 ID:drKlbZNX.net]: sin(n) = 1/sqrt(2) のとき n = 約0.785。 degだと45度。
って、そういう話じゃなくて？
602 名前：デフォルトの名無しさん mailto:sage [2017/07/25(火) 16:29:58.97 ID:GyEh+ENJ.net]: nが自然数でも問題ない
603 名前：デフォルトの名無しさん mailto:sage [2017/07/25(火) 16:30:50.54 ID:GyEh+ENJ.net]: そもそも指数部(1 + sin(n))の話しかしてないんだから
604 名前：デフォルトの名無しさん mailto:sage [2017/07/26(水) 01:18:42.44 ID:lXGGezLP.net]: え？
605 名前：デフォルトの名無しさん mailto:sage [2017/07/26(水) 09:54:26.90 ID:xcmFWevw.net]: お
606 名前：デフォルトの名無しさん [2017/07/28(金) 14:53:29.74 ID:+gMyuDZP.net]: 凄いことにきずいたぜ！
「ポリモーフィズム」と「ラッパー」は反対の関係にあるんだ。
これによって「メソッド名」と「中身」が多対多の関係にできるってことだぜ。
607 名前：デフォルトの名無しさん mailto:sage [2017/07/29(土) 09:28:33.20 ID:eHtT0zBv.net]: ライブラリってログを吐いてもいいの？
608 名前：デフォルトの名無しさん [2017/08/06(日) 03:45:40.20 ID:tlOocLRL.net]: シーケンス図とかスタックトレースって都庁なんだな。
おれの言いたいことが分かるか？「東京都庁」なんだよ。
609 名前：デフォルトの名無しさん [2017/08/06(日) 03:55:13.24 ID:tlOocLRL.net]: 待てよ・・・ピラミッドやサクラダファミリアも同じ形をしてるじゃないか！
この世界の真実を見たぞ・・・
610 名前：デフォルトの名無しさん mailto:sage [2017/08/06(日) 16:19:04.74 ID:J9/QEsgx.net]: ムーの読みすぎ
611 名前：デフォルトの名無しさん [2017/08/08(火) 23:50:20.23 ID:/cPMGZTq.net]: つかオブジェクト名繋げないでいきなり関数とは変数とか
呼ぶやつまじでやめて。
継承した変数や関数なのか、このクラスで定義した変数や関数
のかわからないじゃん。
このクラスで定義したものだったら thisつけろよ。
612 名前：デフォルトの名無しさん mailto:sage [2017/08/09(水) 01:40:35.40 ID:MPlilw1q.net]: >>600
ちょっと何言ってるかよくわからない
613 名前：デフォルトの名無しさん mailto:sage [2017/08/09(水) 06:04:34.33 ID:Iqk5vMYz.net]: 言語なによ
614 名前：デフォルトの名無しさん mailto:sage [2017/08/09(水) 16:52:44.18 ID:dpRGvEHE.net]: javascriptωじゃね
615 名前：デフォルトの名無しさん [2017/08/11(金) 13:57:12.96 ID:Vbqo8hQM.net]: デザパタは覚えたし、クラス図やシーケンス図も読める、クラス図の通り
にコーディングもできるし、だいたい何らかのパターンに当てはめ
ればなんとか動く。
命名規則も全部決めてるからその規則通りに書けば自動的に動く
でも「なんでそうなるの？」って質問されるとさっぱりわからないんだよなぁ…
デザパタに則っていないコードとか、俺と違う命名規則の人が書いた
コードも一切理解不能(無能)。
616 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 14:22:23.73 ID:OJhNtZ6y.net]: >>604
ただの作業員じゃん(笑)
617 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 16:40:01.48 .net]: >>604
なんとなくだけど、将棋弱そう
618 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 16:48:21.14 ID:IcABKbyR.net]: >>604
なんとなくだけど、頭弱そう
619 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 17:03:34.23 ID:4Gx5aAK7.net]: IQ90くらいだろ
620 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 17:12:35.31 ID:07jWFZnC.net]: そんなに煽ってやるなよ
621 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 17:20:22.56 ID:4bbWTV9L.net]: 372仕様書無しさん2017/08/11(金) 10:31:43.41
フリーランスで検索すると引っかかる零細ITがやっているサイトはだめだ。
高額に見せているけど実際は50万前後
JIET加入した方がいいよ。案件は毎日千件以上末端価格は60万円　平凡な稼働時間の80万円の案件もある。
ユー子が求人をだしてる。名刺も渡せる。ユー子に名刺が渡せるんだぞ。夢のようだ

それらの案件まさぐってHPで転売していたのが零細ITがやるフリーランスサイト

自称エージェントはJIETから流れてくる案件を転売してるだけだった。
JIETに加入すれば誰でも案件に応募することができた。収入が40万50万台にならなくて済む

473非決定性名無しさん2017/08/03(木) 15:21:30.71

JIETに加入すれば誰でも3次60万からスタートだ。フリーランスのサイトをやってる
自称エージェントもそこから案件情報を取得しきてる。サイトで60万で釣って40万から55万の
間でやらしている。
622 名前：デフォルトの名無しさん mailto:sage [2017/08/11(金) 22:22:00.80 ID:vOciZ7Dc.net]: >>604
キミは理想のPGだよ。
623 名前：デフォルトの名無しさん [2017/08/11(金) 23:53:53.43 ID:VT8Bdzbq.net]: >>604
いまどきデザインパターン？
624 名前：デフォルトの名無しさん mailto:sage [2017/08/12(土) 05:31:45.11 ID:mqOU9Lu0.net]: オートマ限定免許だな
625 名前：デフォルトの名無しさん [2017/08/12(土) 11:21:25.45 ID:2oFLTBe8.net]: ちょｗｗ俺煽られすぎｗｗｗ
でも、モノは完成するようになったぜ。
要求、仕様から動作原理すっ飛ばして、命名規則だけで
モノが完成するから結構職場では役立ってるぜ。
他のプログラマはフレームワークの使い方がやっとだし
一人だけ技術力があるゴリラ野郎は人望がなくて自分の技術力が
人に盗まれるのを極力恐れているから基本的に部下に意地悪して
教えてあげれば済むことも何も教えてくれない。
社長はどんどん仕事取ってきて、だいたい半数のプロジェクトが進まずに凍結状態に
なり、ブチ切れた客をなんとかかわし続ける日々だ。
そんな状況で俺の場合動くモノを比較的完成する方だからゴリラには結構
気に入られて給料は上がったよ。会社がいつまで持つかは分からんが。
626 名前：デフォルトの名無しさん [2017/08/12(土) 11:28:43.73 ID:WyVA8Sgg.net]: このスレは初心者スレだったな。
627 名前：デフォルトの名無しさん mailto:sage [2017/08/12(土) 11:55:15.14 ID:NKT9PAHK.net]: >>614
どこを縦読み？
628 名前：デフォルトの名無しさん mailto:sage [2017/08/12(土) 14:08:41.06 ID:D9kn9WR2.net]: 戦隊もので言えばブラックじゃないですか！
629 名前：デフォルトの名無しさん mailto:sage [2017/09/01(金) 03:15:32.30 ID:D43WgHq0.net]: 状態遷移のように汎用的に使える技術って他にも何かありますか？
630 名前：デフォルトの名無しさん mailto:sage [2017/09/01(金) 09:04:39.07 ID:s82kToZ5.net]: ストラテジーが最強
631 名前：デフォルトの名無しさん mailto:sage [2017/09/01(金) 15:05:22.49 ID:D43WgHq0.net]: デザインパターンですか？汎用性ありますかね
632 名前：デフォルトの名無しさん [2017/09 ]: [ここ壊れてます]
633 名前：/03(日) 14:32:35.28 ID:8cpPGlhh.net mailto: >>620
概念と用語だけマスターすれば良い。

あとは実務に合わせて使えるところは利用するし、合わない部分は気にしない。 []: [ここ壊れてます]
634 名前：デフォルトの名無しさん mailto:sage [2017/09/03(日) 15:06:35.15 ID:+qi04Kz7.net]: >>621
なるほど
ありがとうございます
635 名前：デフォルトの名無しさん mailto:sage [2017/09/03(日) 17:00:04.12 ID:VeRuY65E.net]: >>622
>>621みたいに、わかったような口を叩くけど実際にやらせてみたら手が動かないカスになったらダメ
自分でどんどん適用してみて、メリットもデメリットも自分の体験として語れるようになった方がいい
636 名前：デフォルトの名無しさん mailto:sage [2017/09/03(日) 21:20:14.64 ID:+qi04Kz7.net]: >>623
なるほど
ありがとうございます
637 名前：デフォルトの名無しさん mailto:sage [2017/09/03(日) 22:05:38.94 ID:+qi04Kz7.net]: https://ideone.com/mWu6mC
写経してみたけどどんな時に使えるのかいまいちわかりませんでした・・・
638 名前：デフォルトの名無しさん mailto:sage [2017/09/03(日) 23:18:58.10 ID:SkKZ7pGs.net]: 正解です。
639 名前：デフォルトの名無しさん mailto:sage [2017/09/04(月) 23:07:19.92 ID:NGSv2EGo.net]: >>625
さらっと読んで写経したぐらいで理解できると思わない方がいい
そのうちわかってくるから、とにかく手を動かしコードを動かす経験を積み重ね続けるんだ
640 名前：デフォルトの名無しさん [2017/09/14(木) 20:19:04.82 ID:VdbIWmI2.net]: Introduction to Algorithms 3rd Editionを読むスレ [無断転載禁止]©2ch.net
mevius.2ch.net/test/read.cgi/tech/1505387171/
641 名前：デフォルトの名無しさん mailto:sage [2017/09/15(金) 07:54:04.88 ID:gy747Xnp.net]: >>618
＞汎用的に使える技術
良い質問だなこれ
遅レスだけど考えたい

地味だけど基礎的なデータ構造が
一番汎用的なんじゃないか？
連結リストとか二分木とかそういうの
642 名前：デフォルトの名無しさん mailto:sage [2017/09/15(金) 11:43:47.38 ID:NePdqYQx.net]: 隣接行列とか
643 名前：デフォルトの名無しさん mailto:sage [2017/09/16(土) 07:20:33.50 ID:DwhIrlJj.net]: >>629
それは言えてるかもしれない
汎用的=基礎的
644 名前：デフォルトの名無しさん mailto:sage [2017/09/16(土) 09:24:14.80 ID:pDAu8pHG.net]: consセル？
645 名前：デフォルトの名無しさん [2017/09/17(日) 17:09:50.02 ID:7slIJ8sy.net]: Kleinberg & Tardosの本に以下のような内容の記述があります。
でも、 n > 1 のとき、 H が universal になることは決してないですよね。
u = v のとき、常に、 h(u) = h(v) なので、問題の確率は 1 ですから。

--------------------------------------------------
U を要素数の非常に多い有限集合とする。

H を U から {0, 1, ..., n-1} へのすべての写像の集合のある部分集合とする。

u, v ∈ U に対して、ランダムに選んだ h ∈ H が h(u) = h(v) を満たす確率はたかだか 1/n であるとき、
H は universal であるという。
646 名前：デフォルトの名無しさん [2017/09/17(日) 17:30:37.45 ID:7slIJ8sy.net]: S を #S ≦ n であるような任意の U の部分集合とする。
u を U の任意の要素とする。
X をランダムな選択 h ∈ H に対して、値 #{s ∈ S | h(s) = h(u)} をとるようなランダム変数とする。

このとき、

E[X] ≦ 1

である。

証明：

s ∈ S に対し、
h(s) = h(u) であるならば、 1
h(s) ≠ h(u) であるならば、 0
となるようなランダム変数を X_s とする。

仮定により、 H は universal であるから、
E[X_s] = Pr[Xs = 1] ≦ 1/n

X = Σ X_s だから期待値の線形性により、

E[X] = ΣE[X_s] ≦ #S * (1/n) ≦ 1
647 名前：デフォルトの名無しさん [2017/09/17(日) 17:32:48.13 ID:7slIJ8sy.net]: この証明は、

u ∈ S であるとき、破綻しますよね。
648 名前：デフォルトの名無しさん [2017/09/17(日) 17:37:20.77 ID:7slIJ8sy.net]: Kleinbergはネヴァンリンナ賞を受賞した人だそうですが、大丈夫な人なのでしょうか？
649 名前：デフォルトの名無しさん mailto:sage [2017/09/17(日) 18:52:52.16 ID:qJGXQCnw.net]: ID:7slIJ8syは馬鹿アスペの松坂君
650 名前：デフォルトの名無しさん mailto:sage [2017/09/17(日) 23:18:40.22 ID:2kxiy1Rb.net]: > u = v のとき、常に、

また勝手におれ条件を付け加えてる�
651 名前：ﾈ。 []: [ここ壊れてます]
652 名前：デフォルトの名無しさん [2017/10/06(金) 23:28:50.73 ID:5xvc7oH2.net]: T(n) = Ω(g(n))

⇔

T(n) ≧ c*g(n) となる n が無限に多く存在するような定数 c が存在する。

という定義がありますが、なぜ、ほとんどすべての n ではないのでしょうか？
653 名前：デフォルトの名無しさん mailto:sage [2017/10/07(土) 08:08:49.02 ID:oYr2GY5l.net]: 「B木」の「B」の由来って謎なのかよ。
654 名前：デフォルトの名無しさん [2017/10/07(土) 08:55:33.93 ID:uFxBTiFA.net]: >>639

Knuthは、

T(n) = Ω(g(n))

⇔

ほとんどすべての n に対して、 T(n) ≧ c*g(n) が成り立つ。

と定義するのがいいと書いていますが。
655 名前：デフォルトの名無しさん [2017/10/07(土) 10:32:49.92 ID:yM1og+Z2.net]: Binary(嘘)
Balance(へ？)
656 名前：デフォルトの名無しさん [2017/10/07(土) 14:37:48.61 ID:a6QcCG6E.net]: Boeing
657 名前：デフォルトの名無しさん mailto:sage [2017/10/07(土) 19:13:27.20 ID:htJPCTEu.net]: バランスだろ
658 名前：デフォルトの名無しさん mailto:sage [2017/10/08(日) 09:18:29.57 ID:IlB/Yh1D.net]: A木があるだから、その次ってことでB木だろ
659 名前：デフォルトの名無しさん mailto:sage [2017/10/08(日) 10:08:31.18 ID:S5+imH6k.net]: C木、D木、・・・、Z木
660 名前：デフォルトの名無しさん mailto:sage [2017/10/08(日) 11:43:33.94 ID:I0zVkG9n.net]: 乃木、高木、猪木
661 名前：デフォルトの名無しさん [2017/10/08(日) 12:52:27.73 ID:u+rv4D7i.net]: Θ(f(n)) を使うべきところで、 O(f(n)) を使っているという批判をする人がいますが、
具体的にはどういう状況でしょうか？
662 名前：デフォルトの名無しさん mailto:sage [2017/10/08(日) 19:44:09.13 ID:bBgzVIcc.net]: シータオメガなんて数学以外で使ったことない
663 名前：デフォルトの名無しさん mailto:sage [2017/10/08(日) 20:36:16.81 ID:IlB/Yh1D.net]: FFでよく使う
664 名前：デフォルトの名無しさん mailto:sage [2017/10/08(日) 20:44:05.42 ID:97xX0KxU.net]: AAでまれに使う
665 名前：デフォルトの名無しさん [2017/10/09(月) 18:34:06.40 ID:vbK8I5kP.net]: 浅野孝夫著『アルゴリズムの基礎とデータ構造』を読んでいます。

「上の挿入ソートの例のように、基本演算回数（比較回数）は入力サイズ n にのみ
依存するとは言えない。そこで、入力サイズ n の入力のうちでアルゴリズムが最も
多くの基本演算を必要とする入力を考えて、それに対する基本演算回数を、本書ではん、
サイズ n の入力に対するアルゴリズムの計算量（time complexity of an algorithm）と
呼ぶ。すなわち、最悪の場合を想定してアルゴリズムの計算量を定めていることになる。
このようにして定められたアルゴリズムの計算量 T はもちろん n にのみ依存する関数で
あるので T(n) と書ける。上の挿入ソートの例では T(n) = n*(n-1)/2 である。」

と書いてあります。

その後、マージソートのところには、

「マージソートの計算量は T(n) = O(n*log(n)) である」

と書いてあります。

T(n) は最悪の場合の計算量ですから、

T(n) = Θ(n*log(n)) が正しいのではないでしょうか？

ちなみに、浅野さんは、この本の最初のほうで O, Ω, Θ を定義しています。
666 名前：デフォルトの名無しさん [2017/10/09(月) 18:35:57.26 ID:vbK8I5kP.net]: もちろん、 f(n) ∈ Θ(n*log(n)) ⇒ f(n) ∈ O(n*log(n)) ですが。
667 名前：デフォルトの名無しさん [2017/10/09(月) 18:51:59.25 ID:vbK8I5kP.net]: 浅野さんは、挿入ソートの計算量を

O(n^2)

と書いています。

これも

Θ(n^2)

と書くべきですよね。

>>652

に引用したように、

「上の挿入ソートの例では T(n) = n*(n-1)/2」

ですから。
668 名前：デフォルトの名無しさん mailto:sage [2017/10/09(月) 20:59:07.08 ID:kKYMaHZG.net]: 馬鹿アスペの連投
669 名前：デフォルトの名無しさん mailto:sage [2017/10/09(月) 21:39:35.32 ID:HQb3QT54.net]: ID:vbK8I5kP くらいの基地外になれば、100連投だって容易い。
670 名前：デフォルトの名無しさん [2017/10/15(日) 10:39:26.70 ID:Cy7I/MU1.net]: ソートの決定木についてですが、葉の数が「少なくとも」 n! 個あると説明されることが多いですが、
ちょうど n! 個と書かない理由は何ですか？
671 名前：デフォルトの名無しさん [2017/10/15(日) 10:46:56.72 ID:Cy7I/MU1.net]: 既に順序が決定されているにもかかわらず、さらに無駄な比較をするようなプログラムの
ことを想定しているのでしょうか？
672 名前：デフォルトの名無しさん [2017/10/15(日) 10:48:49.83 ID:Cy7I/MU1.net]: そうだとすると、決定木のある部分木で、その葉がすべて同じ順序に対応するようなものが
存在することになります。
673 名前：デフォルトの名無しさん [2017/10/15(日) 10:49:46.78 ID:Cy7I/MU1.net]: ソートの決定木について厳密に論じている本はありますか？
674 名前：デフォルトの名無しさん [2017/10/15(日) 11:09:38.82 ID:Cy7I/MU1.net]: This result ser
675 名前：ves as a guide for us to know, when designing a sorting algorithm, how well we can expect to do. For example, without such a result, one might set out to try to design a compare-based sorting algorithm that uses half as many compares as does mergesort, in the worst case. The lower bound in Proposition I says that such an effort is futile?no such algorithm exists []: [ここ壊れてます]
676 名前：デフォルトの名無しさん [2017/10/15(日) 11:10:24.51 ID:Cy7I/MU1.net]: >>661

この説明は間違っていますよね？
677 名前：デフォルトの名無しさん [2017/10/15(日) 11:13:29.73 ID:Cy7I/MU1.net]: 最悪時にマージソートの半分の比較しか必要でないソートのアルゴリズムが存在しないこと
は証明できるのでしょうか？
678 名前：デフォルトの名無しさん [2017/10/15(日) 11:54:45.59 ID:Cy7I/MU1.net]: あ、勘違いしました。

>>661

合っていますね。明らかに。
679 名前：デフォルトの名無しさん mailto:sage [2017/10/15(日) 13:42:57.88 ID:IuOQVSqs.net]: 馬鹿アスペの連投
680 名前：デフォルトの名無しさん [2017/10/21(土) 16:32:10.02 ID:edOw+XtB.net]: 浅野孝夫著『アルゴリズムの基礎とデータ構造』を読んでいます。

以下の問題に対する浅野さんの解答が↓です。

「このとき根は葉ではないので左の子 v および右の子 w をもつ。」などと書いていますが、
深さ d > 0 の二分木で左の子もしくは右の子を持たないものも当然存在します。
おかしな解答ですね。

二分木において、深さ d までの葉の総数は 2^d 以下であることを示せ。

d に関する帰納法で証明できる。 d = 0 のときは根は葉になるので明らかに成立する。 d > 0 未満で
成立すると仮定し d のときを考える。このとき根は葉ではないので左の子 v および右の子 w をもつ。
v を根とする部分木の深さ d - 1 までの葉が元々の二分木の深さ d までの葉になるがそのような葉の
総数は帰納法の仮定より、 2^(d-1) 以下である。同様に w を根とする部分木の深さ d - 1 までの葉の
総数も 2^(d-1) 以下であり、したがって、元々の二分木の深さ d までの葉の総数は 2^d 以下であることが
言えた。

この問題文自体もおかしいです。

この問題の結果が本文中で使われていてそこを読めばわかるのですが、問題文の意味は、
「深さ d の二分木の葉の総数は 2^d 以下であることを示せ」です。以下のような解答が模範解答ですね。

深さ d の二分木でその葉の総数が 2^d + 1 個以上であるような二分木が存在すると仮定する。
そのような二分木のうち葉の総数が最多であるような二分木を T とする。
すべての葉の深さが d であるような二分木の葉の総数は明らかに 2^d 個である。
よって T の葉にはその深さが d 未満であるような葉が存在する。この葉に子ノードを持たせれば
深さ d の二分木で葉の総数が T の葉の総数よりも多い二分木を作ることができるがこれは矛盾である。
よって、深さ d の二分木の葉の総数は 2^d 個以下である。
681 名前：デフォルトの名無しさん mailto:sage [2017/10/21(土) 16:38:07.00 ID:FeyeuQ+N.net]: >すべての葉の深さが d であるような二分木の葉の総数は明らかに 2^d 個である。

これ出しちゃったらそれで証明おしまいのような気がするが。
682 名前：デフォルトの名無しさん [2017/10/21(土) 16:43:21.60 ID:edOw+XtB.net]: あ、問題文はおかしくないようです。

二分木において、深さ d までの葉の総数は 2^d 以下であることを示せ。

という問題でOKです。
683 名前：デフォルトの名無しさん [2017/10/21(土) 16:51:58.42 ID:edOw+XtB.net]: 二分木において、深さ d までの葉の総数が 2^d + 1 個以上である二分木が存在すると仮定する。
深さ d までの葉の総数が最多である二分木を T とする。

このとき、 T には深さ d 未満の葉が少なくとも一つ存在する。もしそうでないと仮定すると、 T の
すべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 2^d 個以下に
なってしまうが、これは矛盾である。

T の深さ d 未満の葉に子ノードを持たせれば、深さ d までの葉の総数が T よりも多い二分木が存在する
ことになってしまい矛盾が発生する。

よって、において、深さ d までの葉の総数は 2^d 個以下である。
684 名前：デフォルトの名無しさん mailto:sage [2017/10/21(土) 18:35:04.55 ID:JlJoedU7.net]: 馬鹿アスペの連投
685 名前：デフォルトの名無しさん mailto:sage [2017/10/21(土) 18:51:41.34 ID:FeyeuQ+N.net]: 二分木じゃなくて三分木なら2^d以下ではないわけだけど、>>669の証明を二分木から三分木に変えても
論理展開に違いが出ないから明らかにおかしいだろう。
686 名前：デフォルトの名無しさん [2017/10/21(土) 19:21:45.75 ID:edOw+XtB.net]: 三分木では、

「もしそうでないと仮定すると、 T のすべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 2^d 個以下に
なってしまう」

が成り立ちません。
687 名前：デフォルトの名無しさん [2017/10/21(土) 19:24:01.05 ID:edOw+XtB.net]: 三分木の場合の証明は以下のようになりますね。

三分木において、深さ d までの葉の総数が 3^d + 1 個以上である三分木が存在すると仮定する。
深さ d までの葉の総数が最多である三分木を T とする。

このとき、 T には深さ d 未満の葉が少なくとも一つ存在する。もしそうでないと仮定すると、 T の
すべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 3^d 個以下に
なってしまうが、これは矛盾である。

T の深さ d 未満の葉に子ノードを持たせれば、深さ d までの葉の総数が T よりも多い三分木が存在する
ことになってしまい矛盾が発生する。

よって、において、深さ d までの葉の総数は 3^d 個以下である。
688 名前：デフォルトの名無しさん mailto:sage [2017/10/21(土) 19:33:58.53 ID:FeyeuQ+N.net]: >が成り立ちません。

成り立たないことがわかっているなら証明いらんだろうｗ
逆に言うと、それが成り立たないことが証明されていない。

>>673
3^dってどこから出てきたわけ？
689 名前：名無しさん＠そうだ選挙に行こう！ Go to vote! [2017/10/22(日) 15:43:58.38 ID:PJF1xk0l.net]: 2分ヒープは完全二分木を使ったデータ構造ですが。

この完全二分木のことを半順序のついた木というのはなぜでしょうか？
690 名前：デフォルトの名無しさん [2017/10/23(月) 05:47:03.23 ID:iFI38Dlw.net]: %%%%1000%%%%

000-[HUM%58*73.1\%]/2I/3NM/61.3SNMK%?%3%51.22222222222221%
001-[[[%6/4$17.6135412α3]]]]+DOM+SIL+7%
002-UML7%[61.2[31.5[!%32∂LM17.36%!16.3!%<<<%!HSTOL7%!Q!S!=3m=<2TOL<3Q9A<2.1GHz%,DOK,HAOARA,
003-[[[HEMLOT47[<\41.2%Q,===>[MLS<DPNO<\2.3>#ESOLA!5%!3MLA!>LTOSA>7TONSA>%>%end
691 名前：デフォルトの名無しさん [2017/10/24(火) 00:30:44.81 ID:jO+jDbIG.net]: バッチ処理, ジョブ制御に有効なデザインパターンって何?
692 名前：デフォルトの名無しさん mailto:sage [2017/10/24(火) 09:45:11.29 ID:JWUKPJot.net]: バッジパターン
693 名前：デフォルトの名無しさん [2017/11/05(日) 08:35:59.08 ID:0dKYGWWl.net]: ヤフーブログの　https://blogs.yahoo.co.jp/kamyu_2010　にデザパタ解説を発見した。
694 名前：デフォルトの名無しさん mailto:sage [2017/11/05(日) 13:49:09.49 ID:kyKiHR5g.net]: >>675
再帰的に、親は両方の子以下の数値をもつ。
左右の子の大小関係は考慮しない

ここでは説明しやすいように、配列の[0]は使わない。
[1]から始めると計算が楽。
親1, 左右の子は2, 3で、法則は、親n, 子2n, 2n+1

もし[0]から始めると、
親0, 左右の子は1, 2で、親1, 左右の子は3, 4で、
法則は、親n, 子2n+1, 2n+2、となり複雑

親[1] → 子[2, 3]
[1]3, [2]10, [3]30

[2] → [4, 5]
[4]100, [5]20

[3] → [6, 7]
[6]70, [7]200

JavaScript で、漏れが作った、2分ヒープ
jsdo.it/michihito/bGH5
695 名前：デフォルトの名無しさん [2017/11/05(日) 13:58:55.54 ID:lcYDevpf.net]: で、半順序はどこに登場するんですか？
696 名前：デフォルトの名無しさん mailto:sage [2017/11/05(日) 19:58:31.80 ID:kyKiHR5g.net]: >左右の子の大小関係は考慮しない
697 名前：デフォルトの名無しさん [2017/11/06(月) 23:54:10.39 ID:Xbh99dPN.net]: シングルトンがいけないとかたまに聞くんだけど
シングルトンなしでどうやるのか誰か教えて

シングルトン使わないで済むならシングルトン辞めることには吝かではないんだが
どうやるのかが分からない

HolderとかRepository作るとどうしてもシングルトンになっちゃう
誰か助けて
698 名前：デフォルトの名無しさん mailto:sage [2017/11/07(火) 08:06:23.75 ID:FkpvBRAi.net]: シングルトンの何がいけないのかをわかっていれば別に使ってもいいんじゃないか？
と思うんだが
699 名前：デフォルトの名無しさん [2017/11/08(水) 03:27:16.05 ID:pi2d/ZnM.net]: staticでおk
700 名前：デフォルトの名無しさん [2017/11/10(金) 09:56:08.91 ID:O+5a47Rv.net]: 内部ノード数 n の 2色木の Black Height を h であらわすと以下の不等式が成り立つ。

2^(h-1) - 1 ≦ n ≦ 2^(2*h-1) - 1

よって、 h = O(log(n))

とある本に書いてあります。

これっておかしいですよね？

h は n の関数ではありません。内部ノード数から2色木の Black Height は一意的にはきまらないからです。

もちろん、　O(log(n)) の左辺には n の関数が来るきまりです。

ですので、 h = O(log(n)) と書くのはおかしいのではないでしょうか？
701 名前：デフォルトの名無しさん [2017/11/10(金) 12:02:03.17 ID:WtBM3Wp4.net]: メッセージキューイングって
Commandパターンで実装するで合ってる？
702 名前：デフォルトの名無しさん mailto:sage [2017/11/12(日) 17:56:18.04 ID:5J9eZD00.net]: >>686
>>2^(h-1) - 1 ≦ n ≦ 2^(2*h-1) - 1 ・・・(1)
>>よって、 h = O(log(n)) ・・・(2)

一見すると正しそうに見えるけど、どっちがどうおかしいと？
703 名前：デフォルトの名無しさん [2017/11/12(日) 19:28:20.81 ID:2NYvmr0h.net]: h が n の関数ではないにもかかわらず

h ∈ O(log(n))

と書いているのがナンセンスです。
704 名前：デフォルトの名無しさん [2017/11/12(日) 19:46:50.82 ID:wWQbf7ET.net]: >>689
nとhの関係は(1)で示されているんじゃね？
不等式を変形すれば良いのでは？
705 名前：デフォルトの名無しさん [2017/11/12(日) 20:23:32.92 ID:2NYvmr0h.net]: n から h は一意的に決まりません。

よって、

h は n の関数ではありません。
706 名前：デフォルトの名無しさん mailto:sage [2017/11/12(日) 21:38:49.52 ID:wkhRVmHI.net]: >>691
(1)より一意に決まらなくても計算量は同じでしょ？
707 名前：デフォルトの名無しさん mailto:sage [2017/11/13(月) 18:01:47.14 ID:O+WFbO9G.net]: ＞もちろん、　O(log(n)) の左辺には n の関数が来るきまりです。
ここの時点でおかしい
708 名前：デフォルトの名無しさん [2017/11/13(月) 18:49:03.12 ID:TURt7nwr.net]: >>693

何がおかしいのでしょうか？
709 名前：デフォルトの名無しさん [2017/11/14(火) 16:22:50.14 ID:kwaLWx7P.net]: 抽象メソッドしか定義されない型のことを
「インタフェース」ってネーミングセンスは頭おかしいんじゃないの？
インタフェースって言ったら通常「UI」とか外部の窓口になったり、
外部デバイスとの接続ポイントになるコネクタのことを言うじゃん。
オブジェクトの型のことを「インタフェース」なんて言ったら誤解を招くだろ。
710 名前：デフォルトの名無しさん [2017/11/14(火) 16:49:12.95 ID:dN7NjwRx.net]: >>695
interfaceには境界面とか接点の意味がある

クラスが持つ他との接点の意味で合ってる
711 名前：デフォルトの名無しさん mailto:sage [2017/11/14(火) 18:46:26.43 ID:9XknVuf7.net]: 外部の窓口になったり、外部デバイスとの接続ポイントになるのが抽象メソッドだから。
つまりそれしか定義されてないということは、インターフェースそのものと言っていいだろう。
712 名前：デフォルトの名無しさん mailto:sage [2017/11/14(火) 20:12:16.44 ID:R1CE9PkA.net]: デザパタスキル、エンベッデイドスキルなんやかや言うが、みんな大事な部分は閃きなんだがなぁ・・・
作曲と同じ。　閃き・・・　とどのつまり、神が書かせているという事。
そこを理解できない限り、そのプログラマーは聖職では無い。
713 名前：デフォルトの名無しさん mailto:sage [2017/11/15(水) 13:14:29.24 ID:qga1lTtf.net]: 神などと妄想するようになったら科学の全否定の始まり。無知が故の過ち。
714 名前：デフォルトの名無しさん mailto:sage [2017/11/18(土) 18:23:02.44 ID:SgBQyEr/.net]: 神「共通化せよ――」
僕「はい」
神「ごめん間違えた――」
僕「うわぁぁああぁああ！！！」
715 名前：デフォルトの名無しさん mailto:sage [2017/11/18(土) 18:29:25.85 ID:ebkB7QGA.net]: 神とは強いて言えば可能性
716 名前：デフォルトの名無しさん [2017/11/19(日) 23:12:44.83 ID:opsy6abA.net]: 以下で定義される写像 A : N × N → N を Ackermann 関数という。

A(1, j) = 2^j for j = 1, 2, 3, …
A(i, 1) = A(i-1, 2) for i = 2, 3, 4, …
A(i, j) = A(i-1, A(i, j-1)) for i = 2, 3, 4, … for j = 2, 3, 4, …

α(m, n) = min {i ≧ 1 | A(i, floor(m/n)) > log_2(n)}

で定義される写像 α : {(m, n) | m, n ∈ N, m ≧ n} → N を Ackermann 逆関数という。

なぜ、この α を Ackermann 関数の逆関数と呼ぶのでしょうか？
717 名前：デフォルトの名無しさん [2017/11/20(月) 20:37:12.88 ID:Sdx1OtwZ.net]: courseraのセジウィックとウエインの講義を受講しています。

プログラミングの課題のチェックが超厳しいですね。

'if' is not followed by whitespace.

「if」の後ろにスペースを入れないといけないなんて初めて聞きました。
そんなことまで強制されたらたまりませんね。
718 名前：デフォルトの名無しさん mailto:sage [2017/11/20(月) 20:40:14.03 ID:uYx1UAMq.net]: 大概のプロジェクトで採用されてるスタイルだから従っとけ
スペース軽視するやつ多すぎ
719 名前：デフォルトの名無しさん mailto:sage [2017/11/20(月) 20:43:51.90 ID:Y8ntE/6M.net]: >>703
K&R2 に従っておけば文句が来ることはない
if ()
while ()
for ()
720 名前：デフォルトの名無しさん mailto:sage [2017/11/20(月) 20:54:20.19 ID:XqE+Nf2F.net]: フオーマッタの設定の指定とか無いの？
721 名前：デフォルトの名無しさん mailto:sage [2017/11/20(月) 23:10:14.23 ID:ohy70QIE.net]: 一般的なコーディングルールには従ったほうがよい
最近の言語環境では放っておいてもツッコミ入れてくれたりもするが
722 名前：デフォルトの名無しさん mailto:sage [2017/11/21(火) 07:03:23.42 ID:G6ETZwfO.net]: 業務システムでオブジェクト指向不要って意見はどう思いますか
大抵スパゲティークエリになってる印象ですが
723 名前：デフォルトの名無しさん mailto:sage [2017/11/21(火) 07:13:27.16 ID:OOffmQFA.net]: 途中からオブジェクト指向混ぜられても困るだろ
実行効率や記述効率は悪くたって別に構わないのだから（ここわかってない人多し）、プロジェクトに来た全員が理解利用できる書き方が最優先

無論技術的にも業務的にもうんこだが、そこを追求すべき場所ではないところで勝手に追及を始めるのはそれこそうんこのやること
ゼロからオーバーホールを提案してもよいが最後まで自己責任で看取れ
724 名前：デフォルトの名無しさん mailto:sage [2017/11/21(火) 17:43:16.86 ID:M9cr/U+S.net]: >>709
サブクエリ五重の塔を見て上長にキツいと報告したら世界にはバベルの塔がいっぱいあるのに根をあげるなと叱られました

せめて何をしたいのかドキュメント欲しいと言ったらコードが全てだとも言われました

IT業界の厳しさを知りました
725 名前：デフォルトの名無しさん mailto:sage [2017/11/21(火) 18:14:34.60 ID:3zrw9He/.net]: >>710
マ板にどうぞ
726 名前：デフォルトの名無しさん [2017/11/22(水) 09:23:31.55 ID:milfaijK.net]: courseraのセジウィックとウエインの講義の最初の課題であるパーコレーションだけど
backwashを防ぐにはどうすればいいんですか？
727 名前：デフォルトの名無しさん [2017/11/22(水) 10:42:20.23 ID:milfaijK.net]: あ、分かりました。

virtual topにはつなぐがvirtual bottomにはつながないUF
virtual topにもvirtual bottomにもつなぐUF

を使えばいいんですね。
728 名前：デフォルトの名無しさん [2017/11/22(水) 10:51:20.09 ID:milfaijK.net]: 成績が100点満点中97点になりました。
729 名前：デフォルトの名無しさん [2017/11/22(水) 10:52:40.54 ID:milfaijK.net]: 成績が100点満点中98点になりました。
730 名前：デフォルトの名無しさん mailto:sage [2017/11/22(水) 11:48:25.03 ID:vqOaIl/E.net]: 今日のNG ID:milfaijK
731 名前：デフォルトの名無しさん [2017/11/22(水) 15:34:31.81 ID:milfaijK.net]: ついに、成績が100点満点中100点になりました。

https://imgur.com/apwKZnf.jpg
732 名前：デフォルトの名無しさん [2017/11/22(水) 15:35:42.67 ID:milfaijK.net]: 快挙ですね。
733 名前：デフォルトの名無しさん [2017/11/23(木) 12:04:48.38 ID:Le5wB72/.net]: デザインパターンで規定されるいろいろなクラスがあるけど
これらのクラスはそれぞれレイヤー化アーキテクチャのどこに
属すのか知りたい。
たとえばStateパターンがあった場合に、
・<<interface>>State
・ConcreteState x n
・Context
があったとき、

これらは、クラスを配置する場所的に
・プレゼンテーション層(UI層)
・App層
・サービス層
・ビジネスロジック層
・パーシステンス層
のどこの層として配置すればいいのか
734 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 12:18:16.35 ID:DeXlBicR.net]: > デザインパターンで規定されるいろいろなクラスがあるけど
> これらのクラスはそれぞれレイヤー化アーキテクチャのどこに
> 属すのか知りたい。

デザパタはレイヤ化アーキテクチャに属すものだという考え方が謎なんだけど
735 名前：デフォルトの名無しさん [2017/11/23(木) 12:18:26.01 ID:fJlhhdGs.net]: >>719
どの層にも配置していいんじゃね

その層の機能とかを実現するのにそのデザインパターンが必要なら使えばいいのではないか

レイヤーとデザインパターンは独立に組み合わせ可能と思う
736 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 13:43:59.34 ID:veVPgurQ.net]: >>719
これでも読めよ

J2EEデザインパターン
https://www.amazon.co.jp/dp/4873111781/
737 名前：デフォルトの名無しさん mailto:sage [2017/11/25(土) 15:28:17.03 ID:unmm6CwQ.net]: java用語発表されてもなー
738 名前：デフォルトの名無しさん mailto:sage [2017/11/27(月) 07:16:56.92 ID:DtvpiAcr.net]: デザパタを適用したクラスがどのレイヤにあっても構わんのじゃ無いか
定石があってもフレームワークごと違うから説明無理だと思う
739 名前：デフォルトの名無しさん [2017/11/28(火) 09:02:37.93 ID:VA+yl+li.net]: 1以上1000以下の整数からなる集合の部分集合で、
その任意の異なる2元 x, y をとったとき、
「x は y を割り切らず、 y も x を割り切らない」
という性質をもつものを考える。

そのような部分集合の中で元の数が最大になるような
集合の元の数を求めよ。
740 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 09:32:48.27 ID:EZT/19IX.net]: めっちゃ勘だが、334から666と、667以上の奇数でどうだろうか
741 名前：デフォルトの名無しさん [2017/11/28(火) 11:34:19.17 ID:VA+yl+li.net]: 答えは500以下です。

1 から 1000 までの整数を 2^n * (2*m + 1) の形で表す。

2*m + 1 の部分は、

2*0 + 1, 2*1 + 1, …, 2*499 + 1

の500個のパターンのいずれかに一致する。

よって、1 から 1000 までの整数の中から501個以上の異なる整数を選び出せば、
その中には、かならず、

2^n1 * (2*m + 1), 2^n2 * (2*m + 1)

という二つの整数が含まれる。

この二つの整数は一方が他方を割り切る。
742 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 12:05:52.85 ID:TRWRICOE.net]: どっかから問題と回答を拾ってきてドヤ顔してる人ってなんなの？
743 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 14:07:31.97 ID:g+QmVGb1.net]: >>727
何をしているのかちゃんと理解したいのですが、
m や n は実数ですか？
744 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 15:55:11.56 ID:8wOk3LC1.net]: >>729
>>727が言葉が足りてないのは確かだが、もうちょっと数学のセンス磨こうぜ
745 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 17:12:15.85 ID:g+QmVGb1.net]: >>730
n=0 にして、m=0, 1, 2 ...
n=1 にして、m=0, 1, 2 ...
...
とやって確かめたら、なんとなく自然数を網羅できそうなのは確認できました。

ただ、本当に網羅できるのか証明はまだできてません。

これ以上はスレチも甚だしいので、独りで頑張ってみます。

流れぶった切ってすみません。
>>725 さん、どうぞ続けてください。
746 名前：デフォルトの名無しさん [2017/11/28(火) 17:15:22.43 ID:VA+yl+li.net]: >>729

整数を 2 で割れるだけ割ると 2^n * (2*m + 1) の形になります。

例：

120 = 2^3 * 15 = 2^3 * (2*7 + 1)

この場合、 n = 3, m = 7 です。
747 名前：デフォルトの名無しさん [2017/11/28(火) 17:16:45.10 ID:VA+yl+li.net]: 2^n * 奇数

です。
748 名前：デフォルトの名無しさん [2017/11/28(火) 17:26:27.93 ID:VA+yl+li.net]: 1 = 2^0 * (2*0 + 1)
2 = 2^1 * (2*0 + 1)
3 = 2^0 * (2*1 + 1)

…

999 = 2^0 * (2*499 + 1)
1000 = 2^3 * (2*62 + 1)

となります。

1, 2, …, 1000 をすべて

2^n * (2*m + 1)

という形に表します。

m は 0 から 499 までの 500 個の整数のどれかになります。

ですので、 1, 2, …, 1000 の中から 501 個以上の整数を取ってきて、それらすべてを

2^n * (2*m + 1)

という形に表すと、

2*m + 1

の部分が同じになるような異なる2つの整数があります。
2*m + 1 の部分は同じで、 2^n の部分が異なります。それら2つの整数は
2^n1 * (2*m + 1), 2^n2 * (2*m + 1) のようにあらわされます。 n1 < n2 と仮定して一般性を失いません。
2^n2 * (2*m + 1) は 2^n1 * (2*m + 1) で割り切れます。 2^n2 * (2*m + 1) ÷ 2^n1 * (2*m + 1) = 2^(n2-n1)
749 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 17:58:11.47 ID:8wOk3LC1.net]: 500以下なのはわかった。500ある例>>726も見つかった。
で、一般に1からNのとき、何個になるのよ？
750 名前：デフォルトの名無しさん [2017/11/28(火) 19:31:53.85 ID:VA+yl+li.net]: >>726

{501, 502, …, 1000} でもOKですね。
751 名前：デフォルトの名無しさん [2017/11/28(火) 19:37:23.97 ID:VA+yl+li.net]: >>735

ceiling(n/2)

ではないでしょうか？
752 名前：デフォルトの名無しさん mailto:sage [2017/11/28(火) 19:54:30.86 ID:8wOk3LC1.net]: あんまり面白くない結果だね
753 名前：デフォルトの名無しさん [2017/11/30(木) 18:59:28.31 ID:A1E/mSxW.net]: セジウィックとウエインのcourseraのオンライン講義を聴講しています。

java.util.List
java.util.Stack
java.util.Queue

は最低だそうですね。

Best practices: Use our implementations of Stack, Queue, and Bag.

だそうです。
754 名前：デフォルトの名無しさん [2017/12/02(土) 11:57:41.11 ID:6Ds5e+ud.net]: 最近傍探索で、最も近いものが複数個あった場合、どうするのが自然ですか？

また、k近傍探索でも、クエリからk番目に近いものが複数あった場合、どうするのが自然ですか？
755 名前：デフォルトの名無しさん [2017/12/02(土) 12:30:23.76 ID:LweVlrmz.net]: セジウィックとウエインのcourseraのオンライン講義を聴講しています。

なんかやけに課題が厳しくないですか？
756 名前：デフォルトの名無しさん [2017/12/02(土) 13:12:04.17 ID:LweVlrmz.net]: セジウィックとウエインのcourseraのオンライン講義Algorithms Part 1のWeek 2の課題、できた人いますか？
757 名前：デフォルトの名無しさん mailto:sage [2017/12/02(土) 17:04:18.29 ID:Rnsbf7Hs.net]: 今日のNG ID:LweVlrmz
758 名前：デフォルトの名無しさん [2017/12/02(土) 20:12:18.77 ID:LweVlrmz.net]: courseraのセジウィックとウエインの講義を聴講している人はいますか？
759 名前：デフォルトの名無しさん mailto:sage [2017/12/04(月) 13:54:02.89 ID:fGqdieY2.net]: >>740
好きなようにするのが自然
760 名前：デフォルトの名無しさん [2017/12/05(火) 09:10:03.39 ID:bL4Z2L1G.net]: ↓この仕様の RandomizedQueue の実装できる人いますか？

coursera.cs.princeton.edu/algs4/assignments/queues.html
761 名前：デフォルトの名無しさん mailto:sage [2017/12/05(火) 09:40:42.14 ID:71Ul9rRS.net]: >>746
宿題なら自分でやれ
そうでないなら読むのめんどくさいから要約しろ
762 名前：デフォルトの名無しさん mailto:sage [2017/12/05(火) 09:45:48.47 ID:afEItlvW.net]: 松坂君につきスルー推奨
763 名前：デフォルトの名無しさん [2017/12/05(火) 12:21:40.49 ID:bL4Z2L1G.net]: あ、仕様Memory量の見積を勘違いしていました。

できそうですね。

Item 型のデータを格納する Linked List
と
Linked List の各要素への参照を格納する Item[] 型の
配列を用意すれば実現できますね。
764 名前：デフォルトの名無しさん [2017/12/05(火) 12:25:30.33 ID:bL4Z2L1G.net]: あ、でも Item[] 型の配列を ResizingArray で実現したとしても、
常に、Memoryの制限である 48*n + 192 bytes というのを満たすのは
無理ですね。

どうすればいいんですかね？

もう少しだけメモリの制限が緩ければ実現可能ですが。
765 名前：デフォルトの名無しさん [2017/12/05(火) 12:30:24.08 ID:bL4Z2L1G.net]: Performance requirements.

Your randomized queue implementation must support each randomized queue
operation (besides creating an iterator) in constant amortized time.

That is, any sequence of m randomized queue operations (starting from an empty
queue) must take at most cm steps in the worst case, for some constant c.

↑これと↓を両立させることはできるのでしょうか？

A randomized queue containing n items must use at most 48n + 192 bytes of
memory.
766 名前：デフォルトの名無しさん [2017/12/05(火) 13:24:03.96 ID:bL4Z2L1G.net]: あ、なんだ

簡単でしたね。

Item[] 型の Resizing Array を使えば、

メモリ使用量～ 8*n

だから、4倍くらいメモリを無駄に使っても

48*n を超えませんね。
767 名前：デフォルトの名無しさん [2017/12/05(火) 13:25:09.16 ID:bL4Z2L1G.net]: あ、なんだ

簡単でしたね。

Item[] 型の Resizing Array を使えば、

無駄が全くないときのメモリ使用量～ 8*n

だから、4倍くらいメモリを無駄に使っても

48*n を超えませんね。
768 名前：デフォルトの名無しさん [2017/12/05(火) 13:27:33.45 ID:bL4Z2L1G.net]: これから実装しますが、また100点満点中100点になりそうです。
769 名前：デフォルトの名無しさん [2017/12/05(火) 13:43:27.58 ID:bL4Z2L1G.net]: あ、やっぱりだめですね。

dequeue の計算量がネックになりますね。
770 名前：デフォルトの名無しさん [2017/12/05(火) 13:45:25.54 ID:bL4Z2L1G.net]: あ、分かりました。
一様ランダムに選択された a[i] に a[N] を移せばいいんですね。
771 名前：デフォルトの名無しさん mailto:sage [2017/12/05(火) 16:58:02.34 ID:Z65eXqg0.net]: 本日のNGID:bL4Z2L1G
772 名前：デフォルトの名無しさん [2017/12/05(火) 21:20:28.14 ID:YaGuI/6t.net]: 経路探査でray cast algorithmというのがあるらしいんだが、わかりやすいサイトない？
773 名前：遊園 mailto:age [2017/12/07(木) 01:30:59.64 ID:AoT+leNM.net]: おちんちん　に　ベロが届くアルゴリズムを教えて下さい。
774 名前：デフォルトの名無しさん mailto:sage [2017/12/07(木) 09:29:15.88 ID:lQf/9LHk.net]: お金が儲かるアルゴリズムを教えてください
775 名前：デフォルトの名無しさん [2017/12/08(金) 13:48:57.43 ID:6WtIjESa.net]: >>759
ム板らしく

香川大
https://www.youtube.com/watch?v=J_R7fgo0FLc
早稲田大
www.takanishi.mech.waseda.ac.jp/top/research/voice/movie/Tongue_Phoneme_s.mpg
www.takanishi.mech.waseda.ac.jp/top/research/voice/movie/Tongue_EMA_s.mpg
www.takanishi.mech.waseda.ac.jp/top/research/voice/index_j.htm
購入可能
https://auctions.yahoo.co.jp/seller/obaba1212
776 名前：デフォルトの名無しさん mailto:sage [2017/12/09(土) 02:58:56.19 ID:ouHX+Izy.net]: >>760
「お金が儲かるアルゴリズム」で儲かる方法を書いた本を売る
777 名前：デフォルトの名無しさん mailto:sage [2017/12/09(土) 09:08:05.27 ID:hr/9uBAF.net]: 子供の言い返しみたい
778 名前：デフォルトの名無しさん mailto:sage [2017/12/09(土) 12:25:33.81 ID:GX7M220U.net]: それは結構知能が高い子供だなw
779 名前：デフォルトの名無しさん mailto:sage [2017/12/09(土) 16:48:02.91 ID:oqulgHhz.net]: https://www.amazon.co.jp/dp/4040800044/ref=cm_sw_r_cp_awdb_c_Kt5kAbQR1S9HF

似たタイトルの本あるな
780 名前：デフォルトの名無しさん mailto:sage [2017/12/19(火) 17:58:55.99 ID:E2JharMg.net]: 関数型言語ってUML使うんですか?
クラス図とかメソッドどう書くんだろうと
781 名前：デフォルトの名無しさん [2017/12/24(日) 12:09:02.25 ID:croU9pw3.net]: ちょっと質問させてください。
状況: トータル1000行くらいある巨大メソッドの改修
言語; PHPだがどの言語でもそう関係のない内容

・まずコントローラのアクションメソッドがあって

public function action(引数){

/* 500行くらいの既存コード */

/*今回改修を加えたい50行位のコード */

/* 500行位の既存コード */
}
となっている。
782 名前：デフォルトの名無しさん [2017/12/24(日) 12:16:40.00 ID:croU9pw3.net]: ・ここで、改修要件は、中間にある「/* 50行くらいの既存コード */」を
　　if文で分岐させて分岐次第で違う処理を入れる。というもの。
　　したがって、

public function action(引数){

　　/* 500行くらいの既存コード */

　　if(条件1){
　　　　/* 新規追加コード */
　　　　if(条件1-1){
　　　　　　/* 新規追加コード */
　　　　}else{
　　　　　　/* 既存コード */
　　　　}
　　}else if(条件2){
　　　　/* 新規追加コード */
　　}else{
　　　　/* 既存コード */
　　}

　　/* 500行位の既存コード */
}

みたいにひたすら条件分岐して既存コードと新規追加コード
が何回も実行されるようにしたい。
783 名前：デフォルトの名無しさん [2017/12/24(日) 12:22:57.90 ID:croU9pw3.net]: ・ここで、俺は「/* 既存コード */」の中身を知っている必要は
　ないと思った。だから、このコードの詳細を読まずに「func()」
　として「action()メソッド内部」に切り出した。
・外部に切り出したのではなく、内部に切り出したのはその処理が
　他のアクションメソッドでは共有されるような汎用的なものではないだろうと
　判断したのと、そのメソッド内で処理を追いやすいようにというのを
　優先させたため。何より、その処理内で使っている関数内ローカル変数の
　依存性の関係上そうせざるを得ないと思った。

public function action(引数){

　　/* 500行くらいの既存コード */

　　private function __legacy(){
　　　　/* 50行くらいの既存コード */　　　　
　　}

　　if(条件1){
　　　　/* 新規追加コード */
　　　　if(条件1-1){
　　　　　　/* 新規追加コード */
　　　　}else{
　　　　　　__legacy();
　　　　}
　　}else if(条件2){
　　　　/* 新規追加コード */
　　}else{
　　　　__legacy();
　　}

　　/* 500行位の既存コード */
}
784 名前：デフォルトの名無しさん [2017/12/24(日) 12:31:59.59 ID:croU9pw3.net]: ・【訂正】上記で「func()」として切り出したと言っているが、
　　「__legacy()」に変更しました。すみません。
・上記のように改修した所、レビューを受けたときに怒られた。
・まず、「この__legacy()の中身ちゃんと読んだ? 把握して書いている?」
　という指摘。
・そして「ここメソッド内だけどどうして関数定義しているの？
　他の人そんなことしてないでしょ。どうして変わったことするの？」
　という指摘。

・まず1つめの指摘に対して異議がある。
　ブラックボックス化しなければ大規模なコードは書けないんじゃない？
　ということが言いたい。ライブラリとかフレームワークの機能も全部
　先に中身をよくよく読んでおかなければ使ってはいけないことになるじゃん。

・2つの指摘に対して、
　「周りの人がやっていること」が正しいとは思えない。
　処理を切り出していないから1000行もある巨大なメソッドになっていて、
　汚いコメントで汚しながら機能追加しまくっているんじゃないのかと。
　ローカル変数を使いまくりの同じ処理を何回も実行するのに
　他に良い手段があるとしたら皆さんに教えて頂きたい。
785 名前：デフォルトの名無しさん mailto:sage [2017/12/24(日) 13:24:11.47 ID:d+M5RyEv.net]: 汎用的でない50行のコードをコピペしてるんなら関数化してもインライン化してもどっちもどっちだな
DRYを意識したのかもしれんがKISSが抜けてる
それにブラックボックスが許されるのは有名なライブラリやフレームワークのようなテストにテストを重ね、かつ多くの利用者による実績があるものだけだよ
社内コードなんて大概クソコードだしブラックボックスにしても後で痛い目を見るのは自分や他の開発者
何なら単に今把握するだけじゃな
786 名前：くて、未来の自分や開発者のためにわかりにくいところをコメントで説明書きしてもいいくらいだ あと関数内関数より無名関数を変数に代入した方がいいんじゃね そもそも新規追加したif文も詳細はわからないがデータよりもロジックに寄っててわかりにくそうな匂いがプンプンする それに上司には理由を聞かれてるんだから同じローカル変数に別の値を入れて使い回すことの危険性、関数化による参照透明の確保や保守性、メンテナンス性の向上を論理的に答えればいいだけ []: [ここ壊れてます]
787 名前：デフォルトの名無しさん [2017/12/24(日) 13:31:29.00 ID:ZUclbhk1.net]: >>770
レビュアーが言ってることを正しいと仮定すれば
・1つ目の指摘は既存のコードがカプセル化されてないからだ
・2つ目の指摘はリファクタリングするだけの時間やお金や技術がないからだ
という前提が必要になるから、まあそういうことなんじゃなかろうかと

残念なコードっていうのはあるからね
それを修正する費用と修正して得られる効果を比較対照して
これだけの効果があるんだからこうするべきだと提案をまとめて
説得するのがいいのだろうけど、技術に理解のある人がいないとなかなか難しいね

レビュアーの立場で考えると以下の作業があるんじゃないかと
・改修要件を満たす改修
・既存のコードをカプセル化する
・リファクタリングする

レビュアーは既存のコードとの一貫性を維持しつつ
改修要件を満たす最小の改修をやって欲しいのだろうね

たとえ汚らしいコードであってもいままで動いてきた実績があると
変更に対しては既存のコードをできるだけ変えないようにと保守的になるものだよ

レビュアーがそれをきちんと説明できればいんだけど
コードはクソ、レビュアーもクソなんてことはザラにあるんですよこれが
788 名前：デフォルトの名無しさん [2017/12/24(日) 13:35:53.06 ID:croU9pw3.net]: >>771 なるほど勉強になります。
少し質問したいが、
・「KISSが抜けている」と言うのはどこらへんでしょうか？
・関数内関数と無名関数の変数化の違いがわからないので教えてください。
　(面倒なら調べます。)
・あなたならどう対応する？
・「理由を聞かれてるんだから答えればいいだけ。」
　→多分論理的に説明したら「じゃあもう何も教えないよ。好きにやって」
　　が返って来ると思われる。
　そう言われると、必要な情報も来なくなるし聞けなくなる。
789 名前：デフォルトの名無しさん [2017/12/24(日) 13:38:47.27 ID:croU9pw3.net]: >>772
なるほど、俺自身が「既存コードのカプセル化」と
「改修要件」という概念と「改修要件を最小に満たす」という
ことについて詳しくないことに問題がありそうだね。
ありがとう、ここらへんをキーワードにして調べてみます。
790 名前：デフォルトの名無しさん mailto:sage [2017/12/24(日) 13:55:23.50 ID:d+M5RyEv.net]: >>773
多分もっと細かく汎用的な(publicにできる)関数の集まりに分解して、汎用的でない部分は最小限に出来るんじゃないかなーって思った
実際のコード見てないから予想だけど

関数内関数だとわざわざprivateかけないと外からアクセス出来ちゃうし、元の親関数抜けても子関数が死なない

そもそも上司とあんまり仲良くないの？
論理的にメリットを売り込んだときに感情論で否定されるくらいの関係性だと下っ端プログラマーはしんどいよ？
まぁ俺ならその段階なら折れて普通にコピペして、もっと実績残して仲良くなってから似たような案件のときに改めて売り込むかな
791 名前：デフォルトの名無しさん mailto:sage [2017/12/24(日) 16:09:59.00 ID:RfRGBvGh.net]: ひとつのメソッドに1000行も書かせる会社はまず危ない

アルゴリズムとかそれ以前
792 名前：デフォルトの名無しさん [2017/12/24(日) 16:57:23.08 ID:croU9pw3.net]: >>775
なるほど、「まるまる関数化」というのが
ちゃんと機能を意識してカプセル化していないってことか。
一応privateは欠けているけど、関数オブジェクトと
関数定義の違いはあまり詳しくないね。そうか、親関数が抜けたとき
子関数が死ぬか否かの違いがあるわけね。
入りたてだから人間関係はいいも悪いもない。
ただ、本来責任ある人はバタバタしていて、経験ある人が自分の意志で
新人のレビューをバラバラに行っている感じ。

>>776
会社がそうさせているというよりはそれぞれの人員が
これまでの追加の仕方を真似て機能追加した結果メソッドがブクブクと太っている
という状況に見える。
メソッド内で各追加機能がコメントで区画されていてそれなら
別関数にすりゃいいのにって思っている。
俺をレビューした人も、別に会社の工程でそうなっているわけでなく、
進捗を見たかったからだと思うが、書き直しを要求してきて困惑している。
ただ彼は業務要件については圧倒的に俺より詳しいから無視すべきではないと
思っている。
793 名前：デフォルトの名無しさん mailto:sage [2017/12/24(日) 17:21:20.21 ID:d+M5RyEv.net]: >>777
カプセル化はオブジェクト指向において関連するものをまとめる作業だから、ちょっと違うかな？
どちらかというと今回の話は関数型プログラミングの考え方に近い
まぁぶっちゃけ職場のコードなんて割り切らんとやってけんよ
出世してコーディングスタイルに口を出せるようになる日を待つしかない
794 名前：デフォルトの名無しさん mailto:sage [2017/12/24(日) 18:02:16.50 ID:ZlmBMffH.net]: >>777
そんな仕事を放置する会社、と言うことだ
795 名前：デフォルトの名無しさん [2017/12/26(火) 20:02:37.53 ID:IVX+3dWv.net]: 名前だらけのコードってどうやって解読すればいいんだ？
変数化するとそのデータの型が何なのか物量的にどれだけの
規模が格納されているかが見えない。
もちろんログに吐けば見えるが、吐き出さなければパッと見で
何をどう処理しているのか分からない。
796 名前：デフォルトの名無しさん mailto:sage [2017/12/26(火) 22:58:59.01 ID:SjDDNmHA.net]: 俺は君の話が見えない
797 名前：デフォルトの名無しさん mailto:sage [2017/12/27(水) 07:26:44.87 ID:uxDwhrz8.net]: 関数型言語の仕様書ってUMLで良いの?

データと振る舞い分離してるからクラス図使って良いのかなと
798 名前：デフォルトの名無しさん mailto:sage [2017/12/27(水) 08:35:11.41 ID:F/9ZaRBN.net]: >>782
ちょうど stackoverfl
799 名前：ow に同じトピックがありました。 参考にしてください。 https://stackoverflow.com/questions/2457903/can-uml-be-used-to-model-a-functional-program []: [ここ壊れてます]
800 名前：デフォルトの名無しさん mailto:sage [2017/12/28(木) 07:02:18.99 ID:THqyhi+6.net]: >>783
英語敷居たけえ

まあデータと振る舞いを書いたクラス設計は関数型言語でも同じように使えるし問題ないか
801 名前：デフォルトの名無しさん [2018/01/10(水) 18:14:12.30 ID:hBlQ00sP.net]: coursera.cs.princeton.edu/algs4/assignments/8puzzle.html

↑この問題分かる人いますか？
802 名前：デフォルトの名無しさん mailto:sage [2018/01/10(水) 18:27:49.76 ID:1dOsaXCv.net]: 粗探しは止めたのか？
803 名前：デフォルトの名無しさん [2018/02/03(土) 08:08:45.43 .net]: 今どきデザインパターンって死語なの？
ちょっと参照したいことがあって書店でデザインパターンの本を探したけど見つからなかった。
リファクタリングの本はあって多少はデザインパターンの話も出てきたけど。
結局は家に帰ってから10年前に買ったデザインパターンの本を参照するしかなかった。
804 名前：デフォルトの名無しさん mailto:sage [2018/02/03(土) 08:51:29.86 ID:KIp4GWtx.net]: ブームが去っただけかな？
銀の弾丸などないと気がついただけ
805 名前：デフォルトの名無しさん mailto:sage [2018/02/03(土) 09:20:07.32 ID:i7L7gFeB.net]: 今更デザインパターンについて新しい本なんて不要
806 名前：デフォルトの名無しさん mailto:sage [2018/02/03(土) 12:22:10.78 ID:ROxRBp/z.net]: デザパタは元々バカの為にまとめられたものだったけどバカには無理だった代物
一方リファクタリングはバカ程好むからなかなか廃れない
807 名前：デフォルトの名無しさん [2018/02/03(土) 19:53:28.27 ID:4eWkMwg8.net]: 21世紀最新のデザインパターン本て誰か書かないかね
Singleton→大抵はstaticでOK
みたいなの
808 名前：デフォルトの名無しさん mailto:sage [2018/02/03(土) 20:04:20.16 ID:gMMiWrqd.net]: >>791
それ以外に何か書くことあんのか？
809 名前：デフォルトの名無しさん mailto:sage [2018/02/04(日) 00:33:23.10 ID:P/Ibpspu.net]: デザインパターンて結局何だったんだ？
高い本まで買ったがほとんど身に付かなかったな
810 名前： mailto:sage [2018/02/04(日) 00:43:54.12 ID:p5zvJFKF.net]: >>793
もともと C++ 界隈で発生したテーマですので、C++ をやっているとデザパタの意義がよくわかります
C++ は細かしいことまで自分で記述しなければならないので、こういう大枠思考がもてはやされたのだと思います
811 名前： mailto:sage [2018/02/04(日) 00:44:42.44 ID:p5zvJFKF.net]: ああ、でも C++ はテンプレートの世界観に移行してしまったので、デザパタ、今はあんまり使いません！
812 名前：デフォルトの名無しさん mailto:sage [2018/02/25(日) 14:54:54.10 ID:LHXgrTbX.net]: >>793
アルゴリズムの話するときの共通語が必要になって
ついでに良し悪しもまとめておこうという話になった
813 名前：デフォルトの名無しさん mailto:sage [2018/02/25(日) 16:52:44.22 ID:bfs3ZT86.net]: アルゴリズムとパターンて違うんじゃね？
814 名前：デフォルトの名無しさん mailto:sage [2018/02/25(日) 18:39:48.45 ID:hAg+nb3o.net]: デザインパターンそこに至る考え方を身につけないと
というわけで、オブジェクト指向のこころをオススメしとく
815 名前：デフォルトの名無しさん mailto:sage [2018/02/25(日) 18:59:31.93 ID:z/Jlakx1.net]: >>798
書評読んでもなかなかよさげだな
816 名前：デフォルトの名無しさん [2018/03/05(月) 21:38:39.67 ID:aiLdZy6r.net]: 『アルゴリズムイントロダクション』を読んでいます。

ヒープソートのところに、

「サイズ n のヒープ上の MAX-HEAPIFY の最悪実行時間が Ω(lg n) であることを示せ。」

という問題があります。

最悪実行時間が Θ(lg n) であることはすぐに分かります。
なぜ、 Ω(lg n) であることを示せという問題なのでしょうか？

最悪実行時間や最良実行時間については、 Θ 記法で書くのが自然だと思います。
817 名前：デフォルトの名無しさん [2018/03/06(火) 01:54:34.90 ID:bDrXTt4P.net]: まるちんこ
818 名前：デフォルトの名無しさん [2018/03/07(水) 21:29:45.52 ID:ukyKg6LA.net]: セジウィックさんはいい加減ですね。

近代科学社から出ている『アルゴリズムC』の最小全域木のところを読んでいますが、
同じ重みの辺が2つ以上あると議論が破綻するところがありますね。

Wayneさんと共著の『Algorithms』では、すべての重みが異なるという仮定をおいていますね。

いずれにしてもひどい本です。
819 名前：デフォルトの名無しさん mailto:sage [2018/03/07(水) 21:31:54.51 ID:MzP8rhu8.net]: キミはまだアルゴリズムの勉強していたのか。

人には向き不向きというのがあってだな。
820 名前：デフォルトの名無しさん [2018/03/07(水) 21:33:49.91 ID:ukyKg6LA.net]: すべての重みが異なるというのは異常な仮定ですよね。
821 名前：デフォルトの名無しさん [2018/03/07(水) 22:27:03.62 ID:ukyKg6LA.net]: 茨木俊秀著『アルゴリズムとデータ構造』を読んでいます。

この本のクラスカルのアルゴリズムの正しさの証明に使われる補題の証明ですが、
読んでも分からなかったのですが、やはりおかしかったんですね。

同じ著者の『Cによるアルゴリズムとデータ構造』を読むと補題の証明が修正されています。

この分野っていい加減な本が多いですよね。
822 名前：デフォルトの名無しさん [2018/03/08(木) 19:38:26.94 ID:NHHLXFak.net]: 任意の連結無向グラフ G = (V, E) は |E| ≧ |V| - 1 を満たすことを示せ。
823 名前：デフォルトの名無しさん mailto:sage [2018/05/12(土) 10:59:28.10 ID:pDgCeBjY.net]: 共同ツール 1
https://seleck.cc/685

https://trello.com/
ボードのメニュー → Power-Upsから拡張可能 Slack DropBoxなど
Trello Chrome拡張機能　elegant
ttp://www.kikakulabo.com/service-eft/
trelloのオープンソースあり

共同ツール 2
https://www.google.com/intl/ja_jp/sheets/about/

共同ツール 3
https://slack.com/intl/ja-jp
https://www.dropbox.com/ja/
https://bitbucket.org/
https://ja.atlassian.com/software/sourcetree
https://sketchapp.com/extensions/plugins/
ttp://photoshopvip.net/103903

ttps://goodpatch.com/blog/sketch-plugins/
824 名前：デフォルトの名無しさん [2018/05/23(水) 20:11:35.70 ID:Au5e7VGg.net]: 僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法　モニアレフヌノ』

BU06O
825 名前：デフォルトの名無しさん [2018/06/24(日) 11:32:17.25 ID:cbD8du/l.net]: AVL木について詳しく載っている本は何ですか？
826 名前：デフォルトの名無しさん mailto:sage [2018/06/24(日) 14:42:02.78 ID:/GtGgmfo.net]: 詳しいと言えるかどうかは別にしてAVL木に関する説明が分かりやすいと思ったのは次の本の該当箇所（§6.3）だ

浅野哲夫『データ構造』、アルゴリズムシリーズ１、近代科学社 (1992)
827 名前：デフォルトの名無しさん [2018/06/24(日) 15:07:06.81 ID:F1zD07yq.net]: ステマ
828 名前：デフォルトの名無しさん [2018/07/04(水) 22:09:33.44 ID:gFgZc5FG.net]: C5O
829 名前：デフォルトの名無しさん mailto:sage [2018/07/05(木) 16:33:38.42 ID:AeL6VB/V.net]: C5O
830 名前：デフォルトの名無しさん [2018/07/21(土) 20:42:50.98 ID:4Q935nRZ.net]: 1つ言えるのはオブジェクト指向のなんかよりも
データ構造とアルゴリズムの方がよっぽど重要だということ。
昔はオブジェクト指向の勉強を頑張っていたけどそのときは
全然プログラミングがうまくならなかった。
現代の世の中はガチガチに設計されたライブラリを使って
コードを書くだけだから生半可なオブジェクト指向の知識なんて
ゴミ同然だよ。80年代90年代に考えられた思想とか、もうゴミに
なってしまった思想が多くて有害だよ。
結局現場でやることは「メソッドの使い方を求めてQiitaやStack OverFlowを
漁って成功するコードを見つけるまで疲れ果てる」ことに変わりはない。
せっかく勉強した内容が時代遅れで「裏切られる」ことのほうが多い。
831 名前：デフォルトの名無しさん [2018/07/21(土) 20:51:29.70 ID:4Q935nRZ.net]: 一方、データ構造とアルゴリズムをガッツリと勉強してから
様々なデータ構造の使い方、問題の解決がうまくなった。
ブロックチェーンのアルゴリズムの理解や
データ分析の数学的演算がコーディング
できるようになってプログラミングが格段に楽しくなった。
スマートにオブジェクト指向で設計する力なんかより
「ゴリゴリとアルゴリズムを書く力」の方がよっぽど重要。
「再利用性」？「変更の影響」だって？そんなものゴミだね。
それは自分以外の人間のメリットのための技術であって、
自分へ還元されるためのメリットではない。
再利用性は自分の書いたコードなら信頼できるしコピペして使えばいい。
自分の書いたコードのコピペは全然ありだと思う。
適したメソッドが見つからなかったらQiitaを漁ったりせずに
自分でゼロから実装したほうが速い。
その場で手っ取り早くコードを生成しているから、
どんな既存コードにも頼っていないから俺の実装したコードは
依存性は低い。
832 名前：デフォルトの名無しさん mailto:sage [2018/07/21(土) 21:29:45.12 ID:BkDv2dG7.net]: ただし>>814-815は何かのアプリを作ったことはない
833 名前： mailto:sage [2018/07/21(土) 21:58:56.02 ID:vWALYQin.net]: >>815
一つ重要な視点を提供しましょうか
自分の記憶などあてになりません、3ヶ月前自分が書いたコードは、もはや他人が書いたコードとなんら変わりありません
834 名前：デフォルトの名無しさん mailto:sage [2018/07/21(土) 22:06:10.19 ID:BkDv2dG7.net]: >>814-815はすでに解いたことのある問題なら
忘れたとしても、少し時間をかければ解けると考えている

つまり誰かが出した出題を解くという作業をしている
835 名前：デフォルトの名無しさん [2018/07/21(土) 22:34:33.64 ID:4Q935nRZ.net]: >>>817, 818
自分のいつも使うアルゴリズムのパターンが身についていれば
そのパターンや命名規則から何をやっているかは解読できる。
読みにくくなるのは外部から取り込んだ機能の実行や
継承している部分。
836 名前：デフォルトの名無しさん mailto:sage [2018/07/21(土) 23:12:43.54 ID:BkDv2dG7.net]: >>819
やっぱり「解読」してるんだｗ

すでに証明済みの問題を自分の力で証明するという
お勉強をやってるだけだね
837 名前：デフォルトの名無しさん [2018/07/21(土) 23:21:07.94 ID:evbWgLmC.net]: 研究者で無い限り新しい証明考える必要ないっしょ
838 名前：デフォルトの名無しさん [2018/07/21(土) 23:22:28.87 ID:evbWgLmC.net]: 解読の工程は業務でも必要であるし
遊びとしても面白い
それが勉強になるならとても有益じゃん
839 名前：デフォルトの名無しさん [2018/07/21(土) 23:34:47.51 ID:4Q935nRZ.net]: 「車輪」は大きさ、材質、シャフトの接合部の形、色…大まかな形や役割は似ているが微妙に違うものが無数にある。
ちょっとでもこれらの特徴がずれたものは他への転用を考えるとすぐに不具合となって使い物にならない。
車輪を最初に「発明」した人物はこれらの無数の車輪を全て発明したわけではない。
だから他の人が死ぬほど似たようなものを作っていたとしても自分で作る必要がある。
他人が作った車輪は無条件で役にたつわけがない、
手直しして組み込むより「自分の規格で」作った方が早い。
840 名前：デフォルトの名無しさん mailto:sage [2018/07/21(土) 23:43:56.82 ID:s1Wh2Ul8.net]: 車輪ってすごいな
841 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 00:34:31.50 ID:J1Nh86LO.net]: 車輪が小さかったからゴム巻いたらなんとかなった
これがオブジェクト指向です
842 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 02:15:34.77 ID:+JtpRhMz.net]: 時代が違うからな。アルゴリズム考えてうんうん唸る時代は終わってるんだよ
今はそういうアルゴリズムが実装されたライブラリを組み合わせて
アプリを作る時代だってMITも言ってる

MIT｢今は基礎よりﾗｲﾌﾞﾗﾘ組み合わせてｱﾌﾟﾘ作る時代｣ [無断転載禁止]©2ch.net
https://medaka.5ch.net/test/read.cgi/prog/1462443213/

MITがSICPを教えなくなった理由
cpplover.blogspot.jp/2016/05/mitsicp.html

今日では、状況が変わっている。

今のエンジニアは、自分が完全に理解していない複雑なハードウェアのための
コードを日常的に書いている（そして、大抵の場合、企業秘密により完全に理解するのは不可能である）。

ソフトウェアでも状況は同じだ。プログラミング環境は、多大な機能を提供する
巨大なライブラリ群の集合として存在している。

Sussmanの今日の生徒は、その時間の大半を、ライブラリのマニュアルを読み、
どのように組み合わせれば目的が達成できるのかを把握することに費やしている。

Sussman曰く、今日のプログラミングは、「より科学に近い。ライブラリを持ち寄って、
つっつき回すのだ。プログラムを書くには、突っつき回して、どのように動作するかを観察する。
そして、「目的を達成するために改造できるか」と考えるのだ」。

SICPの「合成による解析」という物の見方である、小さな、単純な部品を組み合わせて大きなシステムを作るということは、
もはや今日の状況にそぐわなくなった。今や、我々のプログラミングはつっつき回すことで行われている。
843 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 06:06:47.04 ID:woAlzZC1.net]: 車輪の再利用だけ考えて車輪職人が居なくなるって話かな？
844 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 06:11:43.36 ID:+JtpRhMz.net]: そうだね。そもそもソフトウェアは他の製品と違って
完全に同じものを複製するのに技術がいらないからね
コピーすればいいだけだし。

その点、何かを作る職人とはぜんぜん違うよね
そいういう寸分違わないものを作り出す職人は不要な業界
845 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 09:02:23.96 ID:XlZUepQP.net]: >>825
そして、今は鉄道以外のほぼすべてのタイヤの接地面はゴムです。
そういうところもオブジェクト指向と、似てますね。
846 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 09:20:35.56 ID:hOelEibu.net]: 以上、内容無し
847 名前：デフォルトの名無しさん [2018/07/22(日) 13:32:55.77 ID:snsF+l1o.net]: >>826
この論理は完全にお花畑。
完全無欠のライブラリがありそれが唯一無二なら
つつっつき回すだけでいいだろうさ。
だけど現実はほぼ似たような機能で構文が違う、
それに加え実行環境もバージョンも違うライブラリたちが乱立してるんだぜ、
それに加わりローカルで作られた野良ライブラリがある。
当然人によってそれらの使い方の認識に齟齬が生まれる。
信用できるのは、自身の即興のデータ構造定義能力と、
アルゴリズム構築能力だけだ。
848 名前：デフォルトの名無しさん [2018/07/22(日) 13:34:08.83 ID:LiIRy0eu.net]: 今必要なのは解読ではなくて解脱
849 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 14:02:08.11 ID:+JtpRhMz.net]: >>831
> だけど現実はほぼ似たような機能で構文が違う、
> それに加え実行環境もバージョンも違うライブラリたちが乱立してるんだぜ、

乱立しているからなんだっていうんだろう？
乱立してるから自分で作れってことにはならないよな？
何が言いたいんだろう

> それに加わりローカルで作られた野良ライブラリがある。

自分自身で作成したもの = 他人から見れば野良ライブラリだからね
野良ライブラリは作るべきじゃないね

だから乱立されている中のどれかを使うってことになるわけだけど
そういう結論を言いたかったんだよね？
850 名前：デフォルトの名無しさん [2018/07/22(日) 14:02:42.93 ID:YGqHpPTt.net]: >>831
データ構造作るだけだと付加価値が低いというか
ただの作業員でしかなくない？
新しい仮想通貨作るとかだったらすごいけど
851 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 14:06:57.17 ID:+JtpRhMz.net]: まあ言えるのは、データ構造やアルゴリズムを作るだけの仕事なんて無いってことだな

やりたいからといって、それで金がもらえるわけじゃない
金を出す方がやってもらいたいことをやって金が出る

似たようなものを自作して、乱立させたって
そんなものに金を出す人はいない
852 名前：デフォルトの名無しさん [2018/07/22(日) 14:18:22.79 ID:LiIRy0eu.net]: >>835
うむ

>>834
やったことないやつには判らんよ
853 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 14:24:06.48 ID:t9f4aq96.net]: 座禅だな
854 名前：デフォルトの名無しさん [2018/07/22(日) 17:42:32.79 ID:bmpyz9fo.net]: >>827
いや、ちょっと違う
プログラマという職業が、車輪を一から設計できる職人群と
それを再利用する専門家へと二極化していくというお話だよ

この二極化は以前から言われていたことだけど、
それを天下のMITが言い切って行動に移したことに>>826の意義がある
855 名前： mailto:sage [2018/07/22(日) 18:20:24.01 ID:+jM3tBOE.net]: >>838
「職人」と「専門家」が逆ではないですか？
856 名前：デフォルトの名無しさん [2018/07/22(日) 19:59:44.17 ID:bmpyz9fo.net]: いや、逆ではないよ

MITは計算機工学に特化しているわけでもなく、
機械工学、ロボティクス、生産工学、データ解析といった
あらゆる工学分野の専門家を養成し輩出している

そういった(計算機工学を除く)大半の「専門家」の卵達にとって、
優先すべきは(旧コースでSchemを使って学んでいた)計算機の動作原理ではなく、
計算機の利用方法である、という趣旨
彼ら「専門家」は決して計算機工学の専門家ではないが、
それぞれの分野に特化した高度な専門技術を有し、
与えられた問題を解決する道具として計算機を効果的に活用できる
857 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 20:38:21.89 ID:woAlzZC1.net]: 役割が細分化したからそのニーズに応じたという話？
858 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 21:07:14.12 ID:+JtpRhMz.net]: どんな仕事でも、その道の研究者ってのはいるだろう。
例えば数学者とかな。だけど世の中で必要とされてるのは
塾の数学の先生だったりするわけさ

もっとも大学に行った人の殆どは、大学で専攻していたものとは
関係のない仕事をしているわけだけどな
859 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 21:23:40.76 ID:MHyGLJ0L.net]: 数学とコンピュータを一緒にするなよｗ
860 名前：デフォルトの名無しさん [2018/07/22(日) 23:03:00.98 ID:snsF+l1o.net]: たとえばjsでオブジェクト構造をサーバに送りたいとする。
たったこれだけのことなのに邪魔くさい余計な機能が多すぎる。
わざわざ専用のクラスからインスタンス作って
専用の構文使ったりhttpヘッダー設定したりだ。
それでいてサーバ側では糞みたいな細かい仕様認識の違いでリクエストの内容が空だったりする。
サーバ側のコンフィグ見直したりjs側のコード見直したりするわけだ。
ログからライブラリのコード追っていくと大抵
過剰に技法使われてるから自ずと疑うべき探索
範囲は広くなる。
書き方はjQueryベースやangular typescriptなんかが混在してきて文法のちょっとした勘違いなんてのも生まれてくる。
だったらそんなライブラリ鼻っから信用しなけりゃいい。
ライブラリのインスタンスを介さずに多少原始的だが
文字列、数値 for文if文だけで大抵の問題は解決できる。
自力でJSON文字列に情報をぶち込んで送信してやれば、必ずサーバ側で取得できる。
サーバ側も下手なライブラリにパースさせないで自力でパースした方が慣れれば断然こちらの方が早い。
自力で作ったアルゴリズムは信用できるから
関数化しておいてまた似たような問題があったときに
使える。
俺が使うための自作ツールは他人は使わなくていいよ、どうせ価値観が違うんだからな。
自分で作ったもの以外はそりゃ不便だろうよ。
861 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 23:31:00.85 ID:8Bgo+1zG.net]: > たとえばjsでオブジェクト構造をサーバに送りたいとする。

https://api.jquery.com/jquery.post/

$.post( "test.php", { name: "John", time: "2pm" } );

こうだね。で？
862 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 23:37:38.62 ID:zgYMpfBL.net]: それjqueryやんw
863 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 23:58:50.05 ID:8Bgo+1zG.net]: はい。このように他人の成果を利用して
目的を達成するのが今は重要って話です。
864 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 00:05:17.20 ID:jaGQY9G3.net]: >>844
> だったらそんなライブラリ鼻っから信用しなけりゃいい。

とりあえずお前が自力で作ったライブラリは
鼻っから信用しててないよ
865 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 00:19:04.74 ID:jaGQY9G3.net]: >>844
> 俺が使うための自作ツールは他人は使わなくていいよ、どうせ価値観が違うんだからな。
> 自分で作ったもの以外はそりゃ不便だろうよ。

価値観の問題じゃない。単にお前が作ったコードに
バグがあるから使えないだけ。使わないんじゃない。使えない。

反論するならバグがない証拠を出すこと
テストコードをかけという話ね。

> だったらそんなライブラリ鼻っから信用しなけりゃいい。
お前が書いたコードは鼻っから信用できない。するしないじゃない。できない。
866 名前：デフォルトの名無しさん [2018/07/23(月) 06:43:27.98 ID:LtlhEJ9n.net]: みなさんお気づきだろうか
>>844と>>849は同じことを言っている
867 名前：デフォルトの名無しさん [2018/07/23(月) 07:32:08.19 ID:LtlhEJ9n.net]: jQueryはブラウザの差異を吸収するからね
同等のもの作ろうとしたら大変だよ

自前のコードを実装するのが汎用ライブラリを使うよりも早いとするなら
自前のコードは汎用ライブラリよりも機能が少ないものになる

要件がシンプルなら自作するのは効率が良いかもしれないね

システムをユーザのニーズに合わせてたら要件が複雑になり自作するメリットが得られない
ユーザがシステムの都合を忖度するならうまくいく
開発者にとっては桃源郷

開発者の幸せか、ユーザの幸せか
ぼくらはその選択を迫られてるんだ
868 名前：デフォルトの名無しさん mailto:age [2018/07/23(月) 09:47:19.69 ID:nk4BkCBO.net]: 役所が作る神エクセルなんてのはユーザがシステムの都合に合わせてる典型例じゃないか、自作コードに拘るのは神エクセルを作るのと変わらぬよ
869 名前：デフォルトの名無しさん [2018/07/23(月) 11:01:38.63 ID:eU1p7hr8.net]: >>842
自己紹介ですね
870 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 12:24:24.98 ID:jaGQY9G3.net]: >>851
> 要件がシンプルなら自作するのは効率が良いかもしれないね
それは正しくない。要件はシンプルでも実装が大変なことがある。
そもそも「ライブラリの一機能の独自実装」などという要件は
実際には発生しない。これらは単に道具

要件を実装するのに、道具を使うか使わないかの問題
シンプルな要件でも、道具は使ったほうが効率は良いよ

もちろん道具を使えない人であれば、道具を使えるようになるまで時間が
かかるけど、それは素人がプロに速度でかなわないという人間の問題にすぎない
そう道具を使えないなら素人なんだよ。
871 名前：デフォルトの名無しさん [2018/07/23(月) 12:29:27.63 ID:aoV6LMU9.net]: >>850
ヒント：バカは皆がオンリーワン
872 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 12:36:13.41 ID:jaGQY9G3.net]: >>850
同じことは言ってないな

>>844はよくわからないのはライブラリのせいだ
自分で作れば、そのライブラリよりもわかりやすくなるはずだ
って机上の空論を言ってるだけ
873 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 13:54:17.34 ID:wSAPNw7p.net]: PGの愚痴
874 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 15:02:52.51 ID:EWSlu15m.net]: りんごをむくのにピーラーを使うのもいいが、一度ナイフで剥くのを試すのも重要だし、かじってみるのもいい。
道具が解決する問題がなんなのか、体験することは、多くの人にとって有益だと思う（経験主義者）
875 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 15:32:18.18 ID:1W7qAEKf.net]: そこでピーラーを作るのは大変だとか見当違いの所に流れていくやつがいる。

ピーラー（ライブラリ）を使うか、ナイフを使うかだ

ライブラリ？中見たけどわけのわからないことをしてる
理解できない。ナイフのほうが単純だ。ナイフなら作れる。
なぜか作る話になってしまっている。
876 名前：デフォルトの名無しさん mailto:age [2018/07/23(月) 15:38:29.17 ID:nk4BkCBO.net]: 例え話では本質から遠ざかるばかりよ
877 名前：デフォルトの名無しさん mailto:age [2018/07/23(月) 15:39:54.99 ID:nk4BkCBO.net]: 例え話は物事を理解してなくてもそれらしく見せるから知ったか振りが捗りますなあ
878 名前：デフォルトの名無しさん mailto:age [2018/07/23(月) 15:41:15.55 ID:nk4BkCBO.net]: ワシも神エクセルとか言ってた
879 名前：デフォルトの名無しさん mailto:sage [2018/07/24(火) 18:13:24.95 ID:Ce588Hp1.net]: 全部やれ
880 名前：デフォルトの名無しさん [2018/07/24(火) 18:20:36.91 ID:WBO96fmU.net]: 最後までやれ
881 名前：デフォルトの名無しさん mailto:sage [2018/07/24(火) 20:40:39.40 ID:6SRwrowy.net]: 例えがドラゴンボールではないからだろ
882 名前：デフォルトの名無しさん [2018/07/27(金) 22:10:24.05 ID:jesqHVAc.net]: MVC, DAO, O/Rマッピングの発展形として、
俺は「R/Rマッピング(リクエスト/リレーショナルマッピング)」を
提唱したい。
そもそもDB上のカラムと本当に対応付けたいのは画面上のname属性
なんだよなぁ。
オブジェクトを必ず介する必要はない。
(処理が込み入ってきたら定義してもいい程度。)
まず前提として、DBのカラム名とHTML上のname属性を
必ず同じキーにすることを前提とする。(HTML上に関係ない
キーがあっても問題はない。)
その前提の上でDBのカラム名一覧を先に取得しておき、
カラム名リストと、受信したname属性のキーをマッチングして、
マッチングした時にそのキーから取得した値をSQLに突っ込んで
クエリを行う。
こうすることによって、プログラミング言語処理の中で
具体的な「項目名」をほとんど登場させずに処理することができる。
自分でやったらすごく便利だった。
こうなるとそもそもモデルとかDAOとかいらなくね?
ってなって来たよ。
項目数がどんなに二十, 三十と並んでいようがダラダラと羅列しない。
特別な処理を入れたいときだけその項目のカラム名を使って
ifで分岐して日付変換とかをおこなう。
その特別な処理も日付,範囲系、選択肢系などパターンを押さえれば、
めちゃめちゃ簡素化できる。
883 名前：デフォルトの名無しさん mailto:sage [2018/07/27(金) 22:35:03.11 ID:d6sXPNYF.net]: あ、はい、4行ぐらいしか読んでないけど、
そのリクエストに含まれる名前 = オブジェクトのフィールド名なんだから
あんたが言ってるリクエスト = オブジェクトってこと

あとはストレージをなんにするかの話。
ODBMS（オブジェクトデータベース）を使えばそのまま読み書きできる
だけど、なんやかんやでリレーショナルデータベースを使わないといかんから
O/Rマッピングが必要になる
884 名前：デフォルトの名無しさん mailto:sage [2018/07/27(金) 22:38:45.06 ID:d6sXPNYF.net]: >>886
あとRailsでも勉強しようね
普通は画面のname属性 = データーベースのフィールド名になってるから
（もちろん必要なら対応してないものも作れるけど）
885 名前：デフォルトの名無しさん mailto:sage [2018/07/27(金) 22:58:52.80 ID:HpMLTKup.net]: 二層CRUDオモチャ
昔から誰もが一回は考えるアイデアだよ

画面起点だとどうしてもアプリケーションロジックの居場所がないから簡単に作れてもアプリとしての価値が無い
DB起点だとSQLにアプリケーションロジックを埋め込んんで最低限のアプリの体裁は保てるけど保守性が最悪で使い物にならない
という理由から廃れた

なので今はオブジェクト指向の言語でモデルを書いてモデルから画面やDBを生成して微調整しようってのがスタンダード
これなら労力をかけずに豊かな振る舞いを持つアプリケーションを作れるしロジックがモデルに集まるから保守性も高い
886 名前：デフォルトの名無しさん [2018/07/27(金) 23:43:33.59 ID:jesqHVAc.net]: >>869
モデルを作るとしても処理が複雑になる部分だけ
部分的でいいんじゃないか？
全ての要素に対して網羅的にモデルつくって
セッター/ゲッター定義して...ってのは肥大化して馬鹿げてる
気がするんだが。
なにせ機能を複製する時にこれらのずらずら並んだモデルオブジェクト名や
キーの名前をを置換しなけりゃならない。
ならない。
887 名前：デフォルトの名無しさん mailto:sage [2018/07/27(金) 23:51:45.25 ID:d6sXPNYF.net]: > セッター/ゲッター定義して...ってのは肥大化して馬鹿げてる
それはJavaだけ
Javaが馬鹿げているだけ
888 名前：デフォルトの名無しさん mailto:sage [2018/07/27(金) 23:52:00.90 ID:d6sXPNYF.net]: だからいい加減Railsとかを勉強しろと
889 名前：デフォルトの名無しさん mailto:sage [2018/07/27(金) 23:55:06.84 ID:h+bQHJad.net]: .NET Coreにしとけ
890 名前：デフォルトの名無しさん [2018/07/28(土) 02:15:45.58 ID:kGN2HSKI.net]: >>859
さてリンゴをむくか、
ピーラーがないと剥けないから探すか、
あれ、どこにしまったかな？
この引き出しにもこの棚にもない。
道具だらけで見つからない。
店に買いに行こう、たくさんのピーラーが並
んでいてどれを選ぼうか？
ようやく買ってきて構築しているけど、
どうや刃が付け替え式で色々な刃が付け替えられる
ようだ。
刃を買い忘れたからまた買いに行くか…
はぁはぁ…すごい刃を買ったぞ！今構築中だ。
おや？この刃はリンゴを剥く用途には対応して
ないようだ。もう疲れたしこれ無理だろ。
ピーラーが無いから俺にはリンゴを剥くのは
無理だ。前は引き出しにあったからむけたけど
今はできなくなった。

一方、いつも愛用のナイフで剥いてるならそう
はならない。
いつもポッケに入れているからなくさないし、
最悪自作で調達できる。
使い慣れてるからピーラー使うやつと遜色ないスピードで剥けるし形も綺麗に剥ける。
891 名前：デフォルトの名無しさん mailto:sage [2018/07/28(土) 02:38:56.80 ID:Wq9fNSFf.net]: Rails なんか、全自動！

DB の表の構造が定義された、メタテーブルを参照して、
表の列名なども自動的に取得する
892 名前： mailto:sage [2018/07/28(土) 03:14:15.05 ID:AqK1vkX7.net]: >>873
Windows 上で構築できますか？
893 名前：デフォルトの名無しさん mailto:sage [2018/07/28(土) 07:06:05.64 ID:rUA3L/4N.net]: >>870
それでずらずら並んで嫌だというなら、おまえのやり方だと画面定義もずらずらならぶし、テーブル定義やSQLがずらずら並んで更にわけわからなくなるだろ
894 名前：デフォルトの名無しさん mailto:sage [2018/07/28(土) 09:41:18.41 ID:Z4XsBwkZ.net]: >>876
できる
895 名前： mailto:sage [2018/08/11(土) 11:14:19.06 ID:vW2Ha+vq.net]: >>878
やりかたは？
896 名前：デフォルトの名無しさん mailto:sage [2018/08/11(土) 11:16:30.51 ID:CORkkjHt.net]: >>879
住民税納めてる？
897 名前：デフォルトの名無しさん mailto:sage [2018/08/11(土) 11:20:01.67 ID:mZzpchFU.net]: >>879
https://www.microsoft.com/net/learn/get-started-with-dotnet-tutorial
898 名前： mailto:sage [2018/08/11(土) 11:23:26.77 ID:vW2Ha+vq.net]: >>880
固定資産税なら5月に収めました
899 名前：デフォルトの名無しさん mailto:sage [2018/08/11(土) 13:12:12.75 ID:eIyvbe4d.net]: >>882
固定資産もってるんだスゲー（笑）
900 名前：デフォルトの名無しさん [2018/08/16(木) 01:50:12.60 ID:c6C4Pdqe.net]: 最も重要ななのはアルゴリズムとデータ構造
次にI/O
つぎに無名関数やハンドラ、イベント駆動
つぎに並列、非同期処理
その次は画像処理とか3Dとか
ディジタル信号処理またいな各ドメインの専門
技術。
オブジェクトやクラスなんてこれらを達成する
上での手段でしかない。
それ以上のオブジェクト指向の設計思想は
もはや宗教。
唯一絶対に正しいわけでもないし
概念を余計に複雑にするだけ。
SQLやHTML XMLやJavaScript シェルスクリプト
URLなんかが絡んでくるとグダグダに崩壊
するものばかり。
そして現代のアプリケーションはこれら無しで
作るのは無理だからオブジェクト指向の高度な
技法はほどんど不要。
901 名前：デフォルトの名無しさん [2018/08/16(木) 10:35:20.66 ID:wiNukf+g.net]: NoSQLω
902 名前：デフォルトの名無しさん mailto:sage [2018/08/16(木) 14:12:13.61 ID:sOMWRYDA.net]: NoSQL db って、Redis以外はわりと滅びた感じ。
RDBでもスキーマレスなデータ
903 名前：扱えるようになったし、 トランザクションあった方が便利なことやっぱり多いし、 SQLってなんだかんだ言って表現力高いし。 []: [ここ壊れてます]
904 名前：デフォルトの名無しさん [2018/08/16(木) 21:39:02.86 ID:xTRm/dST.net]: pythonスレにも書いたのですが、pandasのMultiIndexにしたデータのままで、データを追加したり、値を更新したり、csvに入出力する方法をご存知の方はいませんか？
905 名前：デフォルトの名無しさん mailto:sage [2018/08/17(金) 05:33:12.57 ID:kMdEBKXA.net]: マルチ
906 名前：デフォルトの名無しさん mailto:sage [2018/08/18(土) 16:47:45.36 ID:Misswrnn.net]: マルチインデックスだけに
907 名前：デフォルトの名無しさん mailto:sage [2018/08/22(水) 13:56:25.55 ID:Opme7aq9.net]: >>886
その辺はクラウドに吸収されたよ
908 名前：デフォルトの名無しさん mailto:sage [2018/08/22(水) 14:04:12.93 ID:85QcXChJ.net]: クラウドだけに雲散霧消
909 名前：デフォルトの名無しさん mailto:sage [2018/08/26(日) 08:51:55.17 ID:rDVjwTPV.net]: クラウドってなんだっけ？
910 名前：デフォルトの名無しさん mailto:sage [2018/08/26(日) 11:43:20.70 ID:oFGqb4Dq.net]: 興味ないね
911 名前：デフォルトの名無しさん mailto:sage [2018/08/26(日) 12:02:43.50 ID:Ecv/l33V.net]: 雲の中にトレーラーがいっぱいあること
912 名前：デフォルトの名無しさん mailto:sage [2018/08/29(水) 11:59:51.59 ID:t35BnR1i.net]: >>893
チリチリしてろ
913 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 11:36:30.01 ID:jf9m7XuW.net]: AOJ の「DPL_1_I: Knapsack Problem with Limitations II」が分からん。

個数制限付きナップサック問題の
・ある品物の重さと個数制限
・ナップサック容量
が極めて大きいバージョン。

例えば解法
judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2856557#1
を見ると、品物の価値の総和が i であるときの最大容量を記録した動的計画法テーブルを作った後に貪欲法で答えを出してるんだが
・なぜこの方法で上手くいくのか
・前半の動的計画法で、品物の個数を min(m[i], MAX_V) としている (できる) 理由が分からない。

誰か知恵を貸してください。
僕としてはこの解法が理解できれば満足です。
914 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 16:30:03.75 ID:OpvYfh8N.net]: >>896
数学からやり直したほうがいい
915 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 16:38:34.35 ID:AAPeDezt.net]: >>897
どういう意味？
「このアルゴリズムを理解するのに必要な数学の分野」というものがあるならそれを参照するが、そんなものはない (挙げられないでしょ？)

俺個人の専門は物理で、「数学の勉強」というものも一応してきたが、このごく具体的な問の一解法を理解することと「数学の勉強」は関係がない

単純に論理的思考力を上げよ、と言っているなら会話になっていないのでこれ以上は結構
916 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 16:59:47.21 ID:rxoSSaq5.net]: 論理的思考力を上げるために将棋をしなさい。数学など不要です。
917 名前：デフォルトの名無しさん [2018/08/30(木) 18:00:22.07 ID:RB/Vojpj.net]: うむ
918 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 18:13:22.55 ID:OpvYfh8N.net]: >>898
DPは数学的に求まるよ
919 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 18:43:47.20 ID:nhWZJRvT.net]: >>898
数学科の数学と物理科の数学とコンピュータの数学は違う（笑）
920 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 19:55:53.34 ID:dq2VmAiX.net]: >>901
最適性の証明のことを言ってるの？
いずれにせよこの問題に限った話じゃないよね？
別に動的計画法が上手くいく理由が分からないと言っているのではなく、>>896の解法が分からないのだが。

>>902
違わない
算術、代数、幾何、解析だ全て
921 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 19:59:32.89 ID:rxoSSaq5.net]: 例えば、バブルソートには
数学の、えっと、幾何？の知識が必要だろ？
え？
922 名前：デフォルトの名無しさん [2018/08/30(木) 20:02:00.51 ID:JJE0QqNc.net]: フローチャートでも書けよバカ。
923 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 20:07:14.70 ID:dq2VmAiX.net]: >>905
無論書いたが分からん
924 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 20:55:16.95 ID:LfSXnVaM.net]: >>903
やったことないだろ（笑）
925 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 20:58:00.20 ID:LfSXnVaM.net]: 単に頭が悪い見栄っ張り
926 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 21:05:25.02 ID:fZXCQKMc.net]: >>906
分からんと思っているだけでは進まない。

なにを目的にして、どのようなフローチャートを描いて、
その結果なにが理解できていて、なにがまだ理解できていないのか、
可能な限り事細かに洗い出して、自分の理解の最前線を特定してみるといい。

と言うことを、私は数学で学んだ。
927 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 21:18:12.57 ID:51/MDOyO.net]: 数I？数II？
928 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 21:43:49.44 ID:HM7SCTN2.net]: >>909
だからそれは>>896の時点で書いてるんだが
関係ないことしか言えないならレス不要です

>>907
何を？
929 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 00:40:53.58 ID:/Xr6ByPq.net]: 俺の周りで物理やってる人はとんでもなく数学ができる人ばかりなのに
930 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 00:57:19.27 ID:1Yp+WIrl.net]: まあゲームじゃない限り物理なんて使わないよね
本格的な物理系シミュレーションとかだと
専門家が担当するだろうし
931 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 01:02:18.59 ID:avsEGe4h.net]: この程度の問題で数学数学言ってるアホ多過ぎて呆れる

多分>>910みたいな感じで高校の算数基準で話してるんだろうな
932 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 01:09:41.75 ID:6Alav1/S.net]: そんなに言うのなら、具体的に数学のどの分野なのか
それが具体的に何と同じなのか言えって。
どうせ論理的思考力がーみたいな精神論しか言えないんだろ
933 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 07:21:05.29 ID:wT3DulcX.net]: 数列、非線形解析学
はい言いました
論理的思考力が無いのはあなたですね
934 名前：デフォルトの名無しさん [2018/08/31(金) 07:23:04.73 ID:KNbvu5CI.net]: どうしてこうなった
935 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 09:04:32.63 ID:csqJsH/K.net]: >>916
では、数列、非線形解析学を利用した
アルゴリズムを答えてください
936 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 09:05:36.36 ID:csqJsH/K.net]: ちなみに、数列は高校数学である
937 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 11:52:41.02 ID:5OSgw2nY.net]: >>918
>>896
938 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 12:44:50.11 ID:DXKxWv2O.net]: >>920
数学の問題をコンピュータで解決するってのはわかる、
だが数学・物理特有の問題以外をコンピュータで解決するのに
数学はいらねーだろって話
939 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 14:32:18.54 ID:5OSgw2nY.net]: >>921
微分積分も理解せずにコンピュータに信号処理をやらせるの？
そういうレベルの質問
940 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 14:39:40.99 ID:DXKxWv2O.net]: 信号処理なんて、誰がやっても同じなんだから
一度ライブラリ作って、他の人はそれ使うだけだろ・・・
941 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 16:28:19.03 ID:5OSgw2nY.net]: >>923
それじゃあ初音ミクは生まれないね
こういうやつが技術を停滞させる
942 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 18:49:37.43 ID:DXKxWv2O.net]: >>924
だからそういうのは専門家に任せたほうが良くね？

音声合成をやる人は、そういう専門家に任せて
他の人は便利なインターフェースを作るとかさ、
なんでも1人でやるもんじゃないよ？
943 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 19:18:52.92 ID:5OSgw2nY.net]: 別にそういう原理を知りたくないんなら勉強しなくて良いんじゃない
表面的なものしか作りたくないなら勉強しないことをおすすめします
944 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 19:24:24.23 ID:DXKxWv2O.net]: >>926
だから作る層が違うって言ってんの
水道局で働いてる人全員が
工事技師じゃないんだよ
945 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 19:27:43.29 ID:5OSgw2nY.net]: >>927
つまり君はそういう層にはなるのを拒む側ってだけだ
946 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 20:05:55.05 ID:OUCwI4mz.net]: >>928
その理屈で言えば、君がそういう層になりたいだけでは？

残念だけど、自分がやりたいことと、他人がやってもらいたいこと
っていうのは同じじゃないんだよね

そして給料っていうのは、他人がやって欲しいことをやった対価として
もらえるものなので、いくら自分がすごいことができるって言ったからって
給料は高くならないんだよね。
947 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 00:41:52.18 ID:GjC7kJfb.net]: >>929
作りたいものがあるから勉強する、それだけ
948 名前：デフォルトの名無しさん [2018/09/01(土) 09:56:42.06 ID:pu0WuyWZ.net]: うむ
949 名前：デフォルトの名無しさん [2018/09/01(土) 10:48:54.59 ID:iQmzKze8.net]: 自分一人で作るような小さいアプリとかなら、
全部を知っておかなければいけない、って思いたくなるのもわかる。

が、通常は数学の専門家でも無い人間を数学で信用する事は無いし、
プログラムの専門家でも無い人間をプログラムで信用する事は無い。

付け焼き刃は事故の元。
大きな仕事になればなるほど役割や責任が細分化される。
950 名前：デフォルトの名無しさん [2018/09/01(土) 12:24:44.93 ID:rDlJp/s7.net]: ぼやっとして結局何を言いたいのか良くわからんが
何か良い事を言いってみたい必死さは伝わった
951 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 12:52:20.45 ID:mPcVbgud.net]: え？言いたいことがわからんの？
952 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 13:01:11.42 ID:8oBLXasx.net]: そりゃあ馬鹿の言ってることは分からんだろ
953 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 13:13:44.90 ID:mPcVbgud.net]: 言ってることがわからんから、言ってるほうが馬鹿だと思ってるだけじゃないの？
俺に言わせれば、馬鹿だから言ってることがわからないんだと思うが？
954 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 13:42:02.18 ID:8oBLXasx.net]: 俺に言わせれば世界はお前を中心に回ってないってこと
955 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 13:47:09.53 ID:mPcVbgud.net]: >>937
お前を中心に回ってるといいたいのかな？
956 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 14:37:08.16 ID:8oBLXasx.net]: >>938
>>936
957 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 14:47:05.92 ID:mPcVbgud.net]: >>939
俺のレスがどうした？
958 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 02:27:34.18 ID:Tt3u8CpR.net]: アルゴリズム辞典みたいなものを手元に置いときたいんだが、最も支持されてるのってどれ？

・網羅性が高い
・支持されている（売れている）
・日本語版がある
・コード例はあってもなくても良くて、あるとしたら C/C++ か擬似コードで
という条件で
テーマ別に「どれとどれとどれを持っとけばまず問題ない」という言い方でもありがたい
とにかく網羅性を重視してる
959 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 07:04:17.98 ID:OlESf3Ok.net]: 英語は知らんけど、日本語なら
[改訂新版]C言語による標準アルゴリズム事典 (Software Technology)
奥村晴彦
amzn.asia/d/bAqY5Be
が網羅性は随一じゃないかな。
改訂だけど初版が1991年で、収録アルゴリズムは増えてないらしいので、
機械学習とかここ25年の新分野は当然入っていない。
960 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 07:32:26.75 ID:/VBaeORw.net]: 機械学習の何をアルゴリズム辞典に入れるべきだというのか

Amazonレビューかよテメェは
961 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 07:36:36.34 ID:5tN3iveh.net]: >>942
この本はBoyer-Moore法が簡易版しか載っていないし、Aho-Corasick法も載ってないから弱い
962 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 08:37:54.35 ID:HF+7qfHp.net]: より網羅的な対案示してからでないと批判にならないよ。

共立のアルゴリズム辞典が現存すればこっちも挙げてたかもしれん。
BM法に関してはコード例は簡略版のみだが。

個別のアルゴリズムについてどこまで踏み込むかは、
辞典の物理的な性質上取捨があるのはしかたないでしょ。
963 名前：デフォルトの名無しさん [2018/09/04(火) 10:34:21.16 ID:gEGTZvcA.net]: >>943
+1
964 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 10:36:29.76 ID:ROt4XEkp.net]: 名前がついていて解放も明らかになってるアルゴリズムに興味はない
そんなのいくらやっても新しいものは生み出されない
965 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 14:25:14.21 ID:JAXadswE.net]: >>947
先輩、かっけぇっす
966 名前：デフォルトの名無しさん [2018/09/11(火) 14:44:06.44 ID:O54onciS.net]: 質問させてください。
マイコンからAD変換で入力したサイン波を配列に格納し、周波数を求めたいと思います。
ゼロクロスの位置を求めれば正確に周波数を求められそうですが、教えてください。
https://i.imgur.com/FC5XP0K.png
967 名前：デフォルトの名無しさん mailto:sage [2018/09/11(火) 16:27:37.38 ID:zEn+kcA0.net]: 質問が不完全だけど、そのためのアルゴリズムを教えてほしいということでよい？

前提として、各周期で確実に2回だけゼロクロスすると保証できるのなら、
前回の値を覚えておいて、今回との積が0以下になったらゼロクロス。

この保証がないのなら十分長く波形をとってFFTしてピークを探す。
968 名前：デフォルトの名無しさん [2018/09/11(火) 22:09:31.90 ID:i7axZbyN.net]: ♀だったらｾｸﾛｽ教えてやる
969 名前：デフォルトの名無しさん [2018/09/11(火) 22:11:28.88 ID:4O7I7zcY.net]: え！？童貞なのにセクロスを！？
970 名前：デフォルトの名無しさん [2018/09/12(水) 03:44:12.77 ID:gw3HbkUV.net]: できらあ！
971 名前：デフォルトの名無しさん mailto:sage [2018/09/12(水) 07:05:35.15 ID:Jy3sklaz.net]: それページ逆だぞ
972 名前：デフォルトの名無しさん [2018/11/05(月) 18:00:44.74 ID:ajh0QscM.net]: 有向グラフの有向閉路を求める問題です。

深さ優先探索を実行したときに、 Backward Edge が存在する。

⇔

有向閉路をもつ

⇒は自明ですが、逆はどう証明するのでしょうか？
973 名前：デフォルトの名無しさん mailto:sage [2018/12/03(月) 20:50:16.30 ID:wBSUle4B.net]: 深さ優先、幅優先探索を理解するのにオススメの本ってありますか？(コードサンプル付きでできればC)
974 名前：デフォルトの名無しさん [2018/12/04(火) 09:57:38.19 ID:euG8Im7Y.net]: https://www.amazon.co.jp/dp/4874084141
975 名前：デフォルトの名無しさん [2018/12/04(火) 10:14:50.08 ID:GTmuusXQ.net]: >>957

全くおすすめできません。その本。
976 名前：デフォルトの名無しさん [2018/12/04(火) 10:27:11.51 ID:GTmuusXQ.net]: >>956

グラフ・ネットワークアルゴリズムの基礎: 数理とCプログラム
浅野孝夫
固定リンク: amzn.asia/d/2MetXvf
977 名前：デフォルトの名無しさん mailto:sage [2018/12/04(火) 11:20:17.46 ID:6CbA0WHr.net]: 馬鹿アスペの推奨ｗ
978 名前：デフォルトの名無しさん mailto:sage [2018/12/04(火) 14:19:52.12 ID:X/ZQLD1J.net]: 学ぶ目的には全くお勧めできないってのはその通りだけど、
手元に置いておいて使う分には便利な本ではあるような。
あ、浅野先生の本も待ってます。
(この分野、浅野先生が2人いて紛らわしい)
979 名前：デフォルトの名無しさん [2018/12/04(火) 14:28:35.23 ID:GTmuusXQ.net]: >>956

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
渡部有隆
固定リンク: amzn.asia/d/g8qmfS6

↑この本にも、 BFS、DFS共に書いてあります。

解説は非常に雑ですが。
980 名前：デフォルトの名無しさん [2018/12/04(火) 14:33:05.75 ID:GTmuusXQ.net]: >>959

の本には、再帰を使う DFS プログラムが書いてあります。（スタックを使う DFS プログラムは演習問題にあり、コードをダウンロードできます。）
981 名前：デフォルトの名無しさん [2018/12/04(火) 14:34:21.14 ID:GTmuusXQ.net]: >>963

スタックを使う DFS プログラムは演習問題にあり、コードをダウンロードできますし、本にも解答のところにコードが載っています。）
982 名前：デフォルトの名無しさん mailto:sage [2018/12/04(火) 14:39:02.72 ID:eKuwOju4.net]: 前置記法（ポーランド記法） + 1 2
後置記法（逆ポーランド記法） 1 2 +
中置記法 1 + 2

確か、構文木をたどる時に、どれかが幅優先で、どれかが深さ優先探索になると、記憶している
983 名前：デフォルトの名無しさん [2018/12/05(水) 13:24:47.73 ID:2sSegHBZ.net]: shaderって何回書き換えてもメモリ壊れない？
984 名前：デフォルトの名無しさん [2018/12/05(水) 21:47:02.62 ID:xYhP2Ga4.net]: テンプレのソース探検なんちゃらのサイトいいね
pdf買えはうざいけど

ソートはクイックマージヒープの特性くらい押さえとけば良さそうな感じだな
そこら中に実装あるしまあ
バケットソートは聞いたこと無かったけど、これは局所で凄い威力発揮しそうだ
覚えとく価値ありそう
985 名前：デフォルトの名無しさん [2019/06/19(水) 04:49:26.98 ID:tVNS+22r.net]: 【出資】松本卓朗人工知能詐欺【注意】
https://rio2016.5ch.net/test/read.cgi/rikei/1560859403/
986 名前：デフォルトの名無しさん mailto:sage [2020/01/03(金) 12:48:16.96 ID:LiTO8m+L.net]: O(n)で中央値を求めるアルゴリズムを思いついた
987 名前：デフォルトの名無しさん mailto:sage [2020/01/04(土) 01:21:11.30 ID:buSsFrEd.net]: クイックセレクトのこと？
988 名前：デフォルトの名無しさん [2020/01/13(月) 02:33:48 ID:D6MgPK0q.net]: こんにちは、初質問させていただきます、グラフアルゴリズム初心者です

・無向グラフGが入力として与えられる(ファイルからでも、コード内での手打ちでも、どちらも良い)
・Gがサイクルを持てばGの中の最小サイクル(長さが最も短いサイクル)とそのコストを出力する
・各辺、頂点の重みは考えなくても良い(つまり辺のコストは1とする)
といったアルゴリズムを実装したいです。
できればC言語もしくはC系統の言語でコーディングしたいです。

考え方と共に、コーディング例をご教授いただけると幸いです。

浅い知識ではありますが、この実装に必要そうである
・DFS,BFS
・ダイクストラ、ベルマンフォード
に関しては、基礎レベルは把握しています。

お手数おかけしますが、ご助力いただけると幸いです。
989 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 04:31:10.60 ID:6QaMEdT1.net]: 適当に言うけど、

すべての辺を1回だけ通りながら、通った頂点を記録していく
それで同じ頂点を、2回以上通ったら、閉路がある？
990 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 12:21:39.99 ID:jqPh5nAm.net]: >>971
グラフのサイズが書いてないと答えられないな
991 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 13:32:08.60 ID:D6MgPK0q.net]: >>973
条件不足で申し訳ございません

グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。

お手数お掛け致しますが、よろしくお願いします。
992 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 13:32:16.76 ID:D6MgPK0q.net]: >>973
条件不足で申し訳ございません

グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。

お手数お掛け致しますが、よろしくお願いします。
993 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 17:13:44.37 ID:jqPh5nAm.net]: >>975
頂点数をn，辺数をmとする
ある頂点uを含んだ最小閉路は頂点uからbfsをすればO(n+m)で求められる（最初にuに戻ってきたときの経路が最小）
あとはすべての頂点に対してこれをして，その中から一番短いものを選べばいいので，全体でO(n(n+m))で求められる
994 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 22:42:08.62 ID:D6MgPK0q.net]: >>976
ありがとうございます。

つまり、例えば
各頂点を始点-終点とするダイクストラアルゴリズム処理を行えば良い
ということでしょうか。
995 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 23:30:01.64 ID:jqPh5nAm.net]: >>977
イメージとしてはそんな感じです
辺を考えたほうがわかりやすいかもしれないです

ある辺(u-v)を含むようなサイクルの中で最小のものを求めたいとします
まずグラフから辺(u-v)を除去します．このグラフ上でuからvの最短距離dを求めます
すると，d + 辺(u-v)が辺(u-v)を含むサイクルの中で最小のものとなります

グラフの中で一番短いサイクルは辺(u-v)を含んでいるかはわからないので，すべての辺に対して上の操作を実行します
その中から一番短いものを選べば，それがグラフの中で一番短いサイクルです
この場合だとO(m(n+m))です
996 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 13:45:14.74 ID:oHYk5H5Q.net]: >>978
ありがとうございます。
ご教授いただいた考えをもとに、ダイクストラ法を用いて実装してみました。
・ダイクストラ(グラフは頂点とコストで表現)
https://ideone.com/bXF0iQ

また、以前似たものを実装したのですが、これはダイクストラ(もしくはBFS)の考えに則れていますでしょうか・・・？
(グラフは隣接行列で表現)
https://ideone.com/snxvav

どちらにしても、始点と終点が同一でない場合はうまくいくのですが、
始点と終点を同一として閉路で求めようとすると、うまくいきません。
自己ループ辺のコストが0であるから、と思い9999などにしてみましたが、うまくいきませんでした。

すごく単純なミスなのでしょうが、詰まってしまっている状態です。
修正等いただけると幸いです。

一応、(可能であれば)望む仕様と結果としては
・グラフは隣接行列で表現
・辺の重みは非負である(今回、簡易化のために辺の重みは1~9)
・グラフサイズは制限しない(今回、簡易化のために10頂点程度)
・ダイクストラを用いて自分自身を始点かつ終点とする最短経路を求める
・各頂点に対して上のダイクストラを行い、中でも最短の閉路の経路とそのコストを表示する

です。

お手数をおかけしますが、よろしくお願いします。
997 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 16:39:42.37 ID:Ex9G0OLU.net]: >>979
>>971だと辺のコストは1となっているが，実際は辺に1以外のコストがある？
求めたい最小サイクルというのは，使う辺の本数が最小という意味なのか，使う辺の合計コストが最小という意味のどちらなのか
998 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 21:49:25 ID:oHYk5H5Q.net]: >>980
コストは1だと申し上げましたが、
ダイクストラなので非負であれば求まると思い、汎用性を考えて1以外のコストも付与してみました。
説明不足で申し訳ございません。
999 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 23:25:41 ID:Ex9G0OLU.net]: >>981
無向グラフだと面倒くさくて，uからvにいったあとvからuにいくような場合がでてくるのでこれを除かないといけない
そのような経路を除いたうえで始点に戻ってきたものが最短になる
ある辺が2回使われることはないので，辺は1度しか使えないようにすればいいと思う
1000 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 23:28:15 ID:Ex9G0OLU.net]: https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/
これとかわりとそのままだな　重みなしだけど
1001 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 23:56:14 ID:Ex9G0OLU.net]: https://www.geeksforgeeks.org/find-minimum-weight-cycle-undirected-graph/
こっちは重み付きのやつ
1002 名前：デフォルトの名無しさん mailto:sage [2020/01/18(土) 22:58:37.26 ID:iLU56BHo.net]: >>983
>>984

ありがとうございます。
コストだけでなく、経路も出力したいのですが、弄ってみてもなかなかうまくいきません...。
1003 名前：デフォルトの名無しさん [2020/01/19(日) 12:55:00.98 ID:VFlG/sWR.net]: CLRSのダイクストラのアルゴリズムの正しさの証明を読み終わりました。
行間が全くなく、確かに、正しいことは分かりますが、あまりイメージのわかない証明ですね。

CLRSって他の本と比べると異常に行間がないですよね。
1004 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 15:11:46.01 ID:+ZQhvd/Y.net]: 巨大なsparce行列（ゼロ要素が多い行列）で行列演算やるときデータ構造考えるよね
1005 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 17:27:30.27 ID:/b+J8VIk.net]: >>985
どのへんがわからないか言ってくれ
Find minimum weight cycle in an undirected graphは
int Graph :: ShortestPathでu-vを削除したときの最短経路を求めてる
このときdist[v]が更新されるたびにvにきたノードをメモしておけば最後にvからprevをたどって復元できる
このときの経路をvector

楽な実装方法は，グローバル変数にこれまでの最短経路の距離とルートをもっておいて
常に最短のものを保存しておけばいい
1006 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 17:28:22.60 ID:/b+J8VIk.net]: 途中で送信してしまった
このときの経路をvetorにいれておけばいい
1007 名前：デフォルトの名無しさん mailto:sage [2020/01/25(土) 23:49:17 ID:Q85YRMjK.net]: >>988
正直、C++の知識不足で勉強を頑張ってはいるのですがVectorの使い方がまだ、慣れていません。。。

厚かましいのは重々理解しているのですが、可能であればFind minimum weight cycle in an undirected graphのプログラムを>>988さんなりに改変したものをお教えいただけると幸いです。。。

悪い勉強法とは分かっているのですが、答えというか実装例が無いとなかなか理解できなくて。。。
1008 名前：デフォルトの名無しさん mailto:sage [2020/01/26(日) 01:32:16.02 ID:63DOpTVc.net]: 言語の基本的な部分はさすがによそでやろうや・・・
1009 名前：デフォルトの名無しさん [2020/01/26(日) 13:25:18.52 ID:eN1PAkvI.net]: >>990

https://ideone.com/pShuim

↑一応動きました。
piという変数に経路を覚えさせています。
1010 名前：デフォルトの名無しさん [2020/01/26(日) 13:32:46.65 ID:eN1PAkvI.net]: >>990

piについては、

Cormen, Leiserson, Rivest, Stein著『Introduction to Algorithms 3rd Edition』の最短路の章を見ると、

書いてあります。
1011 名前：デフォルトの名無しさん [2020/01/26(日) 13:47:50.10 ID:eN1PAkvI.net]: アルゴリズムとデータ構造ってコンピューターサイエンスの分野で人気ないんですか？
1012 名前：デフォルトの名無しさん mailto:sage [2020/01/26(日) 16:03:48.66 ID:gJO14xRt.net]: >>994
ネット以外だとデータ構造とアルゴリズム好きな人見たことないな
CS系だと機械学習やってるやつが多い
1013 名前：デフォルトの名無しさん [2020/01/26(日) 16:28:11 ID:eN1PAkvI.net]: >>995

ありがとうございます。

機械学習は非常に流行していますが、勉強するのに面白い分野だとは思えません。
1014 名前：デフォルトの名無しさん [2020/01/27(月) 12:15:36 ID:Dkceayzl.net]: DAGの単一始点の最短経路問題を解くアルゴリズムとか
Bellman - Fordのアルゴリズムとかの正しさの証明が非常
に面白いですね。
1015 名前：デフォルトの名無しさん [2020/01/27(月) 17:15:29 ID:Xu7tzl7q.net]: >>996
+1
1016 名前：デフォルトの名無しさん [2020/01/27(月) 17:16:05 ID:Xu7tzl7q.net]: >>997
-1
1017 名前：デフォルトの名無しさん [2020/01/27(月) 17:16:23 ID:Xu7tzl7q.net]: >>999
+1=1000
1018 名前：1001 [Over 1000 Thread .net]: このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 1317日 2時間 28分 54秒
1019 名前：過去ログ ★ [[過去ログ]]: ■ このスレッドは過去ログ倉庫に格納されています

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

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