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

1デフォルトの名無しさん 転載ダメ©2ch.net2016/06/19(日) 14:47:29.63ID:5KvSKdL/
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

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

                  京都大学霊長類研究所

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

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

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

2デフォルトの名無しさん2016/06/19(日) 14:52:46.31ID:5KvSKdL/
ttp://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

3デフォルトの名無しさん2016/06/19(日) 15:04:05.74ID:IRfn+3ke
>1 乙

4デフォルトの名無しさん2016/06/19(日) 16:13:42.43ID:gP7jNw8f

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

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

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

8デフォルトの名無しさん2016/06/19(日) 19:46:20.75ID:0JS60cqV
雇われプログラマには不要

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

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

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

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

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

13デフォルトの名無しさん2016/06/20(月) 00:15:53.04ID:VsbhBHIt
>>12
マジかよ

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

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

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

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

16デフォルトの名無しさん2016/06/20(月) 08:05:44.62ID:8yK3ULXk
オブジェクト指向程ではないけどな

17デフォルトの名無しさん2016/06/20(月) 12:30:23.83ID:iz9OSKHh
エンジニアの選定時の足切りにちょうどいいよ

18デフォルトの名無しさん2016/06/20(月) 18:11:51.85ID:Z8Or5TTF
その基準で剪定できるのはかなり恵まれてる気が

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

ここは変だな
「より工学に近い。」
というなら判るが

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

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

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

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

23デフォルトの名無しさん2016/06/20(月) 18:52:50.90ID:1vrQKLsp
なんか計算の理論とかのほうが上みたいな感じじゃない?

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

25デフォルトの名無しさん2016/06/20(月) 18:53:55.59ID:K++azvDQ
自演乙

26デフォルトの名無しさん2016/06/20(月) 19:14:10.85ID:/YC1nkci
>>18
この道30年の修業でようやく一人前

27デフォルトの名無しさん2016/06/20(月) 20:44:30.75ID:EiR/M7I9
寿司職人乙

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

29デフォルトの名無しさん2016/06/20(月) 21:06:41.52ID:taQ4Dh1l
>>28
javaでよくない?

30デフォルトの名無しさん2016/06/20(月) 21:24:25.76ID:iSiyYjqf
javaでconsを表現するときにどうすればいいか知ってますか?

31デフォルトの名無しさん2016/06/20(月) 21:29:28.84ID:1vrQKLsp
>>28

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

32デフォルトの名無しさん2016/06/20(月) 21:47:01.99ID:eW3OX+fW
>>27
植木職人

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

34デフォルトの名無しさん2016/06/20(月) 22:22:55.57ID:m9phkWTx
恵まれてない会社だと全員切る羽目になるって話だろw

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

36デフォルトの名無しさん2016/06/20(月) 22:49:30.47ID:eW3OX+fW
引用できないやつに言われると

37デフォルトの名無しさん2016/06/20(月) 22:50:33.93ID:zvz85rzc
スマホで>>うつのめんどいんだよ

38デフォルトの名無しさん2016/06/22(水) 04:43:48.40ID:W4spe1mc
日立、新型半導体コンピュータの実用化に向けた前処理アルゴリズムを開発
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.76ID:rmORGvIR
日本人の書いたアルゴリズムとデータ構造の本でまともなのって1冊もないの?

40デフォルトの名無しさん2016/06/22(水) 07:53:05.39ID:HSGRYDR8
>>39
まともとは?

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

42デフォルトの名無しさん2016/06/22(水) 08:00:26.15ID:rmORGvIR
杉原厚吉の本は特にひどいと思った。

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

44デフォルトの名無しさん2016/06/22(水) 12:53:15.55ID:YevSrNYa
まともな本とは?
argolythm introduction?
knuth本?
どっちも使い物にならないが

45デフォルトの名無しさん2016/06/22(水) 13:50:41.86ID:WHe3DbmR
>>44
1単語に3箇所もミス入れるなよ

46デフォルトの名無しさん2016/06/22(水) 14:13:53.39ID:sEqYA8cS
根幹のタームの綴りも知らん半可通に何を教われというのか

47デフォルトの名無しさん2016/06/22(水) 14:17:48.79ID:yBOVYSwe
3ヶ所もあると誤り訂正も利かないんじゃまいか

48デフォルトの名無しさん2016/06/22(水) 14:22:16.34ID:EwWgL4+X
バースト発生させんな

49デフォルトの名無しさん2016/06/22(水) 15:16:40.79ID:2z7j8yec
????????????

50デフォルトの名無しさん2016/06/22(水) 21:44:16.49ID:MWgF3eo3
>>44
そんな頭じゃ使いものにならんのも頷けるわ

51デフォルトの名無しさん2016/06/22(水) 22:23:26.91ID:Z2xvvdgM
こんな揚げ足とりの老害から何を学べと?

52デフォルトの名無しさん2016/06/22(水) 22:52:24.12ID:X6XCfxlz
馬鹿の自己紹介されても困る

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

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

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

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

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

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

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

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

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

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

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

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

59デフォルトの名無しさん2016/07/26(火) 06:56:53.95ID:HN1KCMsQ
letの時代がもうすぐそこまで来ているよね

60デフォルトの名無しさん2016/07/26(火) 14:27:18.12ID:z5g/0KTZ
let
-------
 λ

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

https://youtu.be/5m3kPHO2w98

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

62デフォルトの名無しさん2016/09/23(金) 22:16:41.76ID:xWgfj234
誰だ

63デフォルトの名無しさん2016/09/23(金) 22:42:52.63ID:fJ2M8QeM
帰れ

64デフォルトの名無しさん2016/09/24(土) 09:14:59.70ID:osPXZH57
>>61
最初の数分見ましたが..

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

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

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

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

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

以上、感想でした

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

66デフォルトの名無しさん2016/09/24(土) 09:49:16.96ID:B225F1SQ
動画見るの面倒だから3行で説明して

67デフォルトの名無しさん2016/09/24(土) 09:53:53.39ID:trsNBxRI



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

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

69デフォルトの名無しさん2016/09/24(土) 10:46:59.06ID:iZTaxfZT
>隣接するキーの最大値

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

70デフォルトの名無しさん2016/09/24(土) 10:49:01.89ID:9ZsTQHH6
>>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
...
と線形時間になる(やり方あってるよね?)
演算している分、比較だけの線形探索より処理速度が遅くなる

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

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

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

74デフォルトの名無しさん2016/09/25(日) 12:26:29.96ID:3wiQalb8
>>67
ごめん
みたけど
だめだこりゃ

75デフォルトの名無しさん2016/09/25(日) 12:52:11.14ID:NTqjAG/u
>>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デフォルトの名無しさん2016/09/25(日) 14:20:01.83ID:8PebKpFu
>>74
88

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

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

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

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

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

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

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

82デフォルトの名無しさん2016/10/17(月) 15:43:18.44ID:srAFoI0L
>>81
そりゃそうだけど
状態がn個あると過渡状態がたくさんになるのは
辛い

83デフォルトの名無しさん2016/10/17(月) 17:53:14.06ID:75S5w4gh
現在の状態と次の状態のペアにすれば?

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

85デフォルトの名無しさん2016/10/17(月) 23:34:18.88ID:WkWdUImM
>>82には無理ということで

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

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デフォルトの名無しさん2016/12/12(月) 23:13:40.61ID:IcWOSn01
デザインパターンを使って実装すると、年長プログラマーから、またこんなことしやがって的な拒否反応が帰ってくるんだがどうすれば

88デフォルトの名無しさん2016/12/12(月) 23:42:41.92ID:bt79hYqC
排除する他道は無い。

89デフォルトの名無しさん2016/12/12(月) 23:50:03.81ID:hGpJarHd
転職しろ

90デフォルトの名無しさん2016/12/13(火) 03:19:26.34ID:neuXXcOh
若者で組合(または派閥)を創る

91デフォルトの名無しさん2016/12/13(火) 08:14:05.45ID:5xcG7lRc
>>87 がどんなコードを書いたかも分からんのに

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

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

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

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

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

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

というのがあります。

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

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

よろしくお願いします。

95デフォルトの名無しさん2016/12/16(金) 15:34:53.22ID:n8JQ6xp/
assertionじゃね

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

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

97デフォルトの名無しさん2016/12/17(土) 16:09:26.93ID:GDWdcO6h
>>95-96

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

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

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

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

98デフォルトの名無しさん2016/12/17(土) 16:23:27.88ID:GDWdcO6h
>>94

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

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

99デフォルトの名無しさん2016/12/17(土) 16:42:25.50ID:a9hyyPvt
>>97
参考文献ならパクってるとは言わない

100デフォルトの名無しさん2016/12/17(土) 16:43:27.67ID:a9hyyPvt
>>98
こういうのが本当のパクり
訴えられたら負ける

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

102デフォルトの名無しさん2016/12/17(土) 19:29:55.59ID:GDWdcO6h
>>98

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

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

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

103デフォルトの名無しさん2016/12/17(土) 19:31:29.47ID:GDWdcO6h
>>101

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

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

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

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

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

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

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

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

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

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

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

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

>>98

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

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

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

109デフォルトの名無しさん2016/12/17(土) 19:47:48.93ID:YhK78PBA
"error: heap underflow" でググるといっぱい出てくる

110デフォルトの名無しさん2016/12/17(土) 19:57:50.69ID:rDdwnYMe
ID:GDWdcO6h は何をそんなに怒ってるの?
問題が解けなくてイライラしてるだけ?

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

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

111デフォルトの名無しさん2016/12/17(土) 20:55:04.47ID:jmPH7DRp
disるのがはやってるらしい

112デフォルトの名無しさん2016/12/18(日) 00:45:20.51ID:aCKcGLhu
プログラミングコンテスト攻略のための、
アルゴリズムとデータ構造、渡部有隆(わたのべ ゆたか)、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.79ID:VFzWAIXP
めんどくさ

114デフォルトの名無しさん2016/12/18(日) 01:14:58.25ID:aCKcGLhu
漏れも、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、となり複雑だから

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

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

1171142016/12/18(日) 04:57:12.61ID:aCKcGLhu
すまぬ

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

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

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

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

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

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

120デフォルトの名無しさん2016/12/18(日) 11:50:21.36ID:5nrc1ooF
>>114

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

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

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

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

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

123デフォルトの名無しさん2016/12/18(日) 11:57:14.52ID:0+9ctOie
馬鹿ほど自説に拘るw

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

読んでいて楽しい。

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

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

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

127デフォルトの名無しさん2016/12/18(日) 12:20:00.87ID:5nrc1ooF
>>126

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

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

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

129デフォルトの名無しさん2016/12/18(日) 12:37:57.44ID:5nrc1ooF
特許ならありますよね。

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

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

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

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

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

134デフォルトの名無しさん2016/12/18(日) 13:45:05.00ID:RB5DyRP2
リファレンスとしてはどの本がいい?

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

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

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

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

139デフォルトの名無しさん2016/12/18(日) 16:24:54.12ID:+Ko1jSRc
ねーわ、普通のコードが99.99%

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

1411142016/12/18(日) 23:03:56.86ID:aCKcGLhu
>>119
jsdo.it では、全員のソースコードが、サイト内に限り、MITになる

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

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

142デフォルトの名無しさん2016/12/18(日) 23:11:13.26ID:f3M2Oqre

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

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

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

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

145デフォルトの名無しさん2016/12/19(月) 00:01:07.57ID:hSWjQy3F
漏れw

146デフォルトの名無しさん2016/12/19(月) 01:06:56.52ID:8cVREo5r
流石に漏れは笑う

147デフォルトの名無しさん2016/12/19(月) 08:08:43.72ID:judB9f5Y
>>144
全体的なリテラシの底上げがされるまではどうしてもね。

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

149デフォルトの名無しさん2016/12/19(月) 17:37:02.75ID:ic0p/3Yf
長さ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)とかあるので一つには定まってません。
なのでその対応をする関数をおしえてください。

150間違ってたので直します2016/12/19(月) 17:39:59.34ID:ic0p/3Yf
長さ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)とかあるので一つには定まってません。
なのでその対応をする関数をおしえてください。

151デフォルトの名無しさん2016/12/19(月) 17:48:27.12ID:z9XVuDpo
(1,-1,1)の長さが2?

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

意味不明です。

153デフォルトの名無しさん2016/12/19(月) 17:55:40.11ID:yHCszZUX
(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.37ID:yHCszZUX
(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 のときには、条件を満たす列は存在しないね。

155デフォルトの名無しさん2016/12/19(月) 17:58:07.65ID:yHCszZUX
>>150

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

156デフォルトの名無しさん2016/12/19(月) 17:58:17.41ID:hSWjQy3F
>>149
列の最初の数字だけ1足すなり引くなりして返せばいいだけじゃないの?

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

一つに定まらないから、すべての結果を返したいのか、
任意の一つの結果を返したいのか?

158デフォルトの名無しさん2016/12/19(月) 18:02:09.41ID:yHCszZUX
明らかに、

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

159デフォルトの名無しさん2016/12/19(月) 18:50:37.10ID:ic0p/3Yf
0はスタート地点なので

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

161デフォルトの名無しさん2016/12/19(月) 19:06:19.22ID:ic0p/3Yf
>>157
大きさn>0の任意の列aにたいしてf(a)=bでbがn-1の大きさでaと列の中の値が1だけ違う
列を出力する関数fを求めるということです。

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

163デフォルトの名無しさん2016/12/19(月) 19:16:05.63ID:hSWjQy3F
>>161
問題文を鸚鵡返しするんじゃなくて、質問者の質問に答えたら?

164デフォルトの名無しさん2016/12/19(月) 19:23:49.64ID:ic0p/3Yf
>>163
fの出力は列の集合じゃないから普通わかりますよね

165デフォルトの名無しさん2016/12/19(月) 19:31:58.40ID:hSWjQy3F
>>164
fが返すのは集合じゃないってのはどこに書いてある?

166デフォルトの名無しさん2016/12/19(月) 19:34:42.99ID:ic0p/3Yf
>>165
14行上に書いてあります

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

168デフォルトの名無しさん2016/12/19(月) 20:02:25.40ID:ic0p/3Yf
改行コードの数を数えてますか?
文の折り返しと改行とは違いますよ?

169デフォルトの名無しさん2016/12/19(月) 20:17:02.98ID:2q/Y95iw
こりゃまたひどい質問者だな

170デフォルトの名無しさん2016/12/19(月) 20:18:06.39ID:Xx/umGft
課題の丸投げ、しかも「日本語」が

171デフォルトの名無しさん2016/12/19(月) 20:25:56.12ID:ic0p/3Yf
課題という証拠はありますか?
実際課題じゃなくプログラミングしていたら出てきた問題なので
全然課題じゃないです

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

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

174デフォルトの名無しさん2016/12/19(月) 20:50:46.99ID:2q/Y95iw
問題をきちんと記述する能力に欠けている

175デフォルトの名無しさん2016/12/19(月) 20:52:23.54ID:2q/Y95iw
あと、面白い問題だと思うなら、それこそ自分で解くのが楽しいのでは
ここで聞かずに

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

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

178デフォルトの名無しさん2016/12/19(月) 22:34:08.82ID:2q/Y95iw
十分楽しんだからあとは一人で楽しんでくれていいよ

179デフォルトの名無しさん2016/12/19(月) 22:53:51.02ID:Xx/umGft
>>172
馬鹿乙

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

181デフォルトの名無しさん2016/12/19(月) 23:45:15.82ID:Xx/umGft
アルゴリズムは自分で考えるじゃ、ボケ

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

183デフォルトの名無しさん2016/12/21(水) 18:35:54.54ID:UR5SKYPV
数列 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 を求めるプログラムを作れ。

184デフォルトの名無しさん2016/12/21(水) 18:45:01.91ID:trArLuj5
お断りいたします

185デフォルトの名無しさん2016/12/21(水) 18:49:10.92ID:IT3zLaEf
俺も断るわ

186デフォルトの名無しさん2016/12/21(水) 19:41:25.65ID:UR5SKYPV
早くも降参宣言か。

187デフォルトの名無しさん2016/12/21(水) 19:55:05.40ID:RIWp4Ngq
mなんていくらでもあるんじゃないの?
なんで#{m}=1?

188デフォルトの名無しさん2016/12/21(水) 20:06:55.96ID:UR5SKYPV
>>187

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

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

189デフォルトの名無しさん2016/12/21(水) 20:09:57.40ID:trArLuj5
>>183
分からない問題はここに書いてね421 [無断転載禁止]©2ch.net
http://rio2016.2ch.net/test/read.cgi/math/1480771004/493

190デフォルトの名無しさん2016/12/21(水) 20:12:10.26ID:RIWp4Ngq
k=1, l=2で、{m}={2,4,6,8,...}
k=l=1で、{m}=自然数の集合
じゃないの?

191デフォルトの名無しさん2016/12/21(水) 20:16:47.08ID:UR5SKYPV
>>190

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

192デフォルトの名無しさん2016/12/21(水) 20:18:48.11ID:UR5SKYPV
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.67ID:UR5SKYPV
>>191
は勘違いです。

194デフォルトの名無しさん2016/12/21(水) 20:20:14.23ID:UR5SKYPV
a_1 = 1

なので、

b_1 = 0

です。

なので、

{m} = {1}

です。

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

196デフォルトの名無しさん2016/12/21(水) 20:22:42.50ID:RIWp4Ngq
mの条件が足りないんじゃないの?

197デフォルトの名無しさん2016/12/21(水) 20:24:46.75ID:RIWp4Ngq
b_i ≦ b_mさえ満たせばいいんならmなんていくらでもあるでしょ

198デフォルトの名無しさん2016/12/21(水) 20:32:03.58ID:UR5SKYPV
b_m は b_i の最大値です。

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

199デフォルトの名無しさん2016/12/21(水) 20:32:36.28ID:El82f3CE
k≦m≦lという条件が抜けているっぽいね

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

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

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

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

201デフォルトの名無しさん2016/12/21(水) 20:34:58.70ID:UR5SKYPV
>>199

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

202デフォルトの名無しさん2016/12/21(水) 20:39:27.31ID:RIWp4Ngq
不完全な問題出しておいて>>186はないよね

203デフォルトの名無しさん2016/12/21(水) 20:41:22.47ID:UR5SKYPV
>>202

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

204デフォルトの名無しさん2016/12/21(水) 20:42:06.97ID:trArLuj5

205デフォルトの名無しさん2016/12/21(水) 20:43:41.56ID:trArLuj5
マルチ小僧w

206デフォルトの名無しさん2016/12/21(水) 20:44:49.22ID:RIWp4Ngq
>>203
mがkからlの間なんて一言もないんだから不完全

207デフォルトの名無しさん2016/12/21(水) 20:47:08.96ID:UR5SKYPV
>>206

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

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

209デフォルトの名無しさん2016/12/21(水) 20:53:06.55ID:RIWp4Ngq
O(log l)だった

210デフォルトの名無しさん2016/12/21(水) 20:55:14.58ID:UR5SKYPV
>>183

の解答は以下です。

http://imgur.com/rAnp3Ga.jpg

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

211デフォルトの名無しさん2016/12/21(水) 21:27:34.73ID:UR5SKYPV
実は、この問題には続きがあります。

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

このとき、

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

は整数にはならないことを証明せよ。

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

213デフォルトの名無しさん2016/12/21(水) 21:31:37.14ID:xYX0mlO/
提出日はいつですか?

214デフォルトの名無しさん2016/12/21(水) 22:14:54.89ID:auJA5Ak8
またバカな質問者が暴れてるのか

215デフォルトの名無しさん2016/12/21(水) 23:45:05.79ID:mNaBBYjZ
qiitaでやれ

216デフォルトの名無しさん2016/12/23(金) 00:59:54.04ID:gOElNe3R
>>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デフォルトの名無しさん2016/12/23(金) 01:37:11.09ID:gOElNe3R
>>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.27ID:VtFWW7J2
ダイクストラのアルゴリズムの正しさの証明が載っている本で
一番分かりやすい本を教えてください。

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

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

最短路問題の説明で、

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

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

220デフォルトの名無しさん2017/01/02(月) 08:09:15.65ID:03PPbeGI
実数 a が a≠∞のとき、 a + -∞ = -∞
実数 a が a≠-∞のとき、 a + ∞ = ∞

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

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

221デフォルトの名無しさん2017/01/02(月) 09:29:22.45ID:J77W/v0L
それは実無限派の書き方だが,世の趨勢は可能無限
ほどほどに相手をするだけでいいよ

222デフォルトの名無しさん2017/01/02(月) 11:22:57.42ID:03PPbeGI
>>221

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

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

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

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

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

このとき、

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

が成り立つことを示せ。

225デフォルトの名無しさん2017/01/02(月) 12:08:43.26ID:GdcUHK9D
宿題は宿題スレへ

226デフォルトの名無しさん2017/01/02(月) 12:09:56.00ID:GdcUHK9D
宿題は宿題スレへ

227デフォルトの名無しさん2017/01/02(月) 12:22:39.27ID:03PPbeGI
宿題ではないのです。

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

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

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

228デフォルトの名無しさん2017/01/02(月) 12:24:22.04ID:03PPbeGI
もっといい評価はありますでしょうか?

229デフォルトの名無しさん2017/01/02(月) 12:28:36.72ID:GdcUHK9D
判ってるなら効くな

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

発表しましょうか?

231デフォルトの名無しさん2017/01/02(月) 14:21:37.12ID:w6ZCrhsc
どうぞどうぞ

232デフォルトの名無しさん2017/01/02(月) 14:27:23.53ID:yIXUnWg3
>>227
オーダーについてあんま良くわかってないんだろうけどO((n-1)!) なんて書き方はないよ
もし書いたとして、それはO(n!)と同じもの

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

つリーマン球面

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

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

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

235デフォルトの名無しさん2017/01/02(月) 19:05:18.10ID:03PPbeGI
節点 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.40ID:03PPbeGI
第 (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.66ID:03PPbeGI
(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.41ID:03PPbeGI
以上より、第 (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.14ID:03PPbeGI
>>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.44ID:03PPbeGI
したがって、

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

241デフォルトの名無しさん2017/01/03(火) 08:33:06.09ID:3o9M4oho
この狂人ヤバいなw

242デフォルトの名無しさん2017/01/03(火) 08:50:16.82ID:hCDXc7Qp
>>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.04ID:hCDXc7Qp
>>234-238

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

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

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

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

245デフォルトの名無しさん2017/01/03(火) 13:47:58.01ID:hCDXc7Qp
ダイクストラのアルゴリズム:

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.21ID:hCDXc7Qp
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.08ID:hCDXc7Qp
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.27ID:hCDXc7Qp
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.64ID:hCDXc7Qp
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.71ID:hCDXc7Qp
今、 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.21ID:hCDXc7Qp
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.40ID:4i7P3+nF
アルゴリズムイントロダクションって自明なことをわざわざループ不変量を使ったりして、
証明していて、うざすぎますね。

253デフォルトの名無しさん2017/01/05(木) 09:16:52.73ID:4i7P3+nF
通常の数学の本なら自明で済ませるようなことをわざわざ証明している。

254デフォルトの名無しさん2017/01/05(木) 09:57:50.61ID:OZq8Y/OW
このバカ、以前も全く同じこと言って暴れたな。

255デフォルトの名無しさん2017/01/05(木) 10:02:39.43ID:OZq8Y/OW
http://hissi.org/read.php/tech/20160422/cGVtVmVaYUg.html
http://hissi.org/read.php/tech/20160612/YkttemlBQ3Y.html
こいつだ。

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

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

256デフォルトの名無しさん2017/01/05(木) 10:44:28.31ID:W/+CAQrH
数学とコンピュータ科学の区別がつかない厨房だろう

257デフォルトの名無しさん2017/01/05(木) 11:01:45.09ID:4i7P3+nF
クヌースの本なんかだと妙なくどさはない。

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

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

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

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

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

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

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

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

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

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

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

262デフォルトの名無しさん2017/01/05(木) 11:29:47.36ID:W/+CAQrH
結論として4i7P3+nFはNG行き

263デフォルトの名無しさん2017/01/05(木) 11:33:33.85ID:2uA+A+xC
>>253
自明ほど危ういものは無いんだが

264デフォルトの名無しさん2017/01/05(木) 11:40:35.14ID:OZq8Y/OW
例によって ID:4i7P3+nF が発狂しててワロタ

265デフォルトの名無しさん2017/01/05(木) 11:44:36.30ID:4i7P3+nF
>>263

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

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

266デフォルトの名無しさん2017/01/05(木) 11:52:58.57ID:r7KPx/TL
そんな多くねえよちゃんと論文読め

267デフォルトの名無しさん2017/01/05(木) 12:06:11.36ID:2uA+A+xC
自明連発する方が馬鹿なのか

268デフォルトの名無しさん2017/01/05(木) 13:09:24.25ID:c6xYhHVb
>>265
馬鹿丸出し

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

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

270デフォルトの名無しさん2017/01/05(木) 14:56:52.93ID:jagWiFjG
なんでバカって本質に関係ないところでギャーギャー騒ぐの?

271デフォルトの名無しさん2017/01/05(木) 14:58:54.44ID:YjTG1plI
うむ

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

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

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

クヌースの本のように、楽しい本ではない。

273デフォルトの名無しさん2017/01/05(木) 20:37:39.99ID:UiiKd7HR

274デフォルトの名無しさん2017/01/05(木) 22:15:16.24ID:WPj32BYO
書評したければ別のところでやれ

275デフォルトの名無しさん2017/01/06(金) 17:19:30.91ID:TSHa+AxL
再帰の除去についてやり方が詳しく書いてある本を教えてください。

276デフォルトの名無しさん2017/01/06(金) 17:43:03.36ID:TSHa+AxL
プログラミングコンテストチャレンジブック第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デフォルトの名無しさん2017/01/06(金) 18:06:18.89ID:XtKi9eaG

278デフォルトの名無しさん2017/01/06(金) 18:36:23.48ID:TSHa+AxL
Wrong Answerになっちゃうんだけど。

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

280デフォルトの名無しさん2017/01/06(金) 18:43:00.23ID:LxnclcVs
よかったね

281デフォルトの名無しさん2017/01/06(金) 20:15:02.80ID:TSHa+AxL
>>277

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

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

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

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

284デフォルトの名無しさん2017/01/06(金) 20:41:27.59ID:TSHa+AxL
なんなんだろう?

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

285デフォルトの名無しさん2017/01/08(日) 12:26:37.82ID:E98VLsZL
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

286デフォルトの名無しさん2017/01/08(日) 12:31:27.73ID:0mVP2hZ6
O(n^2)

287デフォルトの名無しさん2017/01/08(日) 12:32:34.98ID:0mVP2hZ6

288デフォルトの名無しさん2017/01/08(日) 13:51:15.22ID:E98VLsZL
>>286-287

ありがとうございます。

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

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

何を単位にするんですか?

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

と解けばいいんですかね?

291デフォルトの名無しさん2017/01/08(日) 14:07:36.75ID:E98VLsZL
T(n) = c1 + c2*n + T(n-1)
T(0) = c3

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

292デフォルトの名無しさん2017/01/08(日) 14:12:15.21ID:E98VLsZL
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.92ID:E98VLsZL
>>290-292
は我ながら明解な解答ですが、

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

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

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

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

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

295デフォルトの名無しさん2017/01/08(日) 14:27:53.04ID:rSxBm0q1
馬鹿には無理

296デフォルトの名無しさん2017/01/08(日) 14:28:32.97ID:E98VLsZL
>>289

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

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

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

299デフォルトの名無しさん2017/01/08(日) 18:45:26.96ID:KkEYpXLY
命名ID:E98VLsZは俺様

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

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

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

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

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

一番ひどいのが

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

ですね。

302デフォルトの名無しさん2017/01/08(日) 22:50:51.06ID:E98VLsZL
一番面白いのは、

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

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

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

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

305デフォルトの名無しさん2017/01/09(月) 06:09:36.68ID:cSodeH17
頭の使い方が下手というかそもそも頭が不自由なんだろう

306デフォルトの名無しさん2017/01/09(月) 10:59:50.63ID:TqLncjlX
アルゴリズムイントロダクションの練習問題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.57ID:TqLncjlX
15.1-2

反例

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

308デフォルトの名無しさん2017/01/09(月) 13:21:16.77ID:TqLncjlX
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)と書いてあるんですかね?

309デフォルトの名無しさん2017/01/09(月) 13:34:48.26ID:TqLncjlX
配列を使わないと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.94ID:TqLncjlX
あ、ひっかけがありましたね。
訂正します:

n > 0 のとき、

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

n = 0 のとき

#V = n + 1
#E = 0

ですね。

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

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

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

と書ける。

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

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

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

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

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

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

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

315デフォルトの名無しさん2017/01/10(火) 20:19:42.26ID:kxFYGz06
http://hissi.org/read.php/tech/20160614/U2lCYS9zNTM.html

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

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

317デフォルトの名無しさん2017/01/13(金) 22:37:46.17ID:+ExxsU2F
>>316
Java 再帰下降構文解析超入門
http://qiita.com/7shi/items/64261a67081d49f941e3

ビジュアル構文解析
http://www.csg.ci.i.u-tokyo.ac.jp/~ichikawa/visual_parsing.pdf

318デフォルトの名無しさん2017/01/14(土) 00:10:28.40ID:H4kTcvBH
>>317
これ考えた奴は天才だな

319デフォルトの名無しさん2017/01/16(月) 17:57:37.27ID:YH2Bx58z
Lisperか
BNF

320デフォルトの名無しさん2017/01/19(木) 09:40:05.52ID:uhfgjGGl

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

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

323デフォルトの名無しさん2017/05/14(日) 13:56:17.84ID:CjOSHdvj
Baka ha sinanakya
Naoranai
Fucky ou

324デフォルトの名無しさん2017/05/26(金) 14:08:00.89ID:fOPo0M5r
アルゴリズムイントロダクション

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

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

例えば、p.506定理22.9とか。

325デフォルトの名無しさん2017/05/26(金) 19:39:06.33ID:GnitEmTF
当たり前のことを2chで指摘して回りくどくdisっていますね。
なんなんですか?あなた。
例えば、 >>324 とか。

326デフォルトの名無しさん2017/05/26(金) 21:10:54.45ID:ovKX6RUR
>>324
当たり前が何故当たり前なのかを知るのは割と重要だが。

327デフォルトの名無しさん2017/05/26(金) 22:50:21.07ID:fOPo0M5r
>>324

しかも「証明」が長い。当たり前のことを長々と書いている。
その「証明」自体も意外性ゼロ。

328デフォルトの名無しさん2017/05/26(金) 22:52:14.04ID:fOPo0M5r
しかも徹底していない。

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

基準がさっぱりわからない。

329デフォルトの名無しさん2017/05/26(金) 22:52:58.46ID:ovKX6RUR
初級アルゴリズム本持ち出して何なんですか言われてもねぇ。。。
物足りなかったら上のクラスの本買えば?

330デフォルトの名無しさん2017/05/26(金) 23:04:15.09ID:fOPo0M5r
とにかくしつこい本。

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

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

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

結局、教科書の書き手として優れていない。

331デフォルトの名無しさん2017/05/27(土) 03:04:18.64ID:V3ffhZkY
きっとアスペなんだろう

332デフォルトの名無しさん2017/05/27(土) 03:30:20.38ID:6GQ16ypm
アルゴリズムでは、セジウィックが有名。他に、

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

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

333デフォルトの名無しさん2017/05/27(土) 05:56:26.58ID:0xIYYFUk

334デフォルトの名無しさん2017/05/27(土) 08:08:34.68ID:tcRpjIho
浅野孝夫の新しく出た2冊の本はどうですか?

335デフォルトの名無しさん2017/05/27(土) 11:29:04.28ID:tcRpjIho
アルゴリズムイントロダクションは訳もひどいね。

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

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

本当に理解して訳しているか?

336デフォルトの名無しさん2017/05/27(土) 11:54:19.85ID:tcRpjIho
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 の先行点では、もちろんない。

337デフォルトの名無しさん2017/05/27(土) 13:19:03.94ID:olQh0zw8
>>333
徳永乙

338デフォルトの名無しさん2017/05/27(土) 14:45:49.59ID:m5ivKvT+
本ばかり読んでコードも書かない典型だな

新着レスの表示
レスを投稿する