- 1 名前：デフォルトの名無しさん mailto:sage [2012/03/21(水) 06:40:59.10 ]
- データ構造とアルゴリズムに関する総合スレ。
【関連スレ】
3Dアルゴリズム全般
toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
toro.2ch.net/test/read.cgi/tech/1217773415/
- 263 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 16:56:47.24 ]
- おまえなんでここ監視して余計なこと言ってんの？ここで発言する必要ないだろ
- 264 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 17:44:41.21 ]
- >>261>>263
失せろゴミ
- 265 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 17:48:18.98 ]
- （笑）
- 266 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 20:49:04.54 ]
- 空間ってか直方体を8つごとに分けていって
8分木の形にしたデータ構造の,一部の葉だけが選択されていて,それらの葉の接続関係
を求めるってどうすればできますか？
葉に対応する直方体の面同士が接していれば接続しているとしたいのですが
階層がちがうのの扱いがよくわかりません。。。
- 267 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 21:00:13.81 ]
- ？
- 268 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 21:04:32.27 ]
- 点の絶対座標から、その点を含むノードのアドレスを出せるよう、ノードのアドレスを工夫する。
（ここで言うアドレスとは、root->node[0]->node[1]->node[4] における (0,1,4) のようなもの）
で、選択されたノードの中心座標 (x,y,z) から (x±dx, y±dy, z) (x±dx, y, z±dz) (x, y±dy, z±dz) （復号任意）を含むノードのアドレスを得る。
- 269 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 21:19:16.93 ]
- >>268
どうもです^o^
- 270 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 22:08:59.67 ]
- ミスった。
> (x±dx, y±dy, z) (x±dx, y, z±dz) (x, y±dy, z±dz)
ここ普通に (x±dx, y, z) (x, y±dy, z) (x, y, z±dz) だ。
dx, dy, dz はまあ、直方体のサイズとかでも。
- 271 名前：デフォルトの名無しさん mailto:sage [2012/07/03(火) 23:26:29.68 ]
- >>255
www.pi6.fernuni-hagen.de/publ/tr198.pdf
- 272 名前：デフォルトの名無しさん mailto:sage [2012/07/11(水) 03:06:25.48 ]
- 質問させてください
C++スレから誘導してもらいました
スレチでしたら誘導頂けると幸いです。
O表記法についてなのですが、イマイチ理解できていません。
授業にて以下7つのルールを定義されたのですが
各々について具体的な数字の入った例をいただけませんでしょうか
#数学の勉強が足りないのかもしれませんが、具体的な数字があれば理解できると認識しています。
#宿題ではないのですが、以降のテストで以下ルールを適用しながらアルゴリズムの証明を行う問題が出題される予定です。
1). if f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)) then f(n) ∈ O(h(n))
2). if f(n) ∈ O(h(n)) and g(n) ∈ O(h(n)) then f(n) + g(n) ∈ O(h(n))
3). an^k ∈ O(n^k)
4). n^k ∈ O(n^k+j) for any j
5). if f(n) = cg(n) then f(n) ∈ O(g(n))
6). loga n ∈ O(logb n) O(logn)
7). loge n ∈ O(loge n)
お手数ですがよろしくお願いします。
- 273 名前：デフォルトの名無しさん mailto:sage [2012/07/11(水) 10:26:48.61 ]
- いやです
- 274 名前：デフォルトの名無しさん mailto:sage [2012/07/11(水) 10:42:54.09 ]
- >>272
ggrks
- 275 名前：デフォルトの名無しさん mailto:sage [2012/07/11(水) 11:57:07.67 ]
- 雑多な質問スレっていろいろあるのに
何故このスレに誘導されたのだろうか
- 276 名前：デフォルトの名無しさん mailto:sage [2012/07/11(水) 12:12:31.31 ]
- >>272
ランダウの記号 - Wikipedia
ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7
- 277 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 04:03:56.85 ]
- >>272
オーダー記号って普通は等号使ってn=O(n)とか書くんじゃないかな
それはともかく数字があれば理解できるって神だな。
関数の極限の話だし。
- 278 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 07:19:45.35 ]
- ヒープソートでなぜ再帰？～日本語版ウィキペディアの問題点と最強最速のヒープソート～
www.dreamhope.net/soliloquies/HeapSort/
- 279 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 08:54:36.87 ]
- >>278
この人頭悪いね
>同じコンピュータ環境で、Linux GCC環境では2,500,000件程度のデータを取り扱いできるのに対し、
>Windows BCC環境ではその10分の１の258,000件程度が最大です。
>LinuxがWindowsよりも10倍性能が良いのか、GCCがBCCより10倍性能が良いのかはわかりませんが、
>この性能差には驚きました。
そりゃ
int dat[DC+1]; //データ格納用配列
のようにスタックに巨大な配列を取ればそのうちスタックオーバーフローするって
更にスタックオーバーフローは都合の悪い事にエラーが出ずに結果だけおかしくなる事が多い
ちゃんとソートされているのか結果を見たのかな(ヒープ4だけは見ているようだけど)
Linuxはスタックが足りなくなると自動的に拡大してくれるので問題が出ない
ヒープに取れば同じ事
速度が4倍～13倍も違うのはよく分からない
ちなみにEclipse CDT + gcc4.6.1でやってみたがbccやvcと速度的には大差なかった
スケジューリングの問題かな？
- 280 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 10:12:28.23 ]
- スタックオーバーフローは最近はSEGVで落ちるんじゃね？
ウィキペディアの記事も微妙だが、そのウェブページもいろいろと頭悪いという
ことについては同意。
- 281 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 10:21:47.95 ]
- >>280
Linuxは拡張しきれないスタックを要求した時はSEGVで落ちるけど
Windowsは黙って変な結果を出して終了するか、暴走するかどちらか
- 282 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 12:08:48.86 ]
- ランダウの記号って名前があったのか
知らなかった
- 283 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 12:51:41.81 ]
- Mac も
> 黙って変な結果を出して終了するか、暴走するか
- 284 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 13:50:54.97 ]
- VCのデバッグならスタックオーバーフローを検出して止まるので
リンカのオプションからスタックサイズを改めて指定しなおす事になる
この時に一度ビルドをクリーンしないと単にリンクし直すだけでは
スタックオーバーフローエラーは止まらないようだ
- 285 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 20:40:52.04 ]
- ＞そして、ウィキペディアを書き換えようかと思ったが、とても面倒なのでこちらにて問題提起することにした。
・・・ナゼ
- 286 名前：デフォルトの名無しさん mailto:sage [2012/07/12(木) 21:20:43.48 ]
- 自己顕示欲の強そうな人だね
他の記事も読んだけど首を傾げすぎて首が疲れた
データベースは毎回自分で実装した方がいいらしいよ 目から鱗だわ
- 287 名前：デフォルトの名無しさん mailto:sage [2012/07/13(金) 16:46:26.64 ]
- 最適化を語るのにオプションを明示しないとか、
データ量を語るのにオプションを明示しないとか、
処理速度を語るのに環境を明示しないとか、
10～20年くらい前から知識が更新されていないんじゃないだろうか。
- 288 名前：デフォルトの名無しさん mailto:sage [2012/07/13(金) 16:47:09.23 ]
- >>285
批評に晒されたくないチキンハートなんでしょ。
- 289 名前：デフォルトの名無しさん mailto:sage [2012/07/13(金) 19:20:15.32 ]
- 出回ってる書籍が古いものばかりだからね
図書館で借りようものなら１０年～２０年昔の本だって当たり前のように陳列されてる
- 290 名前：デフォルトの名無しさん [2012/07/17(火) 20:23:27.35 ]
- ①区間スケジューリング問題＜＝ｐ 点カバー問題
②独立集合問題＜＝ｐ 区間スケジューリング問題
この２つについて
(i)Yes (ii)No (iii)「これが解ければP=NP問題が解決できるので不明」
のいずれかで答え、その簡単な説明も与えよ。
という問題の答えを教えて下さい
- 291 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 01:05:55.70 ]
- C/C++の宿題片付けます 158代目
toro.2ch.net/test/read.cgi/tech/1339338438/
- 292 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 01:26:27.60 ]
- すっげえ宿題でるんだな
俺が通ってた大学での「データ構造とアルゴリズム」ってまんまの名前の授業あったけど
宿題に出たのがせいぜい一般的なソートアルゴリズムいくつかををjavascriptで書けとかそういうレベルだったよ
- 293 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 04:41:54.35 ]
- なんでjavascriptなの？なんかその大学に興味があるんだけど
今時は大学でjavascriptでアルゴリズム書かせるのか
- 294 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 10:28:38.16 ]
- schemeの代替
- 295 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:29:46.28 ]
- web限定用語で教育するってのはちょっとナンセンスかと
- 296 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:31:53.61 ]
- 「web限定用語」ってすごい表現だなw
プログラミング言語を「用語」って言うのはどこのマヌケ業界だろう？
- 297 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:39:08.99 ]
- web限定言語で教育するって凄い大学だな
- 298 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:41:14.74 ]
- 逆にCとかJavaみたいな一般のプログラマにとって中途半端に使えない、
実用的でない言語なんて教えたところで意味無いでしょ。
- 299 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:49:22.80 ]
- じゃあpythonでいいだろ
少なくともアルゴリズムの授業でjavascriptってのは学生がかわいそうだ
- 300 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:53:38.65 ]
- >>298
いや相手は情報系の学生だぞ？
CもJavaもダメな奴がどうやって情報科学を学ぶわけ
- 301 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 11:54:58.55 ]
- >>298
世界が狭すぎ
あなたがどういうバックボーンなのか知りたいわ
- 302 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:02:34.74 ]
- 情報系っていうのはプログラマ養成施設じゃないよ。
専門学校か他の工学系と勘違いしてないか？
- 303 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:15:03.55 ]
- 情報系でCもJavaも教えない大学があるのか？
それまともな大学じゃないだろ
そんなカリキュラムが存在するならマジで教えて欲しい 聞いたこと無いから
プログラマ養成機関じゃないからこそCで本質に切り込むんじゃないの
専門学校みたいなプログラマ養成機関こそがPHPとかJavascriptを教えるんでしょ
まあそれはさておき、アルゴリズムの概念を教えるのにJavascriptを使う大学はおかしいよ絶対に
それも否定する？
- 304 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:18:38.42 ]
- まともな大学生ならCは自習で既に学んでるから大学ではいちいち教えない
- 305 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:27:09.76 ]
- アルゴリズムの本質は言語によって変わらない
- 306 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:31:27.01 ]
- 「アルゴリズムの本質は言語によって変わらない」
それはわかるけどさ、だからといって
「アルゴリズムの本質は言語によって変わらないからJavascriptで教えます」
はおかしいでしょう 普通の感覚じゃ考えられない
言語実装に関係のない本質を教えるんであれば、なおのこともっと汎用的な普遍的な言語でやるべきじゃない
- 307 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:34:34.41 ]
- そうかい
- 308 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:36:18.55 ]
- その感覚はわからなくもないが感覚じゃなく理屈で説明してくれ。
- 309 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:42:09.35 ]
- アルゴリズムの授業だからJavascriptなんじゃなくて
別の理由で決まったんだろ
- 310 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 12:44:52.14 ]
- 10年前とは違うからな。javascriptを取り巻く環境は随分改善した。
ブラウザ間の互換性であるとかデバッグ環境はすでに十分な領域に達している。
- 311 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 13:00:17.42 ]
- >>305
8-QueenをCOBOLで書くようにという宿題がでるらしいと聞いたら
その授業は取らない。
- 312 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 13:32:43.00 ]
- そうかい
- 313 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 14:07:00.66 ]
- 8-Queenとアルゴリズム全般、COBOLとJavascriptじゃ違いすぎるな
- 314 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 14:36:01.76 ]
- いい加減スレ違い
- 315 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 14:41:23.22 ]
- そうかい
- 316 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 14:59:25.90 ]
- JavaScriptをウェブ専用とか思ってるバカがプログラマのわけないだろw
- 317 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 15:00:37.58 ]
- そうかい
- 318 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 17:11:07.05 ]
- ECMAScript は Web 専用じゃないけど Javascript は Web 専用とか、そういう揚げ足取りなのかもね。
- 319 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 17:44:37.90 ]
- 言語は手段でしかない
- 320 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 18:22:28.47 ]
- javascriptはクロージャを学ぶのに悪くない
- 321 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 18:57:27.05 ]
- >>319
このスレの住人が口にすると迫力あるな。
- 322 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 19:27:20.07 ]
- そうかい
- 323 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 20:51:20.96 ]
- VB、PHPのように学ぶと頭が悪くなる言語じゃなきゃ、あとは教える教員の好みだろ。
- 324 名前：292 mailto:sage [2012/07/18(水) 20:56:44.84 ]
- 誰のＰＣにでも入ってて使えるプログラム言語だからという理由でjavascriptを指定してたよ
別にHTMLファイルにするとかじゃなくて
アルゴリズムを再現したコードをメールに添付して送信するみたいな宿題だった
ちなみに情報が専門の学科は無い大学だったのでそういうことに
- 325 名前：292 mailto:sage [2012/07/18(水) 21:04:23.79 ]
- ちなみな自分語りになるが
学科名的には電子情報工学科となってて情報系の授業を期待して入学したものの
（ちゃんと調べずに願書出した俺が悪いのだが）
情報とは名ばかりで情報系の授業はほとんど開講されず
電子系、特に半導体系の授業ばかりしかなかった
その大学わが母校はもう存在してないけどね
- 326 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 21:13:34.30 ]
- 本当ただの自分語りだな
- 327 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 21:21:22.30 ]
- 寂しい奴なんだろう。
- 328 名前：デフォルトの名無しさん mailto:sage [2012/07/18(水) 23:16:38.10 ]
- >その大学わが母校はもう存在してないけどね
津波で流されたのね
- 329 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 01:35:32.86 ]
- つまり本格的な情報科学系の授業では無かったという事の証左だよな
まあ非情報系の学生だったらブラウザで誰でも実行環境が整うからあえてJavascriptでやるっていう意味もわかる気がする
- 330 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 04:30:09.03 ]
- VB、PHPのように学ぶと頭が悪くなる言語じゃなきゃ、あとは教える教員の好みだろ。
- 331 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 07:32:51.17 ]
- なんでこんな頭の悪いのがこのスレにいるんだ？
- 332 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 09:04:49.51 ]
- 若者の 2ch 離れが進んでいるな
- 333 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 19:06:58.62 ]
- 2点が与えられたときその2点を結ぶ単純な経路（同じ頂点を通らない経路）
が2つ以上存在するかを判定するアルゴリズムと計算量を述べよ。
深さ優先探索とかでしょうか？
- 334 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 19:12:15.02 ]
- 宿題は宿題スレへ
- 335 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 19:36:47.50 ]
- 失礼しました
- 336 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 21:33:34.33 ]
- >>331
どっちのこと？
- 337 名前：デフォルトの名無しさん mailto:sage [2012/07/19(木) 21:44:47.18 ]
- おそらく自問自答だろう
- 338 名前：デフォルトの名無しさん mailto:sage [2012/07/20(金) 16:42:44.97 ]
- 二分探索木の平均高さが O(logN) の証明ってどういう風にやるんでしょうか？
アルゴリズムイントロダクションに書いてあるらしいのですが見当たりません。どのあたりでしょうか？
- 339 名前：デフォルトの名無しさん mailto:sage [2012/07/20(金) 16:53:14.03 ]
- >>338
2分探索の構造がわかれば少し考えればわかることだよ
- 340 名前：デフォルトの名無しさん mailto:sage [2012/07/20(金) 16:56:17.57 ]
- >>338
木 T が平衡なら、そのまま height(N) = 1 + height(N/2) で O(logN)でしょ。分割統治法
- 341 名前：デフォルトの名無しさん mailto:sage [2012/07/20(金) 17:29:31.19 ]
- 手元の本にありましたのでもういいです。
お騒がせしました
- 342 名前：デフォルトの名無しさん mailto:sage [2012/07/20(金) 19:17:26.17 ]
- 宿題は宿題スレへ
- 343 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 03:01:26.56 ]
- 3つのくっついてる円にこれまたくっついて囲まれてる円の半径を
求めるアルゴリズムってどうすればいい？
- 344 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 03:14:49.30 ]
- ３つの円はどういうくっつき方？
３つの円の半径はばらばら？
○○○
○
○○
- 345 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 03:24:10.91 ]
- 宿題は宿題スレへ
blogs.yahoo.co.jp/oka_yadokary/29892416.html
- 346 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 03:24:54.06 ]
- 343は外接・内接という言葉も知らなそうな雰囲気で困る。
- 347 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 03:28:43.57 ]
- >>344
くっつき方は下の方
円の半径はバラバラ
- 348 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 03:47:28.98 ]
- ２本（３本）の双曲線の交点が共通接円の中心か
- 349 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 14:31:42.96 ]
- 互いに接する３つの円 に外接する円の半径の求め方？
- 350 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 14:32:39.99 ]
- ３つの円すべてと接する外接円は無理じゃね
- 351 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 14:36:32.23 ]
- デカルトの円定理
aozoragakuen.sakura.ne.jp/taiwa/taiwaNch03/enteiri/node2.html
- 352 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 14:36:40.22 ]
- にしてもスレチ。
- 353 名前：デフォルトの名無しさん mailto:sage [2012/07/21(土) 14:55:54.21 ]
- アルゴリズムでも何でもないなコレ
- 354 名前：デフォルトの名無しさん mailto:sage [2012/07/22(日) 10:15:52.04 ]
- プリムのアルゴリズムのヒープ版って
(E+V) log (E) ≒ Elog(E)ってあるけど (E+E) log (E) ≒Elog(E) が正しいと思う
挿入か削除のどっちも Elog(E) でしょ 最悪全枝を一回ずつ挿入と削除する必要があるんだから
- 355 名前：デフォルトの名無しさん mailto:sage [2012/07/25(水) 05:54:32.42 ]
- 王様は王様でも頭が三つある王様はな～んだ
- 356 名前：デフォルトの名無しさん mailto:sage [2012/07/25(水) 06:04:38.43 ]
- 三頭王
- 357 名前：デフォルトの名無しさん [2012/07/25(水) 17:58:22.97 ]
- キングギドラ
- 358 名前： ◆VD2btbRbPs [2012/07/25(水) 21:41:00.81 ]
- 大学の課題で二分探索木の高さを調べる実験とその結果を調べる実験が出たのですが
どうしたらいいですか
- 359 名前：デフォルトの名無しさん mailto:sage [2012/07/25(水) 21:54:46.35 ]
- そのようにプログラムを作って結果を表示すればいいのでは？
- 360 名前：デフォルトの名無しさん mailto:sage [2012/07/26(木) 16:24:57.70 ]
- 宿題は宿題スレへ
- 361 名前：デフォルトの名無しさん mailto:sage [2012/07/26(木) 21:29:42.06 ]
- ほんとこういう質問するガキがムカつく
どうすればいいですか？って何だよ
そんな曖昧な質問で答えられると思ってんのかカスが
どこの底辺大学だか知らないが学費が無駄
- 362 名前：デフォルトの名無しさん mailto:sage [2012/07/26(木) 22:10:01.46 ]
- >>358
擬似乱数から最大の低周波成分を除くアルゴリズムを考案する。最大の低周波成分を除く操作を
繰り返すごとに２分探索木の高さが次第に平坦化することを実験・観察する。
- 363 名前：デフォルトの名無しさん mailto:sage [2012/07/26(木) 22:23:02.61 ]
- 教授に不正してる奴がいたと報告しとく
|
 |
