データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
レス数が1000を超えています。これ以上書き込みはできません。
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
京都大学霊長類研究所
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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 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 ruby って変な人が多いんだね，俺も今 ruby をマスターしようと必死ではあるが Haskellって勉強する意味ある？
実用性はないよね？ なぜ、HaskellやSchemeをありがたがる人がいるの？
どう考えてもC#とかのほうが生産性が高いのに。
単なるかっこつけ？ MITのコンピュータの入門書もSchemeを使っていたりする。 言語としてのlisp最強論は理解できるけどね。
実用的ではないのは言語自体の問題ではなくてシェアとかサポートする企業の存在とかコミュニティの問題。 haskellやschemeは勉強したくない奴には不要
雇われには言語選択権はないので、かりにそれらがよいものであったとしたとしても、フラストレーションたまるだけだろ
一言でいうなら自分で一から十まで計算を構築するための言語だな
ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要 >>12
> ライブラリ駆使して、なんとかすることが求められている人間にはこんなものは不要
ライブラリを駆使するのが今のプログラマに求められている技術だからな。
MITがSICPを教えなくなった理由
https://ezoeryou.github.io/blog/article/2016-05-05-sicp.html
> 今日では、状況が変わっている。今のエンジニアは、自分が完全に理解していない複雑なハードウェアの
> ためのコードを日常的に書いている（そして、大抵の場合、企業秘密により完全に理解するのは不可能である）。
> ソフトウェアでも状況は同じだ。プログラミング環境は、多大な機能を提供する巨大なライブラリ群の集合として存在している。
> Sussmanの今日の生徒は、その時間の大半を、ライブラリのマニュアルを読み、どのように組み合わせれば目的が
> 達成できるのかを把握することに費やしている。Sussman曰く、今日のプログラミングは、「より科学に近い。
> ライブラリを持ち寄って、つっつき回すのだ。プログラムを書くには、突っつき回して、どのように動作するかを観察する。
> そして、「目的を達成するために改造できるか」と考えるのだ」。SICPの「合成による解析」という物の見方である、
> 小さな、単純な部品を組み合わせて大きなシステムを作るということは、もはや今日の状況にそぐわなくなった。
> 今や、我々のプログラミングはつっつき回すことで行われている。
>
> なぜPythonを選んだかということについて、Sussmanは、"late binding"に決定したと冗談を飛ばした。
> Pythonには大量のライブラリがあり、教育者の様々な実習に使いやすい（たとえば、ロボットを制御するソフトウェアを書くなど） HaskellやSchemeの利点は？
少なくとも、分かりにくいよね。 >>14
>今日のプログラミングは、「より科学に近い。
ここは変だな
「より工学に近い。」
というなら判るが SICPをプログラミング初学者に教えるというのは確かに異様だよね。
やっとまともになったというだけの話。 コンピュータサイエンスの中でアルゴリズムとデータ構造ってどれくらい重要な科目なの？ アルゴリズム + データ構造 = プログラム。
ということは。
プログラムの占める割合と等価なのでは。 なんか計算の理論とかのほうが上みたいな感じじゃない？ コンピュータサイエンスで最も重要な科目は、コンパイラとかOS？ schemeやらないとアルゴリズムとデータ構造を組み立てるってことがどういうことなのか、コードでわからないだろうな javaでconsを表現するときにどうすればいいか知ってますか? >>28
アルゴリズムとデータ構造の本に疑似コードが載っていることがあるけど、
Scheme風に書かれていることなど決してない。 >>18
未経験でも理解出来るならとりあえず地雷の可能性は下がる 恵まれてない会社だと全員切る羽目になるって話だろｗ 31
そのSICPはschemeでかかれているわけで
昨今のライブラリ重視の観点からいえば、javaがいいっていうのはとおるけど、アルゴリズムかくのにjavaがいいってのは、センスないというか、お手入れ大好きなんだろうな 日本人の書いたアルゴリズムとデータ構造の本でまともなのって1冊もないの？ 日本人の書いた本は薄っぺらくて説明も十分ではなく厳密でもなく網羅性もない本ばかりに思う。 >>39
そのものズバリでアルゴリズムとデータ構造という本が岩波から出てる まともな本とは?
argolythm introduction?
knuth本?
どっちも使い物にならないが 根幹のタームの綴りも知らん半可通に何を教われというのか >>44
そんな頭じゃ使いものにならんのも頷けるわ >>19
は？変なのはお前だ
プログラミングは最初から工学的だろ何言ってんだ？
そもそもお前は工学と科学を理解してないから可笑しなことを言うんだ 何ヶ月か前に近代科学社に電話でセジウィックアルゴリズムの第四版の翻訳の予定はありますか、と訊いてみたが無いって返事だったんだよな
書いて欲しいんだがな アルゴリズムさえ知ってりゃ動くプログラムは書けるから他は優先度低いと考えてた結果
データ構造すら分からない化石プログラマになってしまった
今必死にデータ構造とデザインパターン勉強中だけど、わかってくると楽しいね
アルゴリズムみたいにオーダー詰める楽しみはないけど… 両方大事だろ。
データ構造が整理されてないとアルゴリズムも煩雑になるし。 vEB木の「僕の考えた最強のデータ構造」感が大好きなんだが誰か共感してくれる人いる？ データ構造の基本は、以下の2つと、他にはハッシュがある
A → B → C → D
のように、メモリ上の位置がバラバラなオブジェクトを、リンクでつないでいくものと、
(シーケンシャルアクセス)
ABCD
のように、連続したメモリ位置に、オブジェクトやオブジェクトの参照が確保されていて、
単純な計算式で、各オブジェクトにアクセスできるもの(ランダムアクセス)
シーケンシャルは、リンクをたどるから、アクセスには時間がかかるけど、
要素の追加・削除では、リンクを付け替えるだけで、要素をずらさないから速い どうも、お久しぶりです。スモモンガーです。（誰って感じだと思いますがそれで結構です）
以前紹介したアルゴリズムですが、結局全然応用分野は見つかっておりません。
前回は画像処理分野を中心に解説しましたが今回はより簡単に実装ができる
探索分野に絞って動画を作ってみました。つたない動画で大変申し訳ございませんが
見てみていただけたら幸いです。特許などは取得しておりませんのでどうかご自由に
お使いください。長文失礼いたします。痛いのは承知なのですが応用分野を必死に
探しているのでどうかご協力よろしくお願いします。
https://youtu.be/5m3kPHO2w98
以上、どうぞよろしくお願いします >>61
最初の数分見ましたが..
1) 何の探索なの？最初は「探索」と聞いて「グラフかな？」とか思ったけど配列みたいだし、最初に想定される入力を明確にした方がいいですね
2) プレゼンが文章を読み上げてるだけでイメージが湧きにくい
1,4,10,20,25 …
の例ではイラストを用いた方がわかりやすいと思います
3) Kangaroo Method とはのスライドでデータがソートされていて、キーの差が (中略) バイナリサーチと同等の効率を .. とありますが、例では入力が完全にソートされているようです。これなら最初からバイナリサーチを使います
また、11m10s くらいのところで「Sinカーブは整ってる」とありますが、「整っている」の定義がよくわかりません。その後の例も見ましたが、どのくらいまで途中に想定されていないデータが混じっていても許容範囲なのかが不明です
4) 先に長所短所のスライドを持ってきて、擬似コードとオーダーも明記し、「一部ソートされてなくても O(logn) で探索できます」みたいなのを書いて、見ている人を「それならもうちょっと続きを見てみようか」みたいな気にさせられればもっといいですね
以上、感想でした 64さん。ありがとうございます。私はこういうスライドを作る機会があまりないのでこんな形になってしまいました。
実は整っているという抽象的な単語を使っていますが、実は定量的にこれを測る方法はまだ思いついていません。
そのほかのご指摘はその通りだと思います。
貴重なご意見ありがとうございます >>66
まず目的のキーと現在探索中のキーの差をとる。
それを隣接するキーの最大値で割る。
その値だけ進む。
まあ、原理は単純なアルゴリズムです >隣接するキーの最大値
これをあらかじめ求めておかなきゃならんってのが一番のネックだな。
一般のデータに対する探索だと、バイナリサーチと比較したメリットと言っていたものの大半が消し飛んでしまう。 >>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
...
と線形時間になる（やり方あってるよね？）
演算している分、比較だけの線形探索より処理速度が遅くなる >>69
>>70
確かにキーの最大値を求めるのは線形時間かかります。なのであらかじめ、隣接するキーの最大値が分かっているデータに使用可能です。
探索の最悪時間は線形時間ですが、平均時間はlogのオーダーになるのではないでしょうか。私が不勉強なもので理論的には、示めせませんが多分logのオーダーになると思います。
ソートしなくても探索できるのは差の絶対値を取るからです。動画に入れるのを忘れました。すいません。
計算についてはそれであっています。わざわざご指摘ありがとうございます >>71
上でも指摘されているが整っているの定義が不明
二分探査の場合は、存在しないこともlog n で確認可能だが、この手法は整っているの定義次第では存在しない者の確認が非常に時間かかる（ソートされている場合は存在するものと同等だが、そうすると二分探索よりも利点が少なくなる）
平均計算量を求めるのはちと難しそうだけど、格納される値の値域に依存するかな
たぶん、log n 程良くはないと思う >>72
ご指摘ありがとうございます。確かに整っているの定義ができていないのが一番の難点ですよね。いつか勉強して考えたいと思います >>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回の演算
結論として
このアルゴリズムの最大の欠点は差の最大値が必要な事を含めて
データ列の内容に左右されてしまうことだな
この手のアルゴリズムはデータの外側にあるべきだな >>61
すもモンがnewton法をガチで知らないのであればnewton法をまず勉強するべき
カンガルーの敵はバイナリではなくnewtonだ 確かにデータ間の差に一様離散分布を使ったのは公平ではなかったです。
なので、データを完全にランダムにして調べてみました。
データはCのrand()%1000000で10000個生成しソートして、
探索の時配列のうちランダムな値を探すキーとし間を線形探索、カンガルー法
バイナリサーチで100回比べてみました。
その結果線形探索では平均比較回数約4963回最大比較回数は9972回でした
カンガルー法は平均比較回数約70回 最大比較回数は111回でした。
バイナリーサーチはやはり一番はやく、平均比較回数約12回、最大比較回数は14回でした
皆さんがご指摘の通りやはりバイナリーサーチが一番はやいようです。
ただ、例えばKMP法が逆行がないから使われているようにカンガルー法も逆行がないので
使うことはできないでしょうか？もし、とんちんかんなこと言ってたらすいません。 >>74
www確かにそうかもしれませんね。
>>77
一応私はニュートン法については知っています。Newton法は求める関数の微分した値を
しっていなければならないとおもうのですが、現実の探索だと関数が微分できないことも
多いかと思います。ちょっと、私が使った例が悪くてsinカーブや円を使ったのがよく
なかったのかもしれません。整っていてソートされていないデータとして扱いやすかったので
sin関数を使ったのであってとくにデータが微分可能である必要はありません。円と
Y切片の交点も中学生でも二次方程式ときゃいいのでもっと簡単にできますが、本来は
多角形とさまざまな図形の交点を探るアルゴリズムです。円を使ったのは例をわかりやすく
したかったからです。 状態遷移ってどういうステータス持てばいいの？
A と B のステータスがあって、お互いが切り替わるのに n秒 かかる
切り替わりに失敗したら切り替えをリトライする
AはBになろうとし、BはAになろうとする
というとき、A と B のほかに AからBになるのを待ってる状態と
BからAになるを待ってる状態の 2つがさらに状態として必要？
過渡状態も状態？ >>80
システムの設計次第。
切り替え中、待ち中が状態として存在するのならプログラムでも状態にすればいい >>81
そりゃそうだけど
状態がn個あると過渡状態がたくさんになるのは
辛い 辛かろうが状態が存在するのならしょうがあるまい。
あるいは遷移をアトミックにして遷移中状態そのものを無くすか、遷移中の動作を共通化
できるなら遷移先をパラメータ化して「*への遷移中」という1状態にしてしまうとか。 ポリモーフィックなクラスの相互作用において特定の型の組み合わせの場合のみ処理を特殊化したい場合はどうすればいいのだろう？
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); デザインパターンを使って実装すると、年長プログラマーから、またこんなことしやがって的な拒否反応が帰ってくるんだがどうすれば 下手くそがデザインパターンとか使うと逆にこんがらがるからなぁ
老害とどっこいどっこいだろ マルチスレッドで、なんの考えもなくオブザーバー使いまくられて、データ破壊しまくられた時には、本気で殺意を抱いたよ 『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』
の優先度付きキューについてのプログラムについて質問です。
p.241の heapIncreaseKey(A, i, key) という関数内で、
「if key < A[i] エラー：新しいキーは現在のキーより小さい」
というのがあります。
これがなぜ必要なのかが分かりません。
insert(key) を見れば分かるように、この本の使われ方では、
key < A[i] になることは決してありません。
よろしくお願いします。 完成形をいきなり見てると不思議に思うよね。
でも実際には作成中のバグを考慮して、最初にチェックを入れておくもんなんだよね。
まあ、一言で言えばassertなんだけど。
ただ、作業やデバッグ用には必須であっても、その本の例示として必要か？と言われれば、確かにいらない気がする。 >>95-96
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の参考文献に
挙げられている『アルゴリズムイントロダクション』を見てみたら、全く同じプログラム
が載っていました。
完全にパクっていますね。
>>96
デバッグ用にどうして必要なのかが分かりません。
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』はお持ちでしょうか？
もし、お持ちでないようでしたら該当箇所の画像をアップロードします。 >>98
こういうのが本当のパクり
訴えられたら負ける >>97
他の本も読んでみるとわかると思うけど、プライオリティキューを二分木ヒープで実装するのは定番で、どの本でも大体同じことが書いてある >>98
「if key < A[i] エラー：新しいキーは現在のキーより小さい」
というのが、デバッグ用であるとは思えないのですが、これは一体何なんでしょうか？
heapIncreaseKey(A, i, key) を何か別の用途に使う場合があって、そのときに必要に
なるのならば納得しますが。 >>101
「if key < A[i] エラー：新しいキーは現在のキーより小さい」
という意味不明のコードも『アルゴリズムイントロダクション』のプログラムには
書いてあります。
こんな余計なコードは普通は入れないと思います。
完全にパクりだと思います。 >>103
参考文献に書いてあるんだからパクリも糞も無い罠
参考文献に書き漏れたら小保方さんみたいに突っ込まれるが 『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の
他のプログラムもおそらくすべて『アルゴリズムイントロダクション』の
プログラムをそのまま使っています。
恥を知れと言いたいです。 参考文献に文献を挙げれば何でも許されるということはないと思いますが。 『アルゴリズムイントロダクション』のほうをよく読んでいませんが、
「if key < A[i] エラー：新しいキーは現在のキーより小さい」
というのも『アルゴリズムイントロダクション』のほうでは意味があるのかもしれません。
それをそのまま何も考えずにコピペしたために、意味不明なことになっているのかも
しれません。
>>98
を見て、誰か納得のいく説明ができるでしょうか？
意味不明としか言えないかと思います。 『アルゴリズムイントロダクション』のほうをよく読んでいませんが、
『アルゴリズムイントロダクション』のほうもまたどっか別の本からのパクリの悪寒。 "error: heap underflow" でググるといっぱい出てくる ID:GDWdcO6h は何をそんなに怒ってるの？
問題が解けなくてイライラしてるだけ？
どんな本も参考文献があり、どんなアルゴリズム、データ構造も元をたどれば最初に「ヒープで実装すればうまく行くぞ！」と発見した人の論文があるはず
新しい本を書くときは参考文献よりもわかりやすくなるように、説明やイラスト、擬似コードを変えたり、あるいは同じものを流用することもあるだろう プログラミングコンテスト攻略のための、
アルゴリズムとデータ構造、渡部有隆(わたのべ ゆたか)、2015
Ozy(協力), 秋葉 拓哉(協力)
Aizu Online Judge(AOJ、会津大学)
プログラミング・コンテスト・チャレンジブック、第2版、2012
秋葉 拓哉, 岩田 陽一, 北川 宜稔
元々は、3人の東大大学院生が作った、チャレンジブックが大ヒットした。
今までは、こういうコンテストの問題を研究した本が無かった
一方、すでに海外では、TopCoder, Google Code Jam などが、
プログラマーの主戦場となっていて、日本では、AOJ が後を追っている状態
渡部有隆の本は、チャレンジブックの後に出した。
協力に、秋葉 拓哉の名前もある
プログラマ脳を鍛える数学パズル
シンプルで高速なコードが書けるようになる70問、増井 敏克、2015
一方、増井は、Rubyで解く、このパズル本で、
「ITエンジニアに読んでほしい！技術書・ビジネス書 大賞（ITエンジニア本大賞）」を受賞している 漏れも、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、となり複雑だから >>114
汚すぎるコードだ。なんだろう。初心者とも違うな。
まるで20年ぐらい前から成長してない人が書いたコードのようだ。 すまぬ
JavaScriptも、よく知らずに書いたのだw
本当は、== ではなく、型も一致する厳密等価演算子、=== を使うべきだろう
まあ、JSなどで、とても開発はできない。
Haxe で書き直せばよいのだろうが
Kotlin, Electron やら何やら、最近の言語に、ついていけてないw > 本当は、== ではなく、型も一致する厳密等価演算子、=== を使うべきだろう
そういうレベルじゃない。
無駄なロジック、意味不明な変数名、多すぎるコメント、
コードの意味を何一つ分かってないとしか思えないといってんの 俺はむしろここ
> このソースコードのライセンスは、MIT License です
> Original Copyright (c) 2014 Michihito Seto All Rights Reserved.
残飯を神棚に飾るが如く宣言
ここにこそ初心者らしさが凝縮されてる >>114
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の
「if key < A[i] エラー：新しいキーは現在のキーより小さい」
というのは意味があるのでしょうか？ jsdo使ってるやつって汚いコードが多いよな。
素人が使いたくなる機能でもあんのか？
ブラウザだけで開発ができるとか？ デバッグなど必要のないくらい簡単なコードなので、デバッグ用とは考えられないかと思います。 Introduction to AlgorithmsよりもAlgorithms(Sedgewick、赤い本)のほうがいい本ですね。
読んでいて楽しい。 日本語のデータ構造とアルゴリズムの本だと、茨木の本が有名だけど、
どこがいいのかさっぱりわからない。
翻訳書ではない日本語の本でまともなのは、浅野孝夫の本くらいではないでしょうか？ アルゴリズムやコードのライセンスってどの程度のものから付けていいんだ
あんまり簡単なものだと既出すぎてライセンス付けられるのか？って考えてしまう
かといってじゃあライセンス付けていい最低ラインは何なんだという話になる >>126
ライセンスとか書いてあっても一部だけコピペして利用したら、分からないですよね。
どうやって、だれかのコードを流用したか判定するのか、それに興味があります。 アルゴリズムには著作権ないよ
あるのはそれをどう表現したか
簡単なアルゴリズムには表現バリエーションなんて限られてるから
ある程度似るのはどうしようもない デザインパターンの本高い・・・
一冊持ってたけど引っ越しのごたごたでなくしちゃった
無料で網羅できるサイトありませんかね
一冊読んではあるので、さらっと構造や仕組みを紹介してくれていればいいし
英語もある程度は読めます
基本のデザインパターンだけでもありがたいし
マルチスレッド対応に踏み込んだサイトならなおありがたいです 基本的な考え方覚えたら幾らでも応用できるだろ
カタログを後生大事にとっておく意味はない 覚えてないんすよ
記憶力ないんで忘れちゃって、ぼんやりとしか覚えてないんです
だから概要をしっかり覚え直したいなと思って >>132
いや、デザパタ本こそ手元においておくべき
わけのわからん二次情報を見るとどんどんブレていくぞ TECHSCOREのデザインパターンのページ見ることで自己解決しました デザパタカタログは便利だよね
煮詰まったときに、休憩がてらパターンを眺めてると、閃くときがある 基本的な発想を学んだらカタログはポイ
パターンに執着してもデザインがぎこちなくなるだけ >>119
jsdo.it では、全員のソースコードが、サイト内に限り、MITになる
漏れが、わざわざ、MITと書いておいたのは、サイト外でも使ってほしいという意味。
学生が勉強することも多いから、コメントも一杯書いた
2分ヒープ、AVL、赤黒木など、アルゴリズムの実装は、どうしても汚いソースコードになる 2分ヒープって簡単なアルゴリズムですよね。
汚くなりようがないように思うのですが。 計算幾何学って難しい割に見返りが少ないように思います。
だからあんまり人気がないのかもしれないですね。 >>144
全体的なリテラシの底上げがされるまではどうしてもね。 >>144
理論的な上限値をあらかじめ計算することが出来て
無駄な努力や試行錯誤をしなくて済むというメリットがあるよ 長さ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)とかあるので一つには定まってません。
なのでその対応をする関数をおしえてください。 長さ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)とかあるので一つには定まってません。
なのでその対応をする関数をおしえてください。 ＞なのでその対応をする関数をおしえてください。
意味不明です。 (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)
を返せばいいのでは？ (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 のときには、条件を満たす列は存在しないね。 >>149
列の最初の数字だけ1足すなり引くなりして返せばいいだけじゃないの？ ＞例えば n=3のとき(1, -1, 1)は大きさが3で、これに対応する大きさ2の列は
＞(0 ,-1 ,1), (1,0,1),(1,-1,0)とかあるので一つには定まってません。
＞なのでその対応をする関数をおしえてください。
一つに定まらないから、すべての結果を返したいのか、
任意の一つの結果を返したいのか？ 明らかに、
(0, 0, ..., 0) に対しては条件を満たす結果は存在しないね。 >>154
a_2を1としたとき(-1, 1)のとき(-1,0)を返し
a_1を-1としたとき (-1,1)は(0,1)をかえすことになるので
一つに定まりません >>157
大きさn>0の任意の列aにたいしてf(a)=bでbがn-1の大きさでaと列の中の値が1だけ違う
列を出力する関数fを求めるということです。 >>156
初めはそんな風に考えてる時期もありました
もう2か考えてるけれど全然わからないのでここで質問してみました >>161
問題文を鸚鵡返しするんじゃなくて、質問者の質問に答えたら？ >>163
fの出力は列の集合じゃないから普通わかりますよね >>164
fが返すのは集合じゃないってのはどこに書いてある？ >>166
Mateだと>>156って書いてあるわ
自分の中ではこれは当然みたいな条件がいろいろあるんだろうけど、それを人に説明するのが下手なんじゃね 改行コードの数を数えてますか？
文の折り返しと改行とは違いますよ？ 課題という証拠はありますか？
実際課題じゃなくプログラミングしていたら出てきた問題なので
全然課題じゃないです >>170
あなたには誤った文を訂正する能力がないんですか？
それでは人間ではなくコンパイラーと同じですよ >>169
面白い問題とつまらない問題を区別する能力が数学的推測には
一番必要なんんです
この問題がつまらないと思うのなら解かないでいいです あと、面白い問題だと思うなら、それこそ自分で解くのが楽しいのでは
ここで聞かずに >>175
楽しいものは独り占めるのではなく分け与えようと習わなかったのでは？ >>174
今読み返してみましたがキチンと書かれてますよ
どこがキチンと書かれてないのか言ってくれたら
それは理解力の無さなので説明してもいいです 先頭から非0を探して、はじめの要素が正なら1ひく、負なら1足す
これで終わりじゃないの？ >>171
茶か尿かもう判らんって意見があるけど
検出時のガスクロのデータ見直したら判るはずという話がある
仮にそれでお茶だとしてももう発表はないだろう 数列 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 を求めるプログラムを作れ。 mなんていくらでもあるんじゃないの？
なんで#{m}=1？ >>187
一意的です。そこがちょっと面白いところです。
反例を作ろうと思ってもできないはずです。 k=1, l=2で、{m}={2,4,6,8,...}
k=l=1で、{m}=自然数の集合
じゃないの？ >>190
{a_n} の任意の＊連続する＊有限部分列を a_k, a_(k+1), …, a_l（k ≦ l）とする。 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} です。 a_1 = 1
なので、
b_1 = 0
です。
なので、
{m} = {1}
です。 k=1, l=2も、k=l=1も、当然連続する部分列でしょ
{b_i}を10個ぐらい挙げてみてよ b_i ≦ b_mさえ満たせばいいんならmなんていくらでもあるでしょ b_m は b_i の最大値です。
その最大値となる b_m の m が一意的であるということです。 テレンス・タオ ルベーグ積分入門
テレンス タオ
固定リンク: http://amzn.asia/8KaL6NK
「日本の理工系学部ではルベーグ積分は3年次程度の必修相当科目なので、」
↑これっておかしくないですか？
普通、ルベーグ積分なんてやるのは数学科かせいぜい物理学科くらいじゃないですか？ >>199
各 i（k ≦ i ≦ l）に対して、0以上の整数 b_i を以下で定義する： >>202
不完全なところはありません。
よく問題文を読んでください。 >>203
mがkからlの間なんて一言もないんだから不完全 >>206
>>183
各 i（k ≦ i ≦ l）に対して、0以上の整数 b_i を以下で定義する そうだとして、わざと誤読を誘おうとしている悪問だね
でO(log k)のアルゴリズム思いついたから俺は降りるね >>183
の解答は以下です。
http://imgur.com/rAnp3Ga.jpg
赤線を引いたところは「odd」が正しいですね。 実は、この問題には続きがあります。
m, n を m < n を満たす正の整数とします。
このとき、
1/m + 1/(m+1) + … + 1/n
は整数にはならないことを証明せよ。 >>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 となって矛盾 >>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 で矛盾 ダイクストラのアルゴリズムの正しさの証明が載っている本で
一番分かりやすい本を教えてください。 『アルゴリズムイントロダクション』について質問です。
この本での実数の集合には、 ∞, -∞ が含まれるのでしょうか？
最短路問題の説明で、
実数 a が a≠∞のとき、 a + -∞ = -∞
実数 a が a≠-∞のとき、 a + ∞ = ∞
という記述があるために質問します。 実数 a が a≠∞のとき、 a + -∞ = -∞
実数 a が a≠-∞のとき、 a + ∞ = ∞
-∞ + -∞ = -∞
∞ + ∞ = ∞
という等式を含めたいからこのような書き方になったのでしょうか？ それは実無限派の書き方だが，世の趨勢は可能無限
ほどほどに相手をするだけでいいよ >>221
ということは、『アルゴリズムイントロダクション』での実数の集合の定義には、
∞、-∞ が含まれるというk十ですね。 頂点の数が n のグラフで、任意の頂点間に辺が存在するようなものを考える。
ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を求めよ。 頂点の数が n（≧2） のグラフで、任意の頂点間に辺が存在するようなものを考える。
ある任意の頂点から別の任意の頂点への閉路をふくまない経路の数を a_n とする。
このとき、
(n-1)! ≧ a_n ≧ (n-2)!
が成り立つことを示せ。 宿題ではないのです。
ある本に、頂点 s から t への最短経路を計算する方法として、
s から ｔ へのあらゆる経路の長さを考えて、最小の経路を選ぶとすると、
経路の数が O(n!) だから現実的ではない
という話が書いてあります。
ところが、計算してみると、 O(n!) は荒い評価であって、 O((n-1)!) とできますね。 ダイクストラ法の正しさの証明で分かりやすい証明を思いつきました。
発表しましょうか？ >>227
オーダーについてあんま良くわかってないんだろうけどO((n-1)!) なんて書き方はないよ
もし書いたとして、それはO(n!)と同じもの >>222
実無限はいろいろ破綻するから可能無限にしておいたほうがいいよ
実数の定義に∞, -∞は入らない
というか，そもそも -∞ というのがおかしい存在
つリーマン球面 なんか正しさの証明を書いてみると簡単なことなのに長くなりますね。
もし、間違っていたら指摘してください。
http://imgur.com/PDx2vmZ.jpg
http://imgur.com/DbMiSz5.jpg
ダイクストラのアルゴリズムは↑のものとします。 節点 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) が成り立つと仮定する。 第 (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) = ∞ が成り立つ。 (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) が成り立つ。 以上より、第 (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) が成り立つ。 >>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)) ではありません。 したがって、
O(f(n)) と O(g(n)) は異なります。 >>224
>>227
閉路を含まないから、各点を高々1回しか通らない。（端点も）
直通の経路が １
途中でｋ個所を通過する経路が
(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)!)
である。 >>234-238
のダイクストラのアルゴリズムの正しさの証明に間違いはないという
ことでOKですか？ Erik DemaineはMITの歴史上最年少で教授になったという天才だそうですね。
今、そのErik Demaineの2005年のダイクストラのアルゴリズムについての講義を見ています。
見終わったら、講義の要約について書きます。 ダイクストラのアルゴリズム：
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) 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) が確かに
成り立っている。 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)
が成り立つが、これは矛盾である。 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)
となる。 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) 今、 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) となるが、これは矛盾である。 Lec 17 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005
https://youtu.be/xhG2DyCX3uA アルゴリズムイントロダクションって自明なことをわざわざループ不変量を使ったりして、
証明していて、うざすぎますね。 通常の数学の本なら自明で済ませるようなことをわざわざ証明している。 http://hissi.org/read.php/tech/20160422/cGVtVmVaYUg.html
http://hissi.org/read.php/tech/20160612/YkttemlBQ3Y.html
こいつだ。
> って当たり前のことをループ不変とかを使って説明しているよね。はっきりいってくどい。
> ループ不変式とかいうのが出てくるけど、当たり前のことを形式的に証明しているだけで、つまらなすぎる。
> 馬鹿の一つ覚えみたいにループ不変式をつかって証明しようとしている。
これぞ「馬鹿の一つ覚え」である。 クヌースの本なんかだと妙なくどさはない。
アルゴリズムイントロダクションはメリハリが全くない。
Trivialなこともそうでないことも平等に扱いすぎている。
要するに本を書くセンスがない。 日本語の本について言及しておく。
例えば、評判のよい茨木俊秀の本。
こんな薄いスカスカの本をよくも恥ずかしげもなく出版するものだとあきれる。 アルゴリズムイントロダクションの悪口を書いたがいいところもある。
例えば、第29章線形計画法。
線形計画法に対しては、Trivialなこともそうでないことも平等に扱うという方針が
向いているように思う。
ただ、アルゴリズムの本に線形計画法を入れる理由が分からない。
整数論的アルゴリズムの章はあまりにも簡単すぎる。
高木貞治の本でも読んだ方がよい。 結論として、ベストな本はクヌースが予定しているTAOCPの要約本ということになる。 例によって ID:4i7P3+nF が発狂しててﾜﾛﾀ >>263
では、なぜ、一般に、コンピュータ科学者よりも頭が良いとされる数学者が
自明で済ませることが多いのでしょうか？
もし危ういのなら頭のよい数学者は自明などと書かないはずです。 >一般に、コンピュータ科学者よりも頭が良いとされる数学者が
根拠は？
>自明で済ませることが多いのでしょうか？
数学のコンテキストの話
そもそも証明の意味もコンピュータ科学と数学では違うだろ なんでバカって本質に関係ないところでギャーギャー騒ぐの？ アルゴリズムイントロダクションについて、数学が出来る人向けの本だという人がいる。
そして、数学ができない人はセジウィック＆ウエインの本を読めという人がいる。
アルゴリズムイントロダクションが数学的な本だとは全く思わない。数学的な内容については
主に結果だけを書いている。
ただネチネチとアルゴリズムの正しさの証明が書かれているだけのこと。
クヌースの本のように、楽しい本ではない。 再帰の除去についてやり方が詳しく書いてある本を教えてください。 プログラミングコンテストチャレンジブック第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
ソースレベルで再帰を除去する方法が知りたいんですが。 秋葉らのプログラムでもWrong Answerになっていまします。
入出力の問題のようですね。 入出力の問題ってやっかいですね。
出力がどうなっているかとかPOJでは調べられないんですか？ なんなんだろう？
scanf,printfを使っていたらダメだったのが、cinとcoutにしたらOKになった。 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-287
ありがとうございます。
でも解説されていませんね。 どうやって計算量を見積もるんですか？
何を単位にするんですか？ T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)
と解けばいいんですかね？ T(n) = c1 + c2*n + T(n-1)
T(0) = c3
この漸化式の解を求めればいいんですかね？ 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)
おお、あってるっぽいですね。 >>290-292
は我ながら明解な解答ですが、
教科書では、以下のように導出しています。
この導出がよく分からないのですが。
「以前に解かれている部分問題を解くための再帰は直ちに戻るので、Fは
各部分問題をただ1度だけ解く。この手続きはサイズが0,1,....,nの部分問題
を解く。サイズがnの部分問題を解くために、for文がn回繰り返される。したがって、
Fの再帰呼び出し全体における、このfor文の繰り返し回数は等差数列を形成し、
総繰り返し回数はΘ(n^2)となる。」 あーあ、分かりました。
T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)
このあたりのことを言っているんですね。 >>289
for文の繰り返し回数＝計算量ですね。 よくやった
褒美として自分専用のスレを立てる権利をやろう プログラミングコンテストチャレンジブック
p.45 Best Cow Lineっていう問題の解答のプログラムって無駄がありますよね。
この本を難しいという人がいますが、そんなに難しいですかね？ プログラミングコンテストチャレンジブック
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
最強最速アルゴリズマー養成講座
この3冊に共通していることですが、日本語が下手ですよね。
一番ひどいのが
最強最速アルゴリズマー養成講座
ですね。 一番面白いのは、
プログラミングコンテストチャレンジブック
だと思いますけど、例えば、貪欲法でなぜうまくいくのかの証明が書いてないですね。 >>301
うむ
日本語下手なのはもちろん英語も下手みたいだな 頭の使い方が下手というかそもそも頭が不自由なんだろう アルゴリズムイントロダクションの練習問題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] 15.1-2
反例
p[1] = 1
p[2] = 5
p[3] = 7 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)と書いてあるんですかね？ 配列を使わないと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)
ですね。 あ、ひっかけがありましたね。
訂正します：
n > 0 のとき、
#V = n + 1
#E = 2*(n - 1)
n = 0 のとき
#V = n + 1
#E = 0
ですね。 アルゴリズムイントロダクションに、以下の事実を1955年にRobbinsが発見したと書いてあります。
--------------------------------------------
すべての n ≧ 1 に対して
n! = sqrt(2*π*n) * (n/e)^n * exp(α_n)
と書ける。
ただし、 1/(12*n+1) < α_n < 1/(12*n)
--------------------------------------------
本当にこんな比較的簡単にみえる結果が1955年という比較的最近になって発見された
のでしょうか？ >>308
フィボナッチだろ
√5が出て来る公式
O(1)になるかも試練が >>311
r ‐､
| ○ | r‐‐､
_,;ﾄ - ｲ、 ∧l☆│∧ 良い子の諸君！
（⌒` ⌒ヽ /,､,,ﾄ.-ｲ/,､ l
|ヽ ~~⌒γ ⌒ ） r'⌒ ｀!´ `⌒） よく頭のおかしい数学者気取りのバカが
│ ヽー―'^ー-' （ ⌒γ ⌒~~ / 「誰も気付かなかった事を発見したことを発表」とほざくが
│ 〉 |│ |｀ー^ｰ― r' | 大抵それは「先人が思いついたけどあえて発表しなかった」ことだ
│ /───| | |/ | l ﾄ､ | 王道が何故面白いか理解できない人間に面白い話は
| irｰ-､ ｰ ,} | / i 作れないぞ！
| / ｀X´ ヽ / 入 | アルゴリズムイントロダクションが難しいという人がいますけど、
この本は馬鹿丁寧に書かれていますよね。
いわゆる「書きすぎ」ですね。
「書きすぎ」れば分かりやすくなると思い込んでいますね、著者らは。 プログラミング言語のパーサーってどういう仕組みで動いてるんですか？
文字列をトークンの配列に分ける
特定のパターンにマッチするトークンの部分集合をひとまとめにして新しいトークンに置き換える
再帰的に同じ事を繰り返す
こんな感じ？ 類似スレ検索とかのアルゴリズムって何がいいのかな？
編集距離とか数字部分のマスキングくらいしか浮かばない
形態素解析して要素の一致率とかもあるみたいだけど、スレタイみたいな短い文字じゃ弱そう むしろ短くて重要な単語が多いスレタイこそ一致率うまく働きそうか
毎回評価してたら検索速度悪そうだけど Baka ha sinanakya
Naoranai
Fucky ou アルゴリズムイントロダクション
当たり前のことを定理などとよんで回りくどく証明していますね。
なんなんですか？この本。
例えば、p.506定理22.9とか。 当たり前のことを2chで指摘して回りくどくdisっていますね。
なんなんですか？あなた。
例えば、 >>324 とか。 >>324
当たり前が何故当たり前なのかを知るのは割と重要だが。 >>324
しかも「証明」が長い。当たり前のことを長々と書いている。
その「証明」自体も意外性ゼロ。 しかも徹底していない。
ある命題は明らかで済ませている。
その一方である命題には長々と「証明」をつけている。
基準がさっぱりわからない。 初級アルゴリズム本持ち出して何なんですか言われてもねぇ。。。
物足りなかったら上のクラスの本買えば？ とにかくしつこい本。
この著者らの感性は、おかしいと思う。
丁寧というよりしつこい。
クヌースの本は丁寧という感じ。
結局、教科書の書き手として優れていない。 アルゴリズムでは、セジウィックが有名。他に、
入門 データ構造とアルゴリズム、2013、オライリー
Narasimha Karumanchi(インド人) 著
プログラミング・コンテスト・チャレンジブック、第2版、2012 アルゴリズムイントロダクションは訳もひどいね。
意味不明だと思って原著を調べるといつも誤訳。
今読んでいるところにも誤訳を見つけた。
本当に理解して訳しているか？ 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 の先行点では、もちろんない。 今扱ってるライブラリのコンストラクタとか生成系のメソッドとかの引数が多すぎるんで何とかしたいんだがビルダーパターンぐらいしかないのかな
今は引数用の構造体を用意して成のメソッドの呼び出し時に構造体を参照させるようにしてるんだが、お前らどう思う？ まあ、ファクトリかビルダだろうな
引数をオーバーライドメソッドでなるべく少なくなる工夫しつつ グラフ理論のアルゴリズムを実装したときに、正しいかどうか
チェックするのって、グラフを用意しなきゃならなくて大変だけど
サンプルのグラフってどこかに公開されていないの？ >>341
>>342
やっぱそれぐらいしかないか
レスさんくす >343
Knuth先生のThe Stanford Graphbase
http://www-cs-staff.stanford.edu/~knuth/sgb.html 2つのグラフが同型かどうか判定するアルゴリズムを教えてください。 ちょっと手間を減らすなら、次数でソートしたりゴニョゴニョできるけど、NPだからあとは力技 最終的に力業になることが分かってる問題って悲しいよね。 >>348-349
ありがとうございました。
基本的で重要な問題なのにアルゴリズムの本で見かけなかったのは効率的な
アルゴリズムが存在しないからだったんですね。
効率的なアルゴリズムが存在しない場合でも、小さい問題は解けるわけですから、
それなりの工夫でもいいから、教科書に載せてほしいです。 >>348-349
グラフが同型かどうかくらいならプログラムを誰でも作れると思います。
効率的なアルゴリズムが存在しない問題の場合、教科書にはアルゴリズムが
載っていないことが多いと思います。自分で力任せのプログラムを書ける場合
はいいですが、力不足で力任せのプログラムすら書けない場合って困りますね。 >347
networkXっていうPythonのグラフアルゴリズムのライブラリに、グラフ同型判定の関数があるよ。
is_isomorphic()
ソースコードも見れるから、実装の参考にしては。
VF2アルゴリズムというのを使っているらしい。どういうのかは、知らない。。 >>352
今、グラフ理論の本を読んでいるのですが、その演習問題の
答えを計算機で計算したいと思いプログラムを作っています。
手計算でできる問題なので計算量とかは無問題です。
情報、ありがとうございました。 セジウィックのアルゴリズムCはコルメン他の本とは対極にあるような本だね。
どっちもどっち。 セジウィックのアルゴリズムＣは定義がダメダメ。
例：
連結グラフの極大木とは、すべての頂点を含む部分グラフであって、
木である限りできるだけ多くの辺をもつものをいう。
この定義だと連結グラフに極大木が常に存在するというのが定理になってしまう。
が、証明せずに、この事実を以下で使っている。 浅野孝夫著『アルゴリズムの基礎とデータ構造 数理とCプログラム』（近代科学社）
ポインタを使えるCでアルゴリズムを実装しておきながらポインタを使わず、
配列を使ってポインタの機能を実現するという面倒なことをしています。
著者は何を考えているのでしょうか？ 浅野孝夫著『アルゴリズムの基礎とデータ構造 数理とCプログラム』（近代科学社）
の公式ページからソースコードをダウンロードできます。
たくさんのソースコードがあるのですが、こういうのを実行するときってみなさんは
どうしていますか？
Visual Studio を使っているのですが、一つのソースファイルに対して、いちいち
プロジェクトを作っていると面倒なんですが、どうすればいいですか？ コマンドプロンプトからコマンドを実行してコンパイルをしたりする原始的なやり方
は避けたいです。 探せば学習用のC言語インタプリタとかあるんじゃない ちょっとサンプルコードを走らせるかって程度なら
Online IDEとか使えばよいのに そもそも何でファイルごとにわざわざプロジェクト作るような原始的なことやってるの プロセス増えるだけだからプロジェクトは増やさなくてもいいんじゃね アルゴリズムとデータ構造の本のソースコードを見ると、よくグローバル変数を
多用していて非常に分かりにくいことが多いです。
グローバル変数を使うのは良くないというのをよく目にしますが、なぜ、
コンピュータサイエンスのプロであるはずのアルゴリズムとデータ構造の本の
著者がそんなプログラムを書くのでしょうか？ 例えば、
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
という本のソースプログラムが分かりにくいです。
拡張子が「.h」のファイルにグローバル変数を定義して使いまわしています。
さらに、その拡張子が「.h」のファイル内で「emaxsize」というのがありますが
それが何なのかが書いてありません。
その拡張子が「.h」のファイルを利用するファイル内で、「emaxsize」を設定しています。
こういうのはありなんでしょうか？
あちこちいろいろなファイルを見ないと、全体が分かりません。 >>371
Javaしか使ったことない人が知ったかぶりでCの本出すからそうなる
捨てろ 全然、プログラム作りの参考になりません。
ただ、例外もあります。
セジウィックの『Algorithms』という赤い本は、参考になります。 >>373
でも、コード自体は非常に巧妙で優れています。 そういえば、茨木俊秀の本のプログラムもひどかったような。 グローバル変数を避けようとかはソフトウェア工学の話で、コンピューター科学とは別の分野なんだよ。 グローバル変数を使った方が、説明しやすいとか、
ソースコードがわかりやすいとか
本の目的が、アルゴリズムの説明だから、
グローバル変数を使って、わかりやすく説明するのも、OK
物事には強弱・重要度があるから、
重要な事を説明する際、重要でない事は無視してもよい
これを、TPO と言って、強弱を付けられる人は、空気を読める
ちょっとしたプログラミングに、型チェックする、Javaなどを使わず、
Rubyで書くのもそう。
ラフな会合に、盛装して行かないのもそう 掲示板のTPO弁えない人にTPO語ってもしょうがないよ グローバル変数を明らかに、分かりにくいやり方で使っています。
何の利点もないと思います。 もしかして、理論ばかりに興味があり、プログラムを作ったことがないんですかね？ プログラム教本ではなくアルゴリズム解説本だからでしょ
擬似言語で書いている場合のが多いと思うけど 最初から完成してたらおまいらの仕事無くなっちゃうだろ 楽器やってるひとがいってたよ。自分がつかえる技術を全部つかうわけじゃない 浅野孝夫の本。
ちょっと説明が足りないところがある。
完成度がやや低い。
他の日本人の本よりはまし。
プログラムは巧妙。 こんなところに日記書く人って、相当追い詰められてるんだろうな。 浅野孝夫の本。
深さ優先探索とか幅優先探索の説明を言葉で長々としています。
そんなことするより、コードを見せたほうがいいと思うんですよね。
コードを見れば一目で分かりますよね。 http://imgur.com/9QGwvmM.jpg
http://imgur.com/j3Dp32V.jpg
http://imgur.com/iJhKoqM.jpg
↑は浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）です。
重大な誤りを発見しました。
G が二部グラフであるための必要十分条件は、G を幅優先探索したときに同じ深さの補木辺がないことであると書かれていますが、
完全な誤りです。
具体的に言うと、「同じ深さの点を結ぶ補木辺がないときは、この色の割当てが実際に2彩色になっている。」と書かれていますが、
間違っています。
反例は3枚目の画像を参照してください。 訂正します：
http://imgur.com/9QGwvmM.jpg
http://imgur.com/j3Dp32V.jpg
http://imgur.com/iJhKoqM.jpg
↑は浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）です。
重大な誤りを発見しました。
G が二部グラフであるための必要十分条件は、G を幅優先探索したときに同じ深さの点を結ぶ補木辺がないことであると書かれていますが、完全な誤りです。
具体的に言うと、「同じ深さの点を結ぶ補木辺がないときは、この色の割当てが実際に2彩色になっている。」と書かれていますが、
間違っています。
反例は3枚目の画像を参照してください。 商品の説明
内容紹介
ネットワーク・人工知能の基礎となるグラフ・ネットワークを学ぶ
アマゾンに商品説明として、↑のように書かれています。
人工知能とグラフ・ネットワーク理論に何の関係があるのでしょうか？
この出版社は、「世界標準MIT教科書」などとタイトルに書いたり、売るためには
手段を選ばない出版社ですね。 >>395
自分の想像力の欠如で批判しないほうがいいよ 外国には「たのしいRuby」が無い
日本人が20時間で勉強できることを、何十時間も掛けて勉強して、なおかつ理解できない。
だから、MIT に頼る
外人でも知っている人は、Ruby でツールを作る。
Chef, Vagrant, SASS とか
Homebrew もRubyで作られているのだから、
Apple は、もっとRubyに力を入れるべき >>394
３枚目は補木辺があって２部グラフではないので、
別におかしくないのでは >>399
「同じ深さの点を結ぶ補木辺がないときは、この色の割当てが実際に2彩色になっている。」
3枚目の画像には同じ深さの点を結ぶ補木辺がありません。
ですが、2彩色ではありません。 松坂君のアスペ日記３
Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net
http://rio2016.2ch.net/test/read.cgi/math/1497007079/ 要するに、↓が間違っているわけです。
「補木辺は、同じ深さの点を結んでいるか、あるいは深さが 1 異なる点を結んでいることに注意しよう。」 ここじゃなくて著者なり出版社なりに連絡しなよ
その方がちゃんと議論できるだろうし修正されればあとから読む人の為になるよ >>400
幅優先で探索木作ったら同じ深さを結ぶ補木辺ができるから二部グラフでないことがわかる >394
三枚目の図は、反例になっていない。
あなたが幅優先探索を理解できていないだけで、書籍の記述は間違っていないよ。
根でない2つの頂点は、どちらも、根から辺が張られていて、根と隣接しているのだから、同じ深さの位置にある。 教科書だって間違いはいくらでもある。
だからといって、間違いらしきものを見つけて喜々としてあげつらうのではなく、
自分の解釈ではこうだが違うのだろうかという態度で質問しておけばよかったね。 >>393-394
他人の誤りを指摘するときに
自分でも誤るとか恥ずかしくないか KIZLA7]]]
%≒72%,M,L,TO"JYOJA" 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）ですが、この
本には強連結成分分解のアルゴリズムは書いてあるのですが、その正しさについて
の説明がありません。
「アルゴリズムの正当性については演習問題とする。」などと書かれているだけです。
そして、解答がありません。
解答をつけないほど簡単な問題でしょうか？
エイホ、ホップクロフト、ウルマン著『データ構造とアルゴリズム』に分かりやすい説明がありました。 強連結成分分解のアルゴリズムはグラフ理論的な観点からは興味深いですが、
応用についてはあまりないようですね。
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）の「はじめに」に
「強連結成分分解はシステムの故障診断や効率的解析への応用があると言われている。」
などと書かれいます。浅野さん自身は応用について具体的な詳細を知らないと宣言して
いるようなものですね。 ところで、LEDAというライブラリはお勧めですか？ 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。
G のトポロジカルラベリングについては説明があるのですが、トポロジカルソートの応用例が
全く書かれていません。
勉強するモチベーションが全くありません。
著者は一体何を考えているのでしょうか？ あ、その後の有向無閉路ネットワークの最長パスを求めるアルゴリズムで
トポロジカルラベリングが使われていました。
なかなか面白い応用ですね。
この本、説明にちょっと粗雑なところもありますが、見せ場があって楽しいですね。 有向無閉路ネットワークという制限が強すぎますね。
でもこの制限のおかげでちょっと面白いトポロジカルラベリングの応用例が見れたわけですね。 プログラミング・コンテスト・チャレンジブック、第2版、2012
ほとんど全てのアルゴリズムを網羅。
問題数も多く、パズル感覚で楽しめる。
AIやシミュレーションゲームの参考になる >>426
それとアルゴリズムの正当性のまともな説明がありません。
計算量の評価についてもまともな説明はありません。 入門 データ構造とアルゴリズム、2013、オライリー
Narasimha Karumanchi(インド人) 著
アルゴリズムなら、セジウィックでも読めば？
プログラミング・コンテスト・チャレンジブックは、
コンテストの問題を集めた本だから、便利
一々、ウェブサイトの問題を見なくても良いから、楽 >>430
そのインド人の本は、アルゴリズムの正当性のまともな説明がありません。
計算量の評価についてもまともな説明がありｍせん。
セジウィックのAlgorithms 4th Editionはいい本ですが、計算量の評価については
まともな説明がないように思います。 D40
T をグラフ G の全域木とする。
C を G のサイクルとする。
AB を C および T に含まれる辺とする。
このとき、 T から AB を除去し、辺 UV を追加したときに、
依然として G の全域木であるような辺 UV が C の中に
含まれることを示せ。 >>432
T は木であるからサイクルを含まない。
よって、 C には T に含まれないような辺が少なくとも一つは存在する。
T は全域木であるから、そのような辺の両端点を結ぶ T の辺のみからなる（一意的な）パスが存在する。
仮に、 T に含まれないような C の辺たちの両端点を結ぶ T の辺のみからなるパスたちがすべて AB を含まない
と仮定すると、 A から B への T の辺のみからなるパスで辺 AB を含まないようなものが存在することになる。
A, B という A から B へのパスは、辺 AB を含み T の辺のみからなる。よって、 A から B への T の辺のみから
なるパスが2つ以上存在することになるが、これは木の性質に反する。
よって、 T に含まれないような C の辺たちの両端点を結ぶ T の辺のみからなるパスたちの中には、 AB を含む
ようなものが存在する。そのようなパスを U, …, A, B, …, V とする。 T から AB を除去し、辺 UV を追加し
たときにできる部分グラフは明らかに T と同じ数の辺をもち、依然として連結なままである。点の数が v で
辺の数が v - 1 であるような連結なグラフは木であるから、そうような部分グラフは木である。 >>432
ヒントとして、 「T - AB は2成分からなる森である」と書いてあるのですが、
このヒントを利用した解答はどうなるのでしょうか？ 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。
↓は、ある点から各点への最長パスを求めるプログラムのメイン関数です。
「出発点を入力してください」などと出力していますが、出発点は 1 でないとダメです。
なぜかというと depth_first() 関数がかならず 1 から深さ優先探索を開始するからです。
↓を見ると、あたかも、出発点に選択の余地があるかのようです。なぜ、こんなことを
しているのか意味不明です。
int main(void){
■■■■directed_network_input();
■■■■// 有向ネットワークの辺数m，点数n，各辺の始点，終点，長さが決定される
■■■■dicomp_incidence_list_construct(); // 接続辺リストが構成される
■■■■printf("出発点を入力してください\n");
■■■■scanf("%d", &s);
■■■■printf("出発点 = %d \n", s); // sからすべての点が到達可能であることを仮定
■■■■depth_first(); // 深さ優先探索をして後行順ラベルを求める
■■■■tpsort(); // トポロジカルソートを行う（tporder[1]==sとなることを仮定）
■■■■longestpath_from(s);// sからの到達可能な点への最長パスが計算される
■■■■longestpath_output();// sからの到達可能な点への最長パスが出力される
■■■■return 0;
} 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。
ひどいバグを発見しました。
void longestpath_from(int s){// sからの到達可能な点への最長パスを計算する関数
■■■■int a, j, v, w;
■■■■dmax[s]=0; // sからsへの最長パスの長さは0である
■■■■path[s]=0; // sからの到達可能な点への最長パス木の根がsである
■■■■for (j = 1; j <= n; j++) {// トポロジカルソートに基づいて
■■■■■■■■v= tporder[j];
■■■■■■■■// sからvまでの最長パスの長さdmax[v]とパス上でvの直前の点path[v]の計算
■■■■■■■■a=revedgefirst[v]; // vを終点とする辺のリストの先頭の辺がaである
■■■■■■■■w=tail[a]; // wはaの始点
■■■■■■■■if(j == 1) printf("v = %2d, a = %2d, w = %2d", v, a, w); //debug
■■■■■■■■dmax[v]=dmax[w]+length[a]; // 式(4.2)に基づくdmax[v]の初期設定
■■■■■■■■path[v]=w; // 式(4.2)に基づくpath[v]の初期設定
■■■■■■■■a=revedgenext[a]; // aの次の辺をaとする
■■■■■■■■while (a != 0) {// vを終点とする辺のリストの末尾の辺になるまで繰り返す
■■■■■■■■■■■■w=tail[a]; // wはaの始点
■■■■■■■■■■■■if (dmax[v] < dmax[w]+length[a]){// wを経由したほうがより長いとき
■■■■■■■■■■■■■■■■dmax[v] = dmax[w]+length[a]; // wを経由するほうに更新する
■■■■■■■■■■■■■■■■path[v]=a; // aに更新する
■■■■■■■■■■■■}
■■■■■■■■■■■■a=revedgenext[a]; // aの次の辺をaとする
■■■■■■■■}
■■■■}
} 366 :nobodyさん 2017/05/29(月) 16:07:39.16 ID:6v4UcGhE
今回の民法改正、ソフトウェア受託開発の場合、(検収後ではなく)バグ発見後１年瑕疵担保責任があるということで、地獄かよ、と思ったが、
元々問題が起きがちな受託案件がビジネス的に成立しなくなることで強制的に業界再編につながるなら良いことかもと思うようになった。
一部で地獄を見ても。
https://twitter.com/yukihiro_matz/status/869061879389343744
367 :nobodyさん 2017/05/29(月) 16:28:06.55 ID:6v4UcGhE
ニュース - 改正民法が成立、「瑕疵担保責任」などシステム開発契約に影響大：ITpro
http://b.hatena.ne.jp/entry/itpro.nikkeibp.co.jp/atcl/news/17/052601508/
372 :nobodyさん2017/05/29(月) 19:10:37.12 ID:???
Railsでシステム作って納品する
↓
Railsはマイナー、メジャーのアップデートが半年以内に必ずある
↓
客がアップデートする。アップデートによるエラーやバグ、動作の不具合に気づく
↓
気づいてから1年以内に通知すれば、5年間無料保証ゲット
↓
つまりRailsがアップデートするたびに、無償の修正作業を発生するということかな
376 :nobodyさん2017/05/30(火) 09:20:20.09 ID:L5po86sS
>>378>>379>>375
客が瑕疵担保責任法の法改正を知ってくると思うから、今後5年無償保証をお願いされるだろう
営業がそれでも仕事を取ってこれるか？たぶん無理だろう。無限の直していたら赤字になる。
こういう保守に弱い言語、ころころ仕様が変わる言語は仕事として発生しなくなってくる。
これは変わり目だ。お前らも早く逃げたほうがいいぞ。RubyやPHPなど動的言語は確実に廃れる。
保守に強い言語のみ生き残れる。 ↑の for 文は j = 1 から始まっています。
v == tporder[1] == 1 です。
a == revedgefirst[1] == 0 です。
ところが、この本では配列のインデックスは 1 からしか利用していません。
インデックスが 0 の要素は初期化すらしていません。
どうも配列を初期化しないと値は不定だそうですが、実際には 0 で初期化されることが
多いようです。
仕様では不定であるはずの
tail[0]
dmax[0]
length[0]
がたまたま 0 で初期化されるため、偶然、問題なく動作しています。
正しくは、
for 文は j = 2 から始めなくては駄目です。 あ、もう一つバグがありました↑
path[v]=w; // 式(4.2)に基づくpath[v]の初期設定
となっていますが、
path[v]=a; // 式(4.2)に基づくpath[v]の初期設定
でなければなりません。 >>438
>インデックスが 0 の要素は初期化すらしていません
配列[0] を使わないのなら、初期化する必要はない >>440
そうですが、
for(j = 1;
とすると
意図せず配列[0]を使うことになってしまいます。
この値がたまたま 0 で初期化されていて、かつ 0 であれば正しく動くため、
問題が表面化していないだけです。 有向無閉路ネットワークの最長パスをトポロジカルラベリングを利用して、
求めるアルゴリズムって他の本に載っていますか？
あまりにも特殊すぎて載っていないのではないかと推測しますが。
この本は、鮮やかに解けるように問題を特殊化して見せ場を作っていますね。 >>426
その本を読むのでしたら、
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
のほうがCプログラムも載っていますし、面白いと思いますよ。
オイラーグラフの一筆書きのプログラムがあったりします。 j=1で始まってんのに意図せず配列[0]を参照するの意味がわからん >>444
このプログラムだけ見てももちろん分からないと思います。
a == revedgefirst[1] == 0 なので、 tail[a] == tail[0] です。 訂正します：
>>445
このプログラムだけ見てももちろん分からないと思います。
a == revedgefirst[1] == 0 なので、 tail[a] == tail[0] です。 さらに、
v == tporder[1] == 1 です。 http://imgur.com/A84Qz1i.jpg
http://imgur.com/NsXCsS1.jpg
http://imgur.com/Bm7ANHm.jpg
http://imgur.com/iSqMNes.jpg
↑は浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）です。
1枚目と2枚目の画像が連結な有向オイラーグラフの一筆書きを求めるアルゴリズムです。
3枚目と4枚目の画像がそのアルゴリズムの正しさの証明です。
「連結グラフ G が一筆書きできるための必要十分条件は、 G がオイラーであることである。」
という定理の証明において、十分性は、↑の3枚目と4枚目の画像の定理5.3により分かるということが書いてあります。
↑の3枚目と4枚目の画像を読めば分かりますが、十分性について証明されていないように思います。
どうでしょうか？ むしろ、十分性が成り立つことを前提にしてアルゴリズムの正しさを証明しているように思います。 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。
段々、面白いアルゴリズムが登場してきていますね。
日本語のアルゴリズムの本は本当に初歩的な本が多いですが、なぜなのでしょうか？
例えば、ホップクロフト - カープのアルゴリズムが載っている本はあるでしょうか？
日本語の本に載っているのは、
リスト、ハッシュ、ヒープ、2分探索木、平衡木、ソート、最短経路、文字列
とかそんなもんだけですよね。 初歩的な問題すら理解できずにドヤ顔で間違った反例晒すやつがいるからだよ それ以上の難解アルゴリズムに挑戦する頭脳があれば英語の習得は容易いので、結果すでにある英語本を買うようになると予想 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。
do {// マッチされていない左端点からマッチされていない右端点へのパスがある限り
■■■■levelgraph(); // レベルグラフの構成
■■■■if (t_found != n+2) augmentation(); // パスがあるときにはマッチングの更新
} while (t_found != n+2);
などというコードがあります。
do {// マッチされていない左端点からマッチされていない右端点へのパスがある限り
■■■■levelgraph(); // レベルグラフの構成
■■■■if (t_found == n+2) break;
■■■■else augmentation(); // パスがあるときにはマッチングの更新
} while (1);
と書いた方が分かりやすいですよね。
augmentation() 内では、グローバル変数 t_found の値は変更されません。
なので、以下のように書くのが標準的だと思います。
levelgraph();
while(t_found != n + 2){
■■■■augmentation();
■■■■levelgraph();
} 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。
a = edgefirst[v1];
while(a != 0){
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
a = edgenext[a];
}
などというコードが本書のソースコードのいたるところで使われています。
↓のように書くべきですよね。
for(a = edgefirst[v1]; a != 0; a = edgenext[a]){
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■
} 茨木俊秀さんの本でも感じましたが、ひどいコードを書く人が多いですよね。
一番、驚いたのが野崎昭弘さんの本です。
goto 文を使わなくていいところで常用しています。 粗さがしが得意みたいだから、出版社で校正でもやったら良いのでは？ 伏字かと思ったらインデントかよ。
これが見やすいと思ったんだろうか？ここに辿り着くまでの思考過程を見てみたいわ。 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。
for (v = 1; v <= n; v++) parent[v] = unvisited;
というコードがあります。
点 v の親の処理ですが、深さ優先探索で使う定数である unvisited == -1 を流用しています。
親は訪問するものではないにもかかわらずです。
単に -1 という値が使いたいだけです。
ひどいコードです。 >>460
基地外の思考過程なんて見たらSAN値下がるぞ。 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。
このプログラムですが、意味不明に冗長なところがあるので超分かりにくいです。
もし、この本を読む人は、注意した方がいいです。
分かりやすい等価なコードにすこしずつ変えながら読んでいます。 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
ホップクロフト - カープのアルゴリズムのところを読んでいます。
プログラムに、非常に非効率な部分を発見しました。
深さ優先探索で最短パスを探す部分があるのですが、一つの最短パスを
発見した後も、うろうろと探索を続けています。 return 文で呼び出し元へと
遡って戻るべき箇所です。
具体的にいうと、p.95の void bipartite_dfs(int) 関数内の
bipartite_dfs(w1);
は、
bipartite_dfs(w1);
if(pathfound) return;
とすべきです。 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
のHopcroft-Karpのアルゴリズムのプログラムを一切変更を加えずに使用して、
Aizu Online Judgeの2部グラフのマッチングの問題を解かせてみたら、
1問目から正しい結果が得られませんでした。
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
では一つの例に対して、プログラムをチェックしているだけです。
その例に対しては正しい結果が得られます。
著者はおそらく他の例についてはチェックしていないと思われます。
これから原因を究明しようと思います。
ちなみに
浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
での例ですが、この著者の旧著でも全く同じ例を使っています。
使いまわしですね。他の例は一度もチェックしていないようです。 👀
Rock54: Caution(BBR-MD5:0be15ced7fbdb9fdb4d0ce1929c1b82f) あ、勘違いでした。
入力のフォーマットが会津と浅野の本で違いました。 >>468
なんか明らかなことをダラダラと証明していますね。 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
を読んでいます。
定理：
G のマッチング M に対して、 M が最大マッチングであるための必要十分条件は M に
関する増加パスが存在しないことである。
という定理が書いてあります。
十分性の証明が長すぎます。見た目はちょっとすっきりとしていていいのですが、長くて
素朴な証明法ではありません。 以下のような証明が素朴なよい証明だと思います。
G のマッチング M に対して、 M が最大マッチングであるための必要十分条件は M に関する増加パスが存在しないことである。
必要性は明らかである。
十分性について証明する。
G は連結である場合に証明できれば、 G が連結でない場合にも、明らかに定理は成り立つ。
そのため、 G は連結であると仮定する。
G には、 M に関する増加パスが存在しないと仮定する。
M の辺に接続されていない点をFreeな点と呼ぶことにする。
G にFreeな点が2点以上存在することはないことを背理法によって証明しよう。
a, b を G の任意のFreeな2点とする。 G は連結だから、 a, b を結ぶ単純なパスが存在する。
a = a_1, …, a_k = b をその単純なパスとする。
このとき、 a_1, …, a_i に含まれるFreeな点の数が 2 であるような i ≧ 2 が存在することは明らかである。
単純なパス a_1, …, a_i は明らかに増加パスである。
これは、 G には、 M に関する増加パスが存在しないという仮定に反する。
よって、 G にFreeな点が2点以上存在することはない
G にFreeな点が1点存在する場合には、 G の点の数は、奇数であり、明らかに M は最大マッチングである。
G にFreeな点が1点も存在しない場合には、 G の点の数は、偶数であり、明らかに M は最大マッチングである。 なんか他の本を調べてみても、
>>471
のような素朴な証明法が載っていませんね。
ソートするアルゴリズムが存在することを示せ
という問題があったとして、答えとして、バブルソートをあげれば十分であるにもかかわらず、
ヒープソートをあげるようなもんですね。 >471
頂点a b c d eがあって、
辺が、
a b
a c
a d のとき、
Mとして
a bを選べば、増加パスはないけど、
cとdはFreeな頂点になるのでは？ >>473
ありがとうございます。
>>471
は間違いですね。 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）を読んでいます。
ネットワークフローについてですが、
ソースから流出する総フローが、
シンクに流入する総フローに
等しいということを自明のこととして、
証明していません。
これはOKなのでしょうか？ やはり証明は必要なんですね。
↓の本に証明が載っていました。
組合せ数学入門 II (共立全書)
C.L.リウ
https://www.amazon.co.jp/dp/4320005422 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）
は、計算量の評価の説明がひどすぎます。
ほとんど結果しか書いていません。 >>478
少し後のところで、
ソースから流出する総フローが、
シンクに流入する総フローに
等しいという結果を特別な場合として
含むような結果を示していました。
ソースから流出する総フローが、
シンクに流入する総フローに
等しいということが自明なことならば、
そのより一般化された結果も自明です。
著者の態度は矛盾していますね。 僕の肛門から流出するソースの総フローがシンクに流入します 今、ウィルソンのグラフ理論の本を見てみたのですが、内容がスカスカですね。
アルゴリズム的なグラフ理論の本のほうが分かりやすいし、面白いですね。 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）の
Ford - Fulkerson のアルゴリズムのプログラムを読んでいます。
ひどいプログラムです。
たとえば、深さ優先探索を行う関数を見てください↓
void dfs(int v, int path[]){// vからの深さ優先探索
■■■■int afwd, abk, w;
■■■■afwd = edgefirst[v];
■■■■while (afwd != 0 && rescap[afwd] == 0) afwd = edgenext[afwd];
■■■■while (t_found == false && afwd != 0) {// 増加パスはまだ発見されいない限り
■■■■■■■■w = head[afwd];
■■■■■■■■if (path[w] == unvisited) {// wが未訪問であったらwへ前進
■■■■■■■■■■■■abk = afwd+1; // abkはafwdの逆向きの辺
■■■■■■■■■■■■if (afwd % 2 ==0) abk = afwd-1;
■■■■■■■■■■■■path[w] = abk; // afwdの逆向きの辺abkをpath[w]に記憶する
■■■■■■■■■■■■if (w != t) dfs(w,path); // wからの深さ優先探索へ進む
■■■■■■■■■■■■else {// w == t なので増加パスPが見つかった
■■■■■■■■■■■■■■■■t_found=true; // dfs(v,path)の強制終了へ
■■■■■■■■■■■■}
■■■■■■■■}
■■■■■■■■if (t_found == false) { // dfs(v,path)が強制終了になっていないときのみ
■■■■■■■■■■■■ afwd = edgenext[afwd]; //次の辺に移る
■■■■■■■■■■■■ while (afwd != 0 && rescap[afwd] == 0) afwd = edgenext[afwd];
■■■■■■■■}
■■■■}
} ↓は、↑と等価なプログラムです。
すっきりとしていて分かりやすいですね。↓
void dfs(int v, int path[]){
■■■■int afwd, abk, w;
■■■■afwd = edgefirst[v];
■■■■for(afwd = edgefirst[v]; afwd != 0; afwd = edgenext[afwd]){
■■■■■■■■if(rescap[afwd] == 0) continue;
■■■■■■■■w = head[afwd];
■■■■■■■■if(path[w] == unvisited){
■■■■■■■■■■■■if(afwd % 2 == 0){
■■■■■■■■■■■■■■■■abk = afwd - 1;
■■■■■■■■■■■■}else{
■■■■■■■■■■■■■■■■abk = afwd + 1;
■■■■■■■■■■■■}■■■■■■■■
■■■■■■■■■■■■path[w] = abk;
■■■■■■■■■■■■if(w != t){
■■■■■■■■■■■■■■■■dfs(w, path);
■■■■■■■■■■■■}else{
■■■■■■■■■■■■■■■■t_found = true;
■■■■■■■■■■■■■■■■return;
■■■■■■■■■■■■}
■■■■■■■■}
■■■■}
} 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社）のプログラムは
すべて↑こんな感じなので、いちいち自分でまともな等価なプログラムに改善してから
読む必要に迫られます。 for-2ch-codes/FlowLibrary.h
↓こちらが浅野さんの Ford - Fulkerson のアルゴリズムのソースコードです：
for-2ch-codes/asano_fordfulkerson.c
↑なぜ、こんな分かりにくいコードを書けるのか不思議です。
アルゴリズムの研究者なのに、プログラミングをしたことがないのでしょうか？
↓こちらが浅野さんのコードを読みやすくした等価なコードです：
for-2ch-codes/my_fordfulkerson.c ■■■■■■■■■■■■■
■■このスレ闇が深すぎ■■
■■■■■■■■■■■■■ >>496
教科書の荒さがして著者をdisることを生きがいとしてる厨房
ID:bx7kaphQ
Daniel Marcus Graph Theory を読む。 [無断転載禁止]©2ch.net
http://rio2016.2ch.net/test/read.cgi/math/1497007079/ >>497
高等な趣味だと思うよ，よく頑張っているね お前ら、ちゃんと次スレ立ててやれよ？
隔離スレさえあればこっちに被害は及ばないからな 比較によるソートの比較回数の下限についての議論で決定木が登場します。
決定木の葉の数が n! 以上だという記述があるのですが、ちょうど n! ではないのでしょうか？
意味不明です。 例えば、決定木の内部ノードに 1: 2 というのノードにおいて、
a_1 ≧ a_2 であるか a_1 < a_2 であるかを計算しますが、
その計算結果を捨ててしまってもいいんですよね？ 例えば、決定木の内部ノードに 1: 2 というノードがあったとすると、そのノードにおいて、
a_1 ≧ a_2 であるか a_1 < a_2 であるかを計算しますが、その計算結果を捨ててしまっ
て以後利用しなくてもいいんですよね？ 段々、言いたいことが分かってきました。
a1, a2, a3, a4 を比較によってソートするあるアルゴリズムがあるとします。
そのアルゴリズムには対応する決定木 T が存在します。
深さ k の決定木の葉の数の最大値は明らかに 2^k です。（深さ k の完全2分木の場合）
a1, a2, a3, a4 の大小関係の可能性は、以下の 4! = 24 通りあります。
a1 < a2 < a3 < a4
a1 < a2 < a4 < a3
…
a4 < a3 < a2 < a1
そのすべての可能性に対してそのアルゴリズムはソートしなければならないので、
T の葉の数はちょうど 24 であるはずです。
深さ 1 の決定木はただ一つ存在し、葉の数は 2 です。
24 ≠ 2 なので、 T の深さは 1 ではありません。
深さ 2 の決定木の葉の数の最大値は 2^2 = 4 です。
24 ≦ 4 ではないため深さ 2 の決定木では、 24 個の葉を収容できません。
深さ 3 の決定木の葉の数の最大値は 2^3 = 8 です。
24 ≦ 8 ではないため深さ 3 の決定木では、 24 個の葉を収容できません。 深さ 4 の決定木の葉の数の最大値は 2^4 = 16 です。
24 ≦ 16 ではないため深さ 4 の決定木では、 24 個の葉を収容できません。
深さ 5 の決定木の葉の数の最大値は 2^5 = 32 です。
24 ≦ 32 であるため深さ 5 の決定木には、 24 個の葉を収容可能です。
以上から、決定木 T の葉の深さは最低でも 5 である必要があります。 a_1, a_2, …, a_n を比較によってソートするあるアルゴリズムがあるとします。
そのアルゴリズムには対応する決定木 T が存在します。
深さ k の決定木の葉の数の最大値は明らかに 2^k です。（深さ k の完全2分木の場合）
a_1, a_2, …, a_n の大小関係の可能性は、以下の n! 通りあります。
a_1 < a_2 < … a_(n-1) < a_n
a_1 < a_2 < … a_n < a_(n-1)
…
a_n < a_(n-1) < … < a_1
そのすべての可能性に対してそのアルゴリズムはソートしなければならないので、
T の葉の数はちょうど n! であるはずです。
n! 個の葉を収容するためには、 T の深さを k とすると、
n! ≦ 2^k
が成り立たなければなりません。
よって、
lg(n!) ≦ lg(2^k) = k*lg(2) = k
が成り立たなければなりません。 lg(n!) = Θ(n*lg(n)) ですので、
Θ(n*lg(n)) ≦ k
が成り立ちます。
以上より、比較によってソートする最高速度のアルゴリズムでも、その決定木の深さは
少なくとも Θ(n*lg(n)) の深さがあります。
よって、その最高速度のアルゴリズムにとって最悪のデータ a_1, a_2, …, a_n を与えた場合、
少なくとも Θ(n*lg(n)) 回の比較が必要です。 訂正します：
lg(n!) = Ω(n*lg(n)) ですので、
Ω(n*lg(n)) ≦ k
が成り立ちます。
以上より、比較によってソートする最高速度のアルゴリズムでも、その決定木の深さは
少なくとも Ω(n*lg(n)) の深さがあります。
よって、その最高速度のアルゴリズムにとって最悪のデータ a_1, a_2, …, a_n を与えた場合、
少なくとも Ω(n*lg(n)) 回の比較が必要です。 なんか非常に大雑把な議論で Ω(n*lg(n)) という評価を得ているのに、
ヒープソートやマージソートのような O(n*lg(n)) のアルゴリズムが存在する
というところが不思議ですね。 アマゾンってダメダメですね。
【全品10%ポイント還元】マンガ・雑誌など本全品がお買い得
7/10 18:00〜7/11 23:59のプライムデー限定で全ての商品が10%ポイント還元中！ ＞今すぐチェック
ヤフーショッピングとかで買えば実質30%引きくらいで買えるときもありますよね。 URLとかファイルパスとかコマンドとかをクッソ汚い文字列として
文字列処理で結合したり変数埋込みしたり正規表現使ったり
するコードとか、
エンコードされたり、エスケープ混じりのぐちゃぐちゃな文字列とか
とにかく汚くて長くて改行されてない文字列処理にも
データ構造やデザインパターンて適用できるの？
またはデータ構造やデザインパターンでソースをきれいに
整形できたりする？ 文字列処理っつってもいろいろあんだろ
どういう処理がしたいのかもわからんのにデザパタ適用もクソもあるかよ クッソ汚いもぐちゃぐちゃも個人の感想だから伝わらない 繁野麻衣子著『ネットワーク最適化とアルゴリズム』を読んでいます。
http://imgur.com/RI1TvXi.jpg
部分グラフの定義がおかしいです。
こんな基礎的なところで間違いを犯しているというのが信じられません。 あ、グラフになっていないと部分グラフとは言わないからOKなんですね。
でも分かりにくい表現ですね。 D40
http://imgur.com/i8hq9mG.jpg
↑この問題に対する解答ですが、
https://github.com/for-2ch/for-2ch/blob/master/Chapter_D.ipynb
の解答であっていますか？
2週間くらい前に書いたものですが、理解ができません。
仮に、 T に含まれないような C の辺たちの両端点を結ぶ T の辺のみからなる
パスたちがすべて辺 AB を含まないと仮定すると、 A から B への T の辺のみ
からなるパスで辺 AB を含まないようなものが存在することになる。
↑ここが理解できません。 あー理解できました。
ここは分かりやすく書き直したほうがいいですね。 仮に、 T に含まれないような C の辺たちの両端点を結ぶ T の辺のみからなる
パスたちがすべて辺 AB を含まないと仮定します。
A_1 := A
A_n ;= B
とします。
サイクル C が以下であるとします：
A_1 → … → A_n → A_1
もしも、
辺 A_i → A_(i+1) が T に含まれないときには、
サイクル C の A_i → A_(i+1) の部分を A_i から A_(i+1) への（一意的な） T の辺のみから
なるパスに置き換えます。
すると、 A から B への T の辺のみからなるパスで辺 AB を含まないようなパスが構成できます。
これは A から B への T の辺のみからなるパスが一意的であるという木の性質に反します。
（ほかに A → B という T の辺のみからなる長さ 1 のパスが存在することに注意。） データ構造とアルゴリズムを勉強するときに、プログラム作成の言語は何がおすすめでしょうか？
なぜ、いまだにC++が幅を利かせているのでしょうか？ 遅いから。
でも、JAVAはアルゴリズムの教科書でも使われていることあるよ。 Foo foo; と
Foo foo = new Foo();
は何が違うの?
あるクラス内で
private String field; のとき
public String method(String field){
return field;
}
と、
public String method(){
return this.field;
}
は何が違うの? >>541
>Foo foo; と
>Foo foo = new Foo();
C/C++ か、それとも C#/Java か、はっきりさせよ >>541
Foo foo; // 参照型変数fooを宣言
Foo foo = new Foo(); // さらに、メモリのヒープ領域ってとこにFoo型のインスタンスを作成し、その場所を代入
コンストラクタとかでよく見ることになると思うけど
Foo(String name) {
this.name = name;
}
これは想像どおりの挙動をしてくれる
引数とフィールドに同じ名前があったとき
フィールドのものを使いたいときあえてthisつける
Foo() {
String name = "bar";
this.name = name;
}
みたいなときも同じ
名前が被ったとき、フィールド側の変数を選ぶのがthis データ構造、アルゴリズムはCで勉強して、デザパタはC++で勉強するのがいいな。 本当はGoやRuby Python JavaScript Kotlinあたりやりたいのに、
本格的なプログラミングとか設計勉強しようとすると
必ずJava, C, C++ あたりで解説されるから覚えざるを得ないというジレンマ。 >>547
インプレイス、という概念を植えつけられない言語でアルゴリズムをやるのは問題
でも Java が使われるのは疑問 Javaだと問題があるのでしょうか？
セジウィックの本の第4版がJavaですが。 >>547
GoやRuby Python JavaScript Kotlinあたりに入門ちゃんと済ませて、これから本格的なプログラミングとか設計を勉強していくぞって人なら
具体例の説明に使われる程度のJavaやCなんて、無勉でもある程度は読めるでしょ 例えば、Pythonだとソートとかハッシュとかリストとかが用意されていますが、
データ構造を学ぶ上では高級すぎるのではないでしょうか？ Sedgwick のアルゴリズムの教科書は、C++版やJava版があるよね。
C++版はちょっと古くて、C++11以降のモダンな書き方で改訂版を出してほしい。
自分は、アルゴリズムの教科書は疑似コードのみを示すの（MITのCormenの）で勉強したんだけど、失敗だったと思っている。
疑似コードを真似してそのまま実装してたから、一文字変数あまりまえ、クラスや構造体を定義することはなく、何でもかんでも配列で済ませるというクセがついてしまった。
もうちょっと、オブジェクト指向とかを勉強してからにすればよかったのかも。 Javaとか連想配列使うだけでもいちいちnewとかキャストとか
鬱陶しい。 アルゴリズムは抽象的で、言語仕様とは切り離されたものであるべきなのだ。
そうは言っても手続き型を意識したものになりがちで、これを関数型に書き直せと言われても一目難しいものがままある アルゴリズムイントロダクションを読んでいます。
http://imgur.com/xbuAPtJ.jpg
↑は、 ω 記法についてです。
「if the limit exists」
と書かれていますが、なぜこんなことを書いているのでしょうか？
意味不明です。 g(n) が漸近的に正であるような関数であれば、
f(n) = ω(g(n))
⇔
lim f(n) / g(n) = ∞
ではないでしょうか？
「if the limit exists」などと書いてある理由が分かりません。 アルゴリズムイントロダクションって結構いい加減ですよね。
やっぱりクヌースの本を読んだ方がいいのかもしれませんね。 漸近的に正である関数
漸近的に非負である関数
について説明がありますが、
なぜ、漸近的に正である関数だけを考えないのでしょうか？
漸近的に非負である関数などこの本で登場する機会はあるのでしょうか？ >>556-559
この基地外が人様を害さないことを祈るばかりだ。 >>555
現実問題、アルゴリズムを書くコードはC、C++に限られる。
Fortran、Java、Python、C#など他の言語はそれで書かれたライブラリを呼ぶだけだ。 機械のパフォーマンスを追求するあまりに
人間時間のパフォーマンスを際限なく犠牲にする池沼 >>563
それはお前みたいな業務プログラマの視点 >>564
何だよ業務プログラマって
俺は人に使役されてないし、インフラも構築できるし、
人工知能や数学もやってるんだぞ。
お前みたいなパフォーマンスオタクのほうが頭おかしいから。 >Javaとか連想配列使うだけでもいちいちnewとかキャストとか
>鬱陶しい。
笑 アルゴリズムイントロダクションを読んでいます。
「関数 n^(1 + sin(n)) の指数部の値は 0 と 2 の間で振動し、その中間にあるすべての値をとる」
などと書かれていますが、明らかに間違っていますよね。
sin(n) = 1/sqrt(2) となるような自然数 n は存在しません。
何を考えているのでしょうか？ n と書いておきながら n が R を動くと仮定しているとかそんなことはないですよね？ オリジナルのほうにも、
p.52
the value of the exponent in n^(1 + sin(n)) oscillates between 0 and 2, taking on all values in between
と書いてあります。 >557
0<=c g(n) < f(n)
って書いてあるのだから、（0 < c g(n) でなく、0 <= c g(n) であることに注意）
g(n) = 0, if n > 3
1, if n <= 3
とかなら、
f(n)/g(n) の極限は存在しないよ。
だから、もし極限が存在すれば、という限定をつけたのだと思うよ。 >>573
それだと、
極限が存在するかしないか以前に、
f(n) / g(n) は n ≦ 3 に対してしか定義されませんよね。
lim f(n) / g(n) と書いた以上は
∃n0 s.t. n ≧ n0 ⇒ g(n) ≠ 0
でないといけないと思います。 たとえば、
関数 h(n) の定義域が {0, 1, 2, 3} のときに、
lim h(n) などそもそも考えられないわけです。 >>573
まず、
0 <= c g(n)
となっているのが問題だと考えます。
g(n) は漸近的に正であるような関数でなければならないはずです。 このあたりのところを4人の著者のうち誰が書いたのか知りませんが、
非常に出来が悪いですね。
世界標準とはとてもいえないと思います。 書いてあるとおりにしか取れない。キミの解釈がむしろ分らない。
the value of the exponent って(1 + sin(n)) だよな。それは between 0 and 2で、taking on all values in betweenだよな。
nが自然数なのかは知らんけど、sin(n) = 1/sqrt(2) という解釈はどこから？ 「if the limit exists」と書いてある理由について考えられる唯一の可能性があります。
それは以下の可能性です。
f(n) = ω(g(n)) の定義では、 n は N を動くと考えている。
一方、
lim f(n) / g(n) = ∞
という式の n は R を動くと考えている。 >>578
例としてそのような値を考えたということです。
0 < 1 + 1/sqrt(2) < 2
ですが、
1 + sin(n) = 1 + 1/sqrt(2) となるような n ∈ N は明らかに存在しません。
1 + sin(n) = 0
1 + sin(n) = 2
となるような n ∈ N も明らかに存在しませんが、 in between というのが
0 と 2 を含まない可能性を考えて、↑のような例にしました。 やっぱりクヌースの本の完成度は群を抜いていますね。 > the value of the exponent in n^(1 + sin(n)) oscillates between 0 and 2, taking on all values in between
書いてあるそのままの意味で、これは数学的に真で、
1 + sin(n) = 1 + 1/sqrt(2) を満たす自然数nが存在するなんてどこにも書いてないし、言ってない。
直前にnは自然数と定義してるならそれも引用してもらわないと判断のしようがない。おそらくnumberの略だろう。変数n。 もっと本質的な勘違いか。
AならばBはA=Bではないし、AならばBは、BならばAでもないぞ。
言ってるのはthe value, taking on all values in between だけだからな。 >>582
n については何も記述がありません。
そもそも、普通なら関数について書くときには、定義域を書くはずですが、
書いてありません。
習慣として、 n と書けば自然数の集合を動く変数ということになりますので、
そう解釈するのが妥当です。
1 + sin(n) が 0 と 2 の間のすべての値をとるのであれば、当然、
0 < 1 + 1/sqrt(2) < 2 ですので、値 1 + 1/sqrt(2) もとります。 念のため、公式ページの正誤表を見てみましたが、書いてありませんでした。
かなり売れている本だと思いますが、飛ばし読みしている人ばかりなのでしょうか？ 数学の世界ならそうだろうが、数学本じゃなくてプログラミングの本なんだろ？
sin(n) と書いてあればプログラマはたいてい n をfloat型かdouble型の変数だと解釈する。
= 一つとっても大抵のプログラミング言語は等式ではなく、代入演算子と定義している。
分野が違うのだから論理的におかしいと思ったらまずは定義を疑う。数学だってブール代数で1+1=1って書く場合もあるだろう。
今のプログラミング言語は+や-の演算子すら再定義できるのだ。
仮に自然数だとしても、次に本質的な論理問題。>>583 これ。
> 0 と 2 の間のすべての値をとる
これも怪しい。take on All Value なので、on 〜の上にという意味で、日本語にするならば結果がその範囲内に収まるだろう。
All values in between take the valueではないのだ。AはBのとき、BはAか？もちろん偽。
つまり1 + sin(n) = 1 + 1/sqrt(2)を保証する記述ではない。 >>569
>「関数 n^(1 + sin(n)) の指数部の値は 0 と 2 の間で振動し、その中間にあるすべての値をとる」
指数部の値は 0 と 2 の間で振動し、その中間にあるすべての値をとるんじゃね？ nが自然数か何かも書いてないのに勝手に自然数だと勘違いして発狂するとか何考えてんでしょうね sin(n) = 1/sqrt(2) のとき n = 約0.785。 degだと45度。
って、そういう話じゃなくて？ そもそも指数部(1 + sin(n))の話しかしてないんだから 凄いことにきずいたぜ！
「ポリモーフィズム」と「ラッパー」は反対の関係にあるんだ。
これによって「メソッド名」と「中身」が 多対多の関係にできるってことだぜ。 シーケンス図とかスタックトレースって都庁なんだな。
おれの言いたいことが分かるか？「東京都庁」なんだよ。 待てよ・・・ピラミッドやサクラダファミリアも同じ形をしてるじゃないか！
この世界の真実を見たぞ・・・ つかオブジェクト名繋げないでいきなり関数とは変数とか
呼ぶやつまじでやめて。
継承した変数や関数なのか、このクラスで定義した変数や関数
のかわからないじゃん。
このクラスで定義したものだったら thisつけろよ。 デザパタは覚えたし、クラス図やシーケンス図も読める、クラス図の通り
にコーディングもできるし、だいたい何らかのパターンに当てはめ
ればなんとか動く。
命名規則も全部決めてるからその規則通りに書けば自動的に動く
でも「なんでそうなるの？」って質問されるとさっぱりわからないんだよなぁ…
デザパタに則っていないコードとか、俺と違う命名規則の人が書いた
コードも一切理解不能(無能)。 372仕様書無しさん2017/08/11(金) 10:31:43.41
フリーランスで検索すると引っかかる零細ITがやっているサイトはだめだ。
高額に見せているけど実際は50万前後
JIET加入した方がいいよ。案件は毎日千件以上末端価格は60万円 平凡な稼働時間の80万円の案件もある。
ユー子が求人をだしてる。名刺も渡せる。ユー子に名刺が渡せるんだぞ。夢のようだ
それらの案件まさぐってHPで転売していたのが零細ITがやるフリーランスサイト
自称エージェントはJIETから流れてくる案件を転売してるだけだった。
JIETに加入すれば誰でも案件に応募することができた。収入が40万50万台にならなくて済む
473非決定性名無しさん2017/08/03(木) 15:21:30.71
JIETに加入すれば誰でも3次60万からスタートだ。フリーランスのサイトをやってる
自称エージェントもそこから案件情報を取得しきてる。サイトで60万で釣って40万から55万の
間でやらしている。 ちょｗｗ俺煽られすぎｗｗｗ
でも、モノは完成するようになったぜ。
要求、仕様から動作原理すっ飛ばして、命名規則だけで
モノが完成するから結構職場では役立ってるぜ。
他のプログラマはフレームワークの使い方がやっとだし
一人だけ技術力があるゴリラ野郎は人望がなくて自分の技術力が
人に盗まれるのを極力恐れているから基本的に部下に意地悪して
教えてあげれば済むことも何も教えてくれない。
社長はどんどん仕事取ってきて、だいたい半数のプロジェクトが進まずに凍結状態に
なり、ブチ切れた客をなんとかかわし続ける日々だ。
そんな状況で俺の場合動くモノを比較的完成する方だからゴリラには結構
気に入られて給料は上がったよ。会社がいつまで持つかは分からんが。 状態遷移のように汎用的に使える技術って他にも何かありますか？ >>620
概念と用語だけマスターすれば良い。
あとは実務に合わせて使えるところは利用するし、合わない部分は気にしない。 >>622
>>621みたいに、わかったような口を叩くけど実際にやらせてみたら手が動かないカスになったらダメ
自分でどんどん適用してみて、メリットもデメリットも自分の体験として語れるようになった方がいい https://ideone.com/mWu6mC
写経してみたけどどんな時に使えるのかいまいちわかりませんでした・・・ >>625
さらっと読んで写経したぐらいで理解できると思わない方がいい
そのうちわかってくるから、とにかく手を動かしコードを動かす経験を積み重ね続けるんだ Introduction to Algorithms 3rd Editionを読むスレ [無断転載禁止]©2ch.net
http://mevius.2ch.net/test/read.cgi/tech/1505387171/ >>618
＞汎用的に使える技術
良い質問だなこれ
遅レスだけど考えたい
地味だけど基礎的なデータ構造が
一番汎用的なんじゃないか？
連結リストとか二分木とかそういうの >>629
それは言えてるかもしれない
汎用的=基礎的 Kleinberg & Tardosの本に以下のような内容の記述があります。
でも、 n > 1 のとき、 H が universal になることは決してないですよね。
u = v のとき、常に、 h(u) = h(v) なので、問題の確率は 1 ですから。
--------------------------------------------------
U を要素数の非常に多い有限集合とする。
H を U から {0, 1, ..., n-1} へのすべての写像の集合のある部分集合とする。
u, v ∈ U に対して、ランダムに選んだ h ∈ H が h(u) = h(v) を満たす確率はたかだか 1/n であるとき、
H は universal であるという。 S を #S ≦ n であるような任意の U の部分集合とする。
u を U の任意の要素とする。
X を ランダムな選択 h ∈ H に対して、値 #{s ∈ S | h(s) = h(u)} をとるようなランダム変数とする。
このとき、
E[X] ≦ 1
である。
証明：
s ∈ S に対し、
h(s) = h(u) であるならば、 1
h(s) ≠ h(u) であるならば、 0
となるようなランダム変数を X_s とする。
仮定により、 H は universal であるから、
E[X_s] = Pr[Xs = 1] ≦ 1/n
X = Σ X_s だから期待値の線形性により、
E[X] = ΣE[X_s] ≦ #S * (1/n) ≦ 1 この証明は、
u ∈ S であるとき、破綻しますよね。 Kleinbergはネヴァンリンナ賞を受賞した人だそうですが、大丈夫な人なのでしょうか？ > u = v のとき、常に、
また勝手におれ条件を付け加えてるな。 T(n) = Ω(g(n))
⇔
T(n) ≧ c*g(n) となる n が無限に多く存在するような定数 c が存在する。
という定義がありますが、なぜ、ほとんどすべての n ではないのでしょうか？ >>639
Knuthは、
T(n) = Ω(g(n))
⇔
ほとんどすべての n に対して、 T(n) ≧ c*g(n) が成り立つ。
と定義するのがいいと書いていますが。 Θ(f(n)) を使うべきところで、 O(f(n)) を使っているという批判をする人がいますが、
具体的にはどういう状況でしょうか？ 浅野孝夫著『アルゴリズムの基礎とデータ構造』を読んでいます。
「上の挿入ソートの例のように、基本演算回数（比較回数）は入力サイズ n にのみ
依存するとは言えない。そこで、入力サイズ n の入力のうちでアルゴリズムが最も
多くの基本演算を必要とする入力を考えて、それに対する基本演算回数を、本書ではん、
サイズ n の入力に対するアルゴリズムの計算量（time complexity of an algorithm）と
呼ぶ。すなわち、最悪の場合を想定してアルゴリズムの計算量を定めていることになる。
このようにして定められたアルゴリズムの計算量 T はもちろん n にのみ依存する関数で
あるので T(n) と書ける。上の挿入ソートの例では T(n) = n*(n-1)/2 である。」
と書いてあります。
その後、マージソートのところには、
「マージソートの計算量は T(n) = O(n*log(n)) である」
と書いてあります。
T(n) は最悪の場合の計算量ですから、
T(n) = Θ(n*log(n)) が正しいのではないでしょうか？
ちなみに、浅野さんは、この本の最初のほうで O, Ω, Θ を定義しています。 もちろん、 f(n) ∈ Θ(n*log(n)) ⇒ f(n) ∈ O(n*log(n)) ですが。 浅野さんは、挿入ソートの計算量を
O(n^2)
と書いています。
これも
Θ(n^2)
と書くべきですよね。
>>652
に引用したように、
「上の挿入ソートの例では T(n) = n*(n-1)/2」
ですから。 ID:vbK8I5kP くらいの基地外になれば、100連投だって容易い。 ソートの決定木についてですが、葉の数が「少なくとも」 n! 個あると説明されることが多いですが、
ちょうど n! 個と書かない理由は何ですか？ 既に順序が決定されているにもかかわらず、さらに無駄な比較をするようなプログラムの
ことを想定しているのでしょうか？ そうだとすると、決定木のある部分木で、その葉がすべて同じ順序に対応するようなものが
存在することになります。 ソートの決定木について厳密に論じている本はありますか？ This result serves as a guide for us to know, when designing a sorting algorithm, how
well we can expect to do. For example, without such a result, one might set out to try
to design a compare-based sorting algorithm that uses half as many compares as does
mergesort, in the worst case. The lower bound in Proposition I says that such an effort
is futile?no such algorithm exists 最悪時にマージソートの半分の比較しか必要でないソートのアルゴリズムが存在しないこと
は証明できるのでしょうか？ あ、勘違いしました。
>>661
合っていますね。明らかに。 浅野孝夫著『アルゴリズムの基礎とデータ構造』を読んでいます。
以下の問題に対する浅野さんの解答が↓です。
「このとき根は葉ではないので左の子 v および右の子 w をもつ。」などと書いていますが、
深さ d > 0 の二分木で左の子もしくは右の子を持たないものも当然存在します。
おかしな解答ですね。
二分木において、深さ d までの葉の総数は 2^d 以下であることを示せ。
d に関する帰納法で証明できる。 d = 0 のときは根は葉になるので明らかに成立する。 d > 0 未満で
成立すると仮定し d のときを考える。このとき根は葉ではないので左の子 v および右の子 w をもつ。
v を根とする部分木の深さ d - 1 までの葉が元々の二分木の深さ d までの葉になるがそのような葉の
総数は帰納法の仮定より、 2^(d-1) 以下である。同様に w を根とする部分木の深さ d - 1 までの葉の
総数も 2^(d-1) 以下であり、したがって、元々の二分木の深さ d までの葉の総数は 2^d 以下であることが
言えた。
この問題文自体もおかしいです。
この問題の結果が本文中で使われていてそこを読めばわかるのですが、問題文の意味は、
「深さ d の二分木の葉の総数は 2^d 以下であることを示せ」です。以下のような解答が模範解答ですね。
深さ d の二分木でその葉の総数が 2^d + 1 個以上であるような二分木が存在すると仮定する。
そのような二分木のうち葉の総数が最多であるような二分木を T とする。
すべての葉の深さが d であるような二分木の葉の総数は明らかに 2^d 個である。
よって T の葉にはその深さが d 未満であるような葉が存在する。この葉に子ノードを持たせれば
深さ d の二分木で葉の総数が T の葉の総数よりも多い二分木を作ることができるがこれは矛盾である。
よって、深さ d の二分木の葉の総数は 2^d 個以下である。 >すべての葉の深さが d であるような二分木の葉の総数は明らかに 2^d 個である。
これ出しちゃったらそれで証明おしまいのような気がするが。 あ、問題文はおかしくないようです。
二分木において、深さ d までの葉の総数は 2^d 以下であることを示せ。
という問題でOKです。 二分木において、深さ d までの葉の総数が 2^d + 1 個以上である二分木が存在すると仮定する。
深さ d までの葉の総数が最多である二分木を T とする。
このとき、 T には深さ d 未満の葉が少なくとも一つ存在する。もしそうでないと仮定すると、 T の
すべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 2^d 個以下に
なってしまうが、これは矛盾である。
T の深さ d 未満の葉に子ノードを持たせれば、深さ d までの葉の総数が T よりも多い二分木が存在する
ことになってしまい矛盾が発生する。
よって、において、深さ d までの葉の総数は 2^d 個以下である。 二分木じゃなくて三分木なら2^d以下ではないわけだけど、>>669の証明を二分木から三分木に変えても
論理展開に違いが出ないから明らかにおかしいだろう。 三分木では、
「もしそうでないと仮定すると、 T のすべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 2^d 個以下に
なってしまう」
が成り立ちません。 三分木の場合の証明は以下のようになりますね。
三分木において、深さ d までの葉の総数が 3^d + 1 個以上である三分木が存在すると仮定する。
深さ d までの葉の総数が最多である三分木を T とする。
このとき、 T には深さ d 未満の葉が少なくとも一つ存在する。もしそうでないと仮定すると、 T の
すべての葉の深さは d 以上であるから、明らかに深さ d までの葉の総数は 3^d 個以下に
なってしまうが、これは矛盾である。
T の深さ d 未満の葉に子ノードを持たせれば、深さ d までの葉の総数が T よりも多い三分木が存在する
ことになってしまい矛盾が発生する。
よって、において、深さ d までの葉の総数は 3^d 個以下である。 >が成り立ちません。
成り立たないことがわかっているなら証明いらんだろうｗ
逆に言うと、それが成り立たないことが証明されていない。
>>673
3^dってどこから出てきたわけ？ 2分ヒープは完全二分木を使ったデータ構造ですが。
この完全二分木のことを半順序のついた木というのはなぜでしょうか？ %%%%1000%%%%
000-[HUM%58*73.1\%]/2I/3NM/61.3SNMK%?%3%51.22222222222221%
001-[[[%6/4$17.6135412α3]]]]+DOM+SIL+7%
002-UML7%[61.2[31.5[!%32∂LM17.36%!16.3!%<<<%!HSTOL7%!Q!S!=3m=<2TOL<3Q9A<2.1GHz%,DOK,HAOARA,
003-[[[HEMLOT47[<\41.2%Q,===>[MLS<DPNO<\2.3>#ESOLA!5%!3MLA!>LTOSA>7TONSA>%>%end バッチ処理, ジョブ制御に有効なデザインパターンって何? >>675
再帰的に、親は両方の子以下の数値をもつ。
左右の子の大小関係は考慮しない
ここでは説明しやすいように、配列の[0]は使わない。
[1]から始めると計算が楽。
親1, 左右の子は2, 3で、法則は、親n, 子2n, 2n+1
もし[0]から始めると、
親0, 左右の子は1, 2で、親1, 左右の子は3, 4で、
法則は、親n, 子2n+1, 2n+2、となり複雑
親[1] → 子[2, 3]
[1]3, [2]10, [3]30
[2] → [4, 5]
[4]100, [5]20
[3] → [6, 7]
[6]70, [7]200
JavaScript で、漏れが作った、2分ヒープ
http://jsdo.it/michihito/bGH5 シングルトンがいけないとかたまに聞くんだけど
シングルトンなしでどうやるのか誰か教えて
シングルトン使わないで済むならシングルトン辞めることには吝かではないんだが
どうやるのかが分からない
HolderとかRepository作るとどうしてもシングルトンになっちゃう
誰か助けて シングルトンの何がいけないのかをわかっていれば別に使ってもいいんじゃないか？
と思うんだが 内部ノード数 n の 2色木の Black Height を h であらわすと以下の不等式が成り立つ。
2^(h-1) - 1 ≦ n ≦ 2^(2*h-1) - 1
よって、 h = O(log(n))
とある本に書いてあります。
これっておかしいですよね？
h は n の関数ではありません。内部ノード数から2色木の Black Height は一意的にはきまらないからです。
もちろん、 O(log(n)) の左辺には n の関数が来るきまりです。
ですので、 h = O(log(n)) と書くのはおかしいのではないでしょうか？ メッセージキューイングって
Commandパターンで実装するで合ってる？ >>686
>>2^(h-1) - 1 ≦ n ≦ 2^(2*h-1) - 1 ・・・(1)
>>よって、 h = O(log(n)) ・・・(2)
一見すると正しそうに見えるけど、どっちがどうおかしいと？ h が n の関数ではないにもかかわらず
h ∈ O(log(n))
と書いているのがナンセンスです。 >>689
nとhの関係は(1)で示されているんじゃね？
不等式を変形すれば良いのでは？ n から h は一意的に決まりません。
よって、
h は n の関数ではありません。 >>691
(1)より一意に決まらなくても計算量は同じでしょ？ ＞もちろん、 O(log(n)) の左辺には n の関数が来るきまりです。
ここの時点でおかしい 抽象メソッドしか定義されない型のことを
「インタフェース」ってネーミングセンスは頭おかしいんじゃないの？
インタフェースって言ったら通常「UI」とか外部の窓口になったり、
外部デバイスとの接続ポイントになるコネクタのことを言うじゃん。
オブジェクトの型のことを「インタフェース」なんて言ったら誤解を招くだろ。 >>695
interfaceには境界面とか接点の意味がある
クラスが持つ他との接点の意味で合ってる 外部の窓口になったり、外部デバイスとの接続ポイントになるのが抽象メソッドだから。
つまりそれしか定義されてないということは、インターフェースそのものと言っていいだろう。 デザパタスキル、エンベッデイドスキルなんやかや言うが、みんな大事な部分は閃きなんだがなぁ・・・
作曲と同じ。 閃き・・・ とどのつまり、神が書かせているという事。
そこを理解できない限り、そのプログラマーは聖職では無い。 神などと妄想するようになったら科学の全否定の始まり。無知が故の過ち。 神「共通化せよ――」
僕「はい」
神「ごめん間違えた――」
僕「うわぁぁああぁああ！！！」 以下で定義される写像 A : N × N → N を Ackermann 関数という。
A(1, j) = 2^j for j = 1, 2, 3, …
A(i, 1) = A(i-1, 2) for i = 2, 3, 4, …
A(i, j) = A(i-1, A(i, j-1)) for i = 2, 3, 4, … for j = 2, 3, 4, …
α(m, n) = min {i ≧ 1 | A(i, floor(m/n)) > log_2(n)}
で定義される写像 α : {(m, n) | m, n ∈ N, m ≧ n} → N を Ackermann 逆関数という。
なぜ、この α を Ackermann 関数の逆関数と呼ぶのでしょうか？ courseraのセジウィックとウエインの講義を受講しています。
プログラミングの課題のチェックが超厳しいですね。
'if' is not followed by whitespace.
「if」の後ろにスペースを入れないといけないなんて初めて聞きました。
そんなことまで強制されたらたまりませんね。 大概のプロジェクトで採用されてるスタイルだから従っとけ
スペース軽視するやつ多すぎ >>703
K&R2 に従っておけば文句が来ることはない
if ()
while ()
for () 一般的なコーディングルールには従ったほうがよい
最近の言語環境では放っておいてもツッコミ入れてくれたりもするが 業務システムでオブジェクト指向不要って意見はどう思いますか
大抵スパゲティークエリになってる印象ですが 途中からオブジェクト指向混ぜられても困るだろ
実行効率や記述効率は悪くたって別に構わないのだから（ここわかってない人多し）、プロジェクトに来た全員が理解利用できる書き方が最優先
無論技術的にも業務的にもうんこだが、そこを追求すべき場所ではないところで勝手に追及を始めるのはそれこそうんこのやること
ゼロからオーバーホールを提案してもよいが最後まで自己責任で看取れ >>709
サブクエリ五重の塔を見て上長にキツいと報告したら世界にはバベルの塔がいっぱいあるのに根をあげるなと叱られました
せめて何をしたいのかドキュメント欲しいと言ったらコードが全てだとも言われました
IT業界の厳しさを知りました courseraのセジウィックとウエインの講義の最初の課題であるパーコレーションだけど
backwashを防ぐにはどうすればいいんですか？ あ、分かりました。
virtual topにはつなぐがvirtual bottomにはつながないUF
virtual topにもvirtual bottomにもつなぐUF
を使えばいいんですね。 デザインパターンで規定されるいろいろなクラスがあるけど
これらのクラスはそれぞれレイヤー化アーキテクチャのどこに
属すのか知りたい。
たとえばStateパターンがあった場合に、
・<<interface>>State
・ConcreteState x n
・Context
があったとき、
これらは、クラスを配置する場所的に
・プレゼンテーション層(UI層)
・App層
・サービス層
・ビジネスロジック層
・パーシステンス層
のどこの層として配置すればいいのか > デザインパターンで規定されるいろいろなクラスがあるけど
> これらのクラスはそれぞれレイヤー化アーキテクチャのどこに
> 属すのか知りたい。
デザパタはレイヤ化アーキテクチャに属すものだという考え方が謎なんだけど >>719
どの層にも配置していいんじゃね
その層の機能とかを実現するのにそのデザインパターンが必要なら使えばいいのではないか
レイヤーとデザインパターンは独立に組み合わせ可能と思う デザパタを適用したクラスがどのレイヤにあっても構わんのじゃ無いか
定石があってもフレームワークごと違うから説明無理だと思う 1以上1000以下の整数からなる集合の部分集合で、
その任意の異なる2元 x, y をとったとき、
「x は y を割り切らず、 y も x を割り切らない」
という性質をもつものを考える。
そのような部分集合の中で元の数が最大になるような
集合の元の数を求めよ。 めっちゃ勘だが、334から666と、667以上の奇数でどうだろうか 答えは500以下です。
1 から 1000 までの整数を 2^n * (2*m + 1) の形で表す。
2*m + 1 の部分は、
2*0 + 1, 2*1 + 1, …, 2*499 + 1
の500個のパターンのいずれかに一致する。
よって、1 から 1000 までの整数の中から501個以上の異なる整数を選び出せば、
その中には、かならず、
2^n1 * (2*m + 1), 2^n2 * (2*m + 1)
という二つの整数が含まれる。
この二つの整数は一方が他方を割り切る。 どっかから問題と回答を拾ってきてドヤ顔してる人ってなんなの？ >>727
何をしているのかちゃんと理解したいのですが、
m や n は実数ですか？ >>729
>>727が言葉が足りてないのは確かだが、もうちょっと数学のセンス磨こうぜ >>730
n=0 にして、m=0, 1, 2 ...
n=1 にして、m=0, 1, 2 ...
...
とやって確かめたら、なんとなく自然数を網羅できそうなのは確認できました。
ただ、本当に網羅できるのか証明はまだできてません。
これ以上はスレチも甚だしいので、独りで頑張ってみます。
流れぶった切ってすみません。
>>725 さん、どうぞ続けてください。 >>729
整数を 2 で割れるだけ割ると 2^n * (2*m + 1) の形になります。
例：
120 = 2^3 * 15 = 2^3 * (2*7 + 1)
この場合、 n = 3, m = 7 です。 1 = 2^0 * (2*0 + 1)
2 = 2^1 * (2*0 + 1)
3 = 2^0 * (2*1 + 1)
…
999 = 2^0 * (2*499 + 1)
1000 = 2^3 * (2*62 + 1)
となります。
1, 2, …, 1000 をすべて
2^n * (2*m + 1)
という形に表します。
m は 0 から 499 までの 500 個の整数のどれかになります。
ですので、 1, 2, …, 1000 の中から 501 個以上の整数を取ってきて、それらすべてを
2^n * (2*m + 1)
という形に表すと、
2*m + 1
の部分が同じになるような異なる2つの整数があります。
2*m + 1 の部分は同じで、 2^n の部分が異なります。それら2つの整数は
2^n1 * (2*m + 1), 2^n2 * (2*m + 1) のようにあらわされます。 n1 < n2 と仮定して一般性を失いません。
2^n2 * (2*m + 1) は 2^n1 * (2*m + 1) で割り切れます。 2^n2 * (2*m + 1) ÷ 2^n1 * (2*m + 1) = 2^(n2-n1) 500以下なのはわかった。500ある例>>726も見つかった。
で、一般に1からNのとき、何個になるのよ？ >>726
{501, 502, …, 1000} でもOKですね。 >>735
ceiling(n/2)
ではないでしょうか？ セジウィックとウエインのcourseraのオンライン講義を聴講しています。
java.util.List
java.util.Stack
java.util.Queue
は最低だそうですね。
Best practices: Use our implementations of Stack, Queue, and Bag.
だそうです。 最近傍探索で、最も近いものが複数個あった場合、どうするのが自然ですか？
また、k近傍探索でも、クエリからk番目に近いものが複数あった場合、どうするのが自然ですか？ セジウィックとウエインのcourseraのオンライン講義を聴講しています。
なんかやけに課題が厳しくないですか？ セジウィックとウエインのcourseraのオンライン講義Algorithms Part 1のWeek 2の課題、できた人いますか？ courseraのセジウィックとウエインの講義を聴講している人はいますか？ >>746
宿題なら自分でやれ
そうでないなら読むのめんどくさいから要約しろ あ、仕様Memory量の見積を勘違いしていました。
できそうですね。
Item 型のデータを格納する Linked List
と
Linked List の各要素への参照を格納する Item[] 型の
配列を用意すれば実現できますね。 あ、でも Item[] 型の配列を ResizingArray で実現したとしても、
常に、Memoryの制限である 48*n + 192 bytes というのを満たすのは
無理ですね。
どうすればいいんですかね？
もう少しだけメモリの制限が緩ければ実現可能ですが。 Performance requirements.
Your randomized queue implementation must support each randomized queue
operation (besides creating an iterator) in constant amortized time.
That is, any sequence of m randomized queue operations (starting from an empty
queue) must take at most cm steps in the worst case, for some constant c.
↑これと↓を両立させることはできるのでしょうか？
A randomized queue containing n items must use at most 48n + 192 bytes of
memory. あ、なんだ
簡単でしたね。
Item[] 型の Resizing Array を使えば、
メモリ使用量 〜 8*n
だから、4倍くらいメモリを無駄に使っても
48*n を超えませんね。 あ、なんだ
簡単でしたね。
Item[] 型の Resizing Array を使えば、
無駄が全くないときのメモリ使用量 〜 8*n
だから、4倍くらいメモリを無駄に使っても
48*n を超えませんね。 これから実装しますが、また100点満点中100点になりそうです。 あ、やっぱりだめですね。
dequeue の計算量がネックになりますね。 あ、分かりました。
一様ランダムに選択された a[i] に a[N] を移せばいいんですね。 経路探査でray cast algorithmというのがあるらしいんだが、わかりやすいサイトない？ おちんちん に ベロが届くアルゴリズムを教えて下さい。 >>760
「お金が儲かるアルゴリズム」で儲かる方法を書いた本を売る 関数型言語ってUML使うんですか?
クラス図とかメソッドどう書くんだろうと ちょっと質問させてください。
状況: トータル1000行くらいある巨大メソッドの改修
言語; PHPだがどの言語でもそう関係のない内容
・まずコントローラのアクションメソッドがあって
public function action(引数){
/* 500行くらいの既存コード */
/*今回改修を加えたい50行位のコード */
/* 500行位の既存コード */
}
となっている。 ・ここで、改修要件は、中間にある「/* 50行くらいの既存コード */」を
if文で分岐させて分岐次第で違う処理を入れる。というもの。
したがって、
public function action(引数){
/* 500行くらいの既存コード */
if(条件1){
/* 新規追加コード */
if(条件1-1){
/* 新規追加コード */
}else{
/* 既存コード */
}
}else if(条件2){
/* 新規追加コード */
}else{
/* 既存コード */
}
/* 500行位の既存コード */
}
みたいにひたすら条件分岐して既存コードと新規追加コード
が何回も実行されるようにしたい。 ・ここで、俺は「/* 既存コード */」の中身を知っている必要は
ないと思った。だから、このコードの詳細を読まずに「func()」
として「action()メソッド内部」に切り出した。
・外部に切り出したのではなく、内部に切り出したのはその処理が
他のアクションメソッドでは共有されるような汎用的なものではないだろうと
判断したのと、そのメソッド内で処理を追いやすいようにというのを
優先させたため。何より、その処理内で使っている関数内ローカル変数の
依存性の関係上そうせざるを得ないと思った。
public function action(引数){
/* 500行くらいの既存コード */
private function __legacy(){
/* 50行くらいの既存コード */
}
if(条件1){
/* 新規追加コード */
if(条件1-1){
/* 新規追加コード */
}else{
__legacy();
}
}else if(条件2){
/* 新規追加コード */
}else{
__legacy();
}
/* 500行位の既存コード */
} ・【訂正】上記で「func()」として切り出したと言っているが、
「__legacy()」に変更しました。すみません。
・上記のように改修した所、レビューを受けたときに怒られた。
・まず、「この__legacy()の中身ちゃんと読んだ? 把握して書いている?」
という指摘。
・そして「ここメソッド内だけどどうして関数定義しているの？
他の人そんなことしてないでしょ。どうして変わったことするの？」
という指摘。
・まず1つめの指摘に対して異議がある。
ブラックボックス化しなければ大規模なコードは書けないんじゃない？
ということが言いたい。ライブラリとかフレームワークの機能も全部
先に中身をよくよく読んでおかなければ使ってはいけないことになるじゃん。
・2つの指摘に対して、
「周りの人がやっていること」が正しいとは思えない。
処理を切り出していないから1000行もある巨大なメソッドになっていて、
汚いコメントで汚しながら機能追加しまくっているんじゃないのかと。
ローカル変数を使いまくりの同じ処理を何回も実行するのに
他に良い手段があるとしたら皆さんに教えて頂きたい。 汎用的でない50行のコードをコピペしてるんなら関数化してもインライン化してもどっちもどっちだな
DRYを意識したのかもしれんがKISSが抜けてる
それにブラックボックスが許されるのは有名なライブラリやフレームワークのようなテストにテストを重ね、かつ多くの利用者による実績があるものだけだよ
社内コードなんて大概クソコードだしブラックボックスにしても後で痛い目を見るのは自分や他の開発者
何なら単に今把握するだけじゃなくて、未来の自分や開発者のためにわかりにくいところをコメントで説明書きしてもいいくらいだ
あと関数内関数より無名関数を変数に代入した方がいいんじゃね
そもそも新規追加したif文も詳細はわからないがデータよりもロジックに寄っててわかりにくそうな匂いがプンプンする
それに上司には理由を聞かれてるんだから同じローカル変数に別の値を入れて使い回すことの危険性、関数化による参照透明の確保や保守性、メンテナンス性の向上を論理的に答えればいいだけ >>770
レビュアーが言ってることを正しいと仮定すれば
・1つ目の指摘は既存のコードがカプセル化されてないからだ
・2つ目の指摘はリファクタリングするだけの時間やお金や技術がないからだ
という前提が必要になるから、まあそういうことなんじゃなかろうかと
残念なコードっていうのはあるからね
それを修正する費用と修正して得られる効果を比較対照して
これだけの効果があるんだからこうするべきだと提案をまとめて
説得するのがいいのだろうけど、技術に理解のある人がいないとなかなか難しいね
レビュアーの立場で考えると以下の作業があるんじゃないかと
・改修要件を満たす改修
・既存のコードをカプセル化する
・リファクタリングする
レビュアーは既存のコードとの一貫性を維持しつつ
改修要件を満たす最小の改修をやって欲しいのだろうね
たとえ汚らしいコードであってもいままで動いてきた実績があると
変更に対しては既存のコードをできるだけ変えないようにと保守的になるものだよ
レビュアーがそれをきちんと説明できればいんだけど
コードはクソ、レビュアーもクソなんてことはザラにあるんですよこれが >>771 なるほど勉強になります。
少し質問したいが、
・「KISSが抜けている」と言うのはどこらへんでしょうか？
・関数内関数と無名関数の変数化の違いがわからないので教えてください。
(面倒なら調べます。)
・あなたならどう対応する？
・「理由を聞かれてるんだから答えればいいだけ。」
→多分論理的に説明したら「じゃあもう何も教えないよ。好きにやって」
が返って来ると思われる。
そう言われると、必要な情報も来なくなるし聞けなくなる。 >>772
なるほど、俺自身が「既存コードのカプセル化」と
「改修要件」という概念と「改修要件を最小に満たす」という
ことについて詳しくないことに問題がありそうだね。
ありがとう、ここらへんをキーワードにして調べてみます。 >>773
多分もっと細かく汎用的な(publicにできる)関数の集まりに分解して、汎用的でない部分は最小限に出来るんじゃないかなーって思った
実際のコード見てないから予想だけど
関数内関数だとわざわざprivateかけないと外からアクセス出来ちゃうし、元の親関数抜けても子関数が死なない
そもそも上司とあんまり仲良くないの？
論理的にメリットを売り込んだときに感情論で否定されるくらいの関係性だと下っ端プログラマーはしんどいよ？
まぁ俺ならその段階なら折れて普通にコピペして、もっと実績残して仲良くなってから似たような案件のときに改めて売り込むかな ひとつのメソッドに1000行も書かせる会社はまず危ない
アルゴリズムとかそれ以前 >>775
なるほど、「まるまる関数化」というのが
ちゃんと機能を意識してカプセル化していないってことか。
一応privateは欠けているけど、関数オブジェクトと
関数定義の違いはあまり詳しくないね。そうか、親関数が抜けたとき
子関数が死ぬか否かの違いがあるわけね。
入りたてだから人間関係はいいも悪いもない。
ただ、本来責任ある人はバタバタしていて、経験ある人が自分の意志で
新人のレビューをバラバラに行っている感じ。
>>776
会社がそうさせているというよりはそれぞれの人員が
これまでの追加の仕方を真似て機能追加した結果メソッドがブクブクと太っている
という状況に見える。
メソッド内で各追加機能がコメントで区画されていてそれなら
別関数にすりゃいいのにって思っている。
俺をレビューした人も、別に会社の工程でそうなっているわけでなく、
進捗を見たかったからだと思うが、書き直しを要求してきて困惑している。
ただ彼は業務要件については圧倒的に俺より詳しいから無視すべきではないと
思っている。 >>777
カプセル化はオブジェクト指向において関連するものをまとめる作業だから、ちょっと違うかな？
どちらかというと今回の話は関数型プログラミングの考え方に近い
まぁぶっちゃけ職場のコードなんて割り切らんとやってけんよ
出世してコーディングスタイルに口を出せるようになる日を待つしかない >>777
そんな仕事を放置する会社、と言うことだ 名前だらけのコードってどうやって解読すればいいんだ？
変数化するとそのデータの型が何なのか物量的にどれだけの
規模が格納されているかが見えない。
もちろんログに吐けば見えるが、吐き出さなければパッと見で
何をどう処理しているのか分からない。 関数型言語の仕様書ってUMLで良いの?
データと振る舞い分離してるからクラス図使って良いのかなと >>783
英語敷居たけえ
まあデータと振る舞いを書いたクラス設計は関数型言語でも同じように使えるし問題ないか 今どきデザインパターンって死語なの？
ちょっと参照したいことがあって書店でデザインパターンの本を探したけど見つからなかった。
リファクタリングの本はあって多少はデザインパターンの話も出てきたけど。
結局は家に帰ってから10年前に買ったデザインパターンの本を参照するしかなかった。 ブームが去っただけかな？
銀の弾丸などないと気がついただけ デザパタは元々バカの為にまとめられたものだったけどバカには無理だった代物
一方リファクタリングはバカ程好むからなかなか廃れない 21世紀最新のデザインパターン本て誰か書かないかね
Singleton→大抵はstaticでOK
みたいなの デザインパターンて結局何だったんだ？
高い本まで買ったがほとんど身に付かなかったな >>793
もともと C++ 界隈で発生したテーマですので、C++ をやっているとデザパタの意義がよくわかります
C++ は細かしいことまで自分で記述しなければならないので、こういう大枠思考がもてはやされたのだと思います ああ、でも C++ はテンプレートの世界観に移行してしまったので、デザパタ、今はあんまり使いません！ >>793
アルゴリズムの話するときの共通語が必要になって
ついでに良し悪しもまとめておこうという話になった デザインパターンそこに至る考え方を身につけないと
というわけで、オブジェクト指向のこころをオススメしとく 『アルゴリズムイントロダクション』を読んでいます。
ヒープソートのところに、
「サイズ n のヒープ上の MAX-HEAPIFY の最悪実行時間が Ω(lg n) であることを示せ。」
という問題があります。
最悪実行時間が Θ(lg n) であることはすぐに分かります。
なぜ、 Ω(lg n) であることを示せという問題なのでしょうか？
最悪実行時間や最良実行時間については、 Θ 記法で書くのが自然だと思います。 セジウィックさんはいい加減ですね。
近代科学社から出ている『アルゴリズムC』の最小全域木のところを読んでいますが、
同じ重みの辺が2つ以上あると議論が破綻するところがありますね。
Wayneさんと共著の『Algorithms』では、すべての重みが異なるという仮定をおいていますね。
いずれにしてもひどい本です。 キミはまだアルゴリズムの勉強していたのか。
人には向き不向きというのがあってだな。 すべての重みが異なるというのは異常な仮定ですよね。 茨木俊秀著『アルゴリズムとデータ構造』を読んでいます。
この本のクラスカルのアルゴリズムの正しさの証明に使われる補題の証明ですが、
読んでも分からなかったのですが、やはりおかしかったんですね。
同じ著者の『Cによるアルゴリズムとデータ構造』を読むと補題の証明が修正されています。
この分野っていい加減な本が多いですよね。 任意の連結無向グラフ G = (V, E) は |E| ≧ |V| - 1 を満たすことを示せ。 僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法 モニアレフヌノ』
BU06O 詳しいと言えるかどうかは別にしてAVL木に関する説明が分かりやすいと思ったのは次の本の該当箇所（§6.3）だ
浅野哲夫『データ構造』、アルゴリズムシリーズ１、近代科学社 (1992) 1つ言えるのはオブジェクト指向のなんかよりも
データ構造とアルゴリズムの方がよっぽど重要だということ。
昔はオブジェクト指向の勉強を頑張っていたけどそのときは
全然プログラミングがうまくならなかった。
現代の世の中はガチガチに設計されたライブラリを使って
コードを書くだけだから生半可なオブジェクト指向の知識なんて
ゴミ同然だよ。80年代90年代に考えられた思想とか、もうゴミに
なってしまった思想が多くて有害だよ。
結局現場でやることは「メソッドの使い方を求めてQiitaやStack OverFlowを
漁って成功するコードを見つけるまで疲れ果てる」ことに変わりはない。
せっかく勉強した内容が時代遅れで「裏切られる」ことのほうが多い。 一方、データ構造とアルゴリズムをガッツリと勉強してから
様々なデータ構造の使い方、問題の解決がうまくなった。
ブロックチェーンのアルゴリズムの理解や
データ分析の数学的演算がコーディング
できるようになってプログラミングが格段に楽しくなった。
スマートにオブジェクト指向で設計する力なんかより
「ゴリゴリとアルゴリズムを書く力」の方がよっぽど重要。
「再利用性」？「変更の影響」だって？そんなものゴミだね。
それは自分以外の人間のメリットのための技術であって、
自分へ還元されるためのメリットではない。
再利用性は自分の書いたコードなら信頼できるしコピペして使えばいい。
自分の書いたコードのコピペは全然ありだと思う。
適したメソッドが見つからなかったらQiitaを漁ったりせずに
自分でゼロから実装したほうが速い。
その場で手っ取り早くコードを生成しているから、
どんな既存コードにも頼っていないから俺の実装したコードは
依存性は低い。 ただし>>814-815は何かのアプリを作ったことはない >>815
一つ重要な視点を提供しましょうか
自分の記憶などあてになりません、3ヶ月前自分が書いたコードは、もはや他人が書いたコードとなんら変わりありません >>814-815はすでに解いたことのある問題なら
忘れたとしても、少し時間をかければ解けると考えている
つまり誰かが出した出題を解くという作業をしている >>>817, 818
自分のいつも使うアルゴリズムのパターンが身についていれば
そのパターンや命名規則から何をやっているかは解読できる。
読みにくくなるのは外部から取り込んだ機能の実行や
継承している部分。 >>819
やっぱり「解読」してるんだｗ
すでに証明済みの問題を自分の力で証明するという
お勉強をやってるだけだね 解読の工程は業務でも必要であるし
遊びとしても面白い
それが勉強になるならとても有益じゃん 「車輪」は大きさ、材質、シャフトの接合部の形、色…大まかな形や役割は似ているが微妙に違うものが無数にある。
ちょっとでもこれらの特徴がずれたものは他への転用を考えるとすぐに不具合となって使い物にならない。
車輪を最初に「発明」した人物はこれらの無数の車輪を全て発明したわけではない。
だから他の人が死ぬほど似たようなものを作っていたとしても自分で作る必要がある。
他人が作った車輪は無条件で役にたつわけがない、
手直しして組み込むより「自分の規格で」作った方が早い。 車輪が小さかったからゴム巻いたらなんとかなった
これがオブジェクト指向です 時代が違うからな。アルゴリズム考えてうんうん唸る時代は終わってるんだよ
今はそういうアルゴリズムが実装されたライブラリを組み合わせて
アプリを作る時代だってMITも言ってる
MIT｢今は基礎よりﾗｲﾌﾞﾗﾘ組み合わせてｱﾌﾟﾘ作る時代｣ [無断転載禁止]©2ch.net
https://medaka.5ch.net/test/read.cgi/prog/1462443213/
MITがSICPを教えなくなった理由
http://cpplover.blogspot.jp/2016/05/mitsicp.html
今日では、状況が変わっている。
今のエンジニアは、自分が完全に理解していない複雑なハードウェアのための
コードを日常的に書いている（そして、大抵の場合、企業秘密により完全に理解するのは不可能である）。
ソフトウェアでも状況は同じだ。プログラミング環境は、多大な機能を提供する
巨大なライブラリ群の集合として存在している。
Sussmanの今日の生徒は、その時間の大半を、ライブラリのマニュアルを読み、
どのように組み合わせれば目的が達成できるのかを把握することに費やしている。
Sussman曰く、今日のプログラミングは、「より科学に近い。ライブラリを持ち寄って、
つっつき回すのだ。プログラムを書くには、突っつき回して、どのように動作するかを観察する。
そして、「目的を達成するために改造できるか」と考えるのだ」。
SICPの「合成による解析」という物の見方である、小さな、単純な部品を組み合わせて大きなシステムを作るということは、
もはや今日の状況にそぐわなくなった。今や、我々のプログラミングはつっつき回すことで行われている。 車輪の再利用だけ考えて車輪職人が居なくなるって話かな？ そうだね。そもそもソフトウェアは他の製品と違って
完全に同じものを複製するのに技術がいらないからね
コピーすればいいだけだし。
その点、何かを作る職人とはぜんぜん違うよね
そいういう寸分違わないものを作り出す職人は不要な業界 >>825
そして、今は鉄道以外のほぼすべてのタイヤの接地面はゴムです。
そういうところもオブジェクト指向と、似てますね。 >>826
この論理は完全にお花畑。
完全無欠のライブラリがありそれが唯一無二なら
つつっつき回すだけでいいだろうさ。
だけど現実はほぼ似たような機能で構文が違う、
それに加え実行環境もバージョンも違うライブラリたちが乱立してるんだぜ、
それに加わりローカルで作られた野良ライブラリがある。
当然人によってそれらの使い方の認識に齟齬が生まれる。
信用できるのは、自身の即興のデータ構造定義能力と、
アルゴリズム構築能力だけだ。 >>831
> だけど現実はほぼ似たような機能で構文が違う、
> それに加え実行環境もバージョンも違うライブラリたちが乱立してるんだぜ、
乱立しているからなんだっていうんだろう？
乱立してるから自分で作れってことにはならないよな？
何が言いたいんだろう
> それに加わりローカルで作られた野良ライブラリがある。
自分自身で作成したもの = 他人から見れば野良ライブラリだからね
野良ライブラリは作るべきじゃないね
だから乱立されている中のどれかを使うってことになるわけだけど
そういう結論を言いたかったんだよね？ >>831
データ構造作るだけだと付加価値が低いというか
ただの作業員でしかなくない？
新しい仮想通貨作るとかだったらすごいけど まあ言えるのは、データ構造やアルゴリズムを作るだけの仕事なんて無いってことだな
やりたいからといって、それで金がもらえるわけじゃない
金を出す方がやってもらいたいことをやって金が出る
似たようなものを自作して、乱立させたって
そんなものに金を出す人はいない >>835
うむ
>>834
やったことないやつには判らんよ >>827
いや、ちょっと違う
プログラマという職業が、車輪を一から設計できる職人群と
それを再利用する専門家へと二極化していくというお話だよ
この二極化は以前から言われていたことだけど、
それを天下のMITが言い切って行動に移したことに>>826の意義がある >>838
「職人」と「専門家」が逆ではないですか？ いや、逆ではないよ
MITは計算機工学に特化しているわけでもなく、
機械工学、ロボティクス、生産工学、データ解析といった
あらゆる工学分野の専門家を養成し輩出している
そういった(計算機工学を除く)大半の「専門家」の卵達にとって、
優先すべきは(旧コースでSchemを使って学んでいた)計算機の動作原理ではなく、
計算機の利用方法である、という趣旨
彼ら「専門家」は決して計算機工学の専門家ではないが、
それぞれの分野に特化した高度な専門技術を有し、
与えられた問題を解決する道具として計算機を効果的に活用できる どんな仕事でも、その道の研究者ってのはいるだろう。
例えば数学者とかな。だけど世の中で必要とされてるのは
塾の数学の先生だったりするわけさ
もっとも大学に行った人の殆どは、大学で専攻していたものとは
関係のない仕事をしているわけだけどな たとえばjsでオブジェクト構造をサーバに送りたいとする。
たったこれだけのことなのに邪魔くさい余計な機能が多すぎる。
わざわざ専用のクラスからインスタンス作って
専用の構文使ったりhttpヘッダー設定したりだ。
それでいてサーバ側では糞みたいな細かい仕様認識の違いでリクエストの内容が空だったりする。
サーバ側のコンフィグ見直したりjs側のコード見直したりするわけだ。
ログからライブラリのコード追っていくと大抵
過剰に技法使われてるから自ずと疑うべき探索
範囲は広くなる。
書き方はjQueryベースやangular typescriptなんかが混在してきて文法のちょっとした勘違いなんてのも生まれてくる。
だったらそんなライブラリ鼻っから信用しなけりゃいい。
ライブラリのインスタンスを介さずに多少原始的だが
文字列、数値 for文if文だけで大抵の問題は解決できる。
自力でJSON文字列に情報をぶち込んで送信してやれば、必ずサーバ側で取得できる。
サーバ側も下手なライブラリにパースさせないで自力でパースした方が慣れれば断然こちらの方が早い。
自力で作ったアルゴリズムは信用できるから
関数化しておいてまた似たような問題があったときに
使える。
俺が使うための自作ツールは他人は使わなくていいよ、どうせ価値観が違うんだからな。
自分で作ったもの以外はそりゃ不便だろうよ。 > たとえばjsでオブジェクト構造をサーバに送りたいとする。
https://api.jquery.com/jquery.post/
$.post( "test.php", { name: "John", time: "2pm" } );
こうだね。で？ はい。このように他人の成果を利用して
目的を達成するのが今は重要って話です。 >>844
> だったらそんなライブラリ鼻っから信用しなけりゃいい。
とりあえずお前が自力で作ったライブラリは
鼻っから信用しててないよ >>844
> 俺が使うための自作ツールは他人は使わなくていいよ、どうせ価値観が違うんだからな。
> 自分で作ったもの以外はそりゃ不便だろうよ。
価値観の問題じゃない。単にお前が作ったコードに
バグがあるから使えないだけ。使わないんじゃない。使えない。
反論するならバグがない証拠を出すこと
テストコードをかけという話ね。
> だったらそんなライブラリ鼻っから信用しなけりゃいい。
お前が書いたコードは鼻っから信用できない。するしないじゃない。できない。 みなさんお気づきだろうか
>>844と>>849は同じことを言っている jQueryはブラウザの差異を吸収するからね
同等のもの作ろうとしたら大変だよ
自前のコードを実装するのが汎用ライブラリを使うよりも早いとするなら
自前のコードは汎用ライブラリよりも機能が少ないものになる
要件がシンプルなら自作するのは効率が良いかもしれないね
システムをユーザのニーズに合わせてたら要件が複雑になり自作するメリットが得られない
ユーザがシステムの都合を忖度するならうまくいく
開発者にとっては桃源郷
開発者の幸せか、ユーザの幸せか
ぼくらはその選択を迫られてるんだ 役所が作る神エクセルなんてのはユーザがシステムの都合に合わせてる典型例じゃないか、自作コードに拘るのは神エクセルを作るのと変わらぬよ >>851
> 要件がシンプルなら自作するのは効率が良いかもしれないね
それは正しくない。要件はシンプルでも実装が大変なことがある。
そもそも「ライブラリの一機能の独自実装」などという要件は
実際には発生しない。これらは単に道具
要件を実装するのに、道具を使うか使わないかの問題
シンプルな要件でも、道具は使ったほうが効率は良いよ
もちろん道具を使えない人であれば、道具を使えるようになるまで時間が
かかるけど、それは素人がプロに速度でかなわないという人間の問題にすぎない
そう道具を使えないなら素人なんだよ。 >>850
同じことは言ってないな
>>844はよくわからないのはライブラリのせいだ
自分で作れば、そのライブラリよりもわかりやすくなるはずだ
って机上の空論を言ってるだけ りんごをむくのにピーラーを使うのもいいが、一度ナイフで剥くのを試すのも重要だし、かじってみるのもいい。
道具が解決する問題がなんなのか、体験することは、多くの人にとって有益だと思う（経験主義者） そこでピーラーを作るのは大変だとか見当違いの所に流れていくやつがいる。
ピーラー（ライブラリ）を使うか、ナイフを使うかだ
ライブラリ？中見たけどわけのわからないことをしてる
理解できない。ナイフのほうが単純だ。ナイフなら作れる。
なぜか作る話になってしまっている。 例え話は物事を理解してなくてもそれらしく見せるから知ったか振りが捗りますなあ MVC, DAO, O/Rマッピングの発展形として、
俺は「R/Rマッピング(リクエスト/リレーショナルマッピング)」を
提唱したい。
そもそもDB上のカラムと本当に対応付けたいのは画面上のname属性
なんだよなぁ。
オブジェクトを必ず介する必要はない。
(処理が込み入ってきたら定義してもいい程度。)
まず前提として、DBのカラム名とHTML上のname属性を
必ず同じキーにすることを前提とする。(HTML上に関係ない
キーがあっても問題はない。)
その前提の上でDBのカラム名一覧を先に取得しておき、
カラム名リストと、受信したname属性のキーをマッチングして、
マッチングした時にそのキーから取得した値をSQLに突っ込んで
クエリを行う。
こうすることによって、プログラミング言語処理の中で
具体的な「項目名」をほとんど登場させずに処理することができる。
自分でやったらすごく便利だった。
こうなるとそもそもモデルとかDAOとかいらなくね?
ってなって来たよ。
項目数がどんなに二十, 三十と並んでいようがダラダラと羅列しない。
特別な処理を入れたいときだけその項目のカラム名を使って
ifで分岐して日付変換とかをおこなう。
その特別な処理も日付,範囲系、選択肢系などパターンを押さえれば、
めちゃめちゃ簡素化できる。 あ、はい、4行ぐらいしか読んでないけど、
そのリクエストに含まれる名前 = オブジェクトのフィールド名なんだから
あんたが言ってるリクエスト = オブジェクトってこと
あとはストレージをなんにするかの話。
ODBMS（オブジェクトデータベース）を使えばそのまま読み書きできる
だけど、なんやかんやでリレーショナルデータベースを使わないといかんから
O/Rマッピングが必要になる >>886
あとRailsでも勉強しようね
普通は画面のname属性 = データーベースのフィールド名になってるから
（もちろん必要なら対応してないものも作れるけど） 二層CRUDオモチャ
昔から誰もが一回は考えるアイデアだよ
画面起点だとどうしてもアプリケーションロジックの居場所がないから簡単に作れてもアプリとしての価値が無い
DB起点だとSQLにアプリケーションロジックを埋め込んんで最低限のアプリの体裁は保てるけど保守性が最悪で使い物にならない
という理由から廃れた
なので今はオブジェクト指向の言語でモデルを書いてモデルから画面やDBを生成して微調整しようってのがスタンダード
これなら労力をかけずに豊かな振る舞いを持つアプリケーションを作れるしロジックがモデルに集まるから保守性も高い >>869
モデルを作るとしても処理が複雑になる部分だけ
部分的でいいんじゃないか？
全ての要素に対して網羅的にモデルつくって
セッター/ゲッター定義して...ってのは肥大化して馬鹿げてる
気がするんだが。
なにせ機能を複製する時にこれらのずらずら並んだモデルオブジェクト名や
キーの名前をを置換しなけりゃならない。
ならない。 > セッター/ゲッター定義して...ってのは肥大化して馬鹿げてる
それはJavaだけ
Javaが馬鹿げているだけ >>859
さてリンゴをむくか、
ピーラーがないと剥けないから探すか、
あれ、どこにしまったかな？
この引き出しにもこの棚にもない。
道具だらけで見つからない。
店に買いに行こう、たくさんのピーラーが並
んでいてどれを選ぼうか？
ようやく買ってきて構築しているけど、
どうや刃が付け替え式で色々な刃が付け替えられる
ようだ。
刃を買い忘れたからまた買いに行くか…
はぁはぁ…すごい刃を買ったぞ！今構築中だ。
おや？この刃はリンゴを剥く用途には対応して
ないようだ。もう疲れたしこれ無理だろ。
ピーラーが無いから俺にはリンゴを剥くのは
無理だ。前は引き出しにあったからむけたけど
今はできなくなった。
一方、いつも愛用のナイフで剥いてるならそう
はならない。
いつもポッケに入れているからなくさないし、
最悪自作で調達できる。
使い慣れてるからピーラー使うやつと遜色ないスピードで剥けるし形も綺麗に剥ける。 Rails なんか、全自動！
DB の表の構造が定義された、メタテーブルを参照して、
表の列名なども自動的に取得する >>870
それでずらずら並んで嫌だというなら、おまえのやり方だと画面定義もずらずらならぶし、テーブル定義やSQLがずらずら並んで更にわけわからなくなるだろ 最も重要ななのはアルゴリズムとデータ構造
次にI/O
つぎに無名関数やハンドラ、イベント駆動
つぎに並列、非同期処理
その次は画像処理とか3Dとか
ディジタル信号処理またいな各ドメインの専門
技術。
オブジェクトやクラスなんてこれらを達成する
上での手段でしかない。
それ以上のオブジェクト指向の設計思想は
もはや宗教。
唯一絶対に正しいわけでもないし
概念を余計に複雑にするだけ。
SQLやHTML XMLやJavaScript シェルスクリプト
URLなんかが絡んでくるとグダグダに崩壊
するものばかり。
そして現代のアプリケーションはこれら無しで
作るのは無理だからオブジェクト指向の高度な
技法はほどんど不要。 NoSQL db って、Redis以外はわりと滅びた感じ。
RDBでもスキーマレスなデータ扱えるようになったし、
トランザクションあった方が便利なことやっぱり多いし、
SQLってなんだかんだ言って表現力高いし。 pythonスレにも書いたのですが、pandasのMultiIndexにしたデータのままで、データを追加したり、値を更新したり、csvに入出力する方法をご存知の方はいませんか？ AOJ の「DPL_1_I: Knapsack Problem with Limitations II」が分からん。
個数制限付きナップサック問題の
・ある品物の重さと個数制限
・ナップサック容量
が極めて大きいバージョン。
例えば解法
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2856557#1
を見ると、品物の価値の総和が i であるときの最大容量を記録した動的計画法テーブルを作った後に貪欲法で答えを出してるんだが
・なぜこの方法で上手くいくのか
・前半の動的計画法で、品物の個数を min(m[i], MAX_V) としている (できる) 理由が分からない。
誰か知恵を貸してください。
僕としてはこの解法が理解できれば満足です。 >>897
どういう意味？
「このアルゴリズムを理解するのに必要な数学の分野」というものがあるならそれを参照するが、そんなものはない (挙げられないでしょ？)
俺個人の専門は物理で、「数学の勉強」というものも一応してきたが、このごく具体的な問の一解法を理解することと「数学の勉強」は関係がない
単純に論理的思考力を上げよ、と言っているなら会話になっていないのでこれ以上は結構 論理的思考力を上げるために将棋をしなさい。数学など不要です。 >>898
数学科の数学と物理科の数学とコンピュータの数学は違う（笑） >>901
最適性の証明のことを言ってるの？
いずれにせよこの問題に限った話じゃないよね？
別に動的計画法が上手くいく理由が分からないと言っているのではなく、>>896の解法が分からないのだが。
>>902
違わない
算術、代数、幾何、解析だ全て 例えば、バブルソートには
数学の、えっと、幾何？の知識が必要だろ？
え？ >>906
分からんと思っているだけでは進まない。
なにを目的にして、どのようなフローチャートを描いて、
その結果なにが理解できていて、なにがまだ理解できていないのか、
可能な限り事細かに洗い出して、自分の理解の最前線を特定してみるといい。
と言うことを、私は数学で学んだ。 >>909
だからそれは>>896の時点で書いてるんだが
関係ないことしか言えないならレス不要です
>>907
何を？ 俺の周りで物理やってる人はとんでもなく数学ができる人ばかりなのに まあゲームじゃない限り物理なんて使わないよね
本格的な物理系シミュレーションとかだと
専門家が担当するだろうし この程度の問題で数学数学言ってるアホ多過ぎて呆れる
多分>>910みたいな感じで高校の算数基準で話してるんだろうな そんなに言うのなら、具体的に数学のどの分野なのか
それが具体的に何と同じなのか言えって。
どうせ論理的思考力がーみたいな精神論しか言えないんだろ 数列、非線形解析学
はい言いました
論理的思考力が無いのはあなたですね >>916
では、数列、非線形解析学を利用した
アルゴリズムを答えてください >>920
数学の問題をコンピュータで解決するってのはわかる、
だが数学・物理特有の問題以外をコンピュータで解決するのに
数学はいらねーだろって話 >>921
微分積分も理解せずにコンピュータに信号処理をやらせるの？
そういうレベルの質問 信号処理なんて、誰がやっても同じなんだから
一度ライブラリ作って、他の人はそれ使うだけだろ・・・ >>923
それじゃあ初音ミクは生まれないね
こういうやつが技術を停滞させる >>924
だからそういうのは専門家に任せたほうが良くね？
音声合成をやる人は、そういう専門家に任せて
他の人は便利なインターフェースを作るとかさ、
なんでも1人でやるもんじゃないよ？ 別にそういう原理を知りたくないんなら勉強しなくて良いんじゃない
表面的なものしか作りたくないなら勉強しないことをおすすめします >>926
だから作る層が違うって言ってんの
水道局で働いてる人全員が
工事技師じゃないんだよ >>927
つまり君はそういう層にはなるのを拒む側ってだけだ >>928
その理屈で言えば、君がそういう層になりたいだけでは？
残念だけど、自分がやりたいことと、他人がやってもらいたいこと
っていうのは同じじゃないんだよね
そして給料っていうのは、他人がやって欲しいことをやった対価として
もらえるものなので、いくら自分がすごいことができるって言ったからって
給料は高くならないんだよね。 >>929
作りたいものがあるから勉強する、それだけ 自分一人で作るような小さいアプリとかなら、
全部を知っておかなければいけない、って思いたくなるのもわかる。
が、通常は数学の専門家でも無い人間を数学で信用する事は無いし、
プログラムの専門家でも無い人間をプログラムで信用する事は無い。
付け焼き刃は事故の元。
大きな仕事になればなるほど役割や責任が細分化される。 ぼやっとして結局何を言いたいのか良くわからんが
何か良い事を言いってみたい必死さは伝わった 言ってることがわからんから、言ってるほうが馬鹿だと思ってるだけじゃないの？
俺に言わせれば、馬鹿だから言ってることがわからないんだと思うが？ 俺に言わせれば世界はお前を中心に回ってないってこと >>937
お前を中心に回ってるといいたいのかな？ アルゴリズム辞典みたいなものを手元に置いときたいんだが、最も支持されてるのってどれ？
・網羅性が高い
・支持されている（売れている）
・日本語版がある
・コード例はあってもなくても良くて、あるとしたら C/C++ か擬似コードで
という条件で
テーマ別に「どれとどれとどれを持っとけばまず問題ない」という言い方でもありがたい
とにかく網羅性を重視してる 英語は知らんけど、日本語なら
[改訂新版]C言語による標準アルゴリズム事典 (Software Technology)
奥村 晴彦
http://amzn.asia/d/bAqY5Be
が網羅性は随一じゃないかな。
改訂だけど初版が1991年で、収録アルゴリズムは増えてないらしいので、
機械学習とかここ25年の新分野は当然入っていない。 機械学習の何をアルゴリズム辞典に入れるべきだというのか
Amazonレビューかよテメェは >>942
この本はBoyer-Moore法が簡易版しか載っていないし、Aho-Corasick法も載ってないから弱い より網羅的な対案示してからでないと批判にならないよ。
共立のアルゴリズム辞典が現存すればこっちも挙げてたかもしれん。
BM法に関してはコード例は簡略版のみだが。
個別のアルゴリズムについてどこまで踏み込むかは、
辞典の物理的な性質上取捨があるのはしかたないでしょ。 名前がついていて解放も明らかになってるアルゴリズムに興味はない
そんなのいくらやっても新しいものは生み出されない 質問させてください。
マイコンからAD変換で入力したサイン波を配列に格納し、周波数を求めたいと思います。
ゼロクロスの位置を求めれば正確に周波数を求められそうですが、教えてください。
https://i.imgur.com/FC5XP0K.png 質問が不完全だけど、そのためのアルゴリズムを教えてほしいということでよい？
前提として、各周期で確実に2回だけゼロクロスすると保証できるのなら、
前回の値を覚えておいて、今回との積が0以下になったらゼロクロス。
この保証がないのなら十分長く波形をとってFFTしてピークを探す。 有向グラフの有向閉路を求める問題です。
深さ優先探索を実行したときに、 Backward Edge が存在する。
⇔
有向閉路をもつ
⇒は自明ですが、逆はどう証明するのでしょうか？ 深さ優先、幅優先探索を理解するのにオススメの本ってありますか？(コードサンプル付きでできればC) >>956
グラフ・ネットワークアルゴリズムの基礎: 数理とCプログラム
浅野 孝夫
固定リンク: http://amzn.asia/d/2MetXvf 学ぶ目的には全くお勧めできないってのはその通りだけど、
手元に置いておいて使う分には便利な本ではあるような。
あ、浅野先生の本も待ってます。
(この分野、浅野先生が2人いて紛らわしい) >>956
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
渡部 有隆
固定リンク: http://amzn.asia/d/g8qmfS6
↑この本にも、 BFS、DFS共に書いてあります。
解説は非常に雑ですが。 >>959
の本には、再帰を使う DFS プログラムが書いてあります。（スタックを使う DFS プログラムは演習問題にあり、コードをダウンロードできます。） >>963
スタックを使う DFS プログラムは演習問題にあり、コードをダウンロードできますし、本にも解答のところにコードが載っています。） 前置記法（ポーランド記法） + 1 2
後置記法（逆ポーランド記法） 1 2 +
中置記法 1 + 2
確か、構文木をたどる時に、どれかが幅優先で、どれかが深さ優先探索になると、記憶している テンプレのソース探検なんちゃらのサイトいいね
pdf買えはうざいけど
ソートはクイックマージヒープの特性くらい押さえとけば良さそうな感じだな
そこら中に実装あるしまあ
バケットソートは聞いたこと無かったけど、これは局所で凄い威力発揮しそうだ
覚えとく価値ありそう こんにちは、初質問させていただきます、グラフアルゴリズム初心者です
・無向グラフGが入力として与えられる(ファイルからでも、コード内での手打ちでも、どちらも良い)
・Gがサイクルを持てばGの中の最小サイクル(長さが最も短いサイクル)とそのコストを出力する
・各辺、頂点の重みは考えなくても良い(つまり辺のコストは1とする)
といったアルゴリズムを実装したいです。
できればC言語もしくはC系統の言語でコーディングしたいです。
考え方と共に、コーディング例をご教授いただけると幸いです。
浅い知識ではありますが、この実装に必要そうである
・DFS,BFS
・ダイクストラ、ベルマンフォード
に関しては、基礎レベルは把握しています。
お手数おかけしますが、ご助力いただけると幸いです。 適当に言うけど、
すべての辺を1回だけ通りながら、通った頂点を記録していく
それで同じ頂点を、2回以上通ったら、閉路がある？ >>971
グラフのサイズが書いてないと答えられないな >>973
条件不足で申し訳ございません
グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。
お手数お掛け致しますが、よろしくお願いします。 >>973
条件不足で申し訳ございません
グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。
お手数お掛け致しますが、よろしくお願いします。 >>975
頂点数をn，辺数をmとする
ある頂点uを含んだ最小閉路は頂点uからbfsをすればO(n+m)で求められる（最初にuに戻ってきたときの経路が最小）
あとはすべての頂点に対してこれをして，その中から一番短いものを選べばいいので，全体でO(n(n+m))で求められる >>976
ありがとうございます。
つまり、例えば
各頂点を始点-終点とするダイクストラアルゴリズム処理を行えば良い
ということでしょうか。 >>977
イメージとしてはそんな感じです
辺を考えたほうがわかりやすいかもしれないです
ある辺(u-v)を含むようなサイクルの中で最小のものを求めたいとします
まずグラフから辺(u-v)を除去します．このグラフ上でuからvの最短距離dを求めます
すると，d + 辺(u-v)が辺(u-v)を含むサイクルの中で最小のものとなります
グラフの中で一番短いサイクルは辺(u-v)を含んでいるかはわからないので，すべての辺に対して上の操作を実行します
その中から一番短いものを選べば，それがグラフの中で一番短いサイクルです
この場合だとO(m(n+m))です >>978
ありがとうございます。
ご教授いただいた考えをもとに、ダイクストラ法を用いて実装してみました。
・ダイクストラ(グラフは頂点とコストで表現)
https://ideone.com/bXF0iQ
また、以前似たものを実装したのですが、これはダイクストラ(もしくはBFS)の考えに則れていますでしょうか・・・？
(グラフは隣接行列で表現)
https://ideone.com/snxvav
どちらにしても、始点と終点が同一でない場合はうまくいくのですが、
始点と終点を同一として閉路で求めようとすると、うまくいきません。
自己ループ辺のコストが0であるから、と思い9999などにしてみましたが、うまくいきませんでした。
すごく単純なミスなのでしょうが、詰まってしまっている状態です。
修正等いただけると幸いです。
一応、(可能であれば)望む仕様と結果としては
・グラフは隣接行列で表現
・辺の重みは非負である(今回、簡易化のために辺の重みは1~9)
・グラフサイズは制限しない(今回、簡易化のために10頂点程度)
・ダイクストラを用いて自分自身を始点かつ終点とする最短経路を求める
・各頂点に対して上のダイクストラを行い、中でも最短の閉路の経路とそのコストを表示する
です。
お手数をおかけしますが、よろしくお願いします。 >>979
>>971だと辺のコストは1となっているが，実際は辺に1以外のコストがある？
求めたい最小サイクルというのは，使う辺の本数が最小という意味なのか，使う辺の合計コストが最小という意味のどちらなのか >>980
コストは1だと申し上げましたが、
ダイクストラなので非負であれば求まると思い、汎用性を考えて1以外のコストも付与してみました。
説明不足で申し訳ございません。 >>981
無向グラフだと面倒くさくて，uからvにいったあとvからuにいくような場合がでてくるのでこれを除かないといけない
そのような経路を除いたうえで始点に戻ってきたものが最短になる
ある辺が2回使われることはないので，辺は1度しか使えないようにすればいいと思う >>983
>>984
ありがとうございます。
コストだけでなく、経路も出力したいのですが、弄ってみてもなかなかうまくいきません...。 CLRSのダイクストラのアルゴリズムの正しさの証明を読み終わりました。
行間が全くなく、確かに、正しいことは分かりますが、あまりイメージのわかない証明ですね。
CLRSって他の本と比べると異常に行間がないですよね。 巨大なsparce行列（ゼロ要素が多い行列）で行列演算やるときデータ構造考えるよね >>985
どのへんがわからないか言ってくれ
Find minimum weight cycle in an undirected graphは
int Graph :: ShortestPathでu-vを削除したときの最短経路を求めてる
このときdist[v]が更新されるたびにvにきたノードをメモしておけば最後にvからprevをたどって復元できる
このときの経路をvector
楽な実装方法は，グローバル変数にこれまでの最短経路の距離とルートをもっておいて
常に最短のものを保存しておけばいい 途中で送信してしまった
このときの経路をvetorにいれておけばいい >>988
正直、C++の知識不足で勉強を頑張ってはいるのですがVectorの使い方がまだ、慣れていません。。。
厚かましいのは重々理解しているのですが、可能であればFind minimum weight cycle in an undirected graphのプログラムを>>988さんなりに改変したものをお教えいただけると幸いです。。。
悪い勉強法とは分かっているのですが、答えというか実装例が無いとなかなか理解できなくて。。。 >>990
https://ideone.com/pShuim
↑一応動きました。
piという変数に経路を覚えさせています。 >>990
piについては、
Cormen, Leiserson, Rivest, Stein著『Introduction to Algorithms 3rd Edition』の最短路の章を見ると、
書いてあります。 アルゴリズムとデータ構造ってコンピューターサイエンスの分野で人気ないんですか？ >>994
ネット以外だとデータ構造とアルゴリズム好きな人見たことないな
CS系だと機械学習やってるやつが多い >>995
ありがとうございます。
機械学習は非常に流行していますが、勉強するのに面白い分野だとは思えません。 DAGの単一始点の最短経路問題を解くアルゴリズムとか
Bellman - Fordのアルゴリズムとかの正しさの証明が非常
に面白いですね。 このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 1317日 2時間 28分 54秒 5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。
───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────
会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。
▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/
▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php レス数が1000を超えています。これ以上書き込みはできません。
