計算機科学・情報科学の本

**名無しさん＠お腹いっぱい。** · 2006/10/13(金) 20:57:25

ないから立てた

**名無しさん＠お腹いっぱい。** · 2010/06/06(日) 17:27:32

>>370
y軸が対数目盛をとっている、と考えるとどうだろうか？

**名無しさん＠お腹いっぱい。** · 2010/06/06(日) 22:55:48

それならO(c^n)のグラフは直線になると思うけど違う？
O(n^k)のグラフが変曲点を持って下に凸だったり上に凸だったりするつのがそもそも変じゃない？

**名無しさん＠お腹いっぱい。** · 2010/06/07(月) 15:54:16

>>370
間違っている可能性があるという指摘で終わらせればいいものを、
つい余計な一文が入ってしまうのは、
足の引っ張り合いといふ日本人としての悲しい性なのだろうか？

**名無しさん＠お腹いっぱい。** · 2010/06/08(火) 21:18:24

>>372
作図者は凸の様子は問題にしなかった、だけだと思うが。
そもそも計算量の評価に関するかぎり、曲線の凹凸具合など関係ない。
>>370 は本質がわからないか、>>373 のとおりか。

**名無しさん＠お腹いっぱい。** · 2010/06/09(水) 02:47:42

>>374
> >>372
> 作図者は凸の様子は問題にしなかった、だけだと思うが。
> そもそも計算量の評価に関するかぎり、曲線の凹凸具合など関係ない。
> >>370 は本質がわからないか、>>373 のとおりか。

本質が分ってないのはお前の方だ

下に凸か上に凸かは問題サイズが大きくなって行くと
計算量の増え方がサイズの増え方より激しいか否かを表しており
計算量の漸近的振る舞いに関して図形として表現できる情報として最も重要なものの一つ

だから本来ならばO(n^k)のグラフはk<1, k=1, k>0の３通りを示す必要がある
そしてO(c^n)は同じ下に凸でもO(n^k)　(k>1)より遥かに急激に増加する様子を示し、
O(log n)は逆に同じ上に凸でもO(n^k)　(k<1)より遥かに緩やかに増加する様子を示す必要がある

その事に気付かず、指摘しても「本質がわからない」なんて強弁してるお前は
この作図者と同じく計算量の漸近的振る舞いを図的に示すとはどういう事なのかのポイントを何も理解していない

**名無しさん＠お腹いっぱい。** · 2010/06/09(水) 20:26:37

>>375
計算量に関する限り、上に凸、下に凸が話題となる問題は聞いた事がないのだが、なにかあるのか？

**名無しさん＠お腹いっぱい。** · 2010/06/10(木) 14:18:09

上に凸な問題なんてないでしょ。ultralinearということだものね。
定数O(1)を除けば線形O(n)が最善で、あとはO(n log n)、O(n^2)、
多項式、指数とふつう区分が問題なのは全部下に凸だよね。だから
上に凸とか下に凸とか問題にしてもあまり意味がない。

**名無しさん＠お腹いっぱい。** · 2010/06/10(木) 15:18:07

2分探索とか普通に上に凸だけど

**名無しさん＠お腹いっぱい。** · 2010/06/11(金) 15:35:43

そうか、失礼。「定数O(1)と対数O(log n)を除けば」でどうかな。

**名無しさん＠お腹いっぱい。** · 2010/06/11(金) 20:30:22

>>377
> 上に凸とか下に凸とか問題にしてもあまり意味がない。

じゃあ、そもそもO(f(n))の大雑把なグラフを見せる意義は何なんだ？
意義のないグラフを見せてるって事だぞ。
お前の言う事に従えば、そもそも>>368のグラフなど見せる必要がないって事だ。

それに>>368のグラフでのO(n^k)には意味不明な変曲点がいくつもある。
図は数値と違って定量的な精密さは期待できない。
だから図を説明に使うのならば定性的に重要なポイントを直感的に理解でしやすいように伝える事が本質だ。
変曲点の有無はO(n^k)のグラフの本質とは無関係で、変曲点の存在などむしろ誤解を招きかねない不要なノイズ的な情報。
（しかも漸近的に上に凸の形にO(n^k)を描いたとあってはね）

だから>>368のグラフを描いた大学教員は計算量の事についてもそれを図で説明する事についても
本質を分かってないと言ってるんだよ。

**名無しさん＠お腹いっぱい。** · 2010/06/11(金) 20:50:25

>>380
>>377 で言及されているとおり、情報工学では、上に凸とか下に凸とかは、あまり話題にならない。
話題にならないものにこだわっても仕方がない。

**名無しさん＠お腹いっぱい。** · 2010/06/12(土) 11:17:01

直感的に違ってるものを提示するのは、話題になるならないにかかわらず、間違ってる。

**名無しさん＠お腹いっぱい。** · 2010/06/13(日) 00:48:52

>>380
O-記法の厳密な意味を調べるんだ。ランダウの記号とかでググってみると良い。

O-記法は、あくまで上界を示すものだから、下に凸だろうが変曲点があろうが
構わないんだよ。実際に、O(n^2)でも変曲点をもつようなアルゴリズムはある
わけで。

だから図は間違ってはいない。ただ説明用の図としては他の例を選んでも
良かったと思うけどね。

**名無しさん＠お腹いっぱい。** · 2010/06/13(日) 05:28:45

>>383
> >>380
> O-記法の厳密な意味を調べるんだ。ランダウの記号とかでググってみると良い。

そんなのは知ってるさ

> O-記法は、あくまで上界を示すものだから、下に凸だろうが変曲点があろうが
> 構わないんだよ。実際に、O(n^2)でも変曲点をもつようなアルゴリズムはある
> わけで。

変曲点の有無は何ら重要性がないから図に入れるべきでないと主張してるんだよ。
図とは本質的に重要な情報だけを入れれば良いのだ。

そもそも個々のアルゴリズムの時間計算量はイグザクトに決まるから
上界を示すO記法でなくΘ記法を用いるのが適切なんだが
慣習的にO記法で済ませている事がおおい。

例えば、O記法は上界を意味するからと言って、
「（Θ(n・log n）と分かっている）ヒープソートの最悪時時間計算量はO(n^2)だ」と言えば
O記法の使用法として論理的には正しいが「こいつ何も分かってないんじゃないの？」と馬鹿にされるのがオチ。

本質的にO記法が必要なのは問題自身の計算量の方だよ。
与えられた問題に対して最適の（つまり最も計算量の小さな）アルゴリズムが発見されているとは限らないからね。
例えばｎ次正方行列２つの積を求める問題の時間計算量はStrassenのアルゴリズムが発見される前まではO(n^3)のクラスであり、
それが発見された事でO(n^(log_2 7))のクラスに下がったわけだ。

> だから図は間違ってはいない。ただ説明用の図としては他の例を選んでも
> 良かったと思うけどね。

O記法が上界を意味するから間違っていないなんて言ったら
O(c^n)に対するグラフとして log n のグラフを示しても間違っていないという事だよ。

じゃあ、何の為にグラフを示すんだね？
O(f(n))に対するグラフはf(n)以下のグラフなら何を示しても間違いでないという事だ。
そんなグラフを見せる事に何の意味がある？

O記法は上界を表すだけだなんて詭弁を弄さずに、O(f(n))のグラフを示す事は何を伝える事が目的かを考えたまえ。
上界としてのf(n)の漸近的振る舞いを示し、f(n)の違いによって n　が大きくなるとどれほど違うかを学生に伝えるのが目的なんじゃないのか？

O記法は単に上界だからO(f(n))に対するグラフは漸近的にf(n)以下となるどんな関数のグラフでも良いなんてなったら何の意味もない。
上界だからこそ、そのオーダーに属し得る最大の関数のグラフを示すべきだろう。

そして線形（つまりO(n)）よりも計算が大変か容易かこそが何よりも伝えるべき事柄だよ。
それが下に凸な形か上に凸な形かという事で明快に表現されるという事だ。

はっきり言えば、何のスケールも示されていない完全に定性的なグラフではO(n^k)とO(c^n) （c, ｋ＞１）とはグラフの形だけでは明確に区別できない。
せいぜいO(n^2), O(n^3), O(n^4), ...　と段々と急増加するグラフを並べてO(c^n)はそれらより更に増加が激しいという様にして示す以外にない。

ここには例のグラフにあった変曲点なんて無意味なものが登場する余地はない。
変曲点の有無なんて計算量のクラスとは何も関係ないのだから。

計算量と関係のない変曲点を書いている一方で線形より遅いはずのO(n^k)のグラフが漸近的に上に凸になるように書いているから
「あのグラフを書いた教員は計算量について何も分かっていない」と批判してるんだよ。

**名無しさん＠お腹いっぱい。** · 2010/06/13(日) 09:21:27

俺はむしろノイズを入れた線をあえて描いておくべきだと思うね。
O(n^2)は、ちょうどn^2に比例した計算量だと思っている奴が多い
こと多いこと。実際にはそんなことは滅多にないわけで、だったら
説明の図もそうあるべきだと思う。

この人がそこまで考慮して作ったのかどうかはわからんが。いずれに
せよ、この図を使ってどう説明したかによるな。少なくとも、3本とも
綺麗な線で描いておくよりは誤解が少なくて済むと思う。

**名無しさん＠お腹いっぱい。** · 2010/06/13(日) 12:14:19

そろそろスレ違いということに気づいてほしい

**名無しさん＠お腹いっぱい。** · 2010/06/13(日) 18:49:41

では、この話題はこれで終了ということで。

**名無しさん＠お腹いっぱい。** · 2010/06/14(月) 01:09:54

>>385
> 俺はむしろノイズを入れた線をあえて描いておくべきだと思うね。
> O(n^2)は、ちょうどn^2に比例した計算量だと思っている奴が多い
> こと多いこと。実際にはそんなことは滅多にないわけで、だったら
> 説明の図もそうあるべきだと思う。

ふーん、計算量理論やアルゴリズム論をお前に習わなくて俺は幸運だったよ。

> この人がそこまで考慮して作ったのかどうかはわからんが。いずれに
> せよ、この図を使ってどう説明したかによるな。少なくとも、3本とも
> 綺麗な線で描いておくよりは誤解が少なくて済むと思う。

まず最も典型的なのを理解させるのが第一歩、一般的な場合を教えるのはその次の段階だと俺は考えてるがな。
典型的なケースさえ理解できん学生が一般的なものを理解できるなど、よほど特殊な人間（人はそういう人間を天才と言う）以外にはまず不可能。
ノイズの入った図からノイズを除去して本質を見抜いて理解できる学生なんて宮廷大クラスでもほとんどいない。

そんな問題以前に、O(n^k)として最も良く出て来るｋ＞1の場合のO(n^k)のグラフが横軸（当然だが問題サイズ n の筈）の大きい部分で上に凸、
つまり漸近的には線形時間のO(n)よりも高速になる形で書いてるのが致命的だね。
これは言い訳が不可能。
まさかO(n^(1/2))を示したなんて言わないだろうな。
O(n^(1/2))の問題やアルゴリズムなんてこのグラフを見る初歩的な段階では出会ってないのは確実だからな。

結局、今回の秋田県立大？のこのグラフを書いた教員は、３つのグラフを違った形で書けば良いぐらいしか考えずに書いたとしか思えんな。

さて、スレチだという批判もあるみたいだし、これだけ説明しても理解できんのなら相手にしても無駄だから、俺も終わりにしよう。

**名無しさん＠お腹いっぱい。** · 2010/06/14(月) 05:55:36

>>388
うぜえからさっさと帰れ

**名無しさん＠お腹いっぱい。** · 2010/06/16(水) 16:36:00

>>388
とっとと死ねやこのクソゴミクズカス

**名無しさん＠お腹いっぱい。** · 2010/06/16(水) 18:35:52

>>389 >>390
>>389 >>390