板検索:
データ構造,アルゴリズム,デザインパターン総合スレ 3 (742)
まとめビュー
重複読み込みスレ:このスレは、2重読み込みでレスが重複している可能性があります。修復する場合はこちらをクリックしてください。
1
デフォルトの名無しさん[sageteoff]   投稿日:2016/06/19 14:47:29  ID:5KvSKdL/.net(4)
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

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

                  京都大学霊長類研究所

データ構造,アルゴリズム,デザインパターン総合スレ 2

【関連スレ】
3Dアルゴリズム全般
<集大成>アルゴリズム大辞典
アルゴリズム総合スレ in ム板

アルゴリズムとデータ構造 - Kaneko Lab.
http://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
http://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
http://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
http://vipprog.net/wiki/algo_and_data_const.html


2
デフォルトの名無しさん[]   投稿日:2016/06/19 14:52:46  ID:5KvSKdL/.net(4)
http://hissi.org/read.php/tech/20160619/YW80V0xnZlg.html
へんなのが居着いたな

981 :デフォルトの名無しさん[sage]:2016/06/19(日) 12:16:06.94 ID:ao4WLgfX
>980
いつも思うんだけれども,この碁の勝負,棋譜は公開されているの?

985 :デフォルトの名無しさん[sage]:2016/06/19(日) 12:47:45.21 ID:ao4WLgfX
>982
どこに貼ってあるかな?たぶん公開されてないんじゃないかな

986 :デフォルトの名無しさん[sage]:2016/06/19(日) 12:59:15.60 ID:ao4WLgfX
http://blogs.yahoo.co.jp/ten_nan_91/35774553.html

988 :デフォルトの名無しさん[sage]:2016/06/19(日) 13:02:20.35 ID:ao4WLgfX
ありがとう

1000:デフォルトの名無しさん[sage]:2016/06/19(日) 14:49:22.87 ID:ao4WLgfX
0
コメント4件

3
デフォルトの名無しさん[sage]   投稿日:2016/06/19 15:04:05  ID:IRfn+3ke.net(2)
>1 乙

4
デフォルトの名無しさん[sage]   投稿日:2016/06/19 16:13:42  ID:gP7jNw8f.net(2)

5
デフォルトの名無しさん[sage]   投稿日:2016/06/19 17:17:34  ID:ao4WLgfX.net(2)
ruby って変な人が多いんだね,俺も今 ruby をマスターしようと必死ではあるが

6
デフォルトの名無しさん[sage]   投稿日:2016/06/19 17:37:31  ID:X+E3gNs8.net(2)
>2
盛大な自演だったってこと?

7
デフォルトの名無しさん[]   投稿日:2016/06/19 19:39:00  ID:iKM7Z0CI.net(6)
Haskellって勉強する意味ある?
実用性はないよね?

8
デフォルトの名無しさん[sage]   投稿日:2016/06/19 19:46:20  ID:0JS60cqV.net(2)
雇われプログラマには不要

9
デフォルトの名無しさん[]   投稿日:2016/06/19 20:49:00  ID:iKM7Z0CI.net(6)
なぜ、HaskellやSchemeをありがたがる人がいるの?
どう考えてもC#とかのほうが生産性が高いのに。
単なるかっこつけ?

10
デフォルトの名無しさん[]   投稿日:2016/06/19 20:49:49  ID:iKM7Z0CI.net(6)
MITのコンピュータの入門書もSchemeを使っていたりする。

11
デフォルトの名無しさん[sage]   投稿日:2016/06/19 20:59:07  ID:Axw7zBsF.net(2)
言語としてのlisp最強論は理解できるけどね。
実用的ではないのは言語自体の問題ではなくてシェアとかサポートする企業の存在とかコミュニティの問題。

12
デフォルトの名無しさん[sage]   投稿日:2016/06/19 23:46:31  ID:XG1Xog94.net(2)
haskellやschemeは勉強したくない奴には不要
雇われには言語選択権はないので、かりにそれらがよいものであったとしたとしても、フラストレーションたまるだけだろ

一言でいうなら自分で一から十まで計算を構築するための言語だな
ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要
コメント4件

13
デフォルトの名無しさん[]   投稿日:2016/06/20 00:15:53  ID:VsbhBHIt.net(2)
>12
マジかよ

14
デフォルトの名無しさん[sage]   投稿日:2016/06/20 00:57:04  ID:rbqmVuz6.net(2)
>12
> ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要

ライブラリを駆使するのが今のプログラマに求められている技術だからな。

MITがSICPを教えなくなった理由
https://ezoeryou.github.io/blog/article/2016-05-05-sicp.html
> 今日では、状況が変わっている。今のエンジニアは、自分が完全に理解していない複雑なハードウェアの
> ためのコードを日常的に書いている(そして、大抵の場合、企業秘密により完全に理解するのは不可能である)。
> ソフトウェアでも状況は同じだ。プログラミング環境は、多大な機能を提供する巨大なライブラリ群の集合として存在している。
> Sussmanの今日の生徒は、その時間の大半を、ライブラリのマニュアルを読み、どのように組み合わせれば目的が
> 達成できるのかを把握することに費やしている。Sussman曰く、今日のプログラミングは、「より科学に近い。
> ライブラリを持ち寄って、つっつき回すのだ。プログラムを書くには、突っつき回して、どのように動作するかを観察する。
> そして、「目的を達成するために改造できるか」と考えるのだ」。SICPの「合成による解析」という物の見方である、
> 小さな、単純な部品を組み合わせて大きなシステムを作るということは、もはや今日の状況にそぐわなくなった。
> 今や、我々のプログラミングはつっつき回すことで行われている。
>
> なぜPythonを選んだかということについて、Sussmanは、"late binding"に決定したと冗談を飛ばした。
> Pythonには大量のライブラリがあり、教育者の様々な実習に使いやすい(たとえば、ロボットを制御するソフトウェアを書くなど)
コメント2件

15
デフォルトの名無しさん[]   投稿日:2016/06/20 06:52:18  ID:1vrQKLsp.net(12)
HaskellやSchemeの利点は?
少なくとも、分かりにくいよね。

16
デフォルトの名無しさん[sage]   投稿日:2016/06/20 08:05:44  ID:8yK3ULXk.net(2)
オブジェクト指向程ではないけどな

17
デフォルトの名無しさん[sage]   投稿日:2016/06/20 12:30:23  ID:iz9OSKHh.net(4)
エンジニアの選定時の足切りにちょうどいいよ

18
デフォルトの名無しさん[sage]   投稿日:2016/06/20 18:11:51  ID:Z8Or5TTF.net(2)
その基準で剪定できるのはかなり恵まれてる気が
コメント4件

19
デフォルトの名無しさん[sage]   投稿日:2016/06/20 18:23:24  ID:78XmmaUt.net(2)
>14
>今日のプログラミングは、「より科学に近い。

ここは変だな
「より工学に近い。」
というなら判るが
コメント2件

20
デフォルトの名無しさん[]   投稿日:2016/06/20 18:31:26  ID:1vrQKLsp.net(12)
SICPをプログラミング初学者に教えるというのは確かに異様だよね。

やっとまともになったというだけの話。

21
デフォルトの名無しさん[]   投稿日:2016/06/20 18:35:05  ID:1vrQKLsp.net(12)
コンピュータサイエンスの中でアルゴリズムとデータ構造ってどれくらい重要な科目なの?

22
デフォルトの名無しさん[]   投稿日:2016/06/20 18:50:31  ID:FhfmjeRD.net(2)
アルゴリズム + データ構造 = プログラム。
ということは。
プログラムの占める割合と等価なのでは。

23
デフォルトの名無しさん[]   投稿日:2016/06/20 18:52:50  ID:1vrQKLsp.net(12)
なんか計算の理論とかのほうが上みたいな感じじゃない?

24
デフォルトの名無しさん[]   投稿日:2016/06/20 18:53:47  ID:1vrQKLsp.net(12)
コンピュータサイエンスで最も重要な科目は、コンパイラとかOS?

25
デフォルトの名無しさん[sage]   投稿日:2016/06/20 18:53:55  ID:K++azvDQ.net(2)
自演乙

26
デフォルトの名無しさん[sage]   投稿日:2016/06/20 19:14:10  ID:/YC1nkci.net(2)
>18
この道30年の修業でようやく一人前

27
デフォルトの名無しさん[sage]   投稿日:2016/06/20 20:44:30  ID:EiR/M7I9.net(2)
寿司職人乙
コメント2件

28
デフォルトの名無しさん[sage]   投稿日:2016/06/20 20:58:16  ID:amTC+NJd.net(2)
schemeやらないとアルゴリズムとデータ構造を組み立てるってことがどういうことなのか、コードでわからないだろうな
コメント4件

29
デフォルトの名無しさん[]   投稿日:2016/06/20 21:06:41  ID:taQ4Dh1l.net(2)
>28
javaでよくない?

30
デフォルトの名無しさん[sage]   投稿日:2016/06/20 21:24:25  ID:iSiyYjqf.net(2)
javaでconsを表現するときにどうすればいいか知ってますか?

31
デフォルトの名無しさん[]   投稿日:2016/06/20 21:29:28  ID:1vrQKLsp.net(12)
>28

アルゴリズムとデータ構造の本に疑似コードが載っていることがあるけど、
Scheme風に書かれていることなど決してない。

32
デフォルトの名無しさん[sage]   投稿日:2016/06/20 21:47:01  ID:eW3OX+fW.net(4)
>27
植木職人

33
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:10:02  ID:iz9OSKHh.net(4)
>18
未経験でも理解出来るならとりあえず地雷の可能性は下がる

34
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:22:55  ID:m9phkWTx.net(2)
恵まれてない会社だと全員切る羽目になるって話だろw

35
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:43:48  ID:zvz85rzc.net(4)
31
そのSICPはschemeでかかれているわけで
昨今のライブラリ重視の観点からいえば、javaがいいっていうのはとおるけど、アルゴリズムかくのにjavaがいいってのは、センスないというか、お手入れ大好きなんだろうな

36
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:49:30  ID:eW3OX+fW.net(4)
引用できないやつに言われると

37
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:50:33  ID:zvz85rzc.net(4)
スマホで>>うつのめんどいんだよ

38
デフォルトの名無しさん[sage]   投稿日:2016/06/22 04:43:48  ID:W4spe1mc.net(2)
日立、新型半導体コンピュータの実用化に向けた前処理アルゴリズムを開発
http://news.mynavi.jp/news/2016/06/21/172/

新型半導体コンピュータの実用化に向けて、
要素間の複雑なつながりを規則的な構造に自動変換する前処理アルゴリズムを開発
http://www.hitachi.co.jp/New/cnews/month/2016/06/0621a.html

関連記事
日立、量子コンピュータに匹敵する性能の室温動作の新型コンピュータを試作
http://news.mynavi.jp/news/2015/02/23/121/

39
デフォルトの名無しさん[]   投稿日:2016/06/22 07:14:40  ID:rmORGvIR.net(6)
日本人の書いたアルゴリズムとデータ構造の本でまともなのって1冊もないの?
コメント4件

40
デフォルトの名無しさん[sage]   投稿日:2016/06/22 07:53:05  ID:HSGRYDR8.net(2)
>39
まともとは?

41
デフォルトの名無しさん[]   投稿日:2016/06/22 07:59:50  ID:rmORGvIR.net(6)
日本人の書いた本は薄っぺらくて説明も十分ではなく厳密でもなく網羅性もない本ばかりに思う。

42
デフォルトの名無しさん[]   投稿日:2016/06/22 08:00:26  ID:rmORGvIR.net(6)
杉原厚吉の本は特にひどいと思った。

43
デフォルトの名無しさん[sage]   投稿日:2016/06/22 11:07:15  ID:DmPvlaR4.net(2)
>39
そのものズバリでアルゴリズムとデータ構造という本が岩波から出てる

44
デフォルトの名無しさん[sage]   投稿日:2016/06/22 12:53:15  ID:YevSrNYa.net(2)
まともな本とは?
argolythm introduction?
knuth本?
どっちも使い物にならないが
コメント4件

45
デフォルトの名無しさん[sage]   投稿日:2016/06/22 13:50:41  ID:WHe3DbmR.net(2)
>44
1単語に3箇所もミス入れるなよ

46
デフォルトの名無しさん[sage]   投稿日:2016/06/22 14:13:53  ID:sEqYA8cS.net(2)
根幹のタームの綴りも知らん半可通に何を教われというのか

47
デフォルトの名無しさん[sage]   投稿日:2016/06/22 14:17:48  ID:yBOVYSwe.net(2)
3ヶ所もあると誤り訂正も利かないんじゃまいか

48
デフォルトの名無しさん[sage]   投稿日:2016/06/22 14:22:16  ID:EwWgL4+X.net(2)
バースト発生させんな

49
デフォルトの名無しさん[sage]   投稿日:2016/06/22 15:16:40  ID:2z7j8yec.net(2)
????????????

50
デフォルトの名無しさん[sage]   投稿日:2016/06/22 21:44:16  ID:MWgF3eo3.net(2)
>44
そんな頭じゃ使いものにならんのも頷けるわ

51
デフォルトの名無しさん[sage]   投稿日:2016/06/22 22:23:26  ID:Z2xvvdgM.net(2)
こんな揚げ足とりの老害から何を学べと?

52
デフォルトの名無しさん[sage]   投稿日:2016/06/22 22:52:24  ID:X6XCfxlz.net(2)
馬鹿の自己紹介されても困る

53
デフォルトの名無しさん[sage]   投稿日:2016/06/24 11:47:43  ID:hSLmnyaY.net(2)
>19
は?変なのはお前だ
プログラミングは最初から工学的だろ何言ってんだ?

そもそもお前は工学と科学を理解してないから可笑しなことを言うんだ

54
デフォルトの名無しさん[sage]   投稿日:2016/07/15 12:10:18  ID:P21uCIN+.net(2)
何ヶ月か前に近代科学社に電話でセジウィックアルゴリズムの第四版の翻訳の予定はありますか、と訊いてみたが無いって返事だったんだよな
書いて欲しいんだがな

55
デフォルトの名無しさん[sage]   投稿日:2016/07/16 08:00:53  ID:Akpk7DL9.net(2)
アルゴリズムさえ知ってりゃ動くプログラムは書けるから他は優先度低いと考えてた結果
データ構造すら分からない化石プログラマになってしまった

今必死にデータ構造とデザインパターン勉強中だけど、わかってくると楽しいね

アルゴリズムみたいにオーダー詰める楽しみはないけど…

56
デフォルトの名無しさん[sage]   投稿日:2016/07/18 09:37:52  ID:YPoLSDg9.net(2)
両方大事だろ。
データ構造が整理されてないとアルゴリズムも煩雑になるし。

57
デフォルトの名無しさん[]   投稿日:2016/07/21 23:06:49  ID:TpMXx+Na.net(2)
vEB木の「僕の考えた最強のデータ構造」感が大好きなんだが誰か共感してくれる人いる?

58
デフォルトの名無しさん[sage]   投稿日:2016/07/22 07:32:19  ID:ot11jjQx.net(2)
データ構造の基本は、以下の2つと、他にはハッシュがある

A → B → C → D
のように、メモリ上の位置がバラバラなオブジェクトを、リンクでつないでいくものと、
(シーケンシャルアクセス)

ABCD
のように、連続したメモリ位置に、オブジェクトやオブジェクトの参照が確保されていて、
単純な計算式で、各オブジェクトにアクセスできるもの(ランダムアクセス)

シーケンシャルは、リンクをたどるから、アクセスには時間がかかるけど、
要素の追加・削除では、リンクを付け替えるだけで、要素をずらさないから速い

59
デフォルトの名無しさん[sage]   投稿日:2016/07/26 06:56:53  ID:HN1KCMsQ.net(2)
letの時代がもうすぐそこまで来ているよね

60
デフォルトの名無しさん[sage]   投稿日:2016/07/26 14:27:18  ID:z5g/0KTZ.net(2)
let
-------
 λ

61
スモモンガー[sage]   投稿日:2016/09/23 22:08:49  ID:oKXONAGb.net(2)
どうも、お久しぶりです。スモモンガーです。(誰って感じだと思いますがそれで結構です)
以前紹介したアルゴリズムですが、結局全然応用分野は見つかっておりません。
前回は画像処理分野を中心に解説しましたが今回はより簡単に実装ができる
探索分野に絞って動画を作ってみました。つたない動画で大変申し訳ございませんが
見てみていただけたら幸いです。特許などは取得しておりませんのでどうかご自由に
お使いください。長文失礼いたします。痛いのは承知なのですが応用分野を必死に
探しているのでどうかご協力よろしくお願いします。

https://youtu.be/5m3kPHO2w98

以上、どうぞよろしくお願いします
コメント6件

62
デフォルトの名無しさん[sage]   投稿日:2016/09/23 22:16:41  ID:xWgfj234.net(2)
誰だ

63
デフォルトの名無しさん[sage]   投稿日:2016/09/23 22:42:52  ID:fJ2M8QeM.net(2)
帰れ

64
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:14:59  ID:osPXZH57.net(2)
>61
最初の数分見ましたが..

1) 何の探索なの?最初は「探索」と聞いて「グラフかな?」とか思ったけど配列みたいだし、最初に想定される入力を明確にした方がいいですね

2) プレゼンが文章を読み上げてるだけでイメージが湧きにくい
1,4,10,20,25 …
の例ではイラストを用いた方がわかりやすいと思います

3) Kangaroo Method とはのスライドでデータがソートされていて、キーの差が (中略) バイナリサーチと同等の効率を .. とありますが、例では入力が完全にソートされているようです。これなら最初からバイナリサーチを使います

また、11m10s くらいのところで「Sinカーブは整ってる」とありますが、「整っている」の定義がよくわかりません。その後の例も見ましたが、どのくらいまで途中に想定されていないデータが混じっていても許容範囲なのかが不明です

4) 先に長所短所のスライドを持ってきて、擬似コードとオーダーも明記し、「一部ソートされてなくても O(logn) で探索できます」みたいなのを書いて、見ている人を「それならもうちょっと続きを見てみようか」みたいな気にさせられればもっといいですね

以上、感想でした

65
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:32:41  ID:n5/uj8Su.net(6)
64さん。ありがとうございます。私はこういうスライドを作る機会があまりないのでこんな形になってしまいました。
実は整っているという抽象的な単語を使っていますが、実は定量的にこれを測る方法はまだ思いついていません。
そのほかのご指摘はその通りだと思います。
貴重なご意見ありがとうございます

66
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:49:16  ID:B225F1SQ.net(2)
動画見るの面倒だから3行で説明して
コメント2件

67
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:53:53  ID:trsNBxRI.net(2)



コメント2件

68
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:55:26  ID:n5/uj8Su.net(6)
>66
まず目的のキーと現在探索中のキーの差をとる。
それを隣接するキーの最大値で割る。
その値だけ進む。

まあ、原理は単純なアルゴリズムです

69
デフォルトの名無しさん[sage]   投稿日:2016/09/24 10:46:59  ID:iZTaxfZT.net(2)
>隣接するキーの最大値

これをあらかじめ求めておかなきゃならんってのが一番のネックだな。
一般のデータに対する探索だと、バイナリサーチと比較したメリットと言っていたものの大半が消し飛んでしまう。
コメント2件

70
デフォルトの名無しさん[sage]   投稿日:2016/09/24 10:49:01  ID:9ZsTQHH6.net(2)
>61
印象としては
1. 要素間の差の最大値を求めるのに線形時間
2. 各要素の値の差が一定でないと性能を発揮しない(最大値を求めるのも含め)
3. 探索の最悪時間が線形時間、恐らく平均も線形時間
4. ソートされていなくても探索可能な条件が不明瞭
5. データの内容に探索コストが大きく左右される

例えば
1 2 4 9 15 24 100 120 1002 1225
とあった時、差の最大値は
1002-120=882
1002を探索すると
1002-1=1001, 1001/882=1
1002-2=1000, 1000/882=1
1002-4=998, 998/882=1
1002-9=993, 993/882=1
...
と線形時間になる(やり方あってるよね?)
演算している分、比較だけの線形探索より処理速度が遅くなる
コメント2件

71
デフォルトの名無しさん[sage]   投稿日:2016/09/24 11:09:23  ID:n5/uj8Su.net(6)
>69
>70
確かにキーの最大値を求めるのは線形時間かかります。なのであらかじめ、隣接するキーの最大値が分かっているデータに使用可能です。
探索の最悪時間は線形時間ですが、平均時間はlogのオーダーになるのではないでしょうか。私が不勉強なもので理論的には、示めせませんが多分logのオーダーになると思います。
ソートしなくても探索できるのは差の絶対値を取るからです。動画に入れるのを忘れました。すいません。
計算についてはそれであっています。わざわざご指摘ありがとうございます
コメント4件

72
デフォルトの名無しさん[sage]   投稿日:2016/09/25 01:17:16  ID:MeFnEkA4.net(2)
>71
上でも指摘されているが整っているの定義が不明
二分探査の場合は、存在しないこともlog n で確認可能だが、この手法は整っているの定義次第では存在しない者の確認が非常に時間かかる(ソートされている場合は存在するものと同等だが、そうすると二分探索よりも利点が少なくなる)
平均計算量を求めるのはちと難しそうだけど、格納される値の値域に依存するかな
たぶん、log n 程良くはないと思う
コメント2件

73
デフォルトの名無しさん[sage]   投稿日:2016/09/25 09:29:52  ID:byM8xGto.net(2)
>72
ご指摘ありがとうございます。確かに整っているの定義ができていないのが一番の難点ですよね。いつか勉強して考えたいと思います

74
デフォルトの名無しさん[]   投稿日:2016/09/25 12:26:29  ID:3wiQalb8.net(2)
>67
ごめん
みたけど
だめだこりゃ
コメント4件

75
デフォルトの名無しさん[sage]   投稿日:2016/09/25 12:52:11  ID:NTqjAG/u.net(2)
>71
各要素間の差が一定であればO(1)、当たり前だけど、これは計算で求まる
各要素間の差の分布数が要素数に近づき、尚且つその落差が激しい場合
著しく線形時間になる

で、探索したい数値と差の最大値の商が1だった場合
その探索したい数値がある位置以下の数値探索はO(n)になる
データ列の後半に行くほど1回の演算で要素をステップする数が増えるけど
その移動は微々たるもの
データ列の内容に左右されることを差っ引いても、O(log n)からは程遠いと思う
詳しい計算は出来ないが、これを線形時間としても無理はないと思う

参考として
0 1 3 6 10 15 21 28 36 45
このデータ列では、15以下の探索はO(n)、
21は5回、28は4回、36は4回、45は3回の演算

結論として
このアルゴリズムの最大の欠点は差の最大値が必要な事を含めて
データ列の内容に左右されてしまうことだな
この手のアルゴリズムはデータの外側にあるべきだな

76
デフォルトの名無しさん[sage]   投稿日:2016/09/25 14:20:01  ID:8PebKpFu.net(2)
>74
88

77
デフォルトの名無しさん[sage]   投稿日:2016/09/26 13:42:01  ID:ymOrEJcI.net(2)
>61
すもモンがnewton法をガチで知らないのであればnewton法をまず勉強するべき
カンガルーの敵はバイナリではなくnewtonだ
コメント2件

78
スモモンガー[sage]   投稿日:2016/09/26 20:32:40  ID:7l1kSKga.net(4)
確かにデータ間の差に一様離散分布を使ったのは公平ではなかったです。
なので、データを完全にランダムにして調べてみました。
データはCのrand()%1000000で10000個生成しソートして、
探索の時配列のうちランダムな値を探すキーとし間を線形探索、カンガルー法
バイナリサーチで100回比べてみました。
その結果線形探索では平均比較回数約4963回最大比較回数は9972回でした
カンガルー法は平均比較回数約70回 最大比較回数は111回でした。
バイナリーサーチはやはり一番はやく、平均比較回数約12回、最大比較回数は14回でした
皆さんがご指摘の通りやはりバイナリーサーチが一番はやいようです。
ただ、例えばKMP法が逆行がないから使われているようにカンガルー法も逆行がないので
使うことはできないでしょうか?もし、とんちんかんなこと言ってたらすいません。

79
デフォルトの名無しさん[sage]   投稿日:2016/09/26 20:37:55  ID:7l1kSKga.net(4)
>74
www確かにそうかもしれませんね。
>77
一応私はニュートン法については知っています。Newton法は求める関数の微分した値を
しっていなければならないとおもうのですが、現実の探索だと関数が微分できないことも
多いかと思います。ちょっと、私が使った例が悪くてsinカーブや円を使ったのがよく
なかったのかもしれません。整っていてソートされていないデータとして扱いやすかったので
sin関数を使ったのであってとくにデータが微分可能である必要はありません。円と
Y切片の交点も中学生でも二次方程式ときゃいいのでもっと簡単にできますが、本来は
多角形とさまざまな図形の交点を探るアルゴリズムです。円を使ったのは例をわかりやすく
したかったからです。

80
デフォルトの名無しさん[]   投稿日:2016/10/16 18:51:48  ID:LqkHCFhg.net(2)
状態遷移ってどういうステータス持てばいいの?

A と B のステータスがあって、お互いが切り替わるのに n秒 かかる
切り替わりに失敗したら切り替えをリトライする
AはBになろうとし、BはAになろうとする

というとき、A と B のほかに AからBになるのを待ってる状態と
BからAになるを待ってる状態の 2つがさらに状態として必要?
過渡状態も状態?
コメント2件

81
デフォルトの名無しさん[sage]   投稿日:2016/10/17 07:56:46  ID:TukeUWYl.net(2)
>80
システムの設計次第。
切り替え中、待ち中が状態として存在するのならプログラムでも状態にすればいい
コメント2件

82
デフォルトの名無しさん[sage]   投稿日:2016/10/17 15:43:18  ID:srAFoI0L.net(2)
>81
そりゃそうだけど
状態がn個あると過渡状態がたくさんになるのは
辛い
コメント2件

83
デフォルトの名無しさん[sage]   投稿日:2016/10/17 17:53:14  ID:75S5w4gh.net(2)
現在の状態と次の状態のペアにすれば?

84
デフォルトの名無しさん[sage]   投稿日:2016/10/17 21:23:44  ID:sc7L52q+.net(2)
辛かろうが状態が存在するのならしょうがあるまい。
あるいは遷移をアトミックにして遷移中状態そのものを無くすか、遷移中の動作を共通化
できるなら遷移先をパラメータ化して「*への遷移中」という1状態にしてしまうとか。

85
デフォルトの名無しさん[sage]   投稿日:2016/10/17 23:34:18  ID:WkWdUImM.net(2)
>82には無理ということで

86
デフォルトの名無しさん[sage]   投稿日:2016/11/05 20:41:10  ID:PXYcOtjJ.net(2)
ポリモーフィックなクラスの相互作用において特定の型の組み合わせの場合のみ処理を特殊化したい場合はどうすればいいのだろう?

x = xFactory.create(...);
y = yFactory.create(...);

if(x.typeCode() == X.Foo && y.typeCode() == Y.Hoge)
executeSpecial((Foo) x, (Hoge) y);
else if (...)
...
else
executeNormal(x, y);

87
デフォルトの名無しさん[sage]   投稿日:2016/12/12 23:13:40  ID:IcWOSn01.net(2)
デザインパターンを使って実装すると、年長プログラマーから、またこんなことしやがって的な拒否反応が帰ってくるんだがどうすれば
コメント2件

88
デフォルトの名無しさん[sage]   投稿日:2016/12/12 23:42:41  ID:bt79hYqC.net(2)
排除する他道は無い。

89
デフォルトの名無しさん[sage]   投稿日:2016/12/12 23:50:03  ID:hGpJarHd.net(2)
転職しろ


90
デフォルトの名無しさん[sage]   投稿日:2016/12/13 03:19:26  ID:neuXXcOh.net(2)
若者で組合(または派閥)を創る

91
デフォルトの名無しさん[sage]   投稿日:2016/12/13 08:14:05  ID:5xcG7lRc.net(2)
>87 がどんなコードを書いたかも分からんのに

92
デフォルトの名無しさん[sage]   投稿日:2016/12/13 18:53:42  ID:MUcELcjh.net(2)
下手くそがデザインパターンとか使うと逆にこんがらがるからなぁ
老害とどっこいどっこいだろ

93
デフォルトの名無しさん[]   投稿日:2016/12/13 21:32:18  ID:lYWHr0pJ.net(2)
マルチスレッドで、なんの考えもなくオブザーバー使いまくられて、データ破壊しまくられた時には、本気で殺意を抱いたよ

94
デフォルトの名無しさん[]   投稿日:2016/12/16 15:12:11  ID:kO0vFktz.net(2)
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』

の優先度付きキューについてのプログラムについて質問です。

p.241の heapIncreaseKey(A, i, key) という関数内で、

「if key < A[i] エラー:新しいキーは現在のキーより小さい」

というのがあります。

これがなぜ必要なのかが分かりません。

insert(key) を見れば分かるように、この本の使われ方では、
key < A[i] になることは決してありません。

よろしくお願いします。
コメント2件

95
デフォルトの名無しさん[sage]   投稿日:2016/12/16 15:34:53  ID:n8JQ6xp/.net(2)
assertionじゃね
コメント2件

96
デフォルトの名無しさん[]   投稿日:2016/12/17 16:05:18  ID:lvQHWty7.net(2)
完成形をいきなり見てると不思議に思うよね。
でも実際には作成中のバグを考慮して、最初にチェックを入れておくもんなんだよね。
まあ、一言で言えばassertなんだけど。

ただ、作業やデバッグ用には必須であっても、その本の例示として必要か?と言われれば、確かにいらない気がする。
コメント2件

97
デフォルトの名無しさん[]   投稿日:2016/12/17 16:09:26  ID:GDWdcO6h.net(14)
>95-96

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の参考文献に
挙げられている『アルゴリズムイントロダクション』を見てみたら、全く同じプログラム
が載っていました。

完全にパクっていますね。

>96
デバッグ用にどうして必要なのかが分かりません。

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』はお持ちでしょうか?
もし、お持ちでないようでしたら該当箇所の画像をアップロードします。
コメント4件

98
デフォルトの名無しさん[]   投稿日:2016/12/17 16:23:27  ID:GDWdcO6h.net(14)
>94

念のため、該当箇所の画像をアップロードさせていただきます。
読めば読むほど意味不明です。

http://imgur.com/zKVWzAJ.jpg
http://imgur.com/owa8NkX.jpg
http://imgur.com/NmCczss.jpg
コメント6件

99
デフォルトの名無しさん[sage]   投稿日:2016/12/17 16:42:25  ID:a9hyyPvt.net(6)
>97
参考文献ならパクってるとは言わない

100
デフォルトの名無しさん[sage]   投稿日:2016/12/17 16:43:27  ID:a9hyyPvt.net(6)
>98
こういうのが本当のパクり
訴えられたら負ける

101
デフォルトの名無しさん[sage]   投稿日:2016/12/17 18:12:28  ID:rDdwnYMe.net(4)
>97
他の本も読んでみるとわかると思うけど、プライオリティキューを二分木ヒープで実装するのは定番で、どの本でも大体同じことが書いてある
コメント2件

102
デフォルトの名無しさん[]   投稿日:2016/12/17 19:29:55  ID:GDWdcO6h.net(14)
>98

「if key < A[i] エラー:新しいキーは現在のキーより小さい」

というのが、デバッグ用であるとは思えないのですが、これは一体何なんでしょうか?

heapIncreaseKey(A, i, key) を何か別の用途に使う場合があって、そのときに必要に
なるのならば納得しますが。

103
デフォルトの名無しさん[]   投稿日:2016/12/17 19:31:29  ID:GDWdcO6h.net(14)
>101

「if key < A[i] エラー:新しいキーは現在のキーより小さい」

という意味不明のコードも『アルゴリズムイントロダクション』のプログラムには
書いてあります。

こんな余計なコードは普通は入れないと思います。

完全にパクりだと思います。
コメント2件

104
デフォルトの名無しさん[]   投稿日:2016/12/17 19:35:00  ID:a9hyyPvt.net(6)
>103
参考文献に書いてあるんだからパクリも糞も無い罠
参考文献に書き漏れたら小保方さんみたいに突っ込まれるが

105
デフォルトの名無しさん[]   投稿日:2016/12/17 19:35:29  ID:GDWdcO6h.net(14)
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の
他のプログラムもおそらくすべて『アルゴリズムイントロダクション』の
プログラムをそのまま使っています。

恥を知れと言いたいです。

106
デフォルトの名無しさん[]   投稿日:2016/12/17 19:36:34  ID:GDWdcO6h.net(14)
参考文献に文献を挙げれば何でも許されるということはないと思いますが。

107
デフォルトの名無しさん[]   投稿日:2016/12/17 19:39:42  ID:GDWdcO6h.net(14)
『アルゴリズムイントロダクション』のほうをよく読んでいませんが、

「if key < A[i] エラー:新しいキーは現在のキーより小さい」

というのも『アルゴリズムイントロダクション』のほうでは意味があるのかもしれません。

それをそのまま何も考えずにコピペしたために、意味不明なことになっているのかも
しれません。

>98

を見て、誰か納得のいく説明ができるでしょうか?

意味不明としか言えないかと思います。

108
デフォルトの名無しさん[sage]   投稿日:2016/12/17 19:42:21  ID:C/wQAZQ3.net(2)
『アルゴリズムイントロダクション』のほうをよく読んでいませんが、
『アルゴリズムイントロダクション』のほうもまたどっか別の本からのパクリの悪寒。

109
デフォルトの名無しさん[sage]   投稿日:2016/12/17 19:47:48  ID:YhK78PBA.net(2)
"error: heap underflow" でググるといっぱい出てくる

110
デフォルトの名無しさん[sage]   投稿日:2016/12/17 19:57:50  ID:rDdwnYMe.net(4)
ID:GDWdcO6h は何をそんなに怒ってるの?
問題が解けなくてイライラしてるだけ?

どんな本も参考文献があり、どんなアルゴリズム、データ構造も元をたどれば最初に「ヒープで実装すればうまく行くぞ!」と発見した人の論文があるはず

新しい本を書くときは参考文献よりもわかりやすくなるように、説明やイラスト、擬似コードを変えたり、あるいは同じものを流用することもあるだろう

111
デフォルトの名無しさん[sage]   投稿日:2016/12/17 20:55:04  ID:jmPH7DRp.net(2)
disるのがはやってるらしい

112
デフォルトの名無しさん[sage]   投稿日:2016/12/18 00:45:20  ID:aCKcGLhu.net(8)
プログラミングコンテスト攻略のための、
アルゴリズムとデータ構造、渡部有隆(わたのべ ゆたか)、2015
Ozy(協力), 秋葉 拓哉(協力)

Aizu Online Judge(AOJ、会津大学)

プログラミング・コンテスト・チャレンジブック、第2版、2012
秋葉 拓哉, 岩田 陽一, 北川 宜稔

元々は、3人の東大大学院生が作った、チャレンジブックが大ヒットした。
今までは、こういうコンテストの問題を研究した本が無かった

一方、すでに海外では、TopCoder, Google Code Jam などが、
プログラマーの主戦場となっていて、日本では、AOJ が後を追っている状態

渡部有隆の本は、チャレンジブックの後に出した。
協力に、秋葉 拓哉の名前もある

プログラマ脳を鍛える数学パズル
シンプルで高速なコードが書けるようになる70問、増井 敏克、2015

一方、増井は、Rubyで解く、このパズル本で、
「ITエンジニアに読んでほしい!技術書・ビジネス書 大賞(ITエンジニア本大賞)」を受賞している

113
デフォルトの名無しさん[]   投稿日:2016/12/18 00:49:54  ID:VFzWAIXP.net(4)
めんどくさ

114
デフォルトの名無しさん[sage]   投稿日:2016/12/18 01:14:58  ID:aCKcGLhu.net(8)
漏れも、JavaScriptで、2分ヒープ(BinaryHeap)を実装したので、参照して
http://jsdo.it/michihito/bGH5

2分ヒープは、優先度つきキュー (順位キュー、priority queue)や、
ダイクストラ法 (Dijkstra's Algorithm)で使う

配列の[0]は使わない。[1]から始めると計算が楽
親1, 左右の子は2, 3で、親n, 子2n, 2n+1

プログラミング・コンテスト・チャレンジブックでは、[0]から始めていますが、
もし[0]から始めると、
親0, 左右の子は1, 2で、
親1, 左右の子は3, 4で、
親n, 子2n+1, 2n+2、となり複雑だから
コメント4件

115
デフォルトの名無しさん[sage]   投稿日:2016/12/18 01:56:35  ID:05Ug+E6t.net(6)
>114
汚すぎるコードだ。なんだろう。初心者とも違うな。
まるで20年ぐらい前から成長してない人が書いたコードのようだ。
コメント2件

116
デフォルトの名無しさん[]   投稿日:2016/12/18 02:12:34  ID:KR24tnjc.net(2)
>115
ド素人と丸出しの感想文だな

117
114[sage]   投稿日:2016/12/18 04:57:12  ID:aCKcGLhu.net(8)
すまぬ

JavaScriptも、よく知らずに書いたのだw
本当は、== ではなく、型も一致する厳密等価演算子、=== を使うべきだろう

まあ、JSなどで、とても開発はできない。
Haxe で書き直せばよいのだろうが

Kotlin, Electron やら何やら、最近の言語に、ついていけてないw

118
デフォルトの名無しさん[sage]   投稿日:2016/12/18 08:19:04  ID:05Ug+E6t.net(6)
> 本当は、== ではなく、型も一致する厳密等価演算子、=== を使うべきだろう
そういうレベルじゃない。

無駄なロジック、意味不明な変数名、多すぎるコメント、
コードの意味を何一つ分かってないとしか思えないといってんの

119
デフォルトの名無しさん[sage]   投稿日:2016/12/18 11:08:48  ID:7J/3tpZx.net(2)
俺はむしろここ
> このソースコードのライセンスは、MIT License です
> Original Copyright (c) 2014 Michihito Seto All Rights Reserved.
残飯を神棚に飾るが如く宣言
ここにこそ初心者らしさが凝縮されてる
コメント2件

120
デフォルトの名無しさん[]   投稿日:2016/12/18 11:50:21  ID:5nrc1ooF.net(20)
>114

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の

「if key < A[i] エラー:新しいキーは現在のキーより小さい」

というのは意味があるのでしょうか?

121
デフォルトの名無しさん[sage]   投稿日:2016/12/18 11:50:54  ID:05Ug+E6t.net(6)
jsdo使ってるやつって汚いコードが多いよな。
素人が使いたくなる機能でもあんのか?
ブラウザだけで開発ができるとか?

122
デフォルトの名無しさん[]   投稿日:2016/12/18 11:53:36  ID:5nrc1ooF.net(20)
デバッグなど必要のないくらい簡単なコードなので、デバッグ用とは考えられないかと思います。

123
デフォルトの名無しさん[sage]   投稿日:2016/12/18 11:57:14  ID:0+9ctOie.net(2)
馬鹿ほど自説に拘るw

124
デフォルトの名無しさん[]   投稿日:2016/12/18 12:12:58  ID:5nrc1ooF.net(20)
Introduction to AlgorithmsよりもAlgorithms(Sedgewick、赤い本)のほうがいい本ですね。

読んでいて楽しい。

125
デフォルトの名無しさん[]   投稿日:2016/12/18 12:18:23  ID:5nrc1ooF.net(20)
日本語のデータ構造とアルゴリズムの本だと、茨木の本が有名だけど、
どこがいいのかさっぱりわからない。

翻訳書ではない日本語の本でまともなのは、浅野孝夫の本くらいではないでしょうか?

126
デフォルトの名無しさん[sage]   投稿日:2016/12/18 12:18:30  ID:d5jVhhWj.net(6)
アルゴリズムやコードのライセンスってどの程度のものから付けていいんだ
あんまり簡単なものだと既出すぎてライセンス付けられるのか?って考えてしまう
かといってじゃあライセンス付けていい最低ラインは何なんだという話になる
コメント2件

127
デフォルトの名無しさん[]   投稿日:2016/12/18 12:20:00  ID:5nrc1ooF.net(20)
>126

ライセンスとか書いてあっても一部だけコピペして利用したら、分からないですよね。

どうやって、だれかのコードを流用したか判定するのか、それに興味があります。

128
デフォルトの名無しさん[sage]   投稿日:2016/12/18 12:30:54  ID:RB5DyRP2.net(4)
アルゴリズムには著作権ないよ
あるのはそれをどう表現したか
簡単なアルゴリズムには表現バリエーションなんて限られてるから
ある程度似るのはどうしようもない

129
デフォルトの名無しさん[]   投稿日:2016/12/18 12:37:57  ID:5nrc1ooF.net(20)
特許ならありますよね。

130
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:02:47  ID:PELrVlNw.net(6)
デザインパターンの本高い・・・
一冊持ってたけど引っ越しのごたごたでなくしちゃった
無料で網羅できるサイトありませんかね
一冊読んではあるので、さらっと構造や仕組みを紹介してくれていればいいし
英語もある程度は読めます

基本のデザインパターンだけでもありがたいし
マルチスレッド対応に踏み込んだサイトならなおありがたいです

131
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:22:26  ID:d5jVhhWj.net(6)
基本的な考え方覚えたら幾らでも応用できるだろ
カタログを後生大事にとっておく意味はない

132
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:35:15  ID:PELrVlNw.net(6)
覚えてないんすよ
記憶力ないんで忘れちゃって、ぼんやりとしか覚えてないんです
だから概要をしっかり覚え直したいなと思って
コメント2件

133
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:42:55  ID:+dKTlaSP.net(2)
>132
いや、デザパタ本こそ手元においておくべき
わけのわからん二次情報を見るとどんどんブレていくぞ

134
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:45:05  ID:RB5DyRP2.net(4)
リファレンスとしてはどの本がいい?

135
デフォルトの名無しさん[]   投稿日:2016/12/18 13:45:12  ID:5nrc1ooF.net(20)
ソフトウェア工学的な本って重要なんですか?

136
デフォルトの名無しさん[]   投稿日:2016/12/18 13:45:59  ID:5nrc1ooF.net(20)
学問的には全く面白くない分野ですよね。

137
デフォルトの名無しさん[sage]   投稿日:2016/12/18 14:08:17  ID:PELrVlNw.net(6)
TECHSCOREのデザインパターンのページ見ることで自己解決しました

138
デフォルトの名無しさん[]   投稿日:2016/12/18 15:45:37  ID:VFzWAIXP.net(4)
デザパタカタログは便利だよね
煮詰まったときに、休憩がてらパターンを眺めてると、閃くときがある

139
デフォルトの名無しさん[sage]   投稿日:2016/12/18 16:24:54  ID:+Ko1jSRc.net(2)
ねーわ、普通のコードが99.99%

140
デフォルトの名無しさん[sage]   投稿日:2016/12/18 18:22:27  ID:d5jVhhWj.net(6)
基本的な発想を学んだらカタログはポイ
パターンに執着してもデザインがぎこちなくなるだけ

141
114[sage]   投稿日:2016/12/18 23:03:56  ID:aCKcGLhu.net(8)
>119
jsdo.it では、全員のソースコードが、サイト内に限り、MITになる

漏れが、わざわざ、MITと書いておいたのは、サイト外でも使ってほしいという意味。
学生が勉強することも多いから、コメントも一杯書いた

2分ヒープ、AVL、赤黒木など、アルゴリズムの実装は、どうしても汚いソースコードになる

142
デフォルトの名無しさん[sage]   投稿日:2016/12/18 23:11:13  ID:f3M2Oqre.net(2)

143
デフォルトの名無しさん[]   投稿日:2016/12/18 23:11:21  ID:5nrc1ooF.net(20)
2分ヒープって簡単なアルゴリズムですよね。

汚くなりようがないように思うのですが。

144
デフォルトの名無しさん[]   投稿日:2016/12/18 23:12:19  ID:5nrc1ooF.net(20)
計算幾何学って難しい割に見返りが少ないように思います。

だからあんまり人気がないのかもしれないですね。
コメント4件

145
デフォルトの名無しさん[sage]   投稿日:2016/12/19 00:01:07  ID:hSWjQy3F.net(10)
漏れw

146
デフォルトの名無しさん[sage]   投稿日:2016/12/19 01:06:56  ID:8cVREo5r.net(2)
流石に漏れは笑う

147
デフォルトの名無しさん[sage]   投稿日:2016/12/19 08:08:43  ID:judB9f5Y.net(2)
>144
全体的なリテラシの底上げがされるまではどうしてもね。

148
デフォルトの名無しさん[]   投稿日:2016/12/19 12:42:11  ID:z9XVuDpo.net(4)
>144
理論的な上限値をあらかじめ計算することが出来て
無駄な努力や試行錯誤をしなくて済むというメリットがあるよ

149
デフォルトの名無しさん[sage]   投稿日:2016/12/19 17:37:02  ID:ic0p/3Yf.net(28)
長さnの整数からなる列(a_1 ,a_2, ..., a_n) があるとして、列の大きさを
|a_1|+...+|a_n|で定義します。、
大きさがmの任意の列を大きさm-1の列の中の一つの値だけ1違う
列一つに対応させたいんですけど
対応のさせ方がわかりません、教えてください。
例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する長さ2の列は
(0 ,-1 ,1), (1,0,1),(1,-1,1),(1,-1,0)とかあるので一つには定まってません。
なのでその対応をする関数をおしえてください。
コメント2件

150
間違ってたので直します[sage]   投稿日:2016/12/19 17:39:59  ID:ic0p/3Yf.net(28)
長さnの整数からなる列(a_1 ,a_2, ..., a_n) があるとして、列の大きさを
|a_1|+...+|a_n|で定義します。、
大きさがmの任意の列を大きさm-1の列の中の一つの値だけ1違う
列一つに対応させたいんですけど
対応のさせ方がわかりません、教えてください。
例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する大きさ2の列は
(0 ,-1 ,1), (1,0,1),(1,-1,0)とかあるので一つには定まってません。
なのでその対応をする関数をおしえてください。
コメント2件

151
デフォルトの名無しさん[sage]   投稿日:2016/12/19 17:48:27  ID:z9XVuDpo.net(4)
(1,-1,1)の長さが2?

152
デフォルトの名無しさん[]   投稿日:2016/12/19 17:53:09  ID:yHCszZUX.net(12)
>なのでその対応をする関数をおしえてください。

意味不明です。

153
デフォルトの名無しさん[]   投稿日:2016/12/19 17:55:40  ID:yHCszZUX.net(12)
(a_1, a_2, ..., a_i, ..., a_n)

a_i > 0 のときには、

(a_1, a_2, ..., a_i-1, ..., a_n)

a_i < 0 のときには、

(a_1, a_2, ..., a_i+1, ..., a_n)

a_i = 0 のときには、

(a_1, a_2, ..., a_i±1, ..., a_n)

を返せばいいのでは?

154
デフォルトの名無しさん[]   投稿日:2016/12/19 17:57:14  ID:yHCszZUX.net(12)
(a_1, a_2, ..., a_i, ..., a_n)

a_i > 0 のときには、

(a_1, a_2, ..., a_i-1, ..., a_n)

a_i < 0 のときには、

(a_1, a_2, ..., a_i+1, ..., a_n)

を返せばいいのでは?

a_i = 0 のときには、条件を満たす列は存在しないね。
コメント2件

155
デフォルトの名無しさん[]   投稿日:2016/12/19 17:58:07  ID:yHCszZUX.net(12)
>150

何がやりたいのかが不明確。

156
デフォルトの名無しさん[sage]   投稿日:2016/12/19 17:58:17  ID:hSWjQy3F.net(10)
>149
列の最初の数字だけ1足すなり引くなりして返せばいいだけじゃないの?
コメント4件

157
デフォルトの名無しさん[]   投稿日:2016/12/19 18:01:17  ID:yHCszZUX.net(12)
>例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する大きさ2の列は
>(0 ,-1 ,1), (1,0,1),(1,-1,0)とかあるので一つには定まってません。
>なのでその対応をする関数をおしえてください。

一つに定まらないから、すべての結果を返したいのか、
任意の一つの結果を返したいのか?
コメント2件

158
デフォルトの名無しさん[]   投稿日:2016/12/19 18:02:09  ID:yHCszZUX.net(12)
明らかに、

(0, 0, ..., 0) に対しては条件を満たす結果は存在しないね。

159
デフォルトの名無しさん[sage]   投稿日:2016/12/19 18:50:37  ID:ic0p/3Yf.net(28)
0はスタート地点なので

160
デフォルトの名無しさん[sage]   投稿日:2016/12/19 18:57:02  ID:ic0p/3Yf.net(28)
>154
a_2を1としたとき(-1, 1)のとき(-1,0)を返し
a_1を-1としたとき (-1,1)は(0,1)をかえすことになるので
一つに定まりません

161
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:06:19  ID:ic0p/3Yf.net(28)
>157
大きさn>0の任意の列aにたいしてf(a)=bでbがn-1の大きさでaと列の中の値が1だけ違う
列を出力する関数fを求めるということです。
コメント2件

162
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:13:51  ID:ic0p/3Yf.net(28)
>156
初めはそんな風に考えてる時期もありました
もう2か考えてるけれど全然わからないのでここで質問してみました

163
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:16:05  ID:hSWjQy3F.net(10)
>161
問題文を鸚鵡返しするんじゃなくて、質問者の質問に答えたら?
コメント2件

164
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:23:49  ID:ic0p/3Yf.net(28)
>163
fの出力は列の集合じゃないから普通わかりますよね
コメント2件

165
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:31:58  ID:hSWjQy3F.net(10)
>164
fが返すのは集合じゃないってのはどこに書いてある?
コメント2件

166
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:34:42  ID:ic0p/3Yf.net(28)
>165
14行上に書いてあります
コメント2件

167
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:47:31  ID:hSWjQy3F.net(10)
>166
Mateだと>156って書いてあるわ
自分の中ではこれは当然みたいな条件がいろいろあるんだろうけど、それを人に説明するのが下手なんじゃね

168
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:02:25  ID:ic0p/3Yf.net(28)
改行コードの数を数えてますか?
文の折り返しと改行とは違いますよ?

169
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:17:02  ID:2q/Y95iw.net(8)
こりゃまたひどい質問者だな
コメント2件

170
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:18:06  ID:Xx/umGft.net(6)
課題の丸投げ、しかも「日本語」が
コメント2件

171
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:25:56  ID:ic0p/3Yf.net(28)
課題という証拠はありますか?
実際課題じゃなくプログラミングしていたら出てきた問題なので
全然課題じゃないです
コメント2件

172
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:33:03  ID:ic0p/3Yf.net(28)
>170
あなたには誤った文を訂正する能力がないんですか?
それでは人間ではなくコンパイラーと同じですよ
コメント2件

173
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:37:51  ID:ic0p/3Yf.net(28)
>169
面白い問題とつまらない問題を区別する能力が数学的推測には
一番必要なんんです
この問題がつまらないと思うのなら解かないでいいです

174
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:50:46  ID:2q/Y95iw.net(8)
問題をきちんと記述する能力に欠けている
コメント2件

175
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:52:23  ID:2q/Y95iw.net(8)
あと、面白い問題だと思うなら、それこそ自分で解くのが楽しいのでは
ここで聞かずに
コメント2件

176
デフォルトの名無しさん[sage]   投稿日:2016/12/19 21:27:51  ID:ic0p/3Yf.net(28)
>175
楽しいものは独り占めるのではなく分け与えようと習わなかったのでは?

177
デフォルトの名無しさん[sage]   投稿日:2016/12/19 21:44:43  ID:ic0p/3Yf.net(28)
>174
今読み返してみましたがキチンと書かれてますよ
どこがキチンと書かれてないのか言ってくれたら
それは理解力の無さなので説明してもいいです

178
デフォルトの名無しさん[sage]   投稿日:2016/12/19 22:34:08  ID:2q/Y95iw.net(8)
十分楽しんだからあとは一人で楽しんでくれていいよ

179
デフォルトの名無しさん[sage]   投稿日:2016/12/19 22:53:51  ID:Xx/umGft.net(6)
>172
馬鹿乙

180
デフォルトの名無しさん[sage]   投稿日:2016/12/19 23:04:39  ID:L2gIhLeK.net(2)
先頭から非0を探して、はじめの要素が正なら1ひく、負なら1足す
これで終わりじゃないの?

181
デフォルトの名無しさん[sage]   投稿日:2016/12/19 23:45:15  ID:Xx/umGft.net(6)
アルゴリズムは自分で考えるじゃ、ボケ

182
デフォルトの名無しさん[sage]   投稿日:2016/12/20 13:05:59  ID:lAXr92yw.net(2)
>171
茶か尿かもう判らんって意見があるけど
検出時のガスクロのデータ見直したら判るはずという話がある
仮にそれでお茶だとしてももう発表はないだろう

183
デフォルトの名無しさん[]   投稿日:2016/12/21 18:35:54  ID:UR5SKYPV.net(30)
数列 1, 2, 3, …

すなわち、

数列 {a_n} = {n}

を考える。

{a_n} の任意の連続する有限部分列を a_k, a_(k+1), …, a_l(k ≦ l)とする。

各 i(k ≦ i ≦ l)に対して、0以上の整数 b_i を以下で定義する:

「2^(b_i) は a_i を割り切るが、 2^(b_i+1) は a_i を割り切らない」

このとき、 #{m | k ≦ i ≦ l である任意の i に対して、 b_i ≦ b_m} = 1 であることを示せ。

また、有限部分列 a_k, a_(k+1), …, a_l(k ≦ l)が与えられたとき、 k ≦ i ≦ l である
任意の i に対して、 b_i ≦ b_m となるような m を求めるプログラムを作れ。
コメント8件

184
デフォルトの名無しさん[sage]   投稿日:2016/12/21 18:45:01  ID:trArLuj5.net(8)
お断りいたします

185
デフォルトの名無しさん[sage]   投稿日:2016/12/21 18:49:10  ID:IT3zLaEf.net(2)
俺も断るわ

186
デフォルトの名無しさん[]   投稿日:2016/12/21 19:41:25  ID:UR5SKYPV.net(30)
早くも降参宣言か。
コメント2件

187
デフォルトの名無しさん[sage]   投稿日:2016/12/21 19:55:05  ID:RIWp4Ngq.net(18)
mなんていくらでもあるんじゃないの?
なんで#{m}=1?
コメント2件

188
デフォルトの名無しさん[]   投稿日:2016/12/21 20:06:55  ID:UR5SKYPV.net(30)
>187

一意的です。そこがちょっと面白いところです。

反例を作ろうと思ってもできないはずです。

189
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:09:57  ID:trArLuj5.net(8)
>183
分からない問題はここに書いてね421 [無断転載禁止]©2ch.net
分からない問題はここに書いてね421 /数学板

190
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:12:10  ID:RIWp4Ngq.net(18)
k=1, l=2で、{m}={2,4,6,8,...}
k=l=1で、{m}=自然数の集合
じゃないの?
コメント2件

191
デフォルトの名無しさん[]   投稿日:2016/12/21 20:16:47  ID:UR5SKYPV.net(30)
>190

{a_n} の任意の*連続する*有限部分列を a_k, a_(k+1), …, a_l(k ≦ l)とする。
コメント2件

192
デフォルトの名無しさん[]   投稿日:2016/12/21 20:18:48  ID:UR5SKYPV.net(30)
k=1, l=2で、{m}={2,4,6,8,...}
k=l=1で、{m}=自然数の集合
じゃないの?

a_1, a_2 = 1, 2

なので、 b_1, b_2 = 0, 1

です。

なので、 {m} = {2} です。

193
デフォルトの名無しさん[]   投稿日:2016/12/21 20:19:15  ID:UR5SKYPV.net(30)
>191
は勘違いです。

194
デフォルトの名無しさん[]   投稿日:2016/12/21 20:20:14  ID:UR5SKYPV.net(30)
a_1 = 1

なので、

b_1 = 0

です。

なので、

{m} = {1}

です。

195
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:21:17  ID:RIWp4Ngq.net(18)
k=1, l=2も、k=l=1も、当然連続する部分列でしょ
{b_i}を10個ぐらい挙げてみてよ

196
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:22:42  ID:RIWp4Ngq.net(18)
mの条件が足りないんじゃないの?

197
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:24:46  ID:RIWp4Ngq.net(18)
b_i ≦ b_mさえ満たせばいいんならmなんていくらでもあるでしょ

198
デフォルトの名無しさん[]   投稿日:2016/12/21 20:32:03  ID:UR5SKYPV.net(30)
b_m は b_i の最大値です。

その最大値となる b_m の m が一意的であるということです。

199
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:32:36  ID:El82f3CE.net(2)
k≦m≦lという条件が抜けているっぽいね
コメント2件

200
デフォルトの名無しさん[]   投稿日:2016/12/21 20:34:06  ID:UR5SKYPV.net(30)
テレンス・タオ ルベーグ積分入門
テレンス タオ
固定リンク: http://amzn.asia/8KaL6NK

「日本の理工系学部ではルベーグ積分は3年次程度の必修相当科目なので、」

↑これっておかしくないですか?

普通、ルベーグ積分なんてやるのは数学科かせいぜい物理学科くらいじゃないですか?
コメント2件

201
デフォルトの名無しさん[]   投稿日:2016/12/21 20:34:58  ID:UR5SKYPV.net(30)
>199

各 i(k ≦ i ≦ l)に対して、0以上の整数 b_i を以下で定義する:

202
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:39:27  ID:RIWp4Ngq.net(18)
不完全な問題出しておいて>186はないよね
コメント2件

203
デフォルトの名無しさん[]   投稿日:2016/12/21 20:41:22  ID:UR5SKYPV.net(30)
>202

不完全なところはありません。
よく問題文を読んでください。
コメント2件

204
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:42:06  ID:trArLuj5.net(8)

205
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:43:41  ID:trArLuj5.net(8)
マルチ小僧w

206
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:44:49  ID:RIWp4Ngq.net(18)
>203
mがkからlの間なんて一言もないんだから不完全
コメント2件

207
デフォルトの名無しさん[]   投稿日:2016/12/21 20:47:08  ID:UR5SKYPV.net(30)
>206

>183
各 i(k ≦ i ≦ l)に対して、0以上の整数 b_i を以下で定義する

208
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:52:23  ID:RIWp4Ngq.net(18)
そうだとして、わざと誤読を誘おうとしている悪問だね
でO(log k)のアルゴリズム思いついたから俺は降りるね

209
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:53:06  ID:RIWp4Ngq.net(18)
O(log l)だった

210
デフォルトの名無しさん[]   投稿日:2016/12/21 20:55:14  ID:UR5SKYPV.net(30)
>183

の解答は以下です。

http://imgur.com/rAnp3Ga.jpg

赤線を引いたところは「odd」が正しいですね。

211
デフォルトの名無しさん[]   投稿日:2016/12/21 21:27:34  ID:UR5SKYPV.net(30)
実は、この問題には続きがあります。

m, n を m < n を満たす正の整数とします。

このとき、

1/m + 1/(m+1) + … + 1/n

は整数にはならないことを証明せよ。
コメント2件

212
デフォルトの名無しさん[]   投稿日:2016/12/21 21:29:28  ID:UR5SKYPV.net(30)
ちょっとアルゴリズム的な問題からは離れますが。

213
デフォルトの名無しさん[sage]   投稿日:2016/12/21 21:31:37  ID:xYX0mlO/.net(2)
提出日はいつですか?

214
デフォルトの名無しさん[sage]   投稿日:2016/12/21 22:14:54  ID:auJA5Ak8.net(2)
またバカな質問者が暴れてるのか

215
デフォルトの名無しさん[sage]   投稿日:2016/12/21 23:45:05  ID:mNaBBYjZ.net(2)
qiitaでやれ

216
デフォルトの名無しさん[sage]   投稿日:2016/12/23 00:59:54  ID:gOElNe3R.net(4)
>183
そのような m が 2 個ある
m1 < m2
とする

m1 の下位ビット 0 〜 n-1 までは 0で、 ビット n が 1 とする
m2 も同様になる(すなわち b_m1 = b_m2 = n )

m3 = m1 + ( 2 の n 乗 )

と定義すると
m1 < m3 <= m2 であるが、b_m3 > n となって矛盾

217
デフォルトの名無しさん[sage]   投稿日:2016/12/23 01:37:11  ID:gOElNe3R.net(4)
>211
1/m + 1/(m+1) + … + 1/n = P = 整数
だとする

L = ∏ r ; r = m…n
を両辺に掛ける

L/m + L/(m+1) + … + L/n = LP

すべての項は整数。

b_LP ( LP の連続する下位ビット 0 の個数 ) >= Σ b_r ; r = m…n

m <= x <= n は b_x を最大にするもの
左辺の L/x だけ連続する下位ビット 0 の個数は他より少ない
よって b_左辺 = b_x で矛盾

218
デフォルトの名無しさん[]   投稿日:2017/01/01 00:15:18  ID:VtFWW7J2.net(2)
ダイクストラのアルゴリズムの正しさの証明が載っている本で
一番分かりやすい本を教えてください。

219
デフォルトの名無しさん[]   投稿日:2017/01/02 07:40:19  ID:03PPbeGI.net(30)
『アルゴリズムイントロダクション』について質問です。

この本での実数の集合には、 ∞, -∞ が含まれるのでしょうか?

最短路問題の説明で、

実数 a が a≠∞のとき、 a + -∞ = -∞
実数 a が a≠-∞のとき、 a + ∞ = ∞

という記述があるために質問します。

220
デフォルトの名無しさん[]   投稿日:2017/01/02 08:09:15  ID:03PPbeGI.net(30)
実数 a が a≠∞のとき、 a + -∞ = -∞
実数 a が a≠-∞のとき、 a + ∞ = ∞

-∞ + -∞ = -∞
∞ + ∞ = ∞

という等式を含めたいからこのような書き方になったのでしょうか?

221
デフォルトの名無しさん[sage]   投稿日:2017/01/02 09:29:22  ID:J77W/v0L.net(4)
それは実無限派の書き方だが,世の趨勢は可能無限
ほどほどに相手をするだけでいいよ
コメント2件

222
デフォルトの名無しさん[]   投稿日:2017/01/02 11:22:57  ID:03PPbeGI.net(30)
>221

ということは、『アルゴリズムイントロダクション』での実数の集合の定義には、
∞、-∞ が含まれるというk十ですね。
コメント2件

223
デフォルトの名無しさん[]   投稿日:2017/01/02 11:23:39  ID:03PPbeGI.net(30)
頂点の数が n のグラフで、任意の頂点間に辺が存在するようなものを考える。

ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を求めよ。

224
デフォルトの名無しさん[]   投稿日:2017/01/02 11:26:14  ID:03PPbeGI.net(30)
頂点の数が n(≧2) のグラフで、任意の頂点間に辺が存在するようなものを考える。

ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を a_n とする。

このとき、

(n-1)! ≧ a_n ≧ (n-2)!

が成り立つことを示せ。
コメント2件

225
デフォルトの名無しさん[sage]   投稿日:2017/01/02 12:08:43  ID:GdcUHK9D.net(6)
宿題は宿題スレへ

226
デフォルトの名無しさん[sage]   投稿日:2017/01/02 12:09:56  ID:GdcUHK9D.net(6)
宿題は宿題スレへ

227
デフォルトの名無しさん[]   投稿日:2017/01/02 12:22:39  ID:03PPbeGI.net(30)
宿題ではないのです。

ある本に、頂点 s から t への最短経路を計算する方法として、
s から t へのあらゆる経路の長さを考えて、最小の経路を選ぶとすると、
経路の数が O(n!) だから現実的ではない

という話が書いてあります。

ところが、計算してみると、 O(n!) は荒い評価であって、 O((n-1)!) とできますね。
コメント4件

228
デフォルトの名無しさん[]   投稿日:2017/01/02 12:24:22  ID:03PPbeGI.net(30)
もっといい評価はありますでしょうか?

229
デフォルトの名無しさん[sage]   投稿日:2017/01/02 12:28:36  ID:GdcUHK9D.net(6)
判ってるなら効くな

230
デフォルトの名無しさん[]   投稿日:2017/01/02 14:08:15  ID:03PPbeGI.net(30)
ダイクストラ法の正しさの証明で分かりやすい証明を思いつきました。

発表しましょうか?


231
デフォルトの名無しさん[sage]   投稿日:2017/01/02 14:21:37  ID:w6ZCrhsc.net(2)
どうぞどうぞ

232
デフォルトの名無しさん[sage]   投稿日:2017/01/02 14:27:23  ID:yIXUnWg3.net(2)
>227
オーダーについてあんま良くわかってないんだろうけどO((n-1)!) なんて書き方はないよ
もし書いたとして、それはO(n!)と同じもの
コメント2件

233
デフォルトの名無しさん[sage]   投稿日:2017/01/02 17:55:38  ID:J77W/v0L.net(4)
>222
実無限はいろいろ破綻するから可能無限にしておいたほうがいいよ
実数の定義に∞, -∞は入らない
というか,そもそも -∞ というのがおかしい存在

つリーマン球面

234
デフォルトの名無しさん[]   投稿日:2017/01/02 19:04:30  ID:03PPbeGI.net(30)
なんか正しさの証明を書いてみると簡単なことなのに長くなりますね。
もし、間違っていたら指摘してください。

http://imgur.com/PDx2vmZ.jpg
http://imgur.com/DbMiSz5.jpg

ダイクストラのアルゴリズムは↑のものとします。
コメント2件

235
デフォルトの名無しさん[]   投稿日:2017/01/02 19:05:18  ID:03PPbeGI.net(30)
節点 s から、ある節点 i への最短経路が存在するとき、その長さを td(i) で表わすことにする。
i への経路、したがって最短経路が存在しないときには、 td(i) = ∞ とする。

ステップ(1)で選ばれる節点 v ∈ V - S に対して、 d(v) = td(v) が成り立つことを数学的帰納法により、以下で証明する。

最初にステップ(1)が実行されるときを考える。
明らかに、 d(s) = td(s) = 0 が成り立つ。

k ≧ 1 とする。
第 1 回目から第 k 回目にステップ(1)が実行されるときに、いつもステップ(1)で選ばれる節点 v ∈ V - S に対して、
d(v) = td(v) が成り立つと仮定する。

236
デフォルトの名無しさん[]   投稿日:2017/01/02 19:05:35  ID:03PPbeGI.net(30)
第 (k+1) 回目にステップ(1)が実行されるときを考える。
このとき、明らかに #S = k であり、 ∀i ∈ S に対して、 d(i) = td(i) が成り立つ。
第 (k+1) 回目にステップ(1)が実行されるときに選ばれる節点を v ∈ V - S とする。
d(v) = ∞ である場合と d(v) ≠ ∞ である場合で場合分けして考える。

(1) d(v) = ∞ である場合。
td(v) ≠ d(v) = ∞ と仮定して矛盾を導く。
td(v) ≠ ∞ であるから、節点 s から節点 v への経路 s = v_0 → v_1 → … → v_(l-1) → v_l = v が存在する。
明らかに、 td(v_0), td(v_1), …, td(v_(l-1)), td(v_l) ≠ ∞ である。
v_0 ∈ S, v_l ∈ V - S であるから、 v_i ∈ S, v_(i+1) ∈ V - S となるような i が存在する。
∀j ∈ V - S に対して、 d(j) = ∞ であるから、 d(v_(i+1)) = ∞ である。また、 v_i ∈ S であるから、
d(v_i) = td(v_i) ≠ ∞ が成り立つ。
v_i がステップ(2)で S に追加されたときのことを考えれば分かるように、 (v_i, v_(i+1)) ∈ E かつ v_(i+1) ∈ V - S であるから、
d(v_(i+1)) = ∞ ということはない。これは矛盾である。
よって、 d(v) = td(v) = ∞ が成り立つ。

237
デフォルトの名無しさん[]   投稿日:2017/01/02 19:05:51  ID:03PPbeGI.net(30)
(2) d(v) ≠ ∞ である場合。
td(v) ≠ d(v) と仮定して矛盾を導く。
ステップ(2)を考えれば明らかなように、 d(v) ≠ ∞ であるから、節点 s から節点 v への
最短経路 s = v_0 → v_1 → … → v_(l-1) → v_l = v が存在する。
よって、 td(v) ≠ ∞ である。
仮定により、 td(v) ≠ d(v) であるから、 td(v) < d(v) が成り立つ。
v_0 ∈ S, v_l ∈ V - S であるから、 v_i ∈ S, v_(i+1) ∈ V - S となるような i が存在する。
td(v_(i+1)) < d(v_(i+1)) である。なぜなら、もし、そうでないと仮定すると、 d(v_(i+1)) = td(v_(i+1)) であるが、
td(v_(i+1)) ≦ td(v) < d(v) であるから、 d(v_(i+1)) < d(v) となってしまい、ステップ(1)での v の
選ばれ方に矛盾するからである。
v_i ∈ S であるから、 d(v_i) = td(v_i) である。
v_i がステップ(2)で S に追加されたときのことを考えれば分かるように、 (v_i, v_(i+1)) ∈ E かつ v_(i+1) ∈ V - S であるから、
d(v_i) + a_(v_i v_(i+1)) ≧ d(v_(i+1)) である。
一方、明らかに、 td(v_i) + a_(v_i v_(i+1)) = td(v_(i+1)) であるから、
td(v_(i+1)) = td(v_i) + a_(v_i v_(i+1)) = d(v_i) + a_(v_i v_(i+1)) ≧ d(v_(i+1)) となるが、これは矛盾である。
よって、 td(v) = d(v) が成り立つ。

238
デフォルトの名無しさん[]   投稿日:2017/01/02 19:06:08  ID:03PPbeGI.net(30)
以上より、第 (k+1) 回目にステップ(1)が実行されるときにも、ステップ(1)で選ばれる節点 v ∈ V - S に対して、
d(v) = td(v) が成り立つ。

S に追加される節点はすべて、ステップ(1)で選ばれた 節点 v ∈ V - S であり、一度 S に追加された節点 v の d(v) はそれ以後、
変更されないから、ステップ(1)でアルゴリズムが終了したとき、 ∀i ∈ S = V に対して、 d(i) = td(i) が成り立つ。

239
デフォルトの名無しさん[]   投稿日:2017/01/02 19:26:36  ID:03PPbeGI.net(30)
>232

ある本では、

正定数 c, n0 が存在して、 n ≧ n0 のとき、 T(n) ≦ c*f(n) であるなら、
T(n) は O(f(n)) であるという

と定義されています。

T(n) = n!
f(n) = n!
g(n) = (n-1)!

とします。

このとき、明らかに、
T(n) は O(f(n)) ですが、
T(n) は O(g(n)) ではありません。

240
デフォルトの名無しさん[]   投稿日:2017/01/02 19:29:54  ID:03PPbeGI.net(30)
したがって、

O(f(n)) と O(g(n)) は異なります。

241
デフォルトの名無しさん[sage]   投稿日:2017/01/03 08:33:06  ID:3o9M4oho.net(2)
この狂人ヤバいなw

242
デフォルトの名無しさん[]   投稿日:2017/01/03 08:50:16  ID:hCDXc7Qp.net(20)
>224
>227

閉路を含まないから、各点を高々1回しか通らない。(端点も)

直通の経路が 1
途中でk個所を通過する経路が
 (n-2)(n-3)・・・・・(n-k-1) = (n-2)!/(n-k-2)!
だけある。ただし、k≦n-2
よって
a_n = (n-2)!{1 + 1/1! + 1/2! + … + 1/(n-2)!},

n ≧ 2 のとき、

(n-2)! ≦ (n-2)! * (1 + 1/1! + 1/2! + … + 1/(n-2)!) ≦ e * (n-2)!

したがって、

a_n = Θ((n-2)!)

である。

243
デフォルトの名無しさん[]   投稿日:2017/01/03 08:52:54  ID:hCDXc7Qp.net(20)
>234-238

のダイクストラのアルゴリズムの正しさの証明に間違いはないという
ことでOKですか?

244
デフォルトの名無しさん[]   投稿日:2017/01/03 11:39:58  ID:hCDXc7Qp.net(20)
Erik DemaineはMITの歴史上最年少で教授になったという天才だそうですね。

今、そのErik Demaineの2005年のダイクストラのアルゴリズムについての講義を見ています。

見終わったら、講義の要約について書きます。

245
デフォルトの名無しさん[]   投稿日:2017/01/03 13:47:58  ID:hCDXc7Qp.net(20)
ダイクストラのアルゴリズム:

01: d[s] ← 0
02: for each v ∈ V - {s}:
03: ■■d[v] ← ∞
04: S ← Φ
05: Q ← V
06: while Q ≠ Φ:
07: ■■u ← ExtractMin(Q)
08: S ← S ∪ {u}
09: for each v ∈ Adj[u]:
10: ■■if d[v] > d[u] + w(u, v):
11: ■■■■d[v] ← d[u] + w(u, v)

246
デフォルトの名無しさん[]   投稿日:2017/01/03 13:49:29  ID:hCDXc7Qp.net(20)
Correctness I:

d[v] の初期化の直後、およびLine 11の直後において、
すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が
成り立つ。

証明:
d[v] の初期化の直後には、
d[s] = 0 かつすべての v ∈ S - {v} に対して、d[v] = ∞
が成り立っている。
δ(s, s) = 0 かつすべての v ∈ S に対して、 δ(s, v) ≦ ∞
であるから、d[v] の初期化の直後には、
すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が確かに
成り立っている。

247
デフォルトの名無しさん[]   投稿日:2017/01/03 13:49:56  ID:hCDXc7Qp.net(20)
Line 11の直後において、すべての v ∈ V に対して、
d[v] ≧ δ(s, v) が成り立つことを背理法により示す。

Line 11の直後において、 d[v] ≧ δ(s, v) が
成り立たないような v ∈ V が存在するとする。
v をそのような点の中で、最初の点とする。

d[v] < δ(s, v)

d[v] < δ(s, v) ≦ ∞ であるから、
ダイクストラのアルゴリズムのLine 11は少なくとも1回は
実行されているはずである。そのような最後の実行を

d[v] ← d[u] + w(u, v)

とすると、

d[u] + w(u, v) = d[v] < δ(s, v)

が成り立つ。

一方、 d[u] ≧ δ(s, u) であるから、

d[u] + w(u, v) ≧ δ(s, u) + w(u, v)
≧ δ(s, u) + δ(u, v)
≧ δ(s, v)

が成り立つが、これは矛盾である。

248
デフォルトの名無しさん[]   投稿日:2017/01/03 13:51:21  ID:hCDXc7Qp.net(20)
Correctness Lemma:
s → … → u → v を s から v への一つの最短路とする。
d[u] = δ(s, u) であるとする。

このとき、Line10-11を実行すると、

d[v] = δ(s, v)

が成り立つ。

証明:
δ(s, v) = w(s → … → u) + w(u, v)
= δ(s, u) + w(u, v)
Correctness Iより、 d[v] ≧ δ(s, v)

(1)Line10-11の実行前に、 d[v] = δ(s, v) である場合。
Line10-11の実行後も d[v] = δ(s, v) である。

(2)Line10-11の実行前に、 d[v] > δ(s, v) である場合。
d[v] > δ(s, v) = δ(s, u) + w(u, v) = d[u] + w(u, v)
Line10-11の実行後は、 d[v] = d[u] + w(u, v) = δ(s, v)
となる。

249
デフォルトの名無しさん[]   投稿日:2017/01/03 13:52:06  ID:hCDXc7Qp.net(20)
Correctness II:
ダイクストラのアルゴリズムが終了したとき、
すべての v ∈ V に対して、 d[v] = δ(s, v) が成り立つ。

証明:
d[v] は v が S に追加された後は、不変である。
よって、 v が S に追加されたときに、
d[v] = δ(s, v) であることを示せばよい。

背理法で示す。
v が S に追加されたときに、 d[v] ≠ δ(s, v) であるような
v ∈ V が存在すると仮定する。
u をそのような点の中で、最初に S に追加された点とする:
d[u] ≠ δ(s, u)
Correctness Iより、
d[u] > δ(s, u)

250
デフォルトの名無しさん[]   投稿日:2017/01/03 13:52:49  ID:hCDXc7Qp.net(20)
今、 u が S に追加される直前の状況を考えることにする。
u はまだ S に追加されていないから、 u ∈ Q である。
p を s から u への一つの最短路とすると、 w(p) = δ(s, u) である。
s ∈ S, u ∈ Q であるから、 p 上の辺 (x, y) で x ∈ S, y ∈ Q となる
ような辺が存在する。そのような辺の一つを (x, y) とする。
すると、 p は以下のようになる。
p : s → … → x → y → … → u
x ∈ S であるから、 u に関する仮定より、
d[x] = δ(s, x) が成り立つ。また、明らかに、
s → … → x → y は s から y への一つの最短路であるから、
Correctness Lemmaより、 d[y] = δ(s, y) が成り立つ。
明らかに、 δ(s, y) ≦ δ(s, u) であるから、
d[y] ≦ δ(s, y)
また、Line07を見れば分かるように、
d[u] ≦ d[y] である。
よって、

d[u] ≦ δ(s, u) となるが、これは矛盾である。

251
デフォルトの名無しさん[]   投稿日:2017/01/03 13:55:46  ID:hCDXc7Qp.net(20)
Lec 17 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005
https://youtu.be/xhG2DyCX3uA

252
デフォルトの名無しさん[]   投稿日:2017/01/05 09:16:14  ID:4i7P3+nF.net(18)
アルゴリズムイントロダクションって自明なことをわざわざループ不変量を使ったりして、
証明していて、うざすぎますね。

253
デフォルトの名無しさん[]   投稿日:2017/01/05 09:16:52  ID:4i7P3+nF.net(18)
通常の数学の本なら自明で済ませるようなことをわざわざ証明している。
コメント2件

254
デフォルトの名無しさん[sage]   投稿日:2017/01/05 09:57:50  ID:OZq8Y/OW.net(6)
このバカ、以前も全く同じこと言って暴れたな。

255
デフォルトの名無しさん[sage]   投稿日:2017/01/05 10:02:39  ID:OZq8Y/OW.net(6)
http://hissi.org/read.php/tech/20160422/cGVtVmVaYUg.html
http://hissi.org/read.php/tech/20160612/YkttemlBQ3Y.html
こいつだ。

> って当たり前のことをループ不変とかを使って説明しているよね。はっきりいってくどい。
> ループ不変式とかいうのが出てくるけど、当たり前のことを形式的に証明しているだけで、つまらなすぎる。
> 馬鹿の一つ覚えみたいにループ不変式をつかって証明しようとしている。

これぞ「馬鹿の一つ覚え」である。

256
デフォルトの名無しさん[sage]   投稿日:2017/01/05 10:44:28  ID:W/+CAQrH.net(4)
数学とコンピュータ科学の区別がつかない厨房だろう

257
デフォルトの名無しさん[]   投稿日:2017/01/05 11:01:45  ID:4i7P3+nF.net(18)
クヌースの本なんかだと妙なくどさはない。

アルゴリズムイントロダクションはメリハリが全くない。
Trivialなこともそうでないことも平等に扱いすぎている。

要するに本を書くセンスがない。

258
デフォルトの名無しさん[]   投稿日:2017/01/05 11:02:52  ID:4i7P3+nF.net(18)
セジウィックとウエインの本のほうがずっとよい。

259
デフォルトの名無しさん[]   投稿日:2017/01/05 11:07:44  ID:4i7P3+nF.net(18)
日本語の本について言及しておく。
例えば、評判のよい茨木俊秀の本。

こんな薄いスカスカの本をよくも恥ずかしげもなく出版するものだとあきれる。

260
デフォルトの名無しさん[]   投稿日:2017/01/05 11:19:31  ID:4i7P3+nF.net(18)
アルゴリズムイントロダクションの悪口を書いたがいいところもある。

例えば、第29章線形計画法。

線形計画法に対しては、Trivialなこともそうでないことも平等に扱うという方針が
向いているように思う。

ただ、アルゴリズムの本に線形計画法を入れる理由が分からない。

整数論的アルゴリズムの章はあまりにも簡単すぎる。
高木貞治の本でも読んだ方がよい。

261
デフォルトの名無しさん[]   投稿日:2017/01/05 11:28:06  ID:4i7P3+nF.net(18)
結論として、ベストな本はクヌースが予定しているTAOCPの要約本ということになる。

262
デフォルトの名無しさん[sage]   投稿日:2017/01/05 11:29:47  ID:W/+CAQrH.net(4)
結論として4i7P3+nFはNG行き

263
デフォルトの名無しさん[sage]   投稿日:2017/01/05 11:33:33  ID:2uA+A+xC.net(4)
>253
自明ほど危ういものは無いんだが
コメント2件

264
デフォルトの名無しさん[sage]   投稿日:2017/01/05 11:40:35  ID:OZq8Y/OW.net(6)
例によって ID:4i7P3+nF が発狂しててワロタ

265
デフォルトの名無しさん[]   投稿日:2017/01/05 11:44:36  ID:4i7P3+nF.net(18)
>263

では、なぜ、一般に、コンピュータ科学者よりも頭が良いとされる数学者が
自明で済ませることが多いのでしょうか?

もし危ういのなら頭のよい数学者は自明などと書かないはずです。
コメント2件

266
デフォルトの名無しさん[sage]   投稿日:2017/01/05 11:52:58  ID:r7KPx/TL.net(2)
そんな多くねえよちゃんと論文読め

267
デフォルトの名無しさん[sage]   投稿日:2017/01/05 12:06:11  ID:2uA+A+xC.net(4)
自明連発する方が馬鹿なのか

268
デフォルトの名無しさん[sage]   投稿日:2017/01/05 13:09:24  ID:c6xYhHVb.net(4)
>265
馬鹿丸出し

269
デフォルトの名無しさん[sage]   投稿日:2017/01/05 13:18:34  ID:c6xYhHVb.net(4)
>一般に、コンピュータ科学者よりも頭が良いとされる数学者が
根拠は?
>自明で済ませることが多いのでしょうか?
数学のコンテキストの話

そもそも証明の意味もコンピュータ科学と数学では違うだろ

270
デフォルトの名無しさん[sage]   投稿日:2017/01/05 14:56:52  ID:jagWiFjG.net(2)
なんでバカって本質に関係ないところでギャーギャー騒ぐの?
コメント2件

271
デフォルトの名無しさん[sage]   投稿日:2017/01/05 14:58:54  ID:YjTG1plI.net(2)
うむ

272
デフォルトの名無しさん[]   投稿日:2017/01/05 19:46:02  ID:4i7P3+nF.net(18)
アルゴリズムイントロダクションについて、数学が出来る人向けの本だという人がいる。
そして、数学ができない人はセジウィック&ウエインの本を読めという人がいる。

アルゴリズムイントロダクションが数学的な本だとは全く思わない。数学的な内容については
主に結果だけを書いている。

ただネチネチとアルゴリズムの正しさの証明が書かれているだけのこと。

クヌースの本のように、楽しい本ではない。
コメント2件

273
デフォルトの名無しさん[sage]   投稿日:2017/01/05 20:37:39  ID:UiiKd7HR.net(2)

274
デフォルトの名無しさん[sage]   投稿日:2017/01/05 22:15:16  ID:WPj32BYO.net(2)
書評したければ別のところでやれ

275
デフォルトの名無しさん[]   投稿日:2017/01/06 17:19:30  ID:TSHa+AxL.net(16)
再帰の除去についてやり方が詳しく書いてある本を教えてください。
コメント2件

276
デフォルトの名無しさん[]   投稿日:2017/01/06 17:43:03  ID:TSHa+AxL.net(16)
プログラミングコンテストチャレンジブック第2版のp.35
Lake Counting(POJ No.2386)

の解答として、以下のプログラムはあっていますか?

void dfs(i, j, n){
if(i < 0 || i >= N || j < 0 || j >= M){
return;
}
if(field[i][j] != 'W'){
return;
}
if(visit[i][j] == true){
return;
}
visit[i][j] = true;
dfs(i-1, j-1, n+1);
dfs(i-1, j, n+1);
dfs(i-1, j+1, n+1);
dfs(i, j-1, n+1);
dfs(i, j+1, n+1);
dfs(i+1, j-1, n+1);
dfs(i+1, j, n+1);
dfs(i+1, j+1, n+1);

if(n == 0){
count++;
}
return;
}

277
デフォルトの名無しさん[sage]   投稿日:2017/01/06 18:06:18  ID:XtKi9eaG.net(2)

278
デフォルトの名無しさん[]   投稿日:2017/01/06 18:36:23  ID:TSHa+AxL.net(16)
Wrong Answerになっちゃうんだけど。

279
デフォルトの名無しさん[]   投稿日:2017/01/06 18:38:07  ID:TSHa+AxL.net(16)
例題については正しい答えが計算されるんだけど。

280
デフォルトの名無しさん[sage]   投稿日:2017/01/06 18:43:00  ID:LxnclcVs.net(2)
よかったね

281
デフォルトの名無しさん[]   投稿日:2017/01/06 20:15:02  ID:TSHa+AxL.net(16)
>277

ソースレベルで再帰を除去する方法が知りたいんですが。

282
デフォルトの名無しさん[]   投稿日:2017/01/06 20:22:33  ID:TSHa+AxL.net(16)
秋葉らのプログラムでもWrong Answerになっていまします。

入出力の問題のようですね。

283
デフォルトの名無しさん[]   投稿日:2017/01/06 20:27:59  ID:TSHa+AxL.net(16)
入出力の問題ってやっかいですね。
出力がどうなっているかとかPOJでは調べられないんですか?

284
デフォルトの名無しさん[]   投稿日:2017/01/06 20:41:27  ID:TSHa+AxL.net(16)
なんなんだろう?

scanf,printfを使っていたらダメだったのが、cinとcoutにしたらOKになった。

285
デフォルトの名無しさん[]   投稿日:2017/01/08 12:26:37  ID:E98VLsZL.net(26)
F(p, n, r) の計算量を教えてください。

n: 整数
p, r: 整数配列(インデックス0からn-1)

F(p, n, r):
■■if r[n] ≧ 0:
■■■■return r[n]
■■if n == 0:
■■■■q = 0
■■else:
■■■■q = -∞
■■■■for i = 1 to n:
■■■■■■q = max(q, p[i] + F(p, n-i, r))
■■r[n] = q
■■return q
コメント2件

286
デフォルトの名無しさん[sage]   投稿日:2017/01/08 12:31:27  ID:0mVP2hZ6.net(4)

287
デフォルトの名無しさん[sage]   投稿日:2017/01/08 12:32:34  ID:0mVP2hZ6.net(4)

288
デフォルトの名無しさん[]   投稿日:2017/01/08 13:51:15  ID:E98VLsZL.net(26)
>286-287

ありがとうございます。

でも解説されていませんね。

289
デフォルトの名無しさん[]   投稿日:2017/01/08 13:57:19  ID:E98VLsZL.net(26)
どうやって計算量を見積もるんですか?

何を単位にするんですか?
コメント2件

290
デフォルトの名無しさん[]   投稿日:2017/01/08 14:06:13  ID:E98VLsZL.net(26)
T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)

と解けばいいんですかね?
コメント2件

291
デフォルトの名無しさん[]   投稿日:2017/01/08 14:07:36  ID:E98VLsZL.net(26)
T(n) = c1 + c2*n + T(n-1)
T(0) = c3

この漸化式の解を求めればいいんですかね?

292
デフォルトの名無しさん[]   投稿日:2017/01/08 14:12:15  ID:E98VLsZL.net(26)
T(n)
=
[T(n) - T(n-1)] + [T(n-2) - T(n-3)] + … + [T(1) - T(0)] + T(0)
=
[c1 + c2*n] + [c1 + c2*(n-1)] + … + [c1 + c2*1] + c3
=
c1*n + c2*(1/2)*n*(n+1) + c3
=
Θ(n^2)

おお、あってるっぽいですね。

293
デフォルトの名無しさん[]   投稿日:2017/01/08 14:20:56  ID:E98VLsZL.net(26)
>290-292
は我ながら明解な解答ですが、

教科書では、以下のように導出しています。
この導出がよく分からないのですが。

「以前に解かれている部分問題を解くための再帰は直ちに戻るので、Fは
各部分問題をただ1度だけ解く。この手続きはサイズが0,1,....,nの部分問題
を解く。サイズがnの部分問題を解くために、for文がn回繰り返される。したがって、
Fの再帰呼び出し全体における、このfor文の繰り返し回数は等差数列を形成し、
総繰り返し回数はΘ(n^2)となる。」

294
デフォルトの名無しさん[]   投稿日:2017/01/08 14:26:56  ID:E98VLsZL.net(26)
あーあ、分かりました。

T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)

このあたりのことを言っているんですね。

295
デフォルトの名無しさん[sage]   投稿日:2017/01/08 14:27:53  ID:rSxBm0q1.net(2)
馬鹿には無理

296
デフォルトの名無しさん[]   投稿日:2017/01/08 14:28:32  ID:E98VLsZL.net(26)
>289

for文の繰り返し回数=計算量ですね。

297
デフォルトの名無しさん[]   投稿日:2017/01/08 14:29:42  ID:E98VLsZL.net(26)
結局自分ですべて解決してしまいました。

298
デフォルトの名無しさん[sage]   投稿日:2017/01/08 17:12:11  ID:8OGZNgRf.net(2)
よくやった
褒美として自分専用のスレを立てる権利をやろう

299
デフォルトの名無しさん[sage]   投稿日:2017/01/08 18:45:26  ID:KkEYpXLY.net(2)
命名ID:E98VLsZは俺様

300
デフォルトの名無しさん[]   投稿日:2017/01/08 20:55:21  ID:E98VLsZL.net(26)
プログラミングコンテストチャレンジブック

p.45 Best Cow Lineっていう問題の解答のプログラムって無駄がありますよね。

この本を難しいという人がいますが、そんなに難しいですかね?

301
デフォルトの名無しさん[]   投稿日:2017/01/08 22:46:42  ID:E98VLsZL.net(26)
プログラミングコンテストチャレンジブック
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
最強最速アルゴリズマー養成講座

この3冊に共通していることですが、日本語が下手ですよね。

一番ひどいのが

最強最速アルゴリズマー養成講座

ですね。
コメント2件

302
デフォルトの名無しさん[]   投稿日:2017/01/08 22:50:51  ID:E98VLsZL.net(26)
一番面白いのは、

プログラミングコンテストチャレンジブック

だと思いますけど、例えば、貪欲法でなぜうまくいくのかの証明が書いてないですね。

303
デフォルトの名無しさん[sage]   投稿日:2017/01/08 22:51:13  ID:Qw43e7Zm.net(2)
ここはプログラミング問題集書評のスレなの?

304
デフォルトの名無しさん[]   投稿日:2017/01/09 06:08:00  ID:JOAqSyBk.net(2)
>301
うむ
日本語下手なのはもちろん英語も下手みたいだな

305
デフォルトの名無しさん[sage]   投稿日:2017/01/09 06:09:36  ID:cSodeH17.net(2)
頭の使い方が下手というかそもそも頭が不自由なんだろう

306
デフォルトの名無しさん[]   投稿日:2017/01/09 10:59:50  ID:TqLncjlX.net(12)
アルゴリズムイントロダクションの練習問題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]

307
デフォルトの名無しさん[]   投稿日:2017/01/09 11:02:45  ID:TqLncjlX.net(12)
15.1-2

反例

p[1] = 1
p[2] = 5
p[3] = 7

308
デフォルトの名無しさん[]   投稿日:2017/01/09 13:21:16  ID:TqLncjlX.net(12)
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)と書いてあるんですかね?
コメント2件

309
デフォルトの名無しさん[]   投稿日:2017/01/09 13:34:48  ID:TqLncjlX.net(12)
配列を使わないと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)ですよね。

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

http://imgur.com/WUQMG8R.jpg

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

ですね。

310
デフォルトの名無しさん[]   投稿日:2017/01/09 13:37:23  ID:TqLncjlX.net(12)
あ、ひっかけがありましたね。
訂正します:

n > 0 のとき、

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

n = 0 のとき

#V = n + 1
#E = 0

ですね。

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

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

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

と書ける。

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

本当にこんな比較的簡単にみえる結果が1955年という比較的最近になって発見された
のでしょうか?
コメント2件

312
デフォルトの名無しさん[]   投稿日:2017/01/09 15:37:47  ID:4OeNzyzM.net(2)
>308
フィボナッチだろ
√5が出て来る公式
O(1)になるかも試練が

313
デフォルトの名無しさん[sage]   投稿日:2017/01/09 15:46:27  ID:FSSb8O2Z.net(2)
>311
      r ‐、
      | ○ |         r‐‐、
     _,;ト - イ、      ∧l☆│∧  良い子の諸君!
    (⌒`    ⌒ヽ   /,、,,ト.-イ/,、 l  
    |ヽ   ~~⌒γ ⌒ ) r'⌒ `!´ `⌒) よく頭のおかしい数学者気取りのバカが
   │ ヽー―'^ー-'  ( ⌒γ ⌒~~ / 「誰も気付かなかった事を発見したことを発表」とほざくが
   │  〉    |│  |`ー^ー― r' | 大抵それは「先人が思いついたけどあえて発表しなかった」ことだ
   │ /───| |  |/ |  l  ト、 |  王道が何故面白いか理解できない人間に面白い話は
   |  irー-、 ー ,} |    /     i 作れないぞ!
   | /   `X´ ヽ    /   入  |

314
デフォルトの名無しさん[]   投稿日:2017/01/10 20:16:10  ID:Zd0v4023.net(2)
アルゴリズムイントロダクションが難しいという人がいますけど、
この本は馬鹿丁寧に書かれていますよね。

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

「書きすぎ」れば分かりやすくなると思い込んでいますね、著者らは。

315
デフォルトの名無しさん[sage]   投稿日:2017/01/10 20:19:42  ID:kxFYGz06.net(2)
http://hissi.org/read.php/tech/20160614/U2lCYS9zNTM.html

マジ基地だな。壊れたレコードかよ。

316
デフォルトの名無しさん[sage]   投稿日:2017/01/13 21:58:42  ID:wiy2qrIv.net(2)
プログラミング言語のパーサーってどういう仕組みで動いてるんですか?
文字列をトークンの配列に分ける
特定のパターンにマッチするトークンの部分集合をひとまとめにして新しいトークンに置き換える
再帰的に同じ事を繰り返す
こんな感じ?
コメント2件

317
デフォルトの名無しさん[sage]   投稿日:2017/01/13 22:37:46  ID:+ExxsU2F.net(2)

318
デフォルトの名無しさん[sage]   投稿日:2017/01/14 00:10:28  ID:H4kTcvBH.net(2)
>317
これ考えた奴は天才だな

319
デフォルトの名無しさん[sage]   投稿日:2017/01/16 17:57:37  ID:YH2Bx58z.net(2)
Lisperか
BNF

320
デフォルトの名無しさん[sage]   投稿日:2017/01/19 09:40:05  ID:uhfgjGGl.net(2)

321
デフォルトの名無しさん[sage]   投稿日:2017/05/14 13:16:07
類似スレ検索とかのアルゴリズムって何がいいのかな?
編集距離とか数字部分のマスキングくらいしか浮かばない
形態素解析して要素の一致率とかもあるみたいだけど、スレタイみたいな短い文字じゃ弱そう

322
デフォルトの名無しさん[sage]   投稿日:2017/05/14 13:20:48
むしろ短くて重要な単語が多いスレタイこそ一致率うまく働きそうか
毎回評価してたら検索速度悪そうだけど

323
デフォルトの名無しさん[sage]   投稿日:2017/05/14 13:56:17
Baka ha sinanakya
Naoranai
Fucky ou

324
デフォルトの名無しさん[sageteoff]   投稿日:2016/06/19 14:47:29  ID:5KvSKdL/.net(4)
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

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

                  京都大学霊長類研究所

データ構造,アルゴリズム,デザインパターン総合スレ 2

【関連スレ】
3Dアルゴリズム全般
<集大成>アルゴリズム大辞典
アルゴリズム総合スレ in ム板

アルゴリズムとデータ構造 - Kaneko Lab.
http://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
http://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
http://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
http://vipprog.net/wiki/algo_and_data_const.html
コメント3件

325
デフォルトの名無しさん[]   投稿日:2016/06/19 14:52:46  ID:5KvSKdL/.net(4)
http://hissi.org/read.php/tech/20160619/YW80V0xnZlg.html
へんなのが居着いたな

981 :デフォルトの名無しさん[sage]:2016/06/19(日) 12:16:06.94 ID:ao4WLgfX
>980
いつも思うんだけれども,この碁の勝負,棋譜は公開されているの?

985 :デフォルトの名無しさん[sage]:2016/06/19(日) 12:47:45.21 ID:ao4WLgfX
>982
どこに貼ってあるかな?たぶん公開されてないんじゃないかな

986 :デフォルトの名無しさん[sage]:2016/06/19(日) 12:59:15.60 ID:ao4WLgfX
http://blogs.yahoo.co.jp/ten_nan_91/35774553.html

988 :デフォルトの名無しさん[sage]:2016/06/19(日) 13:02:20.35 ID:ao4WLgfX
ありがとう

1000:デフォルトの名無しさん[sage]:2016/06/19(日) 14:49:22.87 ID:ao4WLgfX
0

326
デフォルトの名無しさん[sage]   投稿日:2016/06/19 15:04:05  ID:IRfn+3ke.net(2)
>1 乙

327
デフォルトの名無しさん[sage]   投稿日:2016/06/19 16:13:42  ID:gP7jNw8f.net(2)

328
デフォルトの名無しさん[sage]   投稿日:2016/06/19 17:17:34  ID:ao4WLgfX.net(2)
ruby って変な人が多いんだね,俺も今 ruby をマスターしようと必死ではあるが

329
デフォルトの名無しさん[sage]   投稿日:2016/06/19 17:37:31  ID:X+E3gNs8.net(2)
>2
盛大な自演だったってこと?

330
デフォルトの名無しさん[]   投稿日:2016/06/19 19:39:00  ID:iKM7Z0CI.net(6)
Haskellって勉強する意味ある?
実用性はないよね?

331
デフォルトの名無しさん[sage]   投稿日:2016/06/19 19:46:20  ID:0JS60cqV.net(2)
雇われプログラマには不要

332
デフォルトの名無しさん[]   投稿日:2016/06/19 20:49:00  ID:iKM7Z0CI.net(6)
なぜ、HaskellやSchemeをありがたがる人がいるの?
どう考えてもC#とかのほうが生産性が高いのに。
単なるかっこつけ?

333
デフォルトの名無しさん[]   投稿日:2016/06/19 20:49:49  ID:iKM7Z0CI.net(6)
MITのコンピュータの入門書もSchemeを使っていたりする。
コメント1件

334
デフォルトの名無しさん[sage]   投稿日:2016/06/19 20:59:07  ID:Axw7zBsF.net(2)
言語としてのlisp最強論は理解できるけどね。
実用的ではないのは言語自体の問題ではなくてシェアとかサポートする企業の存在とかコミュニティの問題。

335
デフォルトの名無しさん[sage]   投稿日:2016/06/19 23:46:31  ID:XG1Xog94.net(2)
haskellやschemeは勉強したくない奴には不要
雇われには言語選択権はないので、かりにそれらがよいものであったとしたとしても、フラストレーションたまるだけだろ

一言でいうなら自分で一から十まで計算を構築するための言語だな
ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要

336
デフォルトの名無しさん[]   投稿日:2016/06/20 00:15:53  ID:VsbhBHIt.net(2)
>12
マジかよ

337
デフォルトの名無しさん[sage]   投稿日:2016/06/20 00:57:04  ID:rbqmVuz6.net(2)
>12
> ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要

ライブラリを駆使するのが今のプログラマに求められている技術だからな。

MITがSICPを教えなくなった理由
https://ezoeryou.github.io/blog/article/2016-05-05-sicp.html
> 今日では、状況が変わっている。今のエンジニアは、自分が完全に理解していない複雑なハードウェアの
> ためのコードを日常的に書いている(そして、大抵の場合、企業秘密により完全に理解するのは不可能である)。
> ソフトウェアでも状況は同じだ。プログラミング環境は、多大な機能を提供する巨大なライブラリ群の集合として存在している。
> Sussmanの今日の生徒は、その時間の大半を、ライブラリのマニュアルを読み、どのように組み合わせれば目的が
> 達成できるのかを把握することに費やしている。Sussman曰く、今日のプログラミングは、「より科学に近い。
> ライブラリを持ち寄って、つっつき回すのだ。プログラムを書くには、突っつき回して、どのように動作するかを観察する。
> そして、「目的を達成するために改造できるか」と考えるのだ」。SICPの「合成による解析」という物の見方である、
> 小さな、単純な部品を組み合わせて大きなシステムを作るということは、もはや今日の状況にそぐわなくなった。
> 今や、我々のプログラミングはつっつき回すことで行われている。
>
> なぜPythonを選んだかということについて、Sussmanは、"late binding"に決定したと冗談を飛ばした。
> Pythonには大量のライブラリがあり、教育者の様々な実習に使いやすい(たとえば、ロボットを制御するソフトウェアを書くなど)

338
デフォルトの名無しさん[]   投稿日:2016/06/20 06:52:18  ID:1vrQKLsp.net(12)
HaskellやSchemeの利点は?
少なくとも、分かりにくいよね。

339
デフォルトの名無しさん[sage]   投稿日:2016/06/20 08:05:44  ID:8yK3ULXk.net(2)
オブジェクト指向程ではないけどな
コメント1件

340
デフォルトの名無しさん[sage]   投稿日:2016/06/20 12:30:23  ID:iz9OSKHh.net(4)
エンジニアの選定時の足切りにちょうどいいよ

341
デフォルトの名無しさん[sage]   投稿日:2016/06/20 18:11:51  ID:Z8Or5TTF.net(2)
その基準で剪定できるのはかなり恵まれてる気が
コメント1件

342
デフォルトの名無しさん[sage]   投稿日:2016/06/20 18:23:24  ID:78XmmaUt.net(2)
>14
>今日のプログラミングは、「より科学に近い。

ここは変だな
「より工学に近い。」
というなら判るが
コメント1件

343
デフォルトの名無しさん[]   投稿日:2016/06/20 18:31:26  ID:1vrQKLsp.net(12)
SICPをプログラミング初学者に教えるというのは確かに異様だよね。

やっとまともになったというだけの話。

344
デフォルトの名無しさん[]   投稿日:2016/06/20 18:35:05  ID:1vrQKLsp.net(12)
コンピュータサイエンスの中でアルゴリズムとデータ構造ってどれくらい重要な科目なの?

345
デフォルトの名無しさん[]   投稿日:2016/06/20 18:50:31  ID:FhfmjeRD.net(2)
アルゴリズム + データ構造 = プログラム。
ということは。
プログラムの占める割合と等価なのでは。

346
デフォルトの名無しさん[]   投稿日:2016/06/20 18:52:50  ID:1vrQKLsp.net(12)
なんか計算の理論とかのほうが上みたいな感じじゃない?

347
デフォルトの名無しさん[]   投稿日:2016/06/20 18:53:47  ID:1vrQKLsp.net(12)
コンピュータサイエンスで最も重要な科目は、コンパイラとかOS?

348
デフォルトの名無しさん[sage]   投稿日:2016/06/20 18:53:55  ID:K++azvDQ.net(2)
自演乙
コメント2件

349
デフォルトの名無しさん[sage]   投稿日:2016/06/20 19:14:10  ID:/YC1nkci.net(2)
>18
この道30年の修業でようやく一人前

350
デフォルトの名無しさん[sage]   投稿日:2016/06/20 20:44:30  ID:EiR/M7I9.net(2)
寿司職人乙

351
デフォルトの名無しさん[sage]   投稿日:2016/06/20 20:58:16  ID:amTC+NJd.net(2)
schemeやらないとアルゴリズムとデータ構造を組み立てるってことがどういうことなのか、コードでわからないだろうな

352
デフォルトの名無しさん[]   投稿日:2016/06/20 21:06:41  ID:taQ4Dh1l.net(2)
>28
javaでよくない?
コメント2件

353
デフォルトの名無しさん[sage]   投稿日:2016/06/20 21:24:25  ID:iSiyYjqf.net(2)
javaでconsを表現するときにどうすればいいか知ってますか?

354
デフォルトの名無しさん[]   投稿日:2016/06/20 21:29:28  ID:1vrQKLsp.net(12)
>28

アルゴリズムとデータ構造の本に疑似コードが載っていることがあるけど、
Scheme風に書かれていることなど決してない。

355
デフォルトの名無しさん[sage]   投稿日:2016/06/20 21:47:01  ID:eW3OX+fW.net(4)
>27
植木職人

356
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:10:02  ID:iz9OSKHh.net(4)
>18
未経験でも理解出来るならとりあえず地雷の可能性は下がる

357
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:22:55  ID:m9phkWTx.net(2)
恵まれてない会社だと全員切る羽目になるって話だろw

358
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:43:48  ID:zvz85rzc.net(4)
31
そのSICPはschemeでかかれているわけで
昨今のライブラリ重視の観点からいえば、javaがいいっていうのはとおるけど、アルゴリズムかくのにjavaがいいってのは、センスないというか、お手入れ大好きなんだろうな

359
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:49:30  ID:eW3OX+fW.net(4)
引用できないやつに言われると

360
デフォルトの名無しさん[sage]   投稿日:2016/06/20 22:50:33  ID:zvz85rzc.net(4)
スマホで>>うつのめんどいんだよ

361
デフォルトの名無しさん[sage]   投稿日:2016/06/22 04:43:48  ID:W4spe1mc.net(2)
日立、新型半導体コンピュータの実用化に向けた前処理アルゴリズムを開発
http://news.mynavi.jp/news/2016/06/21/172/

新型半導体コンピュータの実用化に向けて、
要素間の複雑なつながりを規則的な構造に自動変換する前処理アルゴリズムを開発
http://www.hitachi.co.jp/New/cnews/month/2016/06/0621a.html

関連記事
日立、量子コンピュータに匹敵する性能の室温動作の新型コンピュータを試作
http://news.mynavi.jp/news/2015/02/23/121/

362
デフォルトの名無しさん[]   投稿日:2016/06/22 07:14:40  ID:rmORGvIR.net(6)
日本人の書いたアルゴリズムとデータ構造の本でまともなのって1冊もないの?

363
デフォルトの名無しさん[sage]   投稿日:2016/06/22 07:53:05  ID:HSGRYDR8.net(2)
>39
まともとは?

364
デフォルトの名無しさん[]   投稿日:2016/06/22 07:59:50  ID:rmORGvIR.net(6)
日本人の書いた本は薄っぺらくて説明も十分ではなく厳密でもなく網羅性もない本ばかりに思う。

365
デフォルトの名無しさん[]   投稿日:2016/06/22 08:00:26  ID:rmORGvIR.net(6)
杉原厚吉の本は特にひどいと思った。

366
デフォルトの名無しさん[sage]   投稿日:2016/06/22 11:07:15  ID:DmPvlaR4.net(2)
>39
そのものズバリでアルゴリズムとデータ構造という本が岩波から出てる

367
デフォルトの名無しさん[sage]   投稿日:2016/06/22 12:53:15  ID:YevSrNYa.net(2)
まともな本とは?
argolythm introduction?
knuth本?
どっちも使い物にならないが

368
デフォルトの名無しさん[sage]   投稿日:2016/06/22 13:50:41  ID:WHe3DbmR.net(2)
>44
1単語に3箇所もミス入れるなよ

369
デフォルトの名無しさん[sage]   投稿日:2016/06/22 14:13:53  ID:sEqYA8cS.net(2)
根幹のタームの綴りも知らん半可通に何を教われというのか

370
デフォルトの名無しさん[sage]   投稿日:2016/06/22 14:17:48  ID:yBOVYSwe.net(2)
3ヶ所もあると誤り訂正も利かないんじゃまいか

371
デフォルトの名無しさん[sage]   投稿日:2016/06/22 14:22:16  ID:EwWgL4+X.net(2)
バースト発生させんな
コメント1件

372
デフォルトの名無しさん[sage]   投稿日:2016/06/22 15:16:40  ID:2z7j8yec.net(2)
????????????

373
デフォルトの名無しさん[sage]   投稿日:2016/06/22 21:44:16  ID:MWgF3eo3.net(2)
>44
そんな頭じゃ使いものにならんのも頷けるわ
コメント1件

374
デフォルトの名無しさん[sage]   投稿日:2016/06/22 22:23:26  ID:Z2xvvdgM.net(2)
こんな揚げ足とりの老害から何を学べと?

375
デフォルトの名無しさん[sage]   投稿日:2016/06/22 22:52:24  ID:X6XCfxlz.net(2)
馬鹿の自己紹介されても困る

376
デフォルトの名無しさん[sage]   投稿日:2016/06/24 11:47:43  ID:hSLmnyaY.net(2)
>19
は?変なのはお前だ
プログラミングは最初から工学的だろ何言ってんだ?

そもそもお前は工学と科学を理解してないから可笑しなことを言うんだ

377
デフォルトの名無しさん[sage]   投稿日:2016/07/15 12:10:18  ID:P21uCIN+.net(2)
何ヶ月か前に近代科学社に電話でセジウィックアルゴリズムの第四版の翻訳の予定はありますか、と訊いてみたが無いって返事だったんだよな
書いて欲しいんだがな

378
デフォルトの名無しさん[sage]   投稿日:2016/07/16 08:00:53  ID:Akpk7DL9.net(2)
アルゴリズムさえ知ってりゃ動くプログラムは書けるから他は優先度低いと考えてた結果
データ構造すら分からない化石プログラマになってしまった

今必死にデータ構造とデザインパターン勉強中だけど、わかってくると楽しいね

アルゴリズムみたいにオーダー詰める楽しみはないけど…

379
デフォルトの名無しさん[sage]   投稿日:2016/07/18 09:37:52  ID:YPoLSDg9.net(2)
両方大事だろ。
データ構造が整理されてないとアルゴリズムも煩雑になるし。

380
デフォルトの名無しさん[]   投稿日:2016/07/21 23:06:49  ID:TpMXx+Na.net(2)
vEB木の「僕の考えた最強のデータ構造」感が大好きなんだが誰か共感してくれる人いる?

381
デフォルトの名無しさん[sage]   投稿日:2016/07/22 07:32:19  ID:ot11jjQx.net(2)
データ構造の基本は、以下の2つと、他にはハッシュがある

A → B → C → D
のように、メモリ上の位置がバラバラなオブジェクトを、リンクでつないでいくものと、
(シーケンシャルアクセス)

ABCD
のように、連続したメモリ位置に、オブジェクトやオブジェクトの参照が確保されていて、
単純な計算式で、各オブジェクトにアクセスできるもの(ランダムアクセス)

シーケンシャルは、リンクをたどるから、アクセスには時間がかかるけど、
要素の追加・削除では、リンクを付け替えるだけで、要素をずらさないから速い

382
デフォルトの名無しさん[sage]   投稿日:2016/07/26 06:56:53  ID:HN1KCMsQ.net(2)
letの時代がもうすぐそこまで来ているよね

383
デフォルトの名無しさん[sage]   投稿日:2016/07/26 14:27:18  ID:z5g/0KTZ.net(2)
let
-------
 λ

384
スモモンガー[sage]   投稿日:2016/09/23 22:08:49  ID:oKXONAGb.net(2)
どうも、お久しぶりです。スモモンガーです。(誰って感じだと思いますがそれで結構です)
以前紹介したアルゴリズムですが、結局全然応用分野は見つかっておりません。
前回は画像処理分野を中心に解説しましたが今回はより簡単に実装ができる
探索分野に絞って動画を作ってみました。つたない動画で大変申し訳ございませんが
見てみていただけたら幸いです。特許などは取得しておりませんのでどうかご自由に
お使いください。長文失礼いたします。痛いのは承知なのですが応用分野を必死に
探しているのでどうかご協力よろしくお願いします。

https://youtu.be/5m3kPHO2w98

以上、どうぞよろしくお願いします

385
デフォルトの名無しさん[sage]   投稿日:2016/09/23 22:16:41  ID:xWgfj234.net(2)
誰だ

386
デフォルトの名無しさん[sage]   投稿日:2016/09/23 22:42:52  ID:fJ2M8QeM.net(2)
帰れ

387
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:14:59  ID:osPXZH57.net(2)
>61
最初の数分見ましたが..

1) 何の探索なの?最初は「探索」と聞いて「グラフかな?」とか思ったけど配列みたいだし、最初に想定される入力を明確にした方がいいですね

2) プレゼンが文章を読み上げてるだけでイメージが湧きにくい
1,4,10,20,25 …
の例ではイラストを用いた方がわかりやすいと思います

3) Kangaroo Method とはのスライドでデータがソートされていて、キーの差が (中略) バイナリサーチと同等の効率を .. とありますが、例では入力が完全にソートされているようです。これなら最初からバイナリサーチを使います

また、11m10s くらいのところで「Sinカーブは整ってる」とありますが、「整っている」の定義がよくわかりません。その後の例も見ましたが、どのくらいまで途中に想定されていないデータが混じっていても許容範囲なのかが不明です

4) 先に長所短所のスライドを持ってきて、擬似コードとオーダーも明記し、「一部ソートされてなくても O(logn) で探索できます」みたいなのを書いて、見ている人を「それならもうちょっと続きを見てみようか」みたいな気にさせられればもっといいですね

以上、感想でした

388
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:32:41  ID:n5/uj8Su.net(6)
64さん。ありがとうございます。私はこういうスライドを作る機会があまりないのでこんな形になってしまいました。
実は整っているという抽象的な単語を使っていますが、実は定量的にこれを測る方法はまだ思いついていません。
そのほかのご指摘はその通りだと思います。
貴重なご意見ありがとうございます

389
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:49:16  ID:B225F1SQ.net(2)
動画見るの面倒だから3行で説明して

390
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:53:53  ID:trsNBxRI.net(2)



391
デフォルトの名無しさん[sage]   投稿日:2016/09/24 09:55:26  ID:n5/uj8Su.net(6)
>66
まず目的のキーと現在探索中のキーの差をとる。
それを隣接するキーの最大値で割る。
その値だけ進む。

まあ、原理は単純なアルゴリズムです

392
デフォルトの名無しさん[sage]   投稿日:2016/09/24 10:46:59  ID:iZTaxfZT.net(2)
>隣接するキーの最大値

これをあらかじめ求めておかなきゃならんってのが一番のネックだな。
一般のデータに対する探索だと、バイナリサーチと比較したメリットと言っていたものの大半が消し飛んでしまう。

393
デフォルトの名無しさん[sage]   投稿日:2016/09/24 10:49:01  ID:9ZsTQHH6.net(2)
>61
印象としては
1. 要素間の差の最大値を求めるのに線形時間
2. 各要素の値の差が一定でないと性能を発揮しない(最大値を求めるのも含め)
3. 探索の最悪時間が線形時間、恐らく平均も線形時間
4. ソートされていなくても探索可能な条件が不明瞭
5. データの内容に探索コストが大きく左右される

例えば
1 2 4 9 15 24 100 120 1002 1225
とあった時、差の最大値は
1002-120=882
1002を探索すると
1002-1=1001, 1001/882=1
1002-2=1000, 1000/882=1
1002-4=998, 998/882=1
1002-9=993, 993/882=1
...
と線形時間になる(やり方あってるよね?)
演算している分、比較だけの線形探索より処理速度が遅くなる
コメント1件

394
デフォルトの名無しさん[sage]   投稿日:2016/09/24 11:09:23  ID:n5/uj8Su.net(6)
>69
>70
確かにキーの最大値を求めるのは線形時間かかります。なのであらかじめ、隣接するキーの最大値が分かっているデータに使用可能です。
探索の最悪時間は線形時間ですが、平均時間はlogのオーダーになるのではないでしょうか。私が不勉強なもので理論的には、示めせませんが多分logのオーダーになると思います。
ソートしなくても探索できるのは差の絶対値を取るからです。動画に入れるのを忘れました。すいません。
計算についてはそれであっています。わざわざご指摘ありがとうございます
コメント2件

395
デフォルトの名無しさん[sage]   投稿日:2016/09/25 01:17:16  ID:MeFnEkA4.net(2)
>71
上でも指摘されているが整っているの定義が不明
二分探査の場合は、存在しないこともlog n で確認可能だが、この手法は整っているの定義次第では存在しない者の確認が非常に時間かかる(ソートされている場合は存在するものと同等だが、そうすると二分探索よりも利点が少なくなる)
平均計算量を求めるのはちと難しそうだけど、格納される値の値域に依存するかな
たぶん、log n 程良くはないと思う
コメント1件

396
デフォルトの名無しさん[sage]   投稿日:2016/09/25 09:29:52  ID:byM8xGto.net(2)
>72
ご指摘ありがとうございます。確かに整っているの定義ができていないのが一番の難点ですよね。いつか勉強して考えたいと思います

397
デフォルトの名無しさん[]   投稿日:2016/09/25 12:26:29  ID:3wiQalb8.net(2)
>67
ごめん
みたけど
だめだこりゃ

398
デフォルトの名無しさん[sage]   投稿日:2016/09/25 12:52:11  ID:NTqjAG/u.net(2)
>71
各要素間の差が一定であればO(1)、当たり前だけど、これは計算で求まる
各要素間の差の分布数が要素数に近づき、尚且つその落差が激しい場合
著しく線形時間になる

で、探索したい数値と差の最大値の商が1だった場合
その探索したい数値がある位置以下の数値探索はO(n)になる
データ列の後半に行くほど1回の演算で要素をステップする数が増えるけど
その移動は微々たるもの
データ列の内容に左右されることを差っ引いても、O(log n)からは程遠いと思う
詳しい計算は出来ないが、これを線形時間としても無理はないと思う

参考として
0 1 3 6 10 15 21 28 36 45
このデータ列では、15以下の探索はO(n)、
21は5回、28は4回、36は4回、45は3回の演算

結論として
このアルゴリズムの最大の欠点は差の最大値が必要な事を含めて
データ列の内容に左右されてしまうことだな
この手のアルゴリズムはデータの外側にあるべきだな

399
デフォルトの名無しさん[sage]   投稿日:2016/09/25 14:20:01  ID:8PebKpFu.net(2)

400
デフォルトの名無しさん[sage]   投稿日:2016/09/26 13:42:01  ID:ymOrEJcI.net(2)
>61
すもモンがnewton法をガチで知らないのであればnewton法をまず勉強するべき
カンガルーの敵はバイナリではなくnewtonだ
コメント1件

401
スモモンガー[sage]   投稿日:2016/09/26 20:32:40  ID:7l1kSKga.net(4)
確かにデータ間の差に一様離散分布を使ったのは公平ではなかったです。
なので、データを完全にランダムにして調べてみました。
データはCのrand()%1000000で10000個生成しソートして、
探索の時配列のうちランダムな値を探すキーとし間を線形探索、カンガルー法
バイナリサーチで100回比べてみました。
その結果線形探索では平均比較回数約4963回最大比較回数は9972回でした
カンガルー法は平均比較回数約70回 最大比較回数は111回でした。
バイナリーサーチはやはり一番はやく、平均比較回数約12回、最大比較回数は14回でした
皆さんがご指摘の通りやはりバイナリーサーチが一番はやいようです。
ただ、例えばKMP法が逆行がないから使われているようにカンガルー法も逆行がないので
使うことはできないでしょうか?もし、とんちんかんなこと言ってたらすいません。

402
デフォルトの名無しさん[sage]   投稿日:2016/09/26 20:37:55  ID:7l1kSKga.net(4)
>74
www確かにそうかもしれませんね。
>77
一応私はニュートン法については知っています。Newton法は求める関数の微分した値を
しっていなければならないとおもうのですが、現実の探索だと関数が微分できないことも
多いかと思います。ちょっと、私が使った例が悪くてsinカーブや円を使ったのがよく
なかったのかもしれません。整っていてソートされていないデータとして扱いやすかったので
sin関数を使ったのであってとくにデータが微分可能である必要はありません。円と
Y切片の交点も中学生でも二次方程式ときゃいいのでもっと簡単にできますが、本来は
多角形とさまざまな図形の交点を探るアルゴリズムです。円を使ったのは例をわかりやすく
したかったからです。

403
デフォルトの名無しさん[]   投稿日:2016/10/16 18:51:48  ID:LqkHCFhg.net(2)
状態遷移ってどういうステータス持てばいいの?

A と B のステータスがあって、お互いが切り替わるのに n秒 かかる
切り替わりに失敗したら切り替えをリトライする
AはBになろうとし、BはAになろうとする

というとき、A と B のほかに AからBになるのを待ってる状態と
BからAになるを待ってる状態の 2つがさらに状態として必要?
過渡状態も状態?

404
デフォルトの名無しさん[sage]   投稿日:2016/10/17 07:56:46  ID:TukeUWYl.net(2)
>80
システムの設計次第。
切り替え中、待ち中が状態として存在するのならプログラムでも状態にすればいい

405
デフォルトの名無しさん[sage]   投稿日:2016/10/17 15:43:18  ID:srAFoI0L.net(2)
>81
そりゃそうだけど
状態がn個あると過渡状態がたくさんになるのは
辛い

406
デフォルトの名無しさん[sage]   投稿日:2016/10/17 17:53:14  ID:75S5w4gh.net(2)
現在の状態と次の状態のペアにすれば?

407
デフォルトの名無しさん[sage]   投稿日:2016/10/17 21:23:44  ID:sc7L52q+.net(2)
辛かろうが状態が存在するのならしょうがあるまい。
あるいは遷移をアトミックにして遷移中状態そのものを無くすか、遷移中の動作を共通化
できるなら遷移先をパラメータ化して「*への遷移中」という1状態にしてしまうとか。

408
デフォルトの名無しさん[sage]   投稿日:2016/10/17 23:34:18  ID:WkWdUImM.net(2)
>82には無理ということで

409
デフォルトの名無しさん[sage]   投稿日:2016/11/05 20:41:10  ID:PXYcOtjJ.net(2)
ポリモーフィックなクラスの相互作用において特定の型の組み合わせの場合のみ処理を特殊化したい場合はどうすればいいのだろう?

x = xFactory.create(...);
y = yFactory.create(...);

if(x.typeCode() == X.Foo && y.typeCode() == Y.Hoge)
executeSpecial((Foo) x, (Hoge) y);
else if (...)
...
else
executeNormal(x, y);

410
デフォルトの名無しさん[sage]   投稿日:2016/12/12 23:13:40  ID:IcWOSn01.net(2)
デザインパターンを使って実装すると、年長プログラマーから、またこんなことしやがって的な拒否反応が帰ってくるんだがどうすれば

411
デフォルトの名無しさん[sage]   投稿日:2016/12/12 23:42:41  ID:bt79hYqC.net(2)
排除する他道は無い。

412
デフォルトの名無しさん[sage]   投稿日:2016/12/12 23:50:03  ID:hGpJarHd.net(2)
転職しろ

413
デフォルトの名無しさん[sage]   投稿日:2016/12/13 03:19:26  ID:neuXXcOh.net(2)
若者で組合(または派閥)を創る

414
デフォルトの名無しさん[sage]   投稿日:2016/12/13 08:14:05  ID:5xcG7lRc.net(2)
>87 がどんなコードを書いたかも分からんのに

415
デフォルトの名無しさん[sage]   投稿日:2016/12/13 18:53:42  ID:MUcELcjh.net(2)
下手くそがデザインパターンとか使うと逆にこんがらがるからなぁ
老害とどっこいどっこいだろ

416
デフォルトの名無しさん[]   投稿日:2016/12/13 21:32:18  ID:lYWHr0pJ.net(2)
マルチスレッドで、なんの考えもなくオブザーバー使いまくられて、データ破壊しまくられた時には、本気で殺意を抱いたよ

417
デフォルトの名無しさん[]   投稿日:2016/12/16 15:12:11  ID:kO0vFktz.net(2)
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』

の優先度付きキューについてのプログラムについて質問です。

p.241の heapIncreaseKey(A, i, key) という関数内で、

「if key < A[i] エラー:新しいキーは現在のキーより小さい」

というのがあります。

これがなぜ必要なのかが分かりません。

insert(key) を見れば分かるように、この本の使われ方では、
key < A[i] になることは決してありません。

よろしくお願いします。

418
デフォルトの名無しさん[sage]   投稿日:2016/12/16 15:34:53  ID:n8JQ6xp/.net(2)
assertionじゃね

419
デフォルトの名無しさん[]   投稿日:2016/12/17 16:05:18  ID:lvQHWty7.net(2)
完成形をいきなり見てると不思議に思うよね。
でも実際には作成中のバグを考慮して、最初にチェックを入れておくもんなんだよね。
まあ、一言で言えばassertなんだけど。

ただ、作業やデバッグ用には必須であっても、その本の例示として必要か?と言われれば、確かにいらない気がする。

420
デフォルトの名無しさん[]   投稿日:2016/12/17 16:09:26  ID:GDWdcO6h.net(14)
>95-96

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の参考文献に
挙げられている『アルゴリズムイントロダクション』を見てみたら、全く同じプログラム
が載っていました。

完全にパクっていますね。

>96
デバッグ用にどうして必要なのかが分かりません。

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』はお持ちでしょうか?
もし、お持ちでないようでしたら該当箇所の画像をアップロードします。

421
デフォルトの名無しさん[]   投稿日:2016/12/17 16:23:27  ID:GDWdcO6h.net(14)
>94

念のため、該当箇所の画像をアップロードさせていただきます。
読めば読むほど意味不明です。

http://imgur.com/zKVWzAJ.jpg
http://imgur.com/owa8NkX.jpg
http://imgur.com/NmCczss.jpg

422
デフォルトの名無しさん[sage]   投稿日:2016/12/17 16:42:25  ID:a9hyyPvt.net(6)
>97
参考文献ならパクってるとは言わない

423
デフォルトの名無しさん[sage]   投稿日:2016/12/17 16:43:27  ID:a9hyyPvt.net(6)
>98
こういうのが本当のパクり
訴えられたら負ける

424
デフォルトの名無しさん[sage]   投稿日:2016/12/17 18:12:28  ID:rDdwnYMe.net(4)
>97
他の本も読んでみるとわかると思うけど、プライオリティキューを二分木ヒープで実装するのは定番で、どの本でも大体同じことが書いてある

425
デフォルトの名無しさん[]   投稿日:2016/12/17 19:29:55  ID:GDWdcO6h.net(14)
>98

「if key < A[i] エラー:新しいキーは現在のキーより小さい」

というのが、デバッグ用であるとは思えないのですが、これは一体何なんでしょうか?

heapIncreaseKey(A, i, key) を何か別の用途に使う場合があって、そのときに必要に
なるのならば納得しますが。

426
デフォルトの名無しさん[]   投稿日:2016/12/17 19:31:29  ID:GDWdcO6h.net(14)
>101

「if key < A[i] エラー:新しいキーは現在のキーより小さい」

という意味不明のコードも『アルゴリズムイントロダクション』のプログラムには
書いてあります。

こんな余計なコードは普通は入れないと思います。

完全にパクりだと思います。

427
デフォルトの名無しさん[]   投稿日:2016/12/17 19:35:00  ID:a9hyyPvt.net(6)
>103
参考文献に書いてあるんだからパクリも糞も無い罠
参考文献に書き漏れたら小保方さんみたいに突っ込まれるが

428
デフォルトの名無しさん[]   投稿日:2016/12/17 19:35:29  ID:GDWdcO6h.net(14)
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の
他のプログラムもおそらくすべて『アルゴリズムイントロダクション』の
プログラムをそのまま使っています。

恥を知れと言いたいです。

429
デフォルトの名無しさん[]   投稿日:2016/12/17 19:36:34  ID:GDWdcO6h.net(14)
参考文献に文献を挙げれば何でも許されるということはないと思いますが。

430
デフォルトの名無しさん[]   投稿日:2016/12/17 19:39:42  ID:GDWdcO6h.net(14)
『アルゴリズムイントロダクション』のほうをよく読んでいませんが、

「if key < A[i] エラー:新しいキーは現在のキーより小さい」

というのも『アルゴリズムイントロダクション』のほうでは意味があるのかもしれません。

それをそのまま何も考えずにコピペしたために、意味不明なことになっているのかも
しれません。

>98

を見て、誰か納得のいく説明ができるでしょうか?

意味不明としか言えないかと思います。

431
デフォルトの名無しさん[sage]   投稿日:2016/12/17 19:42:21  ID:C/wQAZQ3.net(2)
『アルゴリズムイントロダクション』のほうをよく読んでいませんが、
『アルゴリズムイントロダクション』のほうもまたどっか別の本からのパクリの悪寒。

432
デフォルトの名無しさん[sage]   投稿日:2016/12/17 19:47:48  ID:YhK78PBA.net(2)
"error: heap underflow" でググるといっぱい出てくる

433
デフォルトの名無しさん[sage]   投稿日:2016/12/17 19:57:50  ID:rDdwnYMe.net(4)
ID:GDWdcO6h は何をそんなに怒ってるの?
問題が解けなくてイライラしてるだけ?

どんな本も参考文献があり、どんなアルゴリズム、データ構造も元をたどれば最初に「ヒープで実装すればうまく行くぞ!」と発見した人の論文があるはず

新しい本を書くときは参考文献よりもわかりやすくなるように、説明やイラスト、擬似コードを変えたり、あるいは同じものを流用することもあるだろう

434
デフォルトの名無しさん[sage]   投稿日:2016/12/17 20:55:04  ID:jmPH7DRp.net(2)
disるのがはやってるらしい

435
デフォルトの名無しさん[sage]   投稿日:2016/12/18 00:45:20  ID:aCKcGLhu.net(8)
プログラミングコンテスト攻略のための、
アルゴリズムとデータ構造、渡部有隆(わたのべ ゆたか)、2015
Ozy(協力), 秋葉 拓哉(協力)

Aizu Online Judge(AOJ、会津大学)

プログラミング・コンテスト・チャレンジブック、第2版、2012
秋葉 拓哉, 岩田 陽一, 北川 宜稔

元々は、3人の東大大学院生が作った、チャレンジブックが大ヒットした。
今までは、こういうコンテストの問題を研究した本が無かった

一方、すでに海外では、TopCoder, Google Code Jam などが、
プログラマーの主戦場となっていて、日本では、AOJ が後を追っている状態

渡部有隆の本は、チャレンジブックの後に出した。
協力に、秋葉 拓哉の名前もある

プログラマ脳を鍛える数学パズル
シンプルで高速なコードが書けるようになる70問、増井 敏克、2015

一方、増井は、Rubyで解く、このパズル本で、
「ITエンジニアに読んでほしい!技術書・ビジネス書 大賞(ITエンジニア本大賞)」を受賞している


436
デフォルトの名無しさん[]   投稿日:2016/12/18 00:49:54  ID:VFzWAIXP.net(4)
めんどくさ

437
デフォルトの名無しさん[sage]   投稿日:2016/12/18 01:14:58  ID:aCKcGLhu.net(8)
漏れも、JavaScriptで、2分ヒープ(BinaryHeap)を実装したので、参照して
http://jsdo.it/michihito/bGH5

2分ヒープは、優先度つきキュー (順位キュー、priority queue)や、
ダイクストラ法 (Dijkstra's Algorithm)で使う

配列の[0]は使わない。[1]から始めると計算が楽
親1, 左右の子は2, 3で、親n, 子2n, 2n+1

プログラミング・コンテスト・チャレンジブックでは、[0]から始めていますが、
もし[0]から始めると、
親0, 左右の子は1, 2で、
親1, 左右の子は3, 4で、
親n, 子2n+1, 2n+2、となり複雑だから

438
デフォルトの名無しさん[sage]   投稿日:2016/12/18 01:56:35  ID:05Ug+E6t.net(6)
>114
汚すぎるコードだ。なんだろう。初心者とも違うな。
まるで20年ぐらい前から成長してない人が書いたコードのようだ。

439
デフォルトの名無しさん[]   投稿日:2016/12/18 02:12:34  ID:KR24tnjc.net(2)
>115
ド素人と丸出しの感想文だな

440
114[sage]   投稿日:2016/12/18 04:57:12  ID:aCKcGLhu.net(8)
すまぬ

JavaScriptも、よく知らずに書いたのだw
本当は、== ではなく、型も一致する厳密等価演算子、=== を使うべきだろう

まあ、JSなどで、とても開発はできない。
Haxe で書き直せばよいのだろうが

Kotlin, Electron やら何やら、最近の言語に、ついていけてないw

441
デフォルトの名無しさん[sage]   投稿日:2016/12/18 08:19:04  ID:05Ug+E6t.net(6)
> 本当は、== ではなく、型も一致する厳密等価演算子、=== を使うべきだろう
そういうレベルじゃない。

無駄なロジック、意味不明な変数名、多すぎるコメント、
コードの意味を何一つ分かってないとしか思えないといってんの

442
デフォルトの名無しさん[sage]   投稿日:2016/12/18 11:08:48  ID:7J/3tpZx.net(2)
俺はむしろここ
> このソースコードのライセンスは、MIT License です
> Original Copyright (c) 2014 Michihito Seto All Rights Reserved.
残飯を神棚に飾るが如く宣言
ここにこそ初心者らしさが凝縮されてる

443
デフォルトの名無しさん[]   投稿日:2016/12/18 11:50:21  ID:5nrc1ooF.net(20)
>114

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の

「if key < A[i] エラー:新しいキーは現在のキーより小さい」

というのは意味があるのでしょうか?

444
デフォルトの名無しさん[sage]   投稿日:2016/12/18 11:50:54  ID:05Ug+E6t.net(6)
jsdo使ってるやつって汚いコードが多いよな。
素人が使いたくなる機能でもあんのか?
ブラウザだけで開発ができるとか?

445
デフォルトの名無しさん[]   投稿日:2016/12/18 11:53:36  ID:5nrc1ooF.net(20)
デバッグなど必要のないくらい簡単なコードなので、デバッグ用とは考えられないかと思います。

446
デフォルトの名無しさん[sage]   投稿日:2016/12/18 11:57:14  ID:0+9ctOie.net(2)
馬鹿ほど自説に拘るw

447
デフォルトの名無しさん[]   投稿日:2016/12/18 12:12:58  ID:5nrc1ooF.net(20)
Introduction to AlgorithmsよりもAlgorithms(Sedgewick、赤い本)のほうがいい本ですね。

読んでいて楽しい。

448
デフォルトの名無しさん[]   投稿日:2016/12/18 12:18:23  ID:5nrc1ooF.net(20)
日本語のデータ構造とアルゴリズムの本だと、茨木の本が有名だけど、
どこがいいのかさっぱりわからない。

翻訳書ではない日本語の本でまともなのは、浅野孝夫の本くらいではないでしょうか?

449
デフォルトの名無しさん[sage]   投稿日:2016/12/18 12:18:30  ID:d5jVhhWj.net(6)
アルゴリズムやコードのライセンスってどの程度のものから付けていいんだ
あんまり簡単なものだと既出すぎてライセンス付けられるのか?って考えてしまう
かといってじゃあライセンス付けていい最低ラインは何なんだという話になる

450
デフォルトの名無しさん[]   投稿日:2016/12/18 12:20:00  ID:5nrc1ooF.net(20)
>126

ライセンスとか書いてあっても一部だけコピペして利用したら、分からないですよね。

どうやって、だれかのコードを流用したか判定するのか、それに興味があります。

451
デフォルトの名無しさん[sage]   投稿日:2016/12/18 12:30:54  ID:RB5DyRP2.net(4)
アルゴリズムには著作権ないよ
あるのはそれをどう表現したか
簡単なアルゴリズムには表現バリエーションなんて限られてるから
ある程度似るのはどうしようもない

452
デフォルトの名無しさん[]   投稿日:2016/12/18 12:37:57  ID:5nrc1ooF.net(20)
特許ならありますよね。

453
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:02:47  ID:PELrVlNw.net(6)
デザインパターンの本高い・・・
一冊持ってたけど引っ越しのごたごたでなくしちゃった
無料で網羅できるサイトありませんかね
一冊読んではあるので、さらっと構造や仕組みを紹介してくれていればいいし
英語もある程度は読めます

基本のデザインパターンだけでもありがたいし
マルチスレッド対応に踏み込んだサイトならなおありがたいです

454
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:22:26  ID:d5jVhhWj.net(6)
基本的な考え方覚えたら幾らでも応用できるだろ
カタログを後生大事にとっておく意味はない

455
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:35:15  ID:PELrVlNw.net(6)
覚えてないんすよ
記憶力ないんで忘れちゃって、ぼんやりとしか覚えてないんです
だから概要をしっかり覚え直したいなと思って

456
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:42:55  ID:+dKTlaSP.net(2)
>132
いや、デザパタ本こそ手元においておくべき
わけのわからん二次情報を見るとどんどんブレていくぞ

457
デフォルトの名無しさん[sage]   投稿日:2016/12/18 13:45:05  ID:RB5DyRP2.net(4)
リファレンスとしてはどの本がいい?

458
デフォルトの名無しさん[]   投稿日:2016/12/18 13:45:12  ID:5nrc1ooF.net(20)
ソフトウェア工学的な本って重要なんですか?

459
デフォルトの名無しさん[]   投稿日:2016/12/18 13:45:59  ID:5nrc1ooF.net(20)
学問的には全く面白くない分野ですよね。

460
デフォルトの名無しさん[sage]   投稿日:2016/12/18 14:08:17  ID:PELrVlNw.net(6)
TECHSCOREのデザインパターンのページ見ることで自己解決しました

461
デフォルトの名無しさん[]   投稿日:2016/12/18 15:45:37  ID:VFzWAIXP.net(4)
デザパタカタログは便利だよね
煮詰まったときに、休憩がてらパターンを眺めてると、閃くときがある

462
デフォルトの名無しさん[sage]   投稿日:2016/12/18 16:24:54  ID:+Ko1jSRc.net(2)
ねーわ、普通のコードが99.99%

463
デフォルトの名無しさん[sage]   投稿日:2016/12/18 18:22:27  ID:d5jVhhWj.net(6)
基本的な発想を学んだらカタログはポイ
パターンに執着してもデザインがぎこちなくなるだけ

464
114[sage]   投稿日:2016/12/18 23:03:56  ID:aCKcGLhu.net(8)
>119
jsdo.it では、全員のソースコードが、サイト内に限り、MITになる

漏れが、わざわざ、MITと書いておいたのは、サイト外でも使ってほしいという意味。
学生が勉強することも多いから、コメントも一杯書いた

2分ヒープ、AVL、赤黒木など、アルゴリズムの実装は、どうしても汚いソースコードになる

465
デフォルトの名無しさん[sage]   投稿日:2016/12/18 23:11:13  ID:f3M2Oqre.net(2)

466
デフォルトの名無しさん[]   投稿日:2016/12/18 23:11:21  ID:5nrc1ooF.net(20)
2分ヒープって簡単なアルゴリズムですよね。

汚くなりようがないように思うのですが。

467
デフォルトの名無しさん[]   投稿日:2016/12/18 23:12:19  ID:5nrc1ooF.net(20)
計算幾何学って難しい割に見返りが少ないように思います。

だからあんまり人気がないのかもしれないですね。

468
デフォルトの名無しさん[sage]   投稿日:2016/12/19 00:01:07  ID:hSWjQy3F.net(10)
漏れw

469
デフォルトの名無しさん[sage]   投稿日:2016/12/19 01:06:56  ID:8cVREo5r.net(2)
流石に漏れは笑う

470
デフォルトの名無しさん[sage]   投稿日:2016/12/19 08:08:43  ID:judB9f5Y.net(2)
>144
全体的なリテラシの底上げがされるまではどうしてもね。

471
デフォルトの名無しさん[]   投稿日:2016/12/19 12:42:11  ID:z9XVuDpo.net(4)
>144
理論的な上限値をあらかじめ計算することが出来て
無駄な努力や試行錯誤をしなくて済むというメリットがあるよ

472
デフォルトの名無しさん[sage]   投稿日:2016/12/19 17:37:02  ID:ic0p/3Yf.net(28)
長さnの整数からなる列(a_1 ,a_2, ..., a_n) があるとして、列の大きさを
|a_1|+...+|a_n|で定義します。、
大きさがmの任意の列を大きさm-1の列の中の一つの値だけ1違う
列一つに対応させたいんですけど
対応のさせ方がわかりません、教えてください。
例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する長さ2の列は
(0 ,-1 ,1), (1,0,1),(1,-1,1),(1,-1,0)とかあるので一つには定まってません。
なのでその対応をする関数をおしえてください。

473
間違ってたので直します[sage]   投稿日:2016/12/19 17:39:59  ID:ic0p/3Yf.net(28)
長さnの整数からなる列(a_1 ,a_2, ..., a_n) があるとして、列の大きさを
|a_1|+...+|a_n|で定義します。、
大きさがmの任意の列を大きさm-1の列の中の一つの値だけ1違う
列一つに対応させたいんですけど
対応のさせ方がわかりません、教えてください。
例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する大きさ2の列は
(0 ,-1 ,1), (1,0,1),(1,-1,0)とかあるので一つには定まってません。
なのでその対応をする関数をおしえてください。

474
デフォルトの名無しさん[sage]   投稿日:2016/12/19 17:48:27  ID:z9XVuDpo.net(4)
(1,-1,1)の長さが2?

475
デフォルトの名無しさん[]   投稿日:2016/12/19 17:53:09  ID:yHCszZUX.net(12)
>なのでその対応をする関数をおしえてください。

意味不明です。

476
デフォルトの名無しさん[]   投稿日:2016/12/19 17:55:40  ID:yHCszZUX.net(12)
(a_1, a_2, ..., a_i, ..., a_n)

a_i > 0 のときには、

(a_1, a_2, ..., a_i-1, ..., a_n)

a_i < 0 のときには、

(a_1, a_2, ..., a_i+1, ..., a_n)

a_i = 0 のときには、

(a_1, a_2, ..., a_i±1, ..., a_n)

を返せばいいのでは?

477
デフォルトの名無しさん[]   投稿日:2016/12/19 17:57:14  ID:yHCszZUX.net(12)
(a_1, a_2, ..., a_i, ..., a_n)

a_i > 0 のときには、

(a_1, a_2, ..., a_i-1, ..., a_n)

a_i < 0 のときには、

(a_1, a_2, ..., a_i+1, ..., a_n)

を返せばいいのでは?

a_i = 0 のときには、条件を満たす列は存在しないね。

478
デフォルトの名無しさん[]   投稿日:2016/12/19 17:58:07  ID:yHCszZUX.net(12)
>150

何がやりたいのかが不明確。

479
デフォルトの名無しさん[sage]   投稿日:2016/12/19 17:58:17  ID:hSWjQy3F.net(10)
>149
列の最初の数字だけ1足すなり引くなりして返せばいいだけじゃないの?

480
デフォルトの名無しさん[]   投稿日:2016/12/19 18:01:17  ID:yHCszZUX.net(12)
>例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する大きさ2の列は
>(0 ,-1 ,1), (1,0,1),(1,-1,0)とかあるので一つには定まってません。
>なのでその対応をする関数をおしえてください。

一つに定まらないから、すべての結果を返したいのか、
任意の一つの結果を返したいのか?

481
デフォルトの名無しさん[]   投稿日:2016/12/19 18:02:09  ID:yHCszZUX.net(12)
明らかに、

(0, 0, ..., 0) に対しては条件を満たす結果は存在しないね。

482
デフォルトの名無しさん[sage]   投稿日:2016/12/19 18:50:37  ID:ic0p/3Yf.net(28)
0はスタート地点なので

483
デフォルトの名無しさん[sage]   投稿日:2016/12/19 18:57:02  ID:ic0p/3Yf.net(28)
>154
a_2を1としたとき(-1, 1)のとき(-1,0)を返し
a_1を-1としたとき (-1,1)は(0,1)をかえすことになるので
一つに定まりません

484
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:06:19  ID:ic0p/3Yf.net(28)
>157
大きさn>0の任意の列aにたいしてf(a)=bでbがn-1の大きさでaと列の中の値が1だけ違う
列を出力する関数fを求めるということです。

485
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:13:51  ID:ic0p/3Yf.net(28)
>156
初めはそんな風に考えてる時期もありました
もう2か考えてるけれど全然わからないのでここで質問してみました

486
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:16:05  ID:hSWjQy3F.net(10)
>161
問題文を鸚鵡返しするんじゃなくて、質問者の質問に答えたら?

487
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:23:49  ID:ic0p/3Yf.net(28)
>163
fの出力は列の集合じゃないから普通わかりますよね

488
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:31:58  ID:hSWjQy3F.net(10)
>164
fが返すのは集合じゃないってのはどこに書いてある?

489
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:34:42  ID:ic0p/3Yf.net(28)
>165
14行上に書いてあります

490
デフォルトの名無しさん[sage]   投稿日:2016/12/19 19:47:31  ID:hSWjQy3F.net(10)
>166
Mateだと>156って書いてあるわ
自分の中ではこれは当然みたいな条件がいろいろあるんだろうけど、それを人に説明するのが下手なんじゃね

491
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:02:25  ID:ic0p/3Yf.net(28)
改行コードの数を数えてますか?
文の折り返しと改行とは違いますよ?

492
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:17:02  ID:2q/Y95iw.net(8)
こりゃまたひどい質問者だな

493
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:18:06  ID:Xx/umGft.net(6)
課題の丸投げ、しかも「日本語」が

494
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:25:56  ID:ic0p/3Yf.net(28)
課題という証拠はありますか?
実際課題じゃなくプログラミングしていたら出てきた問題なので
全然課題じゃないです

495
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:33:03  ID:ic0p/3Yf.net(28)
>170
あなたには誤った文を訂正する能力がないんですか?
それでは人間ではなくコンパイラーと同じですよ

496
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:37:51  ID:ic0p/3Yf.net(28)
>169
面白い問題とつまらない問題を区別する能力が数学的推測には
一番必要なんんです
この問題がつまらないと思うのなら解かないでいいです

497
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:50:46  ID:2q/Y95iw.net(8)
問題をきちんと記述する能力に欠けている

498
デフォルトの名無しさん[sage]   投稿日:2016/12/19 20:52:23  ID:2q/Y95iw.net(8)
あと、面白い問題だと思うなら、それこそ自分で解くのが楽しいのでは
ここで聞かずに

499
デフォルトの名無しさん[sage]   投稿日:2016/12/19 21:27:51  ID:ic0p/3Yf.net(28)
>175
楽しいものは独り占めるのではなく分け与えようと習わなかったのでは?

500
デフォルトの名無しさん[sage]   投稿日:2016/12/19 21:44:43  ID:ic0p/3Yf.net(28)
>174
今読み返してみましたがキチンと書かれてますよ
どこがキチンと書かれてないのか言ってくれたら
それは理解力の無さなので説明してもいいです

501
デフォルトの名無しさん[sage]   投稿日:2016/12/19 22:34:08  ID:2q/Y95iw.net(8)
十分楽しんだからあとは一人で楽しんでくれていいよ

502
デフォルトの名無しさん[sage]   投稿日:2016/12/19 22:53:51  ID:Xx/umGft.net(6)
>172
馬鹿乙

503
デフォルトの名無しさん[sage]   投稿日:2016/12/19 23:04:39  ID:L2gIhLeK.net(2)
先頭から非0を探して、はじめの要素が正なら1ひく、負なら1足す
これで終わりじゃないの?

504
デフォルトの名無しさん[sage]   投稿日:2016/12/19 23:45:15  ID:Xx/umGft.net(6)
アルゴリズムは自分で考えるじゃ、ボケ

505
デフォルトの名無しさん[sage]   投稿日:2016/12/20 13:05:59  ID:lAXr92yw.net(2)
>171
茶か尿かもう判らんって意見があるけど
検出時のガスクロのデータ見直したら判るはずという話がある
仮にそれでお茶だとしてももう発表はないだろう

506
デフォルトの名無しさん[]   投稿日:2016/12/21 18:35:54  ID:UR5SKYPV.net(30)
数列 1, 2, 3, …

すなわち、

数列 {a_n} = {n}

を考える。

{a_n} の任意の連続する有限部分列を a_k, a_(k+1), …, a_l(k ≦ l)とする。

各 i(k ≦ i ≦ l)に対して、0以上の整数 b_i を以下で定義する:

「2^(b_i) は a_i を割り切るが、 2^(b_i+1) は a_i を割り切らない」

このとき、 #{m | k ≦ i ≦ l である任意の i に対して、 b_i ≦ b_m} = 1 であることを示せ。

また、有限部分列 a_k, a_(k+1), …, a_l(k ≦ l)が与えられたとき、 k ≦ i ≦ l である
任意の i に対して、 b_i ≦ b_m となるような m を求めるプログラムを作れ。

507
デフォルトの名無しさん[sage]   投稿日:2016/12/21 18:45:01  ID:trArLuj5.net(8)
お断りいたします

508
デフォルトの名無しさん[sage]   投稿日:2016/12/21 18:49:10  ID:IT3zLaEf.net(2)
俺も断るわ

509
デフォルトの名無しさん[]   投稿日:2016/12/21 19:41:25  ID:UR5SKYPV.net(30)
早くも降参宣言か。

510
デフォルトの名無しさん[sage]   投稿日:2016/12/21 19:55:05  ID:RIWp4Ngq.net(18)
mなんていくらでもあるんじゃないの?
なんで#{m}=1?

511
デフォルトの名無しさん[]   投稿日:2016/12/21 20:06:55  ID:UR5SKYPV.net(30)
>187

一意的です。そこがちょっと面白いところです。

反例を作ろうと思ってもできないはずです。

512
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:09:57  ID:trArLuj5.net(8)
>183
分からない問題はここに書いてね421 [無断転載禁止]©2ch.net
分からない問題はここに書いてね421 /数学板

513
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:12:10  ID:RIWp4Ngq.net(18)
k=1, l=2で、{m}={2,4,6,8,...}
k=l=1で、{m}=自然数の集合
じゃないの?

514
デフォルトの名無しさん[]   投稿日:2016/12/21 20:16:47  ID:UR5SKYPV.net(30)
>190

{a_n} の任意の*連続する*有限部分列を a_k, a_(k+1), …, a_l(k ≦ l)とする。

515
デフォルトの名無しさん[]   投稿日:2016/12/21 20:18:48  ID:UR5SKYPV.net(30)
k=1, l=2で、{m}={2,4,6,8,...}
k=l=1で、{m}=自然数の集合
じゃないの?

a_1, a_2 = 1, 2

なので、 b_1, b_2 = 0, 1

です。

なので、 {m} = {2} です。

516
デフォルトの名無しさん[]   投稿日:2016/12/21 20:19:15  ID:UR5SKYPV.net(30)
>191
は勘違いです。

517
デフォルトの名無しさん[]   投稿日:2016/12/21 20:20:14  ID:UR5SKYPV.net(30)
a_1 = 1

なので、

b_1 = 0

です。

なので、

{m} = {1}

です。

518
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:21:17  ID:RIWp4Ngq.net(18)
k=1, l=2も、k=l=1も、当然連続する部分列でしょ
{b_i}を10個ぐらい挙げてみてよ

519
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:22:42  ID:RIWp4Ngq.net(18)
mの条件が足りないんじゃないの?

520
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:24:46  ID:RIWp4Ngq.net(18)
b_i ≦ b_mさえ満たせばいいんならmなんていくらでもあるでしょ

521
デフォルトの名無しさん[]   投稿日:2016/12/21 20:32:03  ID:UR5SKYPV.net(30)
b_m は b_i の最大値です。

その最大値となる b_m の m が一意的であるということです。

522
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:32:36  ID:El82f3CE.net(2)
k≦m≦lという条件が抜けているっぽいね

523
デフォルトの名無しさん[]   投稿日:2016/12/21 20:34:06  ID:UR5SKYPV.net(30)
テレンス・タオ ルベーグ積分入門
テレンス タオ
固定リンク: http://amzn.asia/8KaL6NK

「日本の理工系学部ではルベーグ積分は3年次程度の必修相当科目なので、」

↑これっておかしくないですか?

普通、ルベーグ積分なんてやるのは数学科かせいぜい物理学科くらいじゃないですか?

524
デフォルトの名無しさん[]   投稿日:2016/12/21 20:34:58  ID:UR5SKYPV.net(30)
>199

各 i(k ≦ i ≦ l)に対して、0以上の整数 b_i を以下で定義する:

525
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:39:27  ID:RIWp4Ngq.net(18)
不完全な問題出しておいて>186はないよね

526
デフォルトの名無しさん[]   投稿日:2016/12/21 20:41:22  ID:UR5SKYPV.net(30)
>202

不完全なところはありません。
よく問題文を読んでください。

527
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:42:06  ID:trArLuj5.net(8)

528
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:43:41  ID:trArLuj5.net(8)
マルチ小僧w

529
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:44:49  ID:RIWp4Ngq.net(18)
>203
mがkからlの間なんて一言もないんだから不完全

530
デフォルトの名無しさん[]   投稿日:2016/12/21 20:47:08  ID:UR5SKYPV.net(30)
>206

>183
各 i(k ≦ i ≦ l)に対して、0以上の整数 b_i を以下で定義する

531
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:52:23  ID:RIWp4Ngq.net(18)
そうだとして、わざと誤読を誘おうとしている悪問だね
でO(log k)のアルゴリズム思いついたから俺は降りるね

532
デフォルトの名無しさん[sage]   投稿日:2016/12/21 20:53:06  ID:RIWp4Ngq.net(18)
O(log l)だった

533
デフォルトの名無しさん[]   投稿日:2016/12/21 20:55:14  ID:UR5SKYPV.net(30)
>183

の解答は以下です。

http://imgur.com/rAnp3Ga.jpg

赤線を引いたところは「odd」が正しいですね。

534
デフォルトの名無しさん[]   投稿日:2016/12/21 21:27:34  ID:UR5SKYPV.net(30)
実は、この問題には続きがあります。

m, n を m < n を満たす正の整数とします。

このとき、

1/m + 1/(m+1) + … + 1/n

は整数にはならないことを証明せよ。

535
デフォルトの名無しさん[]   投稿日:2016/12/21 21:29:28  ID:UR5SKYPV.net(30)
ちょっとアルゴリズム的な問題からは離れますが。

536
デフォルトの名無しさん[sage]   投稿日:2016/12/21 21:31:37  ID:xYX0mlO/.net(2)
提出日はいつですか?

537
デフォルトの名無しさん[sage]   投稿日:2016/12/21 22:14:54  ID:auJA5Ak8.net(2)
またバカな質問者が暴れてるのか

538
デフォルトの名無しさん[sage]   投稿日:2016/12/21 23:45:05  ID:mNaBBYjZ.net(2)
qiitaでやれ

539
デフォルトの名無しさん[sage]   投稿日:2016/12/23 00:59:54  ID:gOElNe3R.net(4)
>183
そのような m が 2 個ある
m1 < m2
とする

m1 の下位ビット 0 〜 n-1 までは 0で、 ビット n が 1 とする
m2 も同様になる(すなわち b_m1 = b_m2 = n )

m3 = m1 + ( 2 の n 乗 )

と定義すると
m1 < m3 <= m2 であるが、b_m3 > n となって矛盾

540
デフォルトの名無しさん[sage]   投稿日:2016/12/23 01:37:11  ID:gOElNe3R.net(4)
>211
1/m + 1/(m+1) + … + 1/n = P = 整数
だとする

L = ∏ r ; r = m…n
を両辺に掛ける

L/m + L/(m+1) + … + L/n = LP

すべての項は整数。

b_LP ( LP の連続する下位ビット 0 の個数 ) >= Σ b_r ; r = m…n

m <= x <= n は b_x を最大にするもの
左辺の L/x だけ連続する下位ビット 0 の個数は他より少ない
よって b_左辺 = b_x で矛盾

541
デフォルトの名無しさん[]   投稿日:2017/01/01 00:15:18  ID:VtFWW7J2.net(2)
ダイクストラのアルゴリズムの正しさの証明が載っている本で
一番分かりやすい本を教えてください。

542
デフォルトの名無しさん[]   投稿日:2017/01/02 07:40:19  ID:03PPbeGI.net(30)
『アルゴリズムイントロダクション』について質問です。

この本での実数の集合には、 ∞, -∞ が含まれるのでしょうか?

最短路問題の説明で、

実数 a が a≠∞のとき、 a + -∞ = -∞
実数 a が a≠-∞のとき、 a + ∞ = ∞

という記述があるために質問します。

543
デフォルトの名無しさん[]   投稿日:2017/01/02 08:09:15  ID:03PPbeGI.net(30)
実数 a が a≠∞のとき、 a + -∞ = -∞
実数 a が a≠-∞のとき、 a + ∞ = ∞

-∞ + -∞ = -∞
∞ + ∞ = ∞

という等式を含めたいからこのような書き方になったのでしょうか?

544
デフォルトの名無しさん[sage]   投稿日:2017/01/02 09:29:22  ID:J77W/v0L.net(4)
それは実無限派の書き方だが,世の趨勢は可能無限
ほどほどに相手をするだけでいいよ

545
デフォルトの名無しさん[]   投稿日:2017/01/02 11:22:57  ID:03PPbeGI.net(30)
>221

ということは、『アルゴリズムイントロダクション』での実数の集合の定義には、
∞、-∞ が含まれるというk十ですね。

546
デフォルトの名無しさん[]   投稿日:2017/01/02 11:23:39  ID:03PPbeGI.net(30)
頂点の数が n のグラフで、任意の頂点間に辺が存在するようなものを考える。

ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を求めよ。

547
デフォルトの名無しさん[]   投稿日:2017/01/02 11:26:14  ID:03PPbeGI.net(30)
頂点の数が n(≧2) のグラフで、任意の頂点間に辺が存在するようなものを考える。

ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を a_n とする。

このとき、

(n-1)! ≧ a_n ≧ (n-2)!

が成り立つことを示せ。

548
デフォルトの名無しさん[sage]   投稿日:2017/01/02 12:08:43  ID:GdcUHK9D.net(6)
宿題は宿題スレへ

549
デフォルトの名無しさん[sage]   投稿日:2017/01/02 12:09:56  ID:GdcUHK9D.net(6)
宿題は宿題スレへ

550
デフォルトの名無しさん[]   投稿日:2017/01/02 12:22:39  ID:03PPbeGI.net(30)
宿題ではないのです。

ある本に、頂点 s から t への最短経路を計算する方法として、
s から t へのあらゆる経路の長さを考えて、最小の経路を選ぶとすると、
経路の数が O(n!) だから現実的ではない

という話が書いてあります。

ところが、計算してみると、 O(n!) は荒い評価であって、 O((n-1)!) とできますね。

551
デフォルトの名無しさん[]   投稿日:2017/01/02 12:24:22  ID:03PPbeGI.net(30)
もっといい評価はありますでしょうか?

552
デフォルトの名無しさん[sage]   投稿日:2017/01/02 12:28:36  ID:GdcUHK9D.net(6)
判ってるなら効くな

553
デフォルトの名無しさん[]   投稿日:2017/01/02 14:08:15  ID:03PPbeGI.net(30)
ダイクストラ法の正しさの証明で分かりやすい証明を思いつきました。

発表しましょうか?

554
デフォルトの名無しさん[sage]   投稿日:2017/01/02 14:21:37  ID:w6ZCrhsc.net(2)
どうぞどうぞ

555
デフォルトの名無しさん[sage]   投稿日:2017/01/02 14:27:23  ID:yIXUnWg3.net(2)
>227
オーダーについてあんま良くわかってないんだろうけどO((n-1)!) なんて書き方はないよ
もし書いたとして、それはO(n!)と同じもの

556
デフォルトの名無しさん[sage]   投稿日:2017/01/02 17:55:38  ID:J77W/v0L.net(4)
>222
実無限はいろいろ破綻するから可能無限にしておいたほうがいいよ
実数の定義に∞, -∞は入らない
というか,そもそも -∞ というのがおかしい存在

つリーマン球面

557
デフォルトの名無しさん[]   投稿日:2017/01/02 19:04:30  ID:03PPbeGI.net(30)
なんか正しさの証明を書いてみると簡単なことなのに長くなりますね。
もし、間違っていたら指摘してください。

http://imgur.com/PDx2vmZ.jpg
http://imgur.com/DbMiSz5.jpg

ダイクストラのアルゴリズムは↑のものとします。

558
デフォルトの名無しさん[]   投稿日:2017/01/02 19:05:18  ID:03PPbeGI.net(30)
節点 s から、ある節点 i への最短経路が存在するとき、その長さを td(i) で表わすことにする。
i への経路、したがって最短経路が存在しないときには、 td(i) = ∞ とする。

ステップ(1)で選ばれる節点 v ∈ V - S に対して、 d(v) = td(v) が成り立つことを数学的帰納法により、以下で証明する。

最初にステップ(1)が実行されるときを考える。
明らかに、 d(s) = td(s) = 0 が成り立つ。

k ≧ 1 とする。
第 1 回目から第 k 回目にステップ(1)が実行されるときに、いつもステップ(1)で選ばれる節点 v ∈ V - S に対して、
d(v) = td(v) が成り立つと仮定する。

559
デフォルトの名無しさん[]   投稿日:2017/01/02 19:05:35  ID:03PPbeGI.net(30)
第 (k+1) 回目にステップ(1)が実行されるときを考える。
このとき、明らかに #S = k であり、 ∀i ∈ S に対して、 d(i) = td(i) が成り立つ。
第 (k+1) 回目にステップ(1)が実行されるときに選ばれる節点を v ∈ V - S とする。
d(v) = ∞ である場合と d(v) ≠ ∞ である場合で場合分けして考える。

(1) d(v) = ∞ である場合。
td(v) ≠ d(v) = ∞ と仮定して矛盾を導く。
td(v) ≠ ∞ であるから、節点 s から節点 v への経路 s = v_0 → v_1 → … → v_(l-1) → v_l = v が存在する。
明らかに、 td(v_0), td(v_1), …, td(v_(l-1)), td(v_l) ≠ ∞ である。
v_0 ∈ S, v_l ∈ V - S であるから、 v_i ∈ S, v_(i+1) ∈ V - S となるような i が存在する。
∀j ∈ V - S に対して、 d(j) = ∞ であるから、 d(v_(i+1)) = ∞ である。また、 v_i ∈ S であるから、
d(v_i) = td(v_i) ≠ ∞ が成り立つ。
v_i がステップ(2)で S に追加されたときのことを考えれば分かるように、 (v_i, v_(i+1)) ∈ E かつ v_(i+1) ∈ V - S であるから、
d(v_(i+1)) = ∞ ということはない。これは矛盾である。
よって、 d(v) = td(v) = ∞ が成り立つ。

560
デフォルトの名無しさん[]   投稿日:2017/01/02 19:05:51  ID:03PPbeGI.net(30)
(2) d(v) ≠ ∞ である場合。
td(v) ≠ d(v) と仮定して矛盾を導く。
ステップ(2)を考えれば明らかなように、 d(v) ≠ ∞ であるから、節点 s から節点 v への
最短経路 s = v_0 → v_1 → … → v_(l-1) → v_l = v が存在する。
よって、 td(v) ≠ ∞ である。
仮定により、 td(v) ≠ d(v) であるから、 td(v) < d(v) が成り立つ。
v_0 ∈ S, v_l ∈ V - S であるから、 v_i ∈ S, v_(i+1) ∈ V - S となるような i が存在する。
td(v_(i+1)) < d(v_(i+1)) である。なぜなら、もし、そうでないと仮定すると、 d(v_(i+1)) = td(v_(i+1)) であるが、
td(v_(i+1)) ≦ td(v) < d(v) であるから、 d(v_(i+1)) < d(v) となってしまい、ステップ(1)での v の
選ばれ方に矛盾するからである。
v_i ∈ S であるから、 d(v_i) = td(v_i) である。
v_i がステップ(2)で S に追加されたときのことを考えれば分かるように、 (v_i, v_(i+1)) ∈ E かつ v_(i+1) ∈ V - S であるから、
d(v_i) + a_(v_i v_(i+1)) ≧ d(v_(i+1)) である。
一方、明らかに、 td(v_i) + a_(v_i v_(i+1)) = td(v_(i+1)) であるから、
td(v_(i+1)) = td(v_i) + a_(v_i v_(i+1)) = d(v_i) + a_(v_i v_(i+1)) ≧ d(v_(i+1)) となるが、これは矛盾である。
よって、 td(v) = d(v) が成り立つ。

561
デフォルトの名無しさん[]   投稿日:2017/01/02 19:06:08  ID:03PPbeGI.net(30)
以上より、第 (k+1) 回目にステップ(1)が実行されるときにも、ステップ(1)で選ばれる節点 v ∈ V - S に対して、
d(v) = td(v) が成り立つ。

S に追加される節点はすべて、ステップ(1)で選ばれた 節点 v ∈ V - S であり、一度 S に追加された節点 v の d(v) はそれ以後、
変更されないから、ステップ(1)でアルゴリズムが終了したとき、 ∀i ∈ S = V に対して、 d(i) = td(i) が成り立つ。

562
デフォルトの名無しさん[]   投稿日:2017/01/02 19:26:36  ID:03PPbeGI.net(30)
>232

ある本では、

正定数 c, n0 が存在して、 n ≧ n0 のとき、 T(n) ≦ c*f(n) であるなら、
T(n) は O(f(n)) であるという

と定義されています。

T(n) = n!
f(n) = n!
g(n) = (n-1)!

とします。

このとき、明らかに、
T(n) は O(f(n)) ですが、
T(n) は O(g(n)) ではありません。

563
デフォルトの名無しさん[]   投稿日:2017/01/02 19:29:54  ID:03PPbeGI.net(30)
したがって、

O(f(n)) と O(g(n)) は異なります。

564
デフォルトの名無しさん[sage]   投稿日:2017/01/03 08:33:06  ID:3o9M4oho.net(2)
この狂人ヤバいなw

565
デフォルトの名無しさん[]   投稿日:2017/01/03 08:50:16  ID:hCDXc7Qp.net(20)
>224
>227

閉路を含まないから、各点を高々1回しか通らない。(端点も)

直通の経路が 1
途中でk個所を通過する経路が
 (n-2)(n-3)・・・・・(n-k-1) = (n-2)!/(n-k-2)!
だけある。ただし、k≦n-2
よって
a_n = (n-2)!{1 + 1/1! + 1/2! + … + 1/(n-2)!},

n ≧ 2 のとき、

(n-2)! ≦ (n-2)! * (1 + 1/1! + 1/2! + … + 1/(n-2)!) ≦ e * (n-2)!

したがって、

a_n = Θ((n-2)!)

である。

566
デフォルトの名無しさん[]   投稿日:2017/01/03 08:52:54  ID:hCDXc7Qp.net(20)
>234-238

のダイクストラのアルゴリズムの正しさの証明に間違いはないという
ことでOKですか?

567
デフォルトの名無しさん[]   投稿日:2017/01/03 11:39:58  ID:hCDXc7Qp.net(20)
Erik DemaineはMITの歴史上最年少で教授になったという天才だそうですね。

今、そのErik Demaineの2005年のダイクストラのアルゴリズムについての講義を見ています。

見終わったら、講義の要約について書きます。

568
デフォルトの名無しさん[]   投稿日:2017/01/03 13:47:58  ID:hCDXc7Qp.net(20)
ダイクストラのアルゴリズム:

01: d[s] ← 0
02: for each v ∈ V - {s}:
03: ■■d[v] ← ∞
04: S ← Φ
05: Q ← V
06: while Q ≠ Φ:
07: ■■u ← ExtractMin(Q)
08: S ← S ∪ {u}
09: for each v ∈ Adj[u]:
10: ■■if d[v] > d[u] + w(u, v):
11: ■■■■d[v] ← d[u] + w(u, v)

569
デフォルトの名無しさん[]   投稿日:2017/01/03 13:49:29  ID:hCDXc7Qp.net(20)
Correctness I:

d[v] の初期化の直後、およびLine 11の直後において、
すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が
成り立つ。

証明:
d[v] の初期化の直後には、
d[s] = 0 かつすべての v ∈ S - {v} に対して、d[v] = ∞
が成り立っている。
δ(s, s) = 0 かつすべての v ∈ S に対して、 δ(s, v) ≦ ∞
であるから、d[v] の初期化の直後には、
すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が確かに
成り立っている。

570
デフォルトの名無しさん[]   投稿日:2017/01/03 13:49:56  ID:hCDXc7Qp.net(20)
Line 11の直後において、すべての v ∈ V に対して、
d[v] ≧ δ(s, v) が成り立つことを背理法により示す。

Line 11の直後において、 d[v] ≧ δ(s, v) が
成り立たないような v ∈ V が存在するとする。
v をそのような点の中で、最初の点とする。

d[v] < δ(s, v)

d[v] < δ(s, v) ≦ ∞ であるから、
ダイクストラのアルゴリズムのLine 11は少なくとも1回は
実行されているはずである。そのような最後の実行を

d[v] ← d[u] + w(u, v)

とすると、

d[u] + w(u, v) = d[v] < δ(s, v)

が成り立つ。

一方、 d[u] ≧ δ(s, u) であるから、

d[u] + w(u, v) ≧ δ(s, u) + w(u, v)
≧ δ(s, u) + δ(u, v)
≧ δ(s, v)

が成り立つが、これは矛盾である。

571
デフォルトの名無しさん[]   投稿日:2017/01/03 13:51:21  ID:hCDXc7Qp.net(20)
Correctness Lemma:
s → … → u → v を s から v への一つの最短路とする。
d[u] = δ(s, u) であるとする。

このとき、Line10-11を実行すると、

d[v] = δ(s, v)

が成り立つ。

証明:
δ(s, v) = w(s → … → u) + w(u, v)
= δ(s, u) + w(u, v)
Correctness Iより、 d[v] ≧ δ(s, v)

(1)Line10-11の実行前に、 d[v] = δ(s, v) である場合。
Line10-11の実行後も d[v] = δ(s, v) である。

(2)Line10-11の実行前に、 d[v] > δ(s, v) である場合。
d[v] > δ(s, v) = δ(s, u) + w(u, v) = d[u] + w(u, v)
Line10-11の実行後は、 d[v] = d[u] + w(u, v) = δ(s, v)
となる。

572
デフォルトの名無しさん[]   投稿日:2017/01/03 13:52:06  ID:hCDXc7Qp.net(20)
Correctness II:
ダイクストラのアルゴリズムが終了したとき、
すべての v ∈ V に対して、 d[v] = δ(s, v) が成り立つ。

証明:
d[v] は v が S に追加された後は、不変である。
よって、 v が S に追加されたときに、
d[v] = δ(s, v) であることを示せばよい。

背理法で示す。
v が S に追加されたときに、 d[v] ≠ δ(s, v) であるような
v ∈ V が存在すると仮定する。
u をそのような点の中で、最初に S に追加された点とする:
d[u] ≠ δ(s, u)
Correctness Iより、
d[u] > δ(s, u)

573
デフォルトの名無しさん[]   投稿日:2017/01/03 13:52:49  ID:hCDXc7Qp.net(20)
今、 u が S に追加される直前の状況を考えることにする。
u はまだ S に追加されていないから、 u ∈ Q である。
p を s から u への一つの最短路とすると、 w(p) = δ(s, u) である。
s ∈ S, u ∈ Q であるから、 p 上の辺 (x, y) で x ∈ S, y ∈ Q となる
ような辺が存在する。そのような辺の一つを (x, y) とする。
すると、 p は以下のようになる。
p : s → … → x → y → … → u
x ∈ S であるから、 u に関する仮定より、
d[x] = δ(s, x) が成り立つ。また、明らかに、
s → … → x → y は s から y への一つの最短路であるから、
Correctness Lemmaより、 d[y] = δ(s, y) が成り立つ。
明らかに、 δ(s, y) ≦ δ(s, u) であるから、
d[y] ≦ δ(s, y)
また、Line07を見れば分かるように、
d[u] ≦ d[y] である。
よって、

d[u] ≦ δ(s, u) となるが、これは矛盾である。

574
デフォルトの名無しさん[]   投稿日:2017/01/03 13:55:46  ID:hCDXc7Qp.net(20)
Lec 17 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005
https://youtu.be/xhG2DyCX3uA

575
デフォルトの名無しさん[]   投稿日:2017/01/05 09:16:14  ID:4i7P3+nF.net(18)
アルゴリズムイントロダクションって自明なことをわざわざループ不変量を使ったりして、
証明していて、うざすぎますね。

576
デフォルトの名無しさん[]   投稿日:2017/01/05 09:16:52  ID:4i7P3+nF.net(18)
通常の数学の本なら自明で済ませるようなことをわざわざ証明している。

577
デフォルトの名無しさん[sage]   投稿日:2017/01/05 09:57:50  ID:OZq8Y/OW.net(6)
このバカ、以前も全く同じこと言って暴れたな。

578
デフォルトの名無しさん[sage]   投稿日:2017/01/05 10:02:39  ID:OZq8Y/OW.net(6)
http://hissi.org/read.php/tech/20160422/cGVtVmVaYUg.html
http://hissi.org/read.php/tech/20160612/YkttemlBQ3Y.html
こいつだ。

> って当たり前のことをループ不変とかを使って説明しているよね。はっきりいってくどい。
> ループ不変式とかいうのが出てくるけど、当たり前のことを形式的に証明しているだけで、つまらなすぎる。
> 馬鹿の一つ覚えみたいにループ不変式をつかって証明しようとしている。

これぞ「馬鹿の一つ覚え」である。

579
デフォルトの名無しさん[sage]   投稿日:2017/01/05 10:44:28  ID:W/+CAQrH.net(4)
数学とコンピュータ科学の区別がつかない厨房だろう

580
デフォルトの名無しさん[]   投稿日:2017/01/05 11:01:45  ID:4i7P3+nF.net(18)
クヌースの本なんかだと妙なくどさはない。

アルゴリズムイントロダクションはメリハリが全くない。
Trivialなこともそうでないことも平等に扱いすぎている。

要するに本を書くセンスがない。

581
デフォルトの名無しさん[]   投稿日:2017/01/05 11:02:52  ID:4i7P3+nF.net(18)
セジウィックとウエインの本のほうがずっとよい。

582
デフォルトの名無しさん[]   投稿日:2017/01/05 11:07:44  ID:4i7P3+nF.net(18)
日本語の本について言及しておく。
例えば、評判のよい茨木俊秀の本。

こんな薄いスカスカの本をよくも恥ずかしげもなく出版するものだとあきれる。

583
デフォルトの名無しさん[]   投稿日:2017/01/05 11:19:31  ID:4i7P3+nF.net(18)
アルゴリズムイントロダクションの悪口を書いたがいいところもある。

例えば、第29章線形計画法。

線形計画法に対しては、Trivialなこともそうでないことも平等に扱うという方針が
向いているように思う。

ただ、アルゴリズムの本に線形計画法を入れる理由が分からない。

整数論的アルゴリズムの章はあまりにも簡単すぎる。
高木貞治の本でも読んだ方がよい。

584
デフォルトの名無しさん[]   投稿日:2017/01/05 11:28:06  ID:4i7P3+nF.net(18)
結論として、ベストな本はクヌースが予定しているTAOCPの要約本ということになる。

585
デフォルトの名無しさん[sage]   投稿日:2017/01/05 11:29:47  ID:W/+CAQrH.net(4)
結論として4i7P3+nFはNG行き

586
デフォルトの名無しさん[sage]   投稿日:2017/01/05 11:33:33  ID:2uA+A+xC.net(4)
>253
自明ほど危ういものは無いんだが

587
デフォルトの名無しさん[sage]   投稿日:2017/01/05 11:40:35  ID:OZq8Y/OW.net(6)
例によって ID:4i7P3+nF が発狂しててワロタ

588
デフォルトの名無しさん[]   投稿日:2017/01/05 11:44:36  ID:4i7P3+nF.net(18)
>263

では、なぜ、一般に、コンピュータ科学者よりも頭が良いとされる数学者が
自明で済ませることが多いのでしょうか?

もし危ういのなら頭のよい数学者は自明などと書かないはずです。

589
デフォルトの名無しさん[sage]   投稿日:2017/01/05 11:52:58  ID:r7KPx/TL.net(2)
そんな多くねえよちゃんと論文読め

590
デフォルトの名無しさん[sage]   投稿日:2017/01/05 12:06:11  ID:2uA+A+xC.net(4)
自明連発する方が馬鹿なのか

591
デフォルトの名無しさん[sage]   投稿日:2017/01/05 13:09:24  ID:c6xYhHVb.net(4)
>265
馬鹿丸出し

592
デフォルトの名無しさん[sage]   投稿日:2017/01/05 13:18:34  ID:c6xYhHVb.net(4)
>一般に、コンピュータ科学者よりも頭が良いとされる数学者が
根拠は?
>自明で済ませることが多いのでしょうか?
数学のコンテキストの話

そもそも証明の意味もコンピュータ科学と数学では違うだろ

593
デフォルトの名無しさん[sage]   投稿日:2017/01/05 14:56:52  ID:jagWiFjG.net(2)
なんでバカって本質に関係ないところでギャーギャー騒ぐの?

594
デフォルトの名無しさん[sage]   投稿日:2017/01/05 14:58:54  ID:YjTG1plI.net(2)
うむ

595
デフォルトの名無しさん[]   投稿日:2017/01/05 19:46:02  ID:4i7P3+nF.net(18)
アルゴリズムイントロダクションについて、数学が出来る人向けの本だという人がいる。
そして、数学ができない人はセジウィック&ウエインの本を読めという人がいる。

アルゴリズムイントロダクションが数学的な本だとは全く思わない。数学的な内容については
主に結果だけを書いている。

ただネチネチとアルゴリズムの正しさの証明が書かれているだけのこと。

クヌースの本のように、楽しい本ではない。

596
デフォルトの名無しさん[sage]   投稿日:2017/01/05 20:37:39  ID:UiiKd7HR.net(2)

597
デフォルトの名無しさん[sage]   投稿日:2017/01/05 22:15:16  ID:WPj32BYO.net(2)
書評したければ別のところでやれ

598
デフォルトの名無しさん[]   投稿日:2017/01/06 17:19:30  ID:TSHa+AxL.net(16)
再帰の除去についてやり方が詳しく書いてある本を教えてください。

599
デフォルトの名無しさん[]   投稿日:2017/01/06 17:43:03  ID:TSHa+AxL.net(16)
プログラミングコンテストチャレンジブック第2版のp.35
Lake Counting(POJ No.2386)

の解答として、以下のプログラムはあっていますか?

void dfs(i, j, n){
if(i < 0 || i >= N || j < 0 || j >= M){
return;
}
if(field[i][j] != 'W'){
return;
}
if(visit[i][j] == true){
return;
}
visit[i][j] = true;
dfs(i-1, j-1, n+1);
dfs(i-1, j, n+1);
dfs(i-1, j+1, n+1);
dfs(i, j-1, n+1);
dfs(i, j+1, n+1);
dfs(i+1, j-1, n+1);
dfs(i+1, j, n+1);
dfs(i+1, j+1, n+1);

if(n == 0){
count++;
}
return;
}

600
デフォルトの名無しさん[sage]   投稿日:2017/01/06 18:06:18  ID:XtKi9eaG.net(2)

601
デフォルトの名無しさん[]   投稿日:2017/01/06 18:36:23  ID:TSHa+AxL.net(16)
Wrong Answerになっちゃうんだけど。

602
デフォルトの名無しさん[]   投稿日:2017/01/06 18:38:07  ID:TSHa+AxL.net(16)
例題については正しい答えが計算されるんだけど。

603
デフォルトの名無しさん[sage]   投稿日:2017/01/06 18:43:00  ID:LxnclcVs.net(2)
よかったね

604
デフォルトの名無しさん[]   投稿日:2017/01/06 20:15:02  ID:TSHa+AxL.net(16)
>277

ソースレベルで再帰を除去する方法が知りたいんですが。

605
デフォルトの名無しさん[]   投稿日:2017/01/06 20:22:33  ID:TSHa+AxL.net(16)
秋葉らのプログラムでもWrong Answerになっていまします。

入出力の問題のようですね。

606
デフォルトの名無しさん[]   投稿日:2017/01/06 20:27:59  ID:TSHa+AxL.net(16)
入出力の問題ってやっかいですね。
出力がどうなっているかとかPOJでは調べられないんですか?

607
デフォルトの名無しさん[]   投稿日:2017/01/06 20:41:27  ID:TSHa+AxL.net(16)
なんなんだろう?

scanf,printfを使っていたらダメだったのが、cinとcoutにしたらOKになった。

608
デフォルトの名無しさん[]   投稿日:2017/01/08 12:26:37  ID:E98VLsZL.net(26)
F(p, n, r) の計算量を教えてください。

n: 整数
p, r: 整数配列(インデックス0からn-1)

F(p, n, r):
■■if r[n] ≧ 0:
■■■■return r[n]
■■if n == 0:
■■■■q = 0
■■else:
■■■■q = -∞
■■■■for i = 1 to n:
■■■■■■q = max(q, p[i] + F(p, n-i, r))
■■r[n] = q
■■return q

609
デフォルトの名無しさん[sage]   投稿日:2017/01/08 12:31:27  ID:0mVP2hZ6.net(4)
O(n^2)

610
デフォルトの名無しさん[sage]   投稿日:2017/01/08 12:32:34  ID:0mVP2hZ6.net(4)

611
デフォルトの名無しさん[]   投稿日:2017/01/08 13:51:15  ID:E98VLsZL.net(26)
>286-287

ありがとうございます。

でも解説されていませんね。

612
デフォルトの名無しさん[]   投稿日:2017/01/08 13:57:19  ID:E98VLsZL.net(26)
どうやって計算量を見積もるんですか?

何を単位にするんですか?

613
デフォルトの名無しさん[]   投稿日:2017/01/08 14:06:13  ID:E98VLsZL.net(26)
T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)

と解けばいいんですかね?

614
デフォルトの名無しさん[]   投稿日:2017/01/08 14:07:36  ID:E98VLsZL.net(26)
T(n) = c1 + c2*n + T(n-1)
T(0) = c3

この漸化式の解を求めればいいんですかね?

615
デフォルトの名無しさん[]   投稿日:2017/01/08 14:12:15  ID:E98VLsZL.net(26)
T(n)
=
[T(n) - T(n-1)] + [T(n-2) - T(n-3)] + … + [T(1) - T(0)] + T(0)
=
[c1 + c2*n] + [c1 + c2*(n-1)] + … + [c1 + c2*1] + c3
=
c1*n + c2*(1/2)*n*(n+1) + c3
=
Θ(n^2)

おお、あってるっぽいですね。

616
デフォルトの名無しさん[]   投稿日:2017/01/08 14:20:56  ID:E98VLsZL.net(26)
>290-292
は我ながら明解な解答ですが、

教科書では、以下のように導出しています。
この導出がよく分からないのですが。

「以前に解かれている部分問題を解くための再帰は直ちに戻るので、Fは
各部分問題をただ1度だけ解く。この手続きはサイズが0,1,....,nの部分問題
を解く。サイズがnの部分問題を解くために、for文がn回繰り返される。したがって、
Fの再帰呼び出し全体における、このfor文の繰り返し回数は等差数列を形成し、
総繰り返し回数はΘ(n^2)となる。」

617
デフォルトの名無しさん[]   投稿日:2017/01/08 14:26:56  ID:E98VLsZL.net(26)
あーあ、分かりました。

T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)

このあたりのことを言っているんですね。

618
デフォルトの名無しさん[sage]   投稿日:2017/01/08 14:27:53  ID:rSxBm0q1.net(2)
馬鹿には無理

619
デフォルトの名無しさん[]   投稿日:2017/01/08 14:28:32  ID:E98VLsZL.net(26)
>289

for文の繰り返し回数=計算量ですね。

620
デフォルトの名無しさん[]   投稿日:2017/01/08 14:29:42  ID:E98VLsZL.net(26)
結局自分ですべて解決してしまいました。

621
デフォルトの名無しさん[sage]   投稿日:2017/01/08 17:12:11  ID:8OGZNgRf.net(2)
よくやった
褒美として自分専用のスレを立てる権利をやろう

622
デフォルトの名無しさん[sage]   投稿日:2017/01/08 18:45:26  ID:KkEYpXLY.net(2)
命名ID:E98VLsZは俺様

623
デフォルトの名無しさん[]   投稿日:2017/01/08 20:55:21  ID:E98VLsZL.net(26)
プログラミングコンテストチャレンジブック

p.45 Best Cow Lineっていう問題の解答のプログラムって無駄がありますよね。

この本を難しいという人がいますが、そんなに難しいですかね?

624
デフォルトの名無しさん[]   投稿日:2017/01/08 22:46:42  ID:E98VLsZL.net(26)
プログラミングコンテストチャレンジブック
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
最強最速アルゴリズマー養成講座

この3冊に共通していることですが、日本語が下手ですよね。

一番ひどいのが

最強最速アルゴリズマー養成講座

ですね。

625
デフォルトの名無しさん[]   投稿日:2017/01/08 22:50:51  ID:E98VLsZL.net(26)
一番面白いのは、

プログラミングコンテストチャレンジブック

だと思いますけど、例えば、貪欲法でなぜうまくいくのかの証明が書いてないですね。

626
デフォルトの名無しさん[sage]   投稿日:2017/01/08 22:51:13  ID:Qw43e7Zm.net(2)
ここはプログラミング問題集書評のスレなの?

627
デフォルトの名無しさん[]   投稿日:2017/01/09 06:08:00  ID:JOAqSyBk.net(2)
>301
うむ
日本語下手なのはもちろん英語も下手みたいだな

628
デフォルトの名無しさん[sage]   投稿日:2017/01/09 06:09:36  ID:cSodeH17.net(2)
頭の使い方が下手というかそもそも頭が不自由なんだろう

629
デフォルトの名無しさん[]   投稿日:2017/01/09 10:59:50  ID:TqLncjlX.net(12)
アルゴリズムイントロダクションの練習問題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]

630
デフォルトの名無しさん[]   投稿日:2017/01/09 11:02:45  ID:TqLncjlX.net(12)
15.1-2

反例

p[1] = 1
p[2] = 5
p[3] = 7

631
デフォルトの名無しさん[]   投稿日:2017/01/09 13:21:16  ID:TqLncjlX.net(12)
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)と書いてあるんですかね?

632
デフォルトの名無しさん[]   投稿日:2017/01/09 13:34:48  ID:TqLncjlX.net(12)
配列を使わないと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)ですよね。

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

http://imgur.com/WUQMG8R.jpg

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

ですね。

633
デフォルトの名無しさん[]   投稿日:2017/01/09 13:37:23  ID:TqLncjlX.net(12)
あ、ひっかけがありましたね。
訂正します:

n > 0 のとき、

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

n = 0 のとき

#V = n + 1
#E = 0

ですね。

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

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

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

と書ける。

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

本当にこんな比較的簡単にみえる結果が1955年という比較的最近になって発見された
のでしょうか?

635
デフォルトの名無しさん[]   投稿日:2017/01/09 15:37:47  ID:4OeNzyzM.net(2)
>308
フィボナッチだろ
√5が出て来る公式
O(1)になるかも試練が

636
デフォルトの名無しさん[sage]   投稿日:2017/01/09 15:46:27  ID:FSSb8O2Z.net(2)
>311
      r ‐、
      | ○ |         r‐‐、
     _,;ト - イ、      ∧l☆│∧  良い子の諸君!
    (⌒`    ⌒ヽ   /,、,,ト.-イ/,、 l  
    |ヽ   ~~⌒γ ⌒ ) r'⌒ `!´ `⌒) よく頭のおかしい数学者気取りのバカが
   │ ヽー―'^ー-'  ( ⌒γ ⌒~~ / 「誰も気付かなかった事を発見したことを発表」とほざくが
   │  〉    |│  |`ー^ー― r' | 大抵それは「先人が思いついたけどあえて発表しなかった」ことだ
   │ /───| |  |/ |  l  ト、 |  王道が何故面白いか理解できない人間に面白い話は
   |  irー-、 ー ,} |    /     i 作れないぞ!
   | /   `X´ ヽ    /   入  |

637
デフォルトの名無しさん[]   投稿日:2017/01/10 20:16:10  ID:Zd0v4023.net(2)
アルゴリズムイントロダクションが難しいという人がいますけど、
この本は馬鹿丁寧に書かれていますよね。

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

「書きすぎ」れば分かりやすくなると思い込んでいますね、著者らは。

638
デフォルトの名無しさん[sage]   投稿日:2017/01/10 20:19:42  ID:kxFYGz06.net(2)
http://hissi.org/read.php/tech/20160614/U2lCYS9zNTM.html

マジ基地だな。壊れたレコードかよ。

639
デフォルトの名無しさん[sage]   投稿日:2017/01/13 21:58:42  ID:wiy2qrIv.net(2)
プログラミング言語のパーサーってどういう仕組みで動いてるんですか?
文字列をトークンの配列に分ける
特定のパターンにマッチするトークンの部分集合をひとまとめにして新しいトークンに置き換える
再帰的に同じ事を繰り返す
こんな感じ?

640
デフォルトの名無しさん[sage]   投稿日:2017/01/13 22:37:46  ID:+ExxsU2F.net(2)

641
デフォルトの名無しさん[sage]   投稿日:2017/01/14 00:10:28  ID:H4kTcvBH.net(2)
>317
これ考えた奴は天才だな

642
デフォルトの名無しさん[sage]   投稿日:2017/01/16 17:57:37  ID:YH2Bx58z.net(2)
Lisperか
BNF

643
デフォルトの名無しさん[sage]   投稿日:2017/01/19 09:40:05  ID:uhfgjGGl.net(2)

644
デフォルトの名無しさん[sage]   投稿日:2017/05/14 13:16:07
類似スレ検索とかのアルゴリズムって何がいいのかな?
編集距離とか数字部分のマスキングくらいしか浮かばない
形態素解析して要素の一致率とかもあるみたいだけど、スレタイみたいな短い文字じゃ弱そう

645
デフォルトの名無しさん[sage]   投稿日:2017/05/14 13:20:48
むしろ短くて重要な単語が多いスレタイこそ一致率うまく働きそうか
毎回評価してたら検索速度悪そうだけど

646
デフォルトの名無しさん[sage]   投稿日:2017/05/14 13:56:17
Baka ha sinanakya
Naoranai
Fucky ou

647
[]   投稿日:0000/00/00 00:00:00

648
デフォルトの名無しさん[]   投稿日:2017/05/26 14:08:00  ID:fOPo0M5r.net(4)
アルゴリズムイントロダクション

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

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

例えば、p.506定理22.9とか。

649
デフォルトの名無しさん[]   投稿日:2017/05/26 19:39:06  ID:GnitEmTF.net
当たり前のことを2chで指摘して回りくどくdisっていますね。
なんなんですか?あなた。
例えば、 >324 とか。

650
デフォルトの名無しさん[sage]   投稿日:2017/05/26 21:10:54  ID:ovKX6RUR.net(2)
>324
当たり前が何故当たり前なのかを知るのは割と重要だが。

651
デフォルトの名無しさん[]   投稿日:2017/05/26 22:50:21  ID:fOPo0M5r.net(4)
>324

しかも「証明」が長い。当たり前のことを長々と書いている。
その「証明」自体も意外性ゼロ。

652
デフォルトの名無しさん[]   投稿日:2017/05/26 22:52:14  ID:fOPo0M5r.net(4)
しかも徹底していない。

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

基準がさっぱりわからない。

653
デフォルトの名無しさん[sage]   投稿日:2017/05/26 22:52:58  ID:ovKX6RUR.net(2)
初級アルゴリズム本持ち出して何なんですか言われてもねぇ。。。
物足りなかったら上のクラスの本買えば?

654
デフォルトの名無しさん[]   投稿日:2017/05/26 23:04:15  ID:fOPo0M5r.net(4)
とにかくしつこい本。

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

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

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

結局、教科書の書き手として優れていない。


655
デフォルトの名無しさん[]   投稿日:2017/05/27 03:04:18  ID:V3ffhZkY.net
きっとアスペなんだろう

656
デフォルトの名無しさん[sage]   投稿日:2017/05/27 03:30:20  ID:6GQ16ypm.net
アルゴリズムでは、セジウィックが有名。他に、

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

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

657
デフォルトの名無しさん[sage]   投稿日:2017/05/27 05:56:26  ID:0xIYYFUk.net

658
デフォルトの名無しさん[]   投稿日:2017/05/27 08:08:34  ID:tcRpjIho.net(3)
浅野孝夫の新しく出た2冊の本はどうですか?

659
デフォルトの名無しさん[]   投稿日:2017/05/27 11:29:04  ID:tcRpjIho.net(3)
アルゴリズムイントロダクションは訳もひどいね。

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

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

本当に理解して訳しているか?

660
デフォルトの名無しさん[]   投稿日:2017/05/27 11:54:19  ID:tcRpjIho.net(3)
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 の先行点では、もちろんない。

661
デフォルトの名無しさん[sage]   投稿日:2017/05/27 13:19:03  ID:olQh0zw8.net
>333
徳永乙

662
デフォルトの名無しさん[sage]   投稿日:2017/05/27 14:45:49  ID:m5ivKvT+.net
本ばかり読んでコードも書かない典型だな

663
デフォルトの名無しさん[sage]   投稿日:2017/05/31 19:10:09  ID:uNlt1YRD.net(2)
今扱ってるライブラリのコンストラクタとか生成系のメソッドとかの引数が多すぎるんで何とかしたいんだがビルダーパターンぐらいしかないのかな
今は引数用の構造体を用意して成のメソッドの呼び出し時に構造体を参照させるようにしてるんだが、お前らどう思う?

664
デフォルトの名無しさん[sage]   投稿日:2017/05/31 19:13:07  ID:uNlt1YRD.net(2)
>339
s/成のメソッド/生成のメソッド

665
デフォルトの名無しさん[sage]   投稿日:2017/05/31 22:35:13  ID:NSe5u++m.net
クラスを作りまくって引数を減らすんだよ

666
デフォルトの名無しさん[sage]   投稿日:2017/06/01 07:33:57  ID:9lL7NugS.net
まあ、ファクトリかビルダだろうな

引数をオーバーライドメソッドでなるべく少なくなる工夫しつつ

667
デフォルトの名無しさん[]   投稿日:2017/06/01 07:40:31  ID:PJoLYMb9.net
グラフ理論のアルゴリズムを実装したときに、正しいかどうか
チェックするのって、グラフを用意しなきゃならなくて大変だけど
サンプルのグラフってどこかに公開されていないの?

668
デフォルトの名無しさん[sage]   投稿日:2017/06/01 08:27:11  ID:RM67mdjD.net
>341
>342
やっぱそれぐらいしかないか
レスさんくす

669
デフォルトの名無しさん[sage]   投稿日:2017/06/01 09:01:58  ID:dZ2VO+v4.net
>343

Knuth先生のThe Stanford Graphbase

http://www-cs-staff.stanford.edu/~knuth/sgb.html

670
デフォルトの名無しさん[sage]   投稿日:2017/06/01 09:26:44  ID:bUIwnMhK.net
ダイクストラなどのグラフは、Python

671
デフォルトの名無しさん[]   投稿日:2017/06/05 16:05:46  ID:gPC56aZq.net(4)
2つのグラフが同型かどうか判定するアルゴリズムを教えてください。

672
デフォルトの名無しさん[sage]   投稿日:2017/06/05 18:35:40  ID:Vm0ObO74.net
ちょっと手間を減らすなら、次数でソートしたりゴニョゴニョできるけど、NPだからあとは力技

673
デフォルトの名無しさん[sage]   投稿日:2017/06/05 19:30:33  ID:SUt02FhH.net
最終的に力業になることが分かってる問題って悲しいよね。

674
デフォルトの名無しさん[sage]   投稿日:2017/06/05 20:28:56  ID:gPC56aZq.net(4)
>348-349

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

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

効率的なアルゴリズムが存在しない場合でも、小さい問題は解けるわけですから、
それなりの工夫でもいいから、教科書に載せてほしいです。

675
デフォルトの名無しさん[sage]   投稿日:2017/06/05 20:36:06  ID:gPC56aZq.net(4)
>348-349

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

効率的なアルゴリズムが存在しない問題の場合、教科書にはアルゴリズムが
載っていないことが多いと思います。自分で力任せのプログラムを書ける場合
はいいですが、力不足で力任せのプログラムすら書けない場合って困りますね。

676
デフォルトの名無しさん[sage]   投稿日:2017/06/05 21:01:13  ID:sad0uPoZ.net
>347
networkXっていうPythonのグラフアルゴリズムのライブラリに、グラフ同型判定の関数があるよ。
is_isomorphic()
ソースコードも見れるから、実装の参考にしては。
VF2アルゴリズムというのを使っているらしい。どういうのかは、知らない。。

677
デフォルトの名無しさん[sage]   投稿日:2017/06/05 21:17:56  ID:gPC56aZq.net(4)
>352

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

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

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

678
デフォルトの名無しさん[sage]   投稿日:2017/06/08 13:28:45  ID:oPuedIYN.net
>352
thx

679
デフォルトの名無しさん[]   投稿日:2017/06/10 01:09:12  ID:yRjB/26o.net
セジウィックのアルゴリズムCはコルメン他の本とは対極にあるような本だね。
どっちもどっち。

680
デフォルトの名無しさん[]   投稿日:2017/06/10 22:49:54  ID:bkNNwNFI.net
セジウィックのアルゴリズムCは言葉足らず。


681
デフォルトの名無しさん[]   投稿日:2017/06/11 08:24:40  ID:7PvmoOJK.net(2)
セジウィックのアルゴリズムCは定義がダメダメ。

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

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

682
デフォルトの名無しさん[]   投稿日:2017/06/11 11:00:58  ID:7PvmoOJK.net(2)
セジウィックのアルゴリズムCは、訳も最低。

683
デフォルトの名無しさん[]   投稿日:2017/06/16 18:04:24  ID:ixzzoI9b.net(3)
浅野孝夫著『アルゴリズムの基礎とデータ構造 数理とCプログラム』(近代科学社)

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

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

684
デフォルトの名無しさん[]   投稿日:2017/06/16 18:08:47  ID:1eQLQexT.net(2)
javaの逆ポートだろう

685
デフォルトの名無しさん[]   投稿日:2017/06/16 18:30:17  ID:ixzzoI9b.net(3)
浅野孝夫著『アルゴリズムの基礎とデータ構造 数理とCプログラム』(近代科学社)

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

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

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

686
デフォルトの名無しさん[]   投稿日:2017/06/16 18:31:46  ID:ixzzoI9b.net(3)
コマンドプロンプトからコマンドを実行してコンパイルをしたりする原始的なやり方
は避けたいです。

687
デフォルトの名無しさん[]   投稿日:2017/06/16 18:47:18  ID:1eQLQexT.net(2)
なんだ
ステマか

688
デフォルトの名無しさん[sage]   投稿日:2017/06/16 20:42:10  ID:1imKhLwB.net
原始的なやり方×
基本的なやり方〇

689
デフォルトの名無しさん[sage]   投稿日:2017/06/16 20:54:00  ID:RYT773NB.net
探せば学習用のC言語インタプリタとかあるんじゃない

690
デフォルトの名無しさん[sage]   投稿日:2017/06/16 21:27:28  ID:vP51FB3m.net
ちょっとサンプルコードを走らせるかって程度なら
Online IDEとか使えばよいのに

691
デフォルトの名無しさん[sage]   投稿日:2017/06/16 21:42:24  ID:SNTjPZEm.net
そもそも何でファイルごとにわざわざプロジェクト作るような原始的なことやってるの

692
デフォルトの名無しさん[sage]   投稿日:2017/06/16 22:44:29  ID:e6Uo8nQP.net
mainの数だけプロジェクトが必要だから?

693
デフォルトの名無しさん[sage]   投稿日:2017/06/17 15:06:03  ID:SdcHR0BJ.net
プロセス増えるだけだからプロジェクトは増やさなくてもいいんじゃね

694
デフォルトの名無しさん[]   投稿日:2017/06/17 18:14:18  ID:DtePX3I4.net(5)
アルゴリズムとデータ構造の本のソースコードを見ると、よくグローバル変数を
多用していて非常に分かりにくいことが多いです。

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

695
デフォルトの名無しさん[]   投稿日:2017/06/17 18:18:02  ID:DtePX3I4.net(5)
例えば、

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

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

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

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

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

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

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

696
デフォルトの名無しさん[sage]   投稿日:2017/06/17 18:18:09  ID:n14YEU6w.net(2)
サンプルだから

697
デフォルトの名無しさん[sage]   投稿日:2017/06/17 18:19:41  ID:n14YEU6w.net(2)
>371
Javaしか使ったことない人が知ったかぶりでCの本出すからそうなる
捨てろ

698
デフォルトの名無しさん[]   投稿日:2017/06/17 18:19:49  ID:DtePX3I4.net(5)
全然、プログラム作りの参考になりません。

ただ、例外もあります。

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

699
デフォルトの名無しさん[]   投稿日:2017/06/17 18:21:15  ID:DtePX3I4.net(5)
>373

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

700
デフォルトの名無しさん[]   投稿日:2017/06/17 20:50:11  ID:DtePX3I4.net(5)
そういえば、茨木俊秀の本のプログラムもひどかったような。

701
デフォルトの名無しさん[sage]   投稿日:2017/06/17 22:37:25  ID:tNCJKlzg.net
グローバル変数を避けようとかはソフトウェア工学の話で、コンピューター科学とは別の分野なんだよ。

702
デフォルトの名無しさん[]   投稿日:2017/06/17 23:06:32  ID:L9yKSdqC.net
ソフトウェア工学の基本すら知らないんですかね?

703
デフォルトの名無しさん[sage]   投稿日:2017/06/18 00:34:44  ID:o43mtcr6.net
グローバル変数を使った方が、説明しやすいとか、
ソースコードがわかりやすいとか

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

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

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

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

704
デフォルトの名無しさん[sage]   投稿日:2017/06/18 12:26:58  ID:HTlYPuIB.net
掲示板のTPO弁えない人にTPO語ってもしょうがないよ

705
デフォルトの名無しさん[]   投稿日:2017/06/18 12:39:15  ID:4GAQ5Lgy.net(3)
グローバル変数を明らかに、分かりにくいやり方で使っています。

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

706
デフォルトの名無しさん[]   投稿日:2017/06/18 13:30:23  ID:4GAQ5Lgy.net(3)
もしかして、理論ばかりに興味があり、プログラムを作ったことがないんですかね?

707
デフォルトの名無しさん[sage]   投稿日:2017/06/18 14:37:44  ID:7v+ppDWb.net
プログラム教本ではなくアルゴリズム解説本だからでしょ
擬似言語で書いている場合のが多いと思うけど

708
デフォルトの名無しさん[]   投稿日:2017/06/18 15:37:30  ID:xPH4G83l.net
最初から完成してたらおまいらの仕事無くなっちゃうだろ

709
デフォルトの名無しさん[]   投稿日:2017/06/18 18:10:10  ID:L/LJrXI/.net
楽器やってるひとがいってたよ。自分がつかえる技術を全部つかうわけじゃない

710
デフォルトの名無しさん[]   投稿日:2017/06/18 20:13:26  ID:4GAQ5Lgy.net(3)
浅野孝夫の本。

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

プログラムは巧妙。

711
デフォルトの名無しさん[sage]   投稿日:2017/06/18 20:48:27  ID:wscBwMor.net
こんなところに日記書く人って、相当追い詰められてるんだろうな。

712
デフォルトの名無しさん[sage]   投稿日:2017/06/19 04:29:40  ID:+M9YR/5M.net
こんなところだから何書いてもいいよ

713
デフォルトの名無しさん[sage]   投稿日:2017/06/19 09:50:06  ID:JRZAs/i8.net
ステマよりグロい

714
デフォルトの名無しさん[]   投稿日:2017/06/19 12:02:27  ID:0IiK5rsw.net
浅野孝夫の本。

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

715
デフォルトの名無しさん[sage]   投稿日:2017/06/19 12:05:01  ID:TXA5MC9f.net
もうおめーが執筆しろよ

716
デフォルトの名無しさん[sage]   投稿日:2017/06/19 13:13:41  ID:YgkoP+sD.net
コードはあくまで例なので解説が先

717
デフォルトの名無しさん[]   投稿日:2017/06/21 10:56:36  ID:CsbvaOkp.net(6)
http://imgur.com/9QGwvmM.jpg
http://imgur.com/j3Dp32V.jpg
http://imgur.com/iJhKoqM.jpg

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

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

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

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

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

718
デフォルトの名無しさん[]   投稿日:2017/06/21 11:00:57  ID:CsbvaOkp.net(6)
訂正します:

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

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

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

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

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

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

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

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

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

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

720
デフォルトの名無しさん[sage]   投稿日:2017/06/21 12:35:50  ID:TkpRSZSL.net(4)
>395
自分の想像力の欠如で批判しないほうがいいよ

721
デフォルトの名無しさん[sage]   投稿日:2017/06/21 12:37:14  ID:L1LFWazB.net
外国には「たのしいRuby」が無い

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

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

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

722
デフォルトの名無しさん[sage]   投稿日:2017/06/21 12:53:00  ID:TkpRSZSL.net(4)
>394
幅優先探索わかる?

723
デフォルトの名無しさん[sage]   投稿日:2017/06/21 12:54:37  ID:Y4WM7moX.net
>394
3枚目は補木辺があって2部グラフではないので、
別におかしくないのでは

724
デフォルトの名無しさん[]   投稿日:2017/06/21 13:14:54  ID:CsbvaOkp.net(6)
>399

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

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

725
デフォルトの名無しさん[sage]   投稿日:2017/06/21 13:31:42  ID:srnzKpaS.net
松坂君のアスペ日記3

Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net
Daniel Marcus Graph Theory を読む。 /数学板

726
デフォルトの名無しさん[]   投稿日:2017/06/21 13:33:59  ID:CsbvaOkp.net(6)
要するに、↓が間違っているわけです。

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

727
デフォルトの名無しさん[sage]   投稿日:2017/06/21 13:55:32  ID:BP6mUhEj.net
ここじゃなくて著者なり出版社なりに連絡しなよ
その方がちゃんと議論できるだろうし修正されればあとから読む人の為になるよ

728
デフォルトの名無しさん[sage]   投稿日:2017/06/21 14:30:39  ID:TkpRSZSL.net(4)
>400
幅優先で探索木作ったら同じ深さを結ぶ補木辺ができるから二部グラフでないことがわかる

729
デフォルトの名無しさん[sage]   投稿日:2017/06/21 16:12:29  ID:e3wPbus7.net
>394
三枚目の図は、反例になっていない。
あなたが幅優先探索を理解できていないだけで、書籍の記述は間違っていないよ。
根でない2つの頂点は、どちらも、根から辺が張られていて、根と隣接しているのだから、同じ深さの位置にある。

730
デフォルトの名無しさん[]   投稿日:2017/06/21 18:57:35  ID:CsbvaOkp.net(6)
あ、勘違いしました。

無向グラフでしたね。

731
デフォルトの名無しさん[sage]   投稿日:2017/06/21 19:28:34  ID:TkpRSZSL.net(4)
教科書だって間違いはいくらでもある。
だからといって、間違いらしきものを見つけて喜々としてあげつらうのではなく、
自分の解釈ではこうだが違うのだろうかという態度で質問しておけばよかったね。

732
デフォルトの名無しさん[sage]   投稿日:2017/06/21 22:04:49  ID:GPdgYp3Z.net
何がいんだろ

733
デフォルトの名無しさん[]   投稿日:2017/06/23 09:05:15  ID:0OdP20aK.net
>393-394
他人の誤りを指摘するときに
自分でも誤るとか恥ずかしくないか

734
デフォルトの名無しさん[sage]   投稿日:2017/06/23 13:07:58  ID:IBCt0Ik9.net
間違いを恐れるな

735
デフォルトの名無しさん[sage]   投稿日:2017/06/23 13:38:13  ID:8e+v7OlS.net
馬鹿、アスペを恐れるな

736
デフォルトの名無しさん[]   投稿日:2017/06/23 19:23:07  ID:vbPiU/7d.net
KIZLA7]]]

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

737
デフォルトの名無しさん[]   投稿日:2017/06/26 15:07:57  ID:wjem+ipT.net(4)
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』(近代科学社)ですが、この
本には強連結成分分解のアルゴリズムは書いてあるのですが、その正しさについて
の説明がありません。

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

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

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

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

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

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

740
デフォルトの名無しさん[]   投稿日:2017/06/26 15:27:14  ID:H+izVTcm.net
ステマ乙としか

741
デフォルトの名無しさん[]   投稿日:2017/06/26 15:32:39  ID:wjem+ipT.net(4)
ところで、LEDAというライブラリはお勧めですか?

742
デフォルトの名無しさん[sage]   投稿日:2017/06/26 16:23:39  ID:xVfkWcpc.net
病人が粘着してる
更新情報
・スレッド一覧ページで過去ログのタイトル検索・一覧表示ができるようになりました(2016/1/20)
NGワード登録
登録する
スレッド内検索

プログラム板 タイトル検索

このスレッドが人気です(実況系)
NHK総合を常に実況し続けるスレ 135244 原発推進 (969)NHK実況
おはよう!時代劇 暴れん坊将軍4 #42(第45話)[字][再] (648)テレ朝実況
映画天国LGBT映画祭『パレードへようこそ』★2 (474)NTV実況
月曜から夜ふかし★5 珍宝館 (825)NTV実況
小林麻央さん追悼番組〜優しく強く生きた34年〜★7 (956)NTV実況
ユ力タイム★2 (731)フジ実況
キスマイBUSAIKU!?【中居ドッキリ緊急SP キスマイはヤラセするか検証】 (871)フジ実況
月曜名作劇場「はぐれ署長の殺人急行2」 3番のりば (975)TBS実況
このスレッドが人気です(ニュース系)
【芸能】海老蔵 悲痛な思い「まお、…あいたい、あいたいよ」★3 (755)音楽・芸能ニュース
【映画】<邦画の質低下>女優の体当たり演技減少が重大な要因か?「現在の大物女優たちは、若い頃、濡れ場を厭わなかったん」 (861)音楽・芸能ニュース
【芸能】海老蔵 悲痛な思い「まお、…あいたい、あいたいよ」★2 (1001)音楽・芸能ニュース
【文化】スクエニが販売する公式「ドラクエ花札」に、以前花札を自作した同人作家が「一切声掛けもなかった」とブチ切れ★15 (1008)ニュー速+
【加計】安倍総理「獣医師会からの強い要望を踏まえ、1校だけに限定して特区を認めたが、中途半端な妥協が国民的な疑念を招いた」★7 (1001)ニュー速+
【芸能】海老蔵 悲痛な思い「まお、…あいたい、あいたいよ」 (1002)音楽・芸能ニュース
【政治】蓮舫代表、なぜ必死なのか。 (1001)ニュー速+
【将棋】藤井四段が勝利!連勝記録を29に伸ばし新記録樹立!・・・第30期竜王戦決勝トーナメント★4 (1001)音楽・芸能ニュース
プログラム板の人気スレ
ふらっと C#,C♯,C#(初心者用) Part129 (430)
Excel VBA 質問スレ Part48 (1001)
Xamarin Part4 (986)
くだすれPython(超初心者用) その34 (565)
【統計分析】機械学習・データマイニング15 (975)
C言語なら俺に聞け 140 (610)
Java入門・初心者質問スレ Part.3 (953)
スレ立てるまでもない質問はここで 148匹目 (348)
オブジェクト指向って自然な文法だな 3 (921)
次世代言語議論スレ[Go Rust Scala Haskell]第5世代 (143)
Visual Studio 2017 Part2 (749)
Pythonのお勉強 Part53 (409)
ねねっちと一緒にプログラムを勉強するスレ第2話 (896)
Swift part10 (979)
JavaScript の質問用スレッド vol.123 (570)
Ruby 初心者スレッド Part 60 (415)
C++相談室 part130 (576)
Git 15 (912)
推薦図書/必読書のためのスレッド 81 (905)
プログラミング言語 Rust 3 (223)
C#, C♯, C#相談室 Part94 (380)
Visual Studio 2015 Part8 (768)
ふらっと C#,C♯,C#(初心者用) Part127 (408)
Androidプログラミング質問スレ revision53 (479)
関数型プログラミング言語Haskell Part30 (703)
☆★Java質問・相談スレッド180★★ (299)
MacでもLinuxでも使えるVisual Studio Code Part2 (152)
C# vs Java どっちが好き? その3 (359)
このサイトについて
このサイトは2ちゃんねるからデータを取得し、表示するサービスです。
画像のインライン表示機能について
画像のURLの後ろにある[画像をインライン表示]をクリックすると、URLの下に表示します。
表示される画像は横幅100pxに縮小されていて、クリックすると原寸で表示します。
このサイトの特徴
1)スレッド内検索ができます
2)レス(「>>1」など)のポップアップができます
3)不適切な言葉を含む投稿を表示しません
4)ページ内で画像を直接表示できます
5)2ch他スレッドへのリンクはタイトル・板名つきでリンクします
6)すっきりとしたデザインで表示します
7)最新スレや前スレをチェック・一覧表示します
8)NGワード機能の搭載でイヤな言葉が目に入りません
9)荒らしを自動チェックします
10)スレッド内・同一IDの書き込みだけ表示できます
11)レスの返事をレスされた発言の下に表示する「まとめビュー」が利用できます
12)シリーズ化したスレッドの一覧を表示します
13)最新のスレッドがある場合はお知らせします
削除について
こちらをご覧ください
機能要望について
現在機能要望受付中です。
問い合わせについて
こちらのページからどうぞ
広告


首都圏の方、ソフトバンク光オススメですよ


このサイトは2ch.scからデータを取得・表示しています。削除などについてはこちらをご覧ください。 アクセスモード:差分取得 - 正常取得 - 8件 - 取得完了