2ちゃんねる★スマホ版★■掲示板に戻る■全部1-最新50

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

1 :
2016/06/19(日) 14:47:29.63 ID: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.31 ID: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.74 ID:IRfn+3ke
>1 乙
4 :
2016/06/19(日) 16:13:42.43 ID:gP7jNw8f
5 :
2016/06/19(日) 17:17:34.69 ID:ao4WLgfX
ruby って変な人が多いんだね,俺も今 ruby をマスターしようと必死ではあるが
6 :
2016/06/19(日) 17:37:31.60 ID:X+E3gNs8
>>2
盛大な自演だったってこと?
7 :
デフォルトの名無しさん
2016/06/19(日) 19:39:00.16 ID:iKM7Z0CI
Haskellって勉強する意味ある?
実用性はないよね?
8 :
2016/06/19(日) 19:46:20.75 ID:0JS60cqV
雇われプログラマには不要
9 :
デフォルトの名無しさん
2016/06/19(日) 20:49:00.89 ID:iKM7Z0CI
なぜ、HaskellやSchemeをありがたがる人がいるの?
どう考えてもC#とかのほうが生産性が高いのに。
単なるかっこつけ?
10 :
デフォルトの名無しさん
2016/06/19(日) 20:49:49.63 ID:iKM7Z0CI
MITのコンピュータの入門書もSchemeを使っていたりする。
11 :
2016/06/19(日) 20:59:07.46 ID:Axw7zBsF
言語としてのlisp最強論は理解できるけどね。
実用的ではないのは言語自体の問題ではなくてシェアとかサポートする企業の存在とかコミュニティの問題。
12 :
2016/06/19(日) 23:46:31.97 ID:XG1Xog94
haskellやschemeは勉強したくない奴には不要
雇われには言語選択権はないので、かりにそれらがよいものであったとしたとしても、フラストレーションたまるだけだろ

一言でいうなら自分で一から十まで計算を構築するための言語だな
ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要
13 :
デフォルトの名無しさん
2016/06/20(月) 00:15:53.04 ID:VsbhBHIt
>>12
マジかよ
14 :
2016/06/20(月) 00:57:04.30 ID: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.91 ID:1vrQKLsp
HaskellやSchemeの利点は?
少なくとも、分かりにくいよね。
16 :
2016/06/20(月) 08:05:44.62 ID:8yK3ULXk
オブジェクト指向程ではないけどな
17 :
2016/06/20(月) 12:30:23.83 ID:iz9OSKHh
エンジニアの選定時の足切りにちょうどいいよ
18 :
2016/06/20(月) 18:11:51.85 ID:Z8Or5TTF
その基準で剪定できるのはかなり恵まれてる気が
19 :
2016/06/20(月) 18:23:24.04 ID:78XmmaUt
>>14
>今日のプログラミングは、「より科学に近い。

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

やっとまともになったというだけの話。
21 :
デフォルトの名無しさん
2016/06/20(月) 18:35:05.72 ID:1vrQKLsp
コンピュータサイエンスの中でアルゴリズムとデータ構造ってどれくらい重要な科目なの?
22 :
デフォルトの名無しさん
2016/06/20(月) 18:50:31.57 ID:FhfmjeRD
アルゴリズム + データ構造 = プログラム。
ということは。
プログラムの占める割合と等価なのでは。
23 :
デフォルトの名無しさん
2016/06/20(月) 18:52:50.90 ID:1vrQKLsp
なんか計算の理論とかのほうが上みたいな感じじゃない?
24 :
デフォルトの名無しさん
2016/06/20(月) 18:53:47.25 ID:1vrQKLsp
コンピュータサイエンスで最も重要な科目は、コンパイラとかOS?
25 :
2016/06/20(月) 18:53:55.59 ID:K++azvDQ
自演乙
26 :
2016/06/20(月) 19:14:10.85 ID:/YC1nkci
>>18
この道30年の修業でようやく一人前
27 :
2016/06/20(月) 20:44:30.75 ID:EiR/M7I9
寿司職人乙
28 :
2016/06/20(月) 20:58:16.94 ID:amTC+NJd
schemeやらないとアルゴリズムとデータ構造を組み立てるってことがどういうことなのか、コードでわからないだろうな
29 :
デフォルトの名無しさん
2016/06/20(月) 21:06:41.52 ID:taQ4Dh1l
>>28
javaでよくない?
30 :
2016/06/20(月) 21:24:25.76 ID:iSiyYjqf
javaでconsを表現するときにどうすればいいか知ってますか?
31 :
デフォルトの名無しさん
2016/06/20(月) 21:29:28.84 ID:1vrQKLsp
>>28

アルゴリズムとデータ構造の本に疑似コードが載っていることがあるけど、
Scheme風に書かれていることなど決してない。
32 :
2016/06/20(月) 21:47:01.99 ID:eW3OX+fW
>>27
植木職人
33 :
2016/06/20(月) 22:10:02.53 ID:iz9OSKHh
>>18
未経験でも理解出来るならとりあえず地雷の可能性は下がる
34 :
2016/06/20(月) 22:22:55.57 ID:m9phkWTx
恵まれてない会社だと全員切る羽目になるって話だろw
35 :
2016/06/20(月) 22:43:48.30 ID:zvz85rzc
31
そのSICPはschemeでかかれているわけで
昨今のライブラリ重視の観点からいえば、javaがいいっていうのはとおるけど、アルゴリズムかくのにjavaがいいってのは、センスないというか、お手入れ大好きなんだろうな
36 :
2016/06/20(月) 22:49:30.47 ID:eW3OX+fW
引用できないやつに言われると
37 :
2016/06/20(月) 22:50:33.93 ID:zvz85rzc
スマホで>>うつのめんどいんだよ
38 :
2016/06/22(水) 04:43:48.40 ID: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.76 ID:rmORGvIR
日本人の書いたアルゴリズムとデータ構造の本でまともなのって1冊もないの?
40 :
2016/06/22(水) 07:53:05.39 ID:HSGRYDR8
>>39
まともとは?
41 :
デフォルトの名無しさん
2016/06/22(水) 07:59:50.23 ID:rmORGvIR
日本人の書いた本は薄っぺらくて説明も十分ではなく厳密でもなく網羅性もない本ばかりに思う。
42 :
デフォルトの名無しさん
2016/06/22(水) 08:00:26.15 ID:rmORGvIR
杉原厚吉の本は特にひどいと思った。
43 :
2016/06/22(水) 11:07:15.76 ID:DmPvlaR4
>>39
そのものズバリでアルゴリズムとデータ構造という本が岩波から出てる
44 :
2016/06/22(水) 12:53:15.55 ID:YevSrNYa
まともな本とは?
argolythm introduction?
knuth本?
どっちも使い物にならないが
45 :
2016/06/22(水) 13:50:41.86 ID:WHe3DbmR
>>44
1単語に3箇所もミス入れるなよ
46 :
2016/06/22(水) 14:13:53.39 ID:sEqYA8cS
根幹のタームの綴りも知らん半可通に何を教われというのか
47 :
2016/06/22(水) 14:17:48.79 ID:yBOVYSwe
3ヶ所もあると誤り訂正も利かないんじゃまいか
48 :
2016/06/22(水) 14:22:16.34 ID:EwWgL4+X
バースト発生させんな
49 :
2016/06/22(水) 15:16:40.79 ID:2z7j8yec
????????????
50 :
2016/06/22(水) 21:44:16.49 ID:MWgF3eo3
>>44
そんな頭じゃ使いものにならんのも頷けるわ
51 :
2016/06/22(水) 22:23:26.91 ID:Z2xvvdgM
こんな揚げ足とりの老害から何を学べと?
52 :
2016/06/22(水) 22:52:24.12 ID:X6XCfxlz
馬鹿の自己紹介されても困る
53 :
2016/06/24(金) 11:47:43.21 ID:hSLmnyaY
>>19
は?変なのはお前だ
プログラミングは最初から工学的だろ何言ってんだ?

そもそもお前は工学と科学を理解してないから可笑しなことを言うんだ
54 :
2016/07/15(金) 12:10:18.78 ID:P21uCIN+
何ヶ月か前に近代科学社に電話でセジウィックアルゴリズムの第四版の翻訳の予定はありますか、と訊いてみたが無いって返事だったんだよな
書いて欲しいんだがな
55 :
2016/07/16(土) 08:00:53.05 ID:Akpk7DL9
アルゴリズムさえ知ってりゃ動くプログラムは書けるから他は優先度低いと考えてた結果
データ構造すら分からない化石プログラマになってしまった

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

アルゴリズムみたいにオーダー詰める楽しみはないけど…
56 :
2016/07/18(月) 09:37:52.19 ID:YPoLSDg9
両方大事だろ。
データ構造が整理されてないとアルゴリズムも煩雑になるし。
57 :
デフォルトの名無しさん
2016/07/21(木) 23:06:49.37 ID:TpMXx+Na
vEB木の「僕の考えた最強のデータ構造」感が大好きなんだが誰か共感してくれる人いる?
58 :
2016/07/22(金) 07:32:19.08 ID:ot11jjQx
データ構造の基本は、以下の2つと、他にはハッシュがある

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

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

シーケンシャルは、リンクをたどるから、アクセスには時間がかかるけど、
要素の追加・削除では、リンクを付け替えるだけで、要素をずらさないから速い
59 :
2016/07/26(火) 06:56:53.95 ID:HN1KCMsQ
letの時代がもうすぐそこまで来ているよね
60 :
2016/07/26(火) 14:27:18.12 ID:z5g/0KTZ
let
-------
 λ
61 :
2016/09/23(金) 22:08:49.88 ID:oKXONAGb
どうも、お久しぶりです。スモモンガーです。(誰って感じだと思いますがそれで結構です)
以前紹介したアルゴリズムですが、結局全然応用分野は見つかっておりません。
前回は画像処理分野を中心に解説しましたが今回はより簡単に実装ができる
探索分野に絞って動画を作ってみました。つたない動画で大変申し訳ございませんが
見てみていただけたら幸いです。特許などは取得しておりませんのでどうかご自由に
お使いください。長文失礼いたします。痛いのは承知なのですが応用分野を必死に
探しているのでどうかご協力よろしくお願いします。

https://youtu.be/5m3kPHO2w98

以上、どうぞよろしくお願いします
62 :
2016/09/23(金) 22:16:41.76 ID:xWgfj234
誰だ
63 :
2016/09/23(金) 22:42:52.63 ID:fJ2M8QeM
帰れ
64 :
2016/09/24(土) 09:14:59.70 ID:osPXZH57
>>61
最初の数分見ましたが..

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

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

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

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

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

以上、感想でした
65 :
2016/09/24(土) 09:32:41.92 ID:n5/uj8Su
64さん。ありがとうございます。私はこういうスライドを作る機会があまりないのでこんな形になってしまいました。
実は整っているという抽象的な単語を使っていますが、実は定量的にこれを測る方法はまだ思いついていません。
そのほかのご指摘はその通りだと思います。
貴重なご意見ありがとうございます
66 :
2016/09/24(土) 09:49:16.96 ID:B225F1SQ
動画見るの面倒だから3行で説明して
67 :
2016/09/24(土) 09:53:53.39 ID:trsNBxRI


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

まあ、原理は単純なアルゴリズムです
69 :
2016/09/24(土) 10:46:59.06 ID:iZTaxfZT
>隣接するキーの最大値

これをあらかじめ求めておかなきゃならんってのが一番のネックだな。
一般のデータに対する探索だと、バイナリサーチと比較したメリットと言っていたものの大半が消し飛んでしまう。
70 :
2016/09/24(土) 10:49:01.89 ID: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.58 ID:n5/uj8Su
>>69
>>70
確かにキーの最大値を求めるのは線形時間かかります。なのであらかじめ、隣接するキーの最大値が分かっているデータに使用可能です。
探索の最悪時間は線形時間ですが、平均時間はlogのオーダーになるのではないでしょうか。私が不勉強なもので理論的には、示めせませんが多分logのオーダーになると思います。
ソートしなくても探索できるのは差の絶対値を取るからです。動画に入れるのを忘れました。すいません。
計算についてはそれであっています。わざわざご指摘ありがとうございます
72 :
2016/09/25(日) 01:17:16.51 ID:MeFnEkA4
>>71
上でも指摘されているが整っているの定義が不明
二分探査の場合は、存在しないこともlog n で確認可能だが、この手法は整っているの定義次第では存在しない者の確認が非常に時間かかる(ソートされている場合は存在するものと同等だが、そうすると二分探索よりも利点が少なくなる)
平均計算量を求めるのはちと難しそうだけど、格納される値の値域に依存するかな
たぶん、log n 程良くはないと思う
73 :
2016/09/25(日) 09:29:52.06 ID:byM8xGto
>>72
ご指摘ありがとうございます。確かに整っているの定義ができていないのが一番の難点ですよね。いつか勉強して考えたいと思います
74 :
デフォルトの名無しさん
2016/09/25(日) 12:26:29.96 ID:3wiQalb8
>>67
ごめん
みたけど
だめだこりゃ
75 :
2016/09/25(日) 12:52:11.14 ID: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.83 ID:8PebKpFu
>>74
88
77 :
2016/09/26(月) 13:42:01.27 ID:ymOrEJcI
>>61
すもモンがnewton法をガチで知らないのであればnewton法をまず勉強するべき
カンガルーの敵はバイナリではなくnewtonだ
78 :
2016/09/26(月) 20:32:40.67 ID:7l1kSKga
確かにデータ間の差に一様離散分布を使ったのは公平ではなかったです。
なので、データを完全にランダムにして調べてみました。
データはCのrand()%1000000で10000個生成しソートして、
探索の時配列のうちランダムな値を探すキーとし間を線形探索、カンガルー法
バイナリサーチで100回比べてみました。
その結果線形探索では平均比較回数約4963回最大比較回数は9972回でした
カンガルー法は平均比較回数約70回 最大比較回数は111回でした。
バイナリーサーチはやはり一番はやく、平均比較回数約12回、最大比較回数は14回でした
皆さんがご指摘の通りやはりバイナリーサーチが一番はやいようです。
ただ、例えばKMP法が逆行がないから使われているようにカンガルー法も逆行がないので
使うことはできないでしょうか?もし、とんちんかんなこと言ってたらすいません。
79 :
2016/09/26(月) 20:37:55.45 ID:7l1kSKga
>>74
www確かにそうかもしれませんね。
>>77
一応私はニュートン法については知っています。Newton法は求める関数の微分した値を
しっていなければならないとおもうのですが、現実の探索だと関数が微分できないことも
多いかと思います。ちょっと、私が使った例が悪くてsinカーブや円を使ったのがよく
なかったのかもしれません。整っていてソートされていないデータとして扱いやすかったので
sin関数を使ったのであってとくにデータが微分可能である必要はありません。円と
Y切片の交点も中学生でも二次方程式ときゃいいのでもっと簡単にできますが、本来は
多角形とさまざまな図形の交点を探るアルゴリズムです。円を使ったのは例をわかりやすく
したかったからです。
80 :
デフォルトの名無しさん
2016/10/16(日) 18:51:48.49 ID:LqkHCFhg
状態遷移ってどういうステータス持てばいいの?

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

というとき、A と B のほかに AからBになるのを待ってる状態と
BからAになるを待ってる状態の 2つがさらに状態として必要?
過渡状態も状態?
81 :
2016/10/17(月) 07:56:46.27 ID:TukeUWYl
>>80
システムの設計次第。
切り替え中、待ち中が状態として存在するのならプログラムでも状態にすればいい
82 :
2016/10/17(月) 15:43:18.44 ID:srAFoI0L
>>81
そりゃそうだけど
状態がn個あると過渡状態がたくさんになるのは
辛い
83 :
2016/10/17(月) 17:53:14.06 ID:75S5w4gh
現在の状態と次の状態のペアにすれば?
84 :
2016/10/17(月) 21:23:44.83 ID:sc7L52q+
辛かろうが状態が存在するのならしょうがあるまい。
あるいは遷移をアトミックにして遷移中状態そのものを無くすか、遷移中の動作を共通化
できるなら遷移先をパラメータ化して「*への遷移中」という1状態にしてしまうとか。
85 :
2016/10/17(月) 23:34:18.88 ID:WkWdUImM
>>82には無理ということで
86 :
2016/11/05(土) 20:41:10.12 ID: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.61 ID:IcWOSn01
デザインパターンを使って実装すると、年長プログラマーから、またこんなことしやがって的な拒否反応が帰ってくるんだがどうすれば
88 :
2016/12/12(月) 23:42:41.92 ID:bt79hYqC
排除する他道は無い。
89 :
2016/12/12(月) 23:50:03.81 ID:hGpJarHd
転職しろ
90 :
2016/12/13(火) 03:19:26.34 ID:neuXXcOh
若者で組合(または派閥)を創る
91 :
2016/12/13(火) 08:14:05.45 ID:5xcG7lRc
>>87 がどんなコードを書いたかも分からんのに
92 :
2016/12/13(火) 18:53:42.04 ID:MUcELcjh
下手くそがデザインパターンとか使うと逆にこんがらがるからなぁ
老害とどっこいどっこいだろ
93 :
デフォルトの名無しさん
2016/12/13(火) 21:32:18.83 ID:lYWHr0pJ
マルチスレッドで、なんの考えもなくオブザーバー使いまくられて、データ破壊しまくられた時には、本気で殺意を抱いたよ
94 :
デフォルトの名無しさん
2016/12/16(金) 15:12:11.72 ID:kO0vFktz
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』

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

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

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

というのがあります。

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

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

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

ただ、作業やデバッグ用には必須であっても、その本の例示として必要か?と言われれば、確かにいらない気がする。
97 :
デフォルトの名無しさん
2016/12/17(土) 16:09:26.93 ID:GDWdcO6h
>>95-96

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

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

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

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』はお持ちでしょうか?
もし、お持ちでないようでしたら該当箇所の画像をアップロードします。
98 :
デフォルトの名無しさん
2016/12/17(土) 16:23:27.88 ID:GDWdcO6h
>>94

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

http://imgur.com/zKVWzAJ.jpg
http://imgur.com/owa8NkX.jpg
http://imgur.com/NmCczss.jpg
99 :
2016/12/17(土) 16:42:25.50 ID:a9hyyPvt
>>97
参考文献ならパクってるとは言わない
100 :
2016/12/17(土) 16:43:27.67 ID:a9hyyPvt
>>98
こういうのが本当のパクり
訴えられたら負ける
101 :
2016/12/17(土) 18:12:28.79 ID:rDdwnYMe
>>97
他の本も読んでみるとわかると思うけど、プライオリティキューを二分木ヒープで実装するのは定番で、どの本でも大体同じことが書いてある
102 :
デフォルトの名無しさん
2016/12/17(土) 19:29:55.59 ID:GDWdcO6h
>>98

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

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

heapIncreaseKey(A, i, key) を何か別の用途に使う場合があって、そのときに必要に
なるのならば納得しますが。
103 :
デフォルトの名無しさん
2016/12/17(土) 19:31:29.47 ID:GDWdcO6h
>>101

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

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

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

完全にパクりだと思います。
104 :
デフォルトの名無しさん
2016/12/17(土) 19:35:00.61 ID:a9hyyPvt
>>103
参考文献に書いてあるんだからパクリも糞も無い罠
参考文献に書き漏れたら小保方さんみたいに突っ込まれるが
105 :
デフォルトの名無しさん
2016/12/17(土) 19:35:29.11 ID:GDWdcO6h
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の
他のプログラムもおそらくすべて『アルゴリズムイントロダクション』の
プログラムをそのまま使っています。

恥を知れと言いたいです。
106 :
デフォルトの名無しさん
2016/12/17(土) 19:36:34.73 ID:GDWdcO6h
参考文献に文献を挙げれば何でも許されるということはないと思いますが。
107 :
デフォルトの名無しさん
2016/12/17(土) 19:39:42.80 ID:GDWdcO6h
『アルゴリズムイントロダクション』のほうをよく読んでいませんが、

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

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

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

>>98

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

意味不明としか言えないかと思います。
108 :
2016/12/17(土) 19:42:21.87 ID:C/wQAZQ3
『アルゴリズムイントロダクション』のほうをよく読んでいませんが、
『アルゴリズムイントロダクション』のほうもまたどっか別の本からのパクリの悪寒。
109 :
2016/12/17(土) 19:47:48.93 ID:YhK78PBA
"error: heap underflow" でググるといっぱい出てくる
110 :
2016/12/17(土) 19:57:50.69 ID:rDdwnYMe
ID:GDWdcO6h は何をそんなに怒ってるの?
問題が解けなくてイライラしてるだけ?

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

新しい本を書くときは参考文献よりもわかりやすくなるように、説明やイラスト、擬似コードを変えたり、あるいは同じものを流用することもあるだろう
111 :
2016/12/17(土) 20:55:04.47 ID:jmPH7DRp
disるのがはやってるらしい
112 :
2016/12/18(日) 00:45:20.51 ID: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.79 ID:VFzWAIXP
めんどくさ
114 :
2016/12/18(日) 01:14:58.25 ID: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.37 ID:05Ug+E6t
>>114
汚すぎるコードだ。なんだろう。初心者とも違うな。
まるで20年ぐらい前から成長してない人が書いたコードのようだ。
116 :
デフォルトの名無しさん
2016/12/18(日) 02:12:34.14 ID:KR24tnjc
>>115
ド素人と丸出しの感想文だな
117 :
2016/12/18(日) 04:57:12.61 ID:aCKcGLhu
すまぬ

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

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

Kotlin, Electron やら何やら、最近の言語に、ついていけてないw
118 :
2016/12/18(日) 08:19:04.80 ID:05Ug+E6t
> 本当は、== ではなく、型も一致する厳密等価演算子、=== を使うべきだろう
そういうレベルじゃない。

無駄なロジック、意味不明な変数名、多すぎるコメント、
コードの意味を何一つ分かってないとしか思えないといってんの
119 :
2016/12/18(日) 11:08:48.21 ID:7J/3tpZx
俺はむしろここ
> このソースコードのライセンスは、MIT License です
> Original Copyright (c) 2014 Michihito Seto All Rights Reserved.
残飯を神棚に飾るが如く宣言
ここにこそ初心者らしさが凝縮されてる
120 :
デフォルトの名無しさん
2016/12/18(日) 11:50:21.36 ID:5nrc1ooF
>>114

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

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

というのは意味があるのでしょうか?
121 :
2016/12/18(日) 11:50:54.72 ID:05Ug+E6t
jsdo使ってるやつって汚いコードが多いよな。
素人が使いたくなる機能でもあんのか?
ブラウザだけで開発ができるとか?
122 :
デフォルトの名無しさん
2016/12/18(日) 11:53:36.61 ID:5nrc1ooF
デバッグなど必要のないくらい簡単なコードなので、デバッグ用とは考えられないかと思います。
123 :
2016/12/18(日) 11:57:14.52 ID:0+9ctOie
馬鹿ほど自説に拘るw
124 :
デフォルトの名無しさん
2016/12/18(日) 12:12:58.36 ID:5nrc1ooF
Introduction to AlgorithmsよりもAlgorithms(Sedgewick、赤い本)のほうがいい本ですね。

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

翻訳書ではない日本語の本でまともなのは、浅野孝夫の本くらいではないでしょうか?
126 :
2016/12/18(日) 12:18:30.80 ID:d5jVhhWj
アルゴリズムやコードのライセンスってどの程度のものから付けていいんだ
あんまり簡単なものだと既出すぎてライセンス付けられるのか?って考えてしまう
かといってじゃあライセンス付けていい最低ラインは何なんだという話になる
127 :
デフォルトの名無しさん
2016/12/18(日) 12:20:00.87 ID:5nrc1ooF
>>126

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

どうやって、だれかのコードを流用したか判定するのか、それに興味があります。
128 :
2016/12/18(日) 12:30:54.60 ID:RB5DyRP2
アルゴリズムには著作権ないよ
あるのはそれをどう表現したか
簡単なアルゴリズムには表現バリエーションなんて限られてるから
ある程度似るのはどうしようもない
129 :
デフォルトの名無しさん
2016/12/18(日) 12:37:57.44 ID:5nrc1ooF
特許ならありますよね。
130 :
2016/12/18(日) 13:02:47.44 ID:PELrVlNw
デザインパターンの本高い・・・
一冊持ってたけど引っ越しのごたごたでなくしちゃった
無料で網羅できるサイトありませんかね
一冊読んではあるので、さらっと構造や仕組みを紹介してくれていればいいし
英語もある程度は読めます

基本のデザインパターンだけでもありがたいし
マルチスレッド対応に踏み込んだサイトならなおありがたいです
131 :
2016/12/18(日) 13:22:26.46 ID:d5jVhhWj
基本的な考え方覚えたら幾らでも応用できるだろ
カタログを後生大事にとっておく意味はない
132 :
2016/12/18(日) 13:35:15.82 ID:PELrVlNw
覚えてないんすよ
記憶力ないんで忘れちゃって、ぼんやりとしか覚えてないんです
だから概要をしっかり覚え直したいなと思って
133 :
2016/12/18(日) 13:42:55.97 ID:+dKTlaSP
>>132
いや、デザパタ本こそ手元においておくべき
わけのわからん二次情報を見るとどんどんブレていくぞ
134 :
2016/12/18(日) 13:45:05.00 ID:RB5DyRP2
リファレンスとしてはどの本がいい?
135 :
デフォルトの名無しさん
2016/12/18(日) 13:45:12.43 ID:5nrc1ooF
ソフトウェア工学的な本って重要なんですか?
136 :
デフォルトの名無しさん
2016/12/18(日) 13:45:59.00 ID:5nrc1ooF
学問的には全く面白くない分野ですよね。
137 :
2016/12/18(日) 14:08:17.53 ID:PELrVlNw
TECHSCOREのデザインパターンのページ見ることで自己解決しました
138 :
デフォルトの名無しさん
2016/12/18(日) 15:45:37.97 ID:VFzWAIXP
デザパタカタログは便利だよね
煮詰まったときに、休憩がてらパターンを眺めてると、閃くときがある
139 :
2016/12/18(日) 16:24:54.12 ID:+Ko1jSRc
ねーわ、普通のコードが99.99%
140 :
2016/12/18(日) 18:22:27.13 ID:d5jVhhWj
基本的な発想を学んだらカタログはポイ
パターンに執着してもデザインがぎこちなくなるだけ
141 :
2016/12/18(日) 23:03:56.86 ID:aCKcGLhu
>>119
jsdo.it では、全員のソースコードが、サイト内に限り、MITになる

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

2分ヒープ、AVL、赤黒木など、アルゴリズムの実装は、どうしても汚いソースコードになる
142 :
2016/12/18(日) 23:11:13.26 ID:f3M2Oqre
143 :
デフォルトの名無しさん
2016/12/18(日) 23:11:21.17 ID:5nrc1ooF
2分ヒープって簡単なアルゴリズムですよね。

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

だからあんまり人気がないのかもしれないですね。
145 :
2016/12/19(月) 00:01:07.57 ID:hSWjQy3F
漏れw
146 :
2016/12/19(月) 01:06:56.52 ID:8cVREo5r
流石に漏れは笑う
147 :
2016/12/19(月) 08:08:43.72 ID:judB9f5Y
>>144
全体的なリテラシの底上げがされるまではどうしてもね。
148 :
デフォルトの名無しさん
2016/12/19(月) 12:42:11.26 ID:z9XVuDpo
>>144
理論的な上限値をあらかじめ計算することが出来て
無駄な努力や試行錯誤をしなくて済むというメリットがあるよ
149 :
2016/12/19(月) 17:37:02.75 ID: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.34 ID: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.12 ID:z9XVuDpo
(1,-1,1)の長さが2?
152 :
デフォルトの名無しさん
2016/12/19(月) 17:53:09.70 ID:yHCszZUX
>なのでその対応をする関数をおしえてください。

意味不明です。
153 :
デフォルトの名無しさん
2016/12/19(月) 17:55:40.11 ID: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.37 ID: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.65 ID:yHCszZUX
>>150

何がやりたいのかが不明確。
156 :
2016/12/19(月) 17:58:17.41 ID:hSWjQy3F
>>149
列の最初の数字だけ1足すなり引くなりして返せばいいだけじゃないの?
157 :
デフォルトの名無しさん
2016/12/19(月) 18:01:17.72 ID:yHCszZUX
>例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する大きさ2の列は
>(0 ,-1 ,1), (1,0,1),(1,-1,0)とかあるので一つには定まってません。
>なのでその対応をする関数をおしえてください。

一つに定まらないから、すべての結果を返したいのか、
任意の一つの結果を返したいのか?
158 :
デフォルトの名無しさん
2016/12/19(月) 18:02:09.41 ID:yHCszZUX
明らかに、

(0, 0, ..., 0) に対しては条件を満たす結果は存在しないね。
159 :
2016/12/19(月) 18:50:37.10 ID:ic0p/3Yf
0はスタート地点なので
160 :
2016/12/19(月) 18:57:02.98 ID:ic0p/3Yf
>>154
a_2を1としたとき(-1, 1)のとき(-1,0)を返し
a_1を-1としたとき (-1,1)は(0,1)をかえすことになるので
一つに定まりません
161 :
2016/12/19(月) 19:06:19.22 ID:ic0p/3Yf
>>157
大きさn>0の任意の列aにたいしてf(a)=bでbがn-1の大きさでaと列の中の値が1だけ違う
列を出力する関数fを求めるということです。
162 :
2016/12/19(月) 19:13:51.38 ID:ic0p/3Yf
>>156
初めはそんな風に考えてる時期もありました
もう2か考えてるけれど全然わからないのでここで質問してみました
163 :
2016/12/19(月) 19:16:05.63 ID:hSWjQy3F
>>161
問題文を鸚鵡返しするんじゃなくて、質問者の質問に答えたら?
164 :
2016/12/19(月) 19:23:49.64 ID:ic0p/3Yf
>>163
fの出力は列の集合じゃないから普通わかりますよね
165 :
2016/12/19(月) 19:31:58.40 ID:hSWjQy3F
>>164
fが返すのは集合じゃないってのはどこに書いてある?
166 :
2016/12/19(月) 19:34:42.99 ID:ic0p/3Yf
>>165
14行上に書いてあります
167 :
2016/12/19(月) 19:47:31.40 ID:hSWjQy3F
>>166
Mateだと>>156って書いてあるわ
自分の中ではこれは当然みたいな条件がいろいろあるんだろうけど、それを人に説明するのが下手なんじゃね
168 :
2016/12/19(月) 20:02:25.40 ID:ic0p/3Yf
改行コードの数を数えてますか?
文の折り返しと改行とは違いますよ?
169 :
2016/12/19(月) 20:17:02.98 ID:2q/Y95iw
こりゃまたひどい質問者だな
170 :
2016/12/19(月) 20:18:06.39 ID:Xx/umGft
課題の丸投げ、しかも「日本語」が
171 :
2016/12/19(月) 20:25:56.12 ID:ic0p/3Yf
課題という証拠はありますか?
実際課題じゃなくプログラミングしていたら出てきた問題なので
全然課題じゃないです
172 :
2016/12/19(月) 20:33:03.53 ID:ic0p/3Yf
>>170
あなたには誤った文を訂正する能力がないんですか?
それでは人間ではなくコンパイラーと同じですよ
173 :
2016/12/19(月) 20:37:51.17 ID:ic0p/3Yf
>>169
面白い問題とつまらない問題を区別する能力が数学的推測には
一番必要なんんです
この問題がつまらないと思うのなら解かないでいいです
174 :
2016/12/19(月) 20:50:46.99 ID:2q/Y95iw
問題をきちんと記述する能力に欠けている
175 :
2016/12/19(月) 20:52:23.54 ID:2q/Y95iw
あと、面白い問題だと思うなら、それこそ自分で解くのが楽しいのでは
ここで聞かずに
176 :
2016/12/19(月) 21:27:51.26 ID:ic0p/3Yf
>>175
楽しいものは独り占めるのではなく分け与えようと習わなかったのでは?
177 :
2016/12/19(月) 21:44:43.60 ID:ic0p/3Yf
>>174
今読み返してみましたがキチンと書かれてますよ
どこがキチンと書かれてないのか言ってくれたら
それは理解力の無さなので説明してもいいです
178 :
2016/12/19(月) 22:34:08.82 ID:2q/Y95iw
十分楽しんだからあとは一人で楽しんでくれていいよ
179 :
2016/12/19(月) 22:53:51.02 ID:Xx/umGft
>>172
馬鹿乙
180 :
2016/12/19(月) 23:04:39.12 ID:L2gIhLeK
先頭から非0を探して、はじめの要素が正なら1ひく、負なら1足す
これで終わりじゃないの?
181 :
2016/12/19(月) 23:45:15.82 ID:Xx/umGft
アルゴリズムは自分で考えるじゃ、ボケ
182 :
2016/12/20(火) 13:05:59.52 ID:lAXr92yw
>>171
茶か尿かもう判らんって意見があるけど
検出時のガスクロのデータ見直したら判るはずという話がある
仮にそれでお茶だとしてももう発表はないだろう
183 :
デフォルトの名無しさん
2016/12/21(水) 18:35:54.54 ID: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.91 ID:trArLuj5
お断りいたします
185 :
2016/12/21(水) 18:49:10.92 ID:IT3zLaEf
俺も断るわ
186 :
デフォルトの名無しさん
2016/12/21(水) 19:41:25.65 ID:UR5SKYPV
早くも降参宣言か。
187 :
2016/12/21(水) 19:55:05.40 ID:RIWp4Ngq
mなんていくらでもあるんじゃないの?
なんで#{m}=1?
188 :
デフォルトの名無しさん
2016/12/21(水) 20:06:55.96 ID:UR5SKYPV
>>187

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

反例を作ろうと思ってもできないはずです。
189 :
2016/12/21(水) 20:09:57.40 ID:trArLuj5
>>183
分からない問題はここに書いてね421 [無断転載禁止]©2ch.net
http://rio2016.2ch.net/test/read.cgi/math/1480771004/493
190 :
2016/12/21(水) 20:12:10.26 ID:RIWp4Ngq
k=1, l=2で、{m}={2,4,6,8,...}
k=l=1で、{m}=自然数の集合
じゃないの?
191 :
デフォルトの名無しさん
2016/12/21(水) 20:16:47.08 ID:UR5SKYPV
>>190

{a_n} の任意の*連続する*有限部分列を a_k, a_(k+1), …, a_l(k ≦ l)とする。
192 :
デフォルトの名無しさん
2016/12/21(水) 20:18:48.11 ID: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.67 ID:UR5SKYPV
>>191
は勘違いです。
194 :
デフォルトの名無しさん
2016/12/21(水) 20:20:14.23 ID:UR5SKYPV
a_1 = 1

なので、

b_1 = 0

です。

なので、

{m} = {1}

です。
195 :
2016/12/21(水) 20:21:17.66 ID:RIWp4Ngq
k=1, l=2も、k=l=1も、当然連続する部分列でしょ
{b_i}を10個ぐらい挙げてみてよ
196 :
2016/12/21(水) 20:22:42.50 ID:RIWp4Ngq
mの条件が足りないんじゃないの?
197 :
2016/12/21(水) 20:24:46.75 ID:RIWp4Ngq
b_i ≦ b_mさえ満たせばいいんならmなんていくらでもあるでしょ
198 :
デフォルトの名無しさん
2016/12/21(水) 20:32:03.58 ID:UR5SKYPV
b_m は b_i の最大値です。

その最大値となる b_m の m が一意的であるということです。
199 :
2016/12/21(水) 20:32:36.28 ID:El82f3CE
k≦m≦lという条件が抜けているっぽいね
200 :
デフォルトの名無しさん
2016/12/21(水) 20:34:06.08 ID:UR5SKYPV
テレンス・タオ ルベーグ積分入門
テレンス タオ
固定リンク: http://amzn.asia/8KaL6NK

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

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

普通、ルベーグ積分なんてやるのは数学科かせいぜい物理学科くらいじゃないですか?
201 :
デフォルトの名無しさん
2016/12/21(水) 20:34:58.70 ID:UR5SKYPV
>>199

各 i(k ≦ i ≦ l)に対して、0以上の整数 b_i を以下で定義する:
202 :
2016/12/21(水) 20:39:27.31 ID:RIWp4Ngq
不完全な問題出しておいて>>186はないよね
203 :
デフォルトの名無しさん
2016/12/21(水) 20:41:22.47 ID:UR5SKYPV
>>202

不完全なところはありません。
よく問題文を読んでください。
204 :
2016/12/21(水) 20:42:06.97 ID:trArLuj5
205 :
2016/12/21(水) 20:43:41.56 ID:trArLuj5
マルチ小僧w
206 :
2016/12/21(水) 20:44:49.22 ID:RIWp4Ngq
>>203
mがkからlの間なんて一言もないんだから不完全
207 :
デフォルトの名無しさん
2016/12/21(水) 20:47:08.96 ID:UR5SKYPV
>>206

>>183
各 i(k ≦ i ≦ l)に対して、0以上の整数 b_i を以下で定義する
208 :
2016/12/21(水) 20:52:23.64 ID:RIWp4Ngq
そうだとして、わざと誤読を誘おうとしている悪問だね
でO(log k)のアルゴリズム思いついたから俺は降りるね
209 :
2016/12/21(水) 20:53:06.55 ID:RIWp4Ngq
O(log l)だった
210 :
デフォルトの名無しさん
2016/12/21(水) 20:55:14.58 ID:UR5SKYPV
>>183

の解答は以下です。

http://imgur.com/rAnp3Ga.jpg

赤線を引いたところは「odd」が正しいですね。
211 :
デフォルトの名無しさん
2016/12/21(水) 21:27:34.73 ID:UR5SKYPV
実は、この問題には続きがあります。

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

このとき、

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

は整数にはならないことを証明せよ。
212 :
デフォルトの名無しさん
2016/12/21(水) 21:29:28.61 ID:UR5SKYPV
ちょっとアルゴリズム的な問題からは離れますが。
213 :
2016/12/21(水) 21:31:37.14 ID:xYX0mlO/
提出日はいつですか?
214 :
2016/12/21(水) 22:14:54.89 ID:auJA5Ak8
またバカな質問者が暴れてるのか
215 :
2016/12/21(水) 23:45:05.79 ID:mNaBBYjZ
qiitaでやれ
216 :
2016/12/23(金) 00:59:54.04 ID: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.09 ID: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.27 ID:VtFWW7J2
ダイクストラのアルゴリズムの正しさの証明が載っている本で
一番分かりやすい本を教えてください。
219 :
デフォルトの名無しさん
2017/01/02(月) 07:40:19.35 ID:03PPbeGI
『アルゴリズムイントロダクション』について質問です。

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

最短路問題の説明で、

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

という記述があるために質問します。
220 :
デフォルトの名無しさん
2017/01/02(月) 08:09:15.65 ID:03PPbeGI
実数 a が a≠∞のとき、 a + -∞ = -∞
実数 a が a≠-∞のとき、 a + ∞ = ∞

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

という等式を含めたいからこのような書き方になったのでしょうか?
221 :
2017/01/02(月) 09:29:22.45 ID:J77W/v0L
それは実無限派の書き方だが,世の趨勢は可能無限
ほどほどに相手をするだけでいいよ
222 :
デフォルトの名無しさん
2017/01/02(月) 11:22:57.42 ID:03PPbeGI
>>221

ということは、『アルゴリズムイントロダクション』での実数の集合の定義には、
∞、-∞ が含まれるというk十ですね。
223 :
デフォルトの名無しさん
2017/01/02(月) 11:23:39.72 ID:03PPbeGI
頂点の数が n のグラフで、任意の頂点間に辺が存在するようなものを考える。

ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を求めよ。
224 :
デフォルトの名無しさん
2017/01/02(月) 11:26:14.49 ID:03PPbeGI
頂点の数が n(≧2) のグラフで、任意の頂点間に辺が存在するようなものを考える。

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

このとき、

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

が成り立つことを示せ。
225 :
2017/01/02(月) 12:08:43.26 ID:GdcUHK9D
宿題は宿題スレへ
226 :
2017/01/02(月) 12:09:56.00 ID:GdcUHK9D
宿題は宿題スレへ
227 :
デフォルトの名無しさん
2017/01/02(月) 12:22:39.27 ID:03PPbeGI
宿題ではないのです。

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

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

ところが、計算してみると、 O(n!) は荒い評価であって、 O((n-1)!) とできますね。
228 :
デフォルトの名無しさん
2017/01/02(月) 12:24:22.04 ID:03PPbeGI
もっといい評価はありますでしょうか?
229 :
2017/01/02(月) 12:28:36.72 ID:GdcUHK9D
判ってるなら効くな
230 :
デフォルトの名無しさん
2017/01/02(月) 14:08:15.59 ID:03PPbeGI
ダイクストラ法の正しさの証明で分かりやすい証明を思いつきました。

発表しましょうか?
231 :
2017/01/02(月) 14:21:37.12 ID:w6ZCrhsc
どうぞどうぞ
232 :
2017/01/02(月) 14:27:23.53 ID:yIXUnWg3
>>227
オーダーについてあんま良くわかってないんだろうけどO((n-1)!) なんて書き方はないよ
もし書いたとして、それはO(n!)と同じもの
233 :
2017/01/02(月) 17:55:38.72 ID:J77W/v0L
>>222
実無限はいろいろ破綻するから可能無限にしておいたほうがいいよ
実数の定義に∞, -∞は入らない
というか,そもそも -∞ というのがおかしい存在

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

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

ダイクストラのアルゴリズムは↑のものとします。
235 :
デフォルトの名無しさん
2017/01/02(月) 19:05:18.10 ID: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.40 ID: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.66 ID: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.41 ID: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.14 ID: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.44 ID:03PPbeGI
したがって、

O(f(n)) と O(g(n)) は異なります。
241 :
2017/01/03(火) 08:33:06.09 ID:3o9M4oho
この狂人ヤバいなw
242 :
デフォルトの名無しさん
2017/01/03(火) 08:50:16.82 ID: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.04 ID:hCDXc7Qp
>>234-238

のダイクストラのアルゴリズムの正しさの証明に間違いはないという
ことでOKですか?
244 :
デフォルトの名無しさん
2017/01/03(火) 11:39:58.60 ID:hCDXc7Qp
Erik DemaineはMITの歴史上最年少で教授になったという天才だそうですね。

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

見終わったら、講義の要約について書きます。
245 :
デフォルトの名無しさん
2017/01/03(火) 13:47:58.01 ID: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.21 ID: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.08 ID: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.27 ID: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.64 ID: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.71 ID: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.21 ID: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.40 ID:4i7P3+nF
アルゴリズムイントロダクションって自明なことをわざわざループ不変量を使ったりして、
証明していて、うざすぎますね。
253 :
デフォルトの名無しさん
2017/01/05(木) 09:16:52.73 ID:4i7P3+nF
通常の数学の本なら自明で済ませるようなことをわざわざ証明している。
254 :
2017/01/05(木) 09:57:50.61 ID:OZq8Y/OW
このバカ、以前も全く同じこと言って暴れたな。
255 :
2017/01/05(木) 10:02:39.43 ID: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.31 ID:W/+CAQrH
数学とコンピュータ科学の区別がつかない厨房だろう
257 :
デフォルトの名無しさん
2017/01/05(木) 11:01:45.09 ID:4i7P3+nF
クヌースの本なんかだと妙なくどさはない。

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

要するに本を書くセンスがない。
258 :
デフォルトの名無しさん
2017/01/05(木) 11:02:52.69 ID:4i7P3+nF
セジウィックとウエインの本のほうがずっとよい。
259 :
デフォルトの名無しさん
2017/01/05(木) 11:07:44.54 ID:4i7P3+nF
日本語の本について言及しておく。
例えば、評判のよい茨木俊秀の本。

こんな薄いスカスカの本をよくも恥ずかしげもなく出版するものだとあきれる。
260 :
デフォルトの名無しさん
2017/01/05(木) 11:19:31.17 ID:4i7P3+nF
アルゴリズムイントロダクションの悪口を書いたがいいところもある。

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

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

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

整数論的アルゴリズムの章はあまりにも簡単すぎる。
高木貞治の本でも読んだ方がよい。
261 :
デフォルトの名無しさん
2017/01/05(木) 11:28:06.54 ID:4i7P3+nF
結論として、ベストな本はクヌースが予定しているTAOCPの要約本ということになる。
262 :
2017/01/05(木) 11:29:47.36 ID:W/+CAQrH
結論として4i7P3+nFはNG行き
263 :
2017/01/05(木) 11:33:33.85 ID:2uA+A+xC
>>253
自明ほど危ういものは無いんだが
264 :
2017/01/05(木) 11:40:35.14 ID:OZq8Y/OW
例によって ID:4i7P3+nF が発狂しててワロタ
265 :
デフォルトの名無しさん
2017/01/05(木) 11:44:36.30 ID:4i7P3+nF
>>263

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

もし危ういのなら頭のよい数学者は自明などと書かないはずです。
266 :
2017/01/05(木) 11:52:58.57 ID:r7KPx/TL
そんな多くねえよちゃんと論文読め
267 :
2017/01/05(木) 12:06:11.36 ID:2uA+A+xC
自明連発する方が馬鹿なのか
268 :
2017/01/05(木) 13:09:24.25 ID:c6xYhHVb
>>265
馬鹿丸出し
269 :
2017/01/05(木) 13:18:34.40 ID:c6xYhHVb
>一般に、コンピュータ科学者よりも頭が良いとされる数学者が
根拠は?
>自明で済ませることが多いのでしょうか?
数学のコンテキストの話

そもそも証明の意味もコンピュータ科学と数学では違うだろ
270 :
2017/01/05(木) 14:56:52.93 ID:jagWiFjG
なんでバカって本質に関係ないところでギャーギャー騒ぐの?
271 :
2017/01/05(木) 14:58:54.44 ID:YjTG1plI
うむ
272 :
デフォルトの名無しさん
2017/01/05(木) 19:46:02.51 ID:4i7P3+nF
アルゴリズムイントロダクションについて、数学が出来る人向けの本だという人がいる。
そして、数学ができない人はセジウィック&ウエインの本を読めという人がいる。

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

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

クヌースの本のように、楽しい本ではない。
273 :
2017/01/05(木) 20:37:39.99 ID:UiiKd7HR
274 :
2017/01/05(木) 22:15:16.24 ID:WPj32BYO
書評したければ別のところでやれ
275 :
デフォルトの名無しさん
2017/01/06(金) 17:19:30.91 ID:TSHa+AxL
再帰の除去についてやり方が詳しく書いてある本を教えてください。
276 :
デフォルトの名無しさん
2017/01/06(金) 17:43:03.36 ID: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.89 ID:XtKi9eaG
278 :
デフォルトの名無しさん
2017/01/06(金) 18:36:23.48 ID:TSHa+AxL
Wrong Answerになっちゃうんだけど。
279 :
デフォルトの名無しさん
2017/01/06(金) 18:38:07.31 ID:TSHa+AxL
例題については正しい答えが計算されるんだけど。
280 :
2017/01/06(金) 18:43:00.23 ID:LxnclcVs
よかったね
281 :
デフォルトの名無しさん
2017/01/06(金) 20:15:02.80 ID:TSHa+AxL
>>277

ソースレベルで再帰を除去する方法が知りたいんですが。
282 :
デフォルトの名無しさん
2017/01/06(金) 20:22:33.43 ID:TSHa+AxL
秋葉らのプログラムでもWrong Answerになっていまします。

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

scanf,printfを使っていたらダメだったのが、cinとcoutにしたらOKになった。
285 :
デフォルトの名無しさん
2017/01/08(日) 12:26:37.82 ID: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.73 ID:0mVP2hZ6
O(n^2)
287 :
2017/01/08(日) 12:32:34.98 ID:0mVP2hZ6
288 :
デフォルトの名無しさん
2017/01/08(日) 13:51:15.22 ID:E98VLsZL
>>286-287

ありがとうございます。

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

何を単位にするんですか?
290 :
デフォルトの名無しさん
2017/01/08(日) 14:06:13.08 ID: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.75 ID:E98VLsZL
T(n) = c1 + c2*n + T(n-1)
T(0) = c3

この漸化式の解を求めればいいんですかね?
292 :
デフォルトの名無しさん
2017/01/08(日) 14:12:15.21 ID: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.92 ID:E98VLsZL
>>290-292
は我ながら明解な解答ですが、

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

「以前に解かれている部分問題を解くための再帰は直ちに戻るので、Fは
各部分問題をただ1度だけ解く。この手続きはサイズが0,1,....,nの部分問題
を解く。サイズがnの部分問題を解くために、for文がn回繰り返される。したがって、
Fの再帰呼び出し全体における、このfor文の繰り返し回数は等差数列を形成し、
総繰り返し回数はΘ(n^2)となる。」
294 :
デフォルトの名無しさん
2017/01/08(日) 14:26:56.39 ID: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.04 ID:rSxBm0q1
馬鹿には無理
296 :
デフォルトの名無しさん
2017/01/08(日) 14:28:32.97 ID:E98VLsZL
>>289

for文の繰り返し回数=計算量ですね。
297 :
デフォルトの名無しさん
2017/01/08(日) 14:29:42.72 ID:E98VLsZL
結局自分ですべて解決してしまいました。
298 :
2017/01/08(日) 17:12:11.39 ID:8OGZNgRf
よくやった
褒美として自分専用のスレを立てる権利をやろう
299 :
2017/01/08(日) 18:45:26.96 ID:KkEYpXLY
命名ID:E98VLsZは俺様
300 :
デフォルトの名無しさん
2017/01/08(日) 20:55:21.87 ID:E98VLsZL
プログラミングコンテストチャレンジブック

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

この本を難しいという人がいますが、そんなに難しいですかね?
301 :
デフォルトの名無しさん
2017/01/08(日) 22:46:42.12 ID:E98VLsZL
プログラミングコンテストチャレンジブック
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
最強最速アルゴリズマー養成講座

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

一番ひどいのが

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

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

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

だと思いますけど、例えば、貪欲法でなぜうまくいくのかの証明が書いてないですね。
303 :
2017/01/08(日) 22:51:13.67 ID:Qw43e7Zm
ここはプログラミング問題集書評のスレなの?
304 :
デフォルトの名無しさん
2017/01/09(月) 06:08:00.57 ID:JOAqSyBk
>>301
うむ
日本語下手なのはもちろん英語も下手みたいだな
305 :
2017/01/09(月) 06:09:36.68 ID:cSodeH17
頭の使い方が下手というかそもそも頭が不自由なんだろう
306 :
デフォルトの名無しさん
2017/01/09(月) 10:59:50.63 ID: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.57 ID:TqLncjlX
15.1-2

反例

p[1] = 1
p[2] = 5
p[3] = 7
308 :
デフォルトの名無しさん
2017/01/09(月) 13:21:16.77 ID: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.26 ID: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.94 ID:TqLncjlX
あ、ひっかけがありましたね。
訂正します:

n > 0 のとき、

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

n = 0 のとき

#V = n + 1
#E = 0

ですね。
311 :
デフォルトの名無しさん
2017/01/09(月) 15:27:31.58 ID: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.20 ID:4OeNzyzM
>>308
フィボナッチだろ
√5が出て来る公式
O(1)になるかも試練が
313 :
2017/01/09(月) 15:46:27.18 ID:FSSb8O2Z
>>311
      r ‐、
      | ○ |         r‐‐、
     _,;ト - イ、      ∧l☆│∧  良い子の諸君!
    (⌒`    ⌒ヽ   /,、,,ト.-イ/,、 l  
    |ヽ   ~~⌒γ ⌒ ) r'⌒ `!´ `⌒) よく頭のおかしい数学者気取りのバカが
   │ ヽー―'^ー-'  ( ⌒γ ⌒~~ / 「誰も気付かなかった事を発見したことを発表」とほざくが
   │  〉    |│  |`ー^ー― r' | 大抵それは「先人が思いついたけどあえて発表しなかった」ことだ
   │ /───| |  |/ |  l  ト、 |  王道が何故面白いか理解できない人間に面白い話は
   |  irー-、 ー ,} |    /     i 作れないぞ!
   | /   `X´ ヽ    /   入  |
314 :
デフォルトの名無しさん
2017/01/10(火) 20:16:10.65 ID:Zd0v4023
アルゴリズムイントロダクションが難しいという人がいますけど、
この本は馬鹿丁寧に書かれていますよね。

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

「書きすぎ」れば分かりやすくなると思い込んでいますね、著者らは。
315 :
2017/01/10(火) 20:19:42.26 ID:kxFYGz06
http://hissi.org/read.php/tech/20160614/U2lCYS9zNTM.html

マジ基地だな。壊れたレコードかよ。
316 :
2017/01/13(金) 21:58:42.65 ID:wiy2qrIv
プログラミング言語のパーサーってどういう仕組みで動いてるんですか?
文字列をトークンの配列に分ける
特定のパターンにマッチするトークンの部分集合をひとまとめにして新しいトークンに置き換える
再帰的に同じ事を繰り返す
こんな感じ?
317 :
2017/01/13(金) 22:37:46.17 ID:+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.40 ID:H4kTcvBH
>>317
これ考えた奴は天才だな
319 :
2017/01/16(月) 17:57:37.27 ID:YH2Bx58z
Lisperか
BNF
320 :
2017/01/19(木) 09:40:05.52 ID:uhfgjGGl
110KB

新着レスの表示

★スマホ版★■掲示板に戻る■全部前100次100最新50

名前:E-mail: