データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
京都大学霊長類研究所
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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 アルゴリズムイントロダクションを読んでいます。
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連投だって容易い。 ■ このスレッドは過去ログ倉庫に格納されています
