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

**デフォルトの名無しさん転載ダメ©2ch.net** · 2016/06/19(日) 14:47:29.63

このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

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

　　　　　　　　　　　　　　　　　　京都大学霊長類研究所

データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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

**デフォルトの名無しさん** · 2017/11/27(月) 07:16:56.92

デザパタを適用したクラスがどのレイヤにあっても構わんのじゃ無いか
定石があってもフレームワークごと違うから説明無理だと思う

**デフォルトの名無しさん** · 2017/11/28(火) 09:02:37.93

1以上1000以下の整数からなる集合の部分集合で、
その任意の異なる2元 x, y をとったとき、
「x は y を割り切らず、 y も x を割り切らない」
という性質をもつものを考える。

そのような部分集合の中で元の数が最大になるような
集合の元の数を求めよ。

**デフォルトの名無しさん** · 2017/11/28(火) 09:32:48.27

めっちゃ勘だが、334から666と、667以上の奇数でどうだろうか

**デフォルトの名無しさん** · 2017/11/28(火) 11:34:19.17

答えは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)

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

この二つの整数は一方が他方を割り切る。

**デフォルトの名無しさん** · 2017/11/28(火) 12:05:52.85

どっかから問題と回答を拾ってきてドヤ顔してる人ってなんなの？

**デフォルトの名無しさん** · 2017/11/28(火) 14:07:31.97

>>727
何をしているのかちゃんと理解したいのですが、
m や n は実数ですか？

**デフォルトの名無しさん** · 2017/11/28(火) 15:55:11.56

>>729
>>727が言葉が足りてないのは確かだが、もうちょっと数学のセンス磨こうぜ

**デフォルトの名無しさん** · 2017/11/28(火) 17:12:15.85

>>730
n=0 にして、m=0, 1, 2 ...
n=1 にして、m=0, 1, 2 ...
...
とやって確かめたら、なんとなく自然数を網羅できそうなのは確認できました。

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

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

流れぶった切ってすみません。
>>725 さん、どうぞ続けてください。

**デフォルトの名無しさん** · 2017/11/28(火) 17:15:22.43

>>729

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

例：

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

この場合、 n = 3, m = 7 です。

**デフォルトの名無しさん** · 2017/11/28(火) 17:16:45.10

2^n * 奇数

です。

**デフォルトの名無しさん** · 2017/11/28(火) 17:26:27.93

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)

**デフォルトの名無しさん** · 2017/11/28(火) 17:58:11.47

500以下なのはわかった。500ある例>>726も見つかった。
で、一般に1からNのとき、何個になるのよ？

**デフォルトの名無しさん** · 2017/11/28(火) 19:31:53.85

>>726

{501, 502, …, 1000} でもOKですね。

**デフォルトの名無しさん** · 2017/11/28(火) 19:37:23.97

>>735

ceiling(n/2)

ではないでしょうか？

**デフォルトの名無しさん** · 2017/11/28(火) 19:54:30.86

あんまり面白くない結果だね

**デフォルトの名無しさん** · 2017/11/30(木) 18:59:28.31

セジウィックとウエインのcourseraのオンライン講義を聴講しています。

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

は最低だそうですね。

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

だそうです。

**デフォルトの名無しさん** · 2017/12/02(土) 11:57:41.11

最近傍探索で、最も近いものが複数個あった場合、どうするのが自然ですか？

また、k近傍探索でも、クエリからk番目に近いものが複数あった場合、どうするのが自然ですか？

**デフォルトの名無しさん** · 2017/12/02(土) 12:30:23.76

セジウィックとウエインのcourseraのオンライン講義を聴講しています。

なんかやけに課題が厳しくないですか？

**デフォルトの名無しさん** · 2017/12/02(土) 13:12:04.17

セジウィックとウエインのcourseraのオンライン講義Algorithms Part 1のWeek 2の課題、できた人いますか？

**デフォルトの名無しさん** · 2017/12/02(土) 17:04:18.29

今日のNG ID:LweVlrmz

**デフォルトの名無しさん** · 2017/12/02(土) 20:12:18.77

courseraのセジウィックとウエインの講義を聴講している人はいますか？

**デフォルトの名無しさん** · 2017/12/04(月) 13:54:02.89

>>740
好きなようにするのが自然

**デフォルトの名無しさん** · 2017/12/05(火) 09:10:03.39

↓この仕様の RandomizedQueue の実装できる人いますか？

http://coursera.cs.princeton.edu/algs4/assignments/queues.html

**デフォルトの名無しさん** · 2017/12/05(火) 09:40:42.14

>>746
宿題なら自分でやれ
そうでないなら読むのめんどくさいから要約しろ

**デフォルトの名無しさん** · 2017/12/05(火) 09:45:48.47

松坂君につきスルー推奨

**デフォルトの名無しさん** · 2017/12/05(火) 12:21:40.49

あ、仕様Memory量の見積を勘違いしていました。

できそうですね。

Item 型のデータを格納する Linked List
と
Linked List の各要素への参照を格納する Item[] 型の
配列を用意すれば実現できますね。

**デフォルトの名無しさん** · 2017/12/05(火) 12:25:30.33

あ、でも Item[] 型の配列を ResizingArray で実現したとしても、
常に、Memoryの制限である 48*n + 192 bytes というのを満たすのは
無理ですね。

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

もう少しだけメモリの制限が緩ければ実現可能ですが。

**デフォルトの名無しさん** · 2017/12/05(火) 12:30:24.08

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.

**デフォルトの名無しさん** · 2017/12/05(火) 13:24:03.96

あ、なんだ

簡単でしたね。

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

メモリ使用量～ 8*n

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

48*n を超えませんね。

**デフォルトの名無しさん** · 2017/12/05(火) 13:25:09.16

あ、なんだ

簡単でしたね。

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

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

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

48*n を超えませんね。

**デフォルトの名無しさん** · 2017/12/05(火) 13:27:33.45

これから実装しますが、また100点満点中100点になりそうです。

**デフォルトの名無しさん** · 2017/12/05(火) 13:43:27.58

あ、やっぱりだめですね。

dequeue の計算量がネックになりますね。

**デフォルトの名無しさん** · 2017/12/05(火) 13:45:25.54

あ、分かりました。
一様ランダムに選択された a[i] に a[N] を移せばいいんですね。

**デフォルトの名無しさん** · 2017/12/05(火) 16:58:02.34

本日のNGID:bL4Z2L1G

**デフォルトの名無しさん** · 2017/12/05(火) 21:20:28.14

経路探査でray cast algorithmというのがあるらしいんだが、わかりやすいサイトない？

遊園 · 2017/12/07(木) 01:30:59.64

おちんちん　に　ベロが届くアルゴリズムを教えて下さい。

**デフォルトの名無しさん** · 2017/12/07(木) 09:29:15.88

お金が儲かるアルゴリズムを教えてください

**デフォルトの名無しさん** · 2017/12/08(金) 13:48:57.43

>>759
ム板らしく

香川大
https://www.youtube.com/watch?v=J_R7fgo0FLc
早稲田大
http://www.takanishi.mech.waseda.ac.jp/top/research/voice/movie/Tongue_Phoneme_s.mpg
http://www.takanishi.mech.waseda.ac.jp/top/research/voice/movie/Tongue_EMA_s.mpg
http://www.takanishi.mech.waseda.ac.jp/top/research/voice/index_j.htm
購入可能
https://auctions.yahoo.co.jp/seller/obaba1212

**デフォルトの名無しさん** · 2017/12/09(土) 02:58:56.19

>>760
「お金が儲かるアルゴリズム」で儲かる方法を書いた本を売る

**デフォルトの名無しさん** · 2017/12/09(土) 09:08:05.27

子供の言い返しみたい

**デフォルトの名無しさん** · 2017/12/09(土) 12:25:33.81

それは結構知能が高い子供だなw

**デフォルトの名無しさん** · 2017/12/09(土) 16:48:02.91

https://www.amazon.co.jp/dp/4040800044/ref=cm_sw_r_cp_awdb_c_Kt5kAbQR1S9HF

似たタイトルの本あるな

**デフォルトの名無しさん** · 2017/12/19(火) 17:58:55.99

関数型言語ってUML使うんですか?
クラス図とかメソッドどう書くんだろうと

**デフォルトの名無しさん** · 2017/12/24(日) 12:09:02.25

ちょっと質問させてください。
状況: トータル1000行くらいある巨大メソッドの改修
言語; PHPだがどの言語でもそう関係のない内容

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

public function action(引数){

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

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

/* 500行位の既存コード */
}
となっている。

**デフォルトの名無しさん** · 2017/12/24(日) 12:16:40.00

・ここで、改修要件は、中間にある「/* 50行くらいの既存コード */」を
　　if文で分岐させて分岐次第で違う処理を入れる。というもの。
　　したがって、

public function action(引数){

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

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

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

みたいにひたすら条件分岐して既存コードと新規追加コード
が何回も実行されるようにしたい。

**デフォルトの名無しさん** · 2017/12/24(日) 12:22:57.90

・ここで、俺は「/* 既存コード */」の中身を知っている必要は
　ないと思った。だから、このコードの詳細を読まずに「func()」
　として「action()メソッド内部」に切り出した。
・外部に切り出したのではなく、内部に切り出したのはその処理が
　他のアクションメソッドでは共有されるような汎用的なものではないだろうと
　判断したのと、そのメソッド内で処理を追いやすいようにというのを
　優先させたため。何より、その処理内で使っている関数内ローカル変数の
　依存性の関係上そうせざるを得ないと思った。

public function action(引数){

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

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

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

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

**デフォルトの名無しさん** · 2017/12/24(日) 12:31:59.59

・【訂正】上記で「func()」として切り出したと言っているが、
　　「__legacy()」に変更しました。すみません。
・上記のように改修した所、レビューを受けたときに怒られた。
・まず、「この__legacy()の中身ちゃんと読んだ? 把握して書いている?」
　という指摘。
・そして「ここメソッド内だけどどうして関数定義しているの？
　他の人そんなことしてないでしょ。どうして変わったことするの？」
　という指摘。

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

・2つの指摘に対して、
　「周りの人がやっていること」が正しいとは思えない。
　処理を切り出していないから1000行もある巨大なメソッドになっていて、
　汚いコメントで汚しながら機能追加しまくっているんじゃないのかと。
　ローカル変数を使いまくりの同じ処理を何回も実行するのに
　他に良い手段があるとしたら皆さんに教えて頂きたい。

**デフォルトの名無しさん** · 2017/12/24(日) 13:24:11.47

汎用的でない50行のコードをコピペしてるんなら関数化してもインライン化してもどっちもどっちだな
DRYを意識したのかもしれんがKISSが抜けてる
それにブラックボックスが許されるのは有名なライブラリやフレームワークのようなテストにテストを重ね、かつ多くの利用者による実績があるものだけだよ
社内コードなんて大概クソコードだしブラックボックスにしても後で痛い目を見るのは自分や他の開発者
何なら単に今把握するだけじゃなくて、未来の自分や開発者のためにわかりにくいところをコメントで説明書きしてもいいくらいだ

あと関数内関数より無名関数を変数に代入した方がいいんじゃね
そもそも新規追加したif文も詳細はわからないがデータよりもロジックに寄っててわかりにくそうな匂いがプンプンする

それに上司には理由を聞かれてるんだから同じローカル変数に別の値を入れて使い回すことの危険性、関数化による参照透明の確保や保守性、メンテナンス性の向上を論理的に答えればいいだけ

**デフォルトの名無しさん** · 2017/12/24(日) 13:31:29.00

>>770
レビュアーが言ってることを正しいと仮定すれば
・1つ目の指摘は既存のコードがカプセル化されてないからだ
・2つ目の指摘はリファクタリングするだけの時間やお金や技術がないからだ
という前提が必要になるから、まあそういうことなんじゃなかろうかと

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

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

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

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

レビュアーがそれをきちんと説明できればいんだけど
コードはクソ、レビュアーもクソなんてことはザラにあるんですよこれが

**デフォルトの名無しさん** · 2017/12/24(日) 13:35:53.06

>>771 なるほど勉強になります。
少し質問したいが、
・「KISSが抜けている」と言うのはどこらへんでしょうか？
・関数内関数と無名関数の変数化の違いがわからないので教えてください。
　(面倒なら調べます。)
・あなたならどう対応する？
・「理由を聞かれてるんだから答えればいいだけ。」
　→多分論理的に説明したら「じゃあもう何も教えないよ。好きにやって」
　　が返って来ると思われる。
　そう言われると、必要な情報も来なくなるし聞けなくなる。

**デフォルトの名無しさん** · 2017/12/24(日) 13:38:47.27

>>772
なるほど、俺自身が「既存コードのカプセル化」と
「改修要件」という概念と「改修要件を最小に満たす」という
ことについて詳しくないことに問題がありそうだね。
ありがとう、ここらへんをキーワードにして調べてみます。

**デフォルトの名無しさん** · 2017/12/24(日) 13:55:23.50

>>773
多分もっと細かく汎用的な(publicにできる)関数の集まりに分解して、汎用的でない部分は最小限に出来るんじゃないかなーって思った
実際のコード見てないから予想だけど

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

そもそも上司とあんまり仲良くないの？
論理的にメリットを売り込んだときに感情論で否定されるくらいの関係性だと下っ端プログラマーはしんどいよ？
まぁ俺ならその段階なら折れて普通にコピペして、もっと実績残して仲良くなってから似たような案件のときに改めて売り込むかな

**デフォルトの名無しさん** · 2017/12/24(日) 16:09:59.00

ひとつのメソッドに1000行も書かせる会社はまず危ない

アルゴリズムとかそれ以前

**デフォルトの名無しさん** · 2017/12/24(日) 16:57:23.08

>>775
なるほど、「まるまる関数化」というのが
ちゃんと機能を意識してカプセル化していないってことか。
一応privateは欠けているけど、関数オブジェクトと
関数定義の違いはあまり詳しくないね。そうか、親関数が抜けたとき
子関数が死ぬか否かの違いがあるわけね。
入りたてだから人間関係はいいも悪いもない。
ただ、本来責任ある人はバタバタしていて、経験ある人が自分の意志で
新人のレビューをバラバラに行っている感じ。

>>776
会社がそうさせているというよりはそれぞれの人員が
これまでの追加の仕方を真似て機能追加した結果メソッドがブクブクと太っている
という状況に見える。
メソッド内で各追加機能がコメントで区画されていてそれなら
別関数にすりゃいいのにって思っている。
俺をレビューした人も、別に会社の工程でそうなっているわけでなく、
進捗を見たかったからだと思うが、書き直しを要求してきて困惑している。
ただ彼は業務要件については圧倒的に俺より詳しいから無視すべきではないと
思っている。

**デフォルトの名無しさん** · 2017/12/24(日) 17:21:20.21

>>777
カプセル化はオブジェクト指向において関連するものをまとめる作業だから、ちょっと違うかな？
どちらかというと今回の話は関数型プログラミングの考え方に近い
まぁぶっちゃけ職場のコードなんて割り切らんとやってけんよ
出世してコーディングスタイルに口を出せるようになる日を待つしかない

**デフォルトの名無しさん** · 2017/12/24(日) 18:02:16.50

>>777
そんな仕事を放置する会社、と言うことだ

**デフォルトの名無しさん** · 2017/12/26(火) 20:02:37.53

名前だらけのコードってどうやって解読すればいいんだ？
変数化するとそのデータの型が何なのか物量的にどれだけの
規模が格納されているかが見えない。
もちろんログに吐けば見えるが、吐き出さなければパッと見で
何をどう処理しているのか分からない。

**デフォルトの名無しさん** · 2017/12/26(火) 22:58:59.01

俺は君の話が見えない

**デフォルトの名無しさん** · 2017/12/27(水) 07:26:44.87

関数型言語の仕様書ってUMLで良いの?

データと振る舞い分離してるからクラス図使って良いのかなと

**デフォルトの名無しさん** · 2017/12/27(水) 08:35:11.41

>>782
ちょうど stackoverflow に同じトピックがありました。
参考にしてください。
https://stackoverflow.com/questions/2457903/can-uml-be-used-to-model-a-functional-program

**デフォルトの名無しさん** · 2017/12/28(木) 07:02:18.99

>>783
英語敷居たけえ

まあデータと振る舞いを書いたクラス設計は関数型言語でも同じように使えるし問題ないか

**デフォルトの名無しさん** · 2018/01/10(水) 18:14:12.30

http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html

↑この問題分かる人いますか？

**デフォルトの名無しさん** · 2018/01/10(水) 18:27:49.76

粗探しは止めたのか？

**デフォルトの名無しさん** · 2018/02/03(土) 08:08:45.43

今どきデザインパターンって死語なの？
ちょっと参照したいことがあって書店でデザインパターンの本を探したけど見つからなかった。
リファクタリングの本はあって多少はデザインパターンの話も出てきたけど。
結局は家に帰ってから10年前に買ったデザインパターンの本を参照するしかなかった。

**デフォルトの名無しさん** · 2018/02/03(土) 08:51:29.86

ブームが去っただけかな？
銀の弾丸などないと気がついただけ

**デフォルトの名無しさん** · 2018/02/03(土) 09:20:07.32

今更デザインパターンについて新しい本なんて不要

**デフォルトの名無しさん** · 2018/02/03(土) 12:22:10.78

デザパタは元々バカの為にまとめられたものだったけどバカには無理だった代物
一方リファクタリングはバカ程好むからなかなか廃れない

**デフォルトの名無しさん** · 2018/02/03(土) 19:53:28.27

21世紀最新のデザインパターン本て誰か書かないかね
Singleton→大抵はstaticでOK
みたいなの

**デフォルトの名無しさん** · 2018/02/03(土) 20:04:20.16

>>791
それ以外に何か書くことあんのか？

**デフォルトの名無しさん** · 2018/02/04(日) 00:33:23.10

デザインパターンて結局何だったんだ？
高い本まで買ったがほとんど身に付かなかったな

◆QZaw55cn4c · 2018/02/04(日) 00:43:54.12

>>793
もともと C++ 界隈で発生したテーマですので、C++ をやっているとデザパタの意義がよくわかります
C++ は細かしいことまで自分で記述しなければならないので、こういう大枠思考がもてはやされたのだと思います

◆QZaw55cn4c · 2018/02/04(日) 00:44:42.44

ああ、でも C++ はテンプレートの世界観に移行してしまったので、デザパタ、今はあんまり使いません！

**デフォルトの名無しさん** · 2018/02/25(日) 14:54:54.10

>>793
アルゴリズムの話するときの共通語が必要になって
ついでに良し悪しもまとめておこうという話になった

**デフォルトの名無しさん** · 2018/02/25(日) 16:52:44.22

アルゴリズムとパターンて違うんじゃね？

**デフォルトの名無しさん** · 2018/02/25(日) 18:39:48.45

デザインパターンそこに至る考え方を身につけないと
というわけで、オブジェクト指向のこころをオススメしとく

**デフォルトの名無しさん** · 2018/02/25(日) 18:59:31.93

>>798
書評読んでもなかなかよさげだな

**デフォルトの名無しさん** · 2018/03/05(月) 21:38:39.67

『アルゴリズムイントロダクション』を読んでいます。

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

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

という問題があります。

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

最悪実行時間や最良実行時間については、 Θ 記法で書くのが自然だと思います。

**デフォルトの名無しさん** · 2018/03/06(火) 01:54:34.90

まるちんこ

**デフォルトの名無しさん** · 2018/03/07(水) 21:29:45.52

セジウィックさんはいい加減ですね。

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

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

いずれにしてもひどい本です。

**デフォルトの名無しさん** · 2018/03/07(水) 21:31:54.51

キミはまだアルゴリズムの勉強していたのか。

人には向き不向きというのがあってだな。

**デフォルトの名無しさん** · 2018/03/07(水) 21:33:49.91

すべての重みが異なるというのは異常な仮定ですよね。

**デフォルトの名無しさん** · 2018/03/07(水) 22:27:03.62

茨木俊秀著『アルゴリズムとデータ構造』を読んでいます。

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

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

この分野っていい加減な本が多いですよね。

**デフォルトの名無しさん** · 2018/03/08(木) 19:38:26.94

任意の連結無向グラフ G = (V, E) は |E| ≧ |V| - 1 を満たすことを示せ。

**デフォルトの名無しさん** · 2018/05/12(土) 10:59:28.10

共同ツール 1
https://seleck.cc/685

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

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

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

ttps://goodpatch.com/blog/sketch-plugins/

**デフォルトの名無しさん** · 2018/05/23(水) 20:11:35.70

僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法　モニアレフヌノ』

BU06O

**デフォルトの名無しさん** · 2018/06/24(日) 11:32:17.25

AVL木について詳しく載っている本は何ですか？

**デフォルトの名無しさん** · 2018/06/24(日) 14:42:02.78

詳しいと言えるかどうかは別にしてAVL木に関する説明が分かりやすいと思ったのは次の本の該当箇所（§6.3）だ

浅野哲夫『データ構造』、アルゴリズムシリーズ１、近代科学社 (1992)

**デフォルトの名無しさん** · 2018/06/24(日) 15:07:06.81

ステマ

**デフォルトの名無しさん** · 2018/07/04(水) 22:09:33.44

C5O

**デフォルトの名無しさん** · 2018/07/05(木) 16:33:38.42

C5O

**デフォルトの名無しさん** · 2018/07/21(土) 20:42:50.98

1つ言えるのはオブジェクト指向のなんかよりも
データ構造とアルゴリズムの方がよっぽど重要だということ。
昔はオブジェクト指向の勉強を頑張っていたけどそのときは
全然プログラミングがうまくならなかった。
現代の世の中はガチガチに設計されたライブラリを使って
コードを書くだけだから生半可なオブジェクト指向の知識なんて
ゴミ同然だよ。80年代90年代に考えられた思想とか、もうゴミに
なってしまった思想が多くて有害だよ。
結局現場でやることは「メソッドの使い方を求めてQiitaやStack OverFlowを
漁って成功するコードを見つけるまで疲れ果てる」ことに変わりはない。
せっかく勉強した内容が時代遅れで「裏切られる」ことのほうが多い。

**デフォルトの名無しさん** · 2018/07/21(土) 20:51:29.70

一方、データ構造とアルゴリズムをガッツリと勉強してから
様々なデータ構造の使い方、問題の解決がうまくなった。
ブロックチェーンのアルゴリズムの理解や
データ分析の数学的演算がコーディング
できるようになってプログラミングが格段に楽しくなった。
スマートにオブジェクト指向で設計する力なんかより
「ゴリゴリとアルゴリズムを書く力」の方がよっぽど重要。
「再利用性」？「変更の影響」だって？そんなものゴミだね。
それは自分以外の人間のメリットのための技術であって、
自分へ還元されるためのメリットではない。
再利用性は自分の書いたコードなら信頼できるしコピペして使えばいい。
自分の書いたコードのコピペは全然ありだと思う。
適したメソッドが見つからなかったらQiitaを漁ったりせずに
自分でゼロから実装したほうが速い。
その場で手っ取り早くコードを生成しているから、
どんな既存コードにも頼っていないから俺の実装したコードは
依存性は低い。

**デフォルトの名無しさん** · 2018/07/21(土) 21:29:45.12

ただし>>814-815は何かのアプリを作ったことはない

◆QZaw55cn4c · 2018/07/21(土) 21:58:56.02

>>815
一つ重要な視点を提供しましょうか
自分の記憶などあてになりません、3ヶ月前自分が書いたコードは、もはや他人が書いたコードとなんら変わりありません

**デフォルトの名無しさん** · 2018/07/21(土) 22:06:10.19

>>814-815はすでに解いたことのある問題なら
忘れたとしても、少し時間をかければ解けると考えている

つまり誰かが出した出題を解くという作業をしている

**デフォルトの名無しさん** · 2018/07/21(土) 22:34:33.64

>>>817, 818
自分のいつも使うアルゴリズムのパターンが身についていれば
そのパターンや命名規則から何をやっているかは解読できる。
読みにくくなるのは外部から取り込んだ機能の実行や
継承している部分。

**デフォルトの名無しさん** · 2018/07/21(土) 23:12:43.54

>>819
やっぱり「解読」してるんだｗ

すでに証明済みの問題を自分の力で証明するという
お勉強をやってるだけだね

**デフォルトの名無しさん** · 2018/07/21(土) 23:21:07.94

研究者で無い限り新しい証明考える必要ないっしょ

**デフォルトの名無しさん** · 2018/07/21(土) 23:22:28.87

解読の工程は業務でも必要であるし
遊びとしても面白い
それが勉強になるならとても有益じゃん

**デフォルトの名無しさん** · 2018/07/21(土) 23:34:47.51

「車輪」は大きさ、材質、シャフトの接合部の形、色…大まかな形や役割は似ているが微妙に違うものが無数にある。
ちょっとでもこれらの特徴がずれたものは他への転用を考えるとすぐに不具合となって使い物にならない。
車輪を最初に「発明」した人物はこれらの無数の車輪を全て発明したわけではない。
だから他の人が死ぬほど似たようなものを作っていたとしても自分で作る必要がある。
他人が作った車輪は無条件で役にたつわけがない、
手直しして組み込むより「自分の規格で」作った方が早い。