2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

アルゴリズム Algorithm

1 :名無しさん@お腹いっぱい。:2007/06/25(月) 22:06:59 ID:pQcV23tD0
アルゴリズム全般の話題はここでやれ!

2 :名無しさん@お腹いっぱい。:2007/06/26(火) 00:13:32 ID:KPnnITHL0
このスレは伸びない。

3 :名無しさん@お腹いっぱい。:2007/06/26(火) 17:20:27 ID:Sgu5LsuW0
この板にあるスレはみんな伸びない。

4 :名無しさん@お腹いっぱい。:2007/06/28(木) 00:28:10 ID:KVOce1Jx0
勢いトップが3.9だぜwwww
どんだけwwww

5 :名無しさん@お腹いっぱい。:2007/06/29(金) 23:14:35 ID:r2dt+jlx0
おいおい、何で伸びないんだ
情報学の根幹は論理とアルゴリズムだろ

6 :名無しさん@お腹いっぱい。:2007/06/30(土) 00:23:47 ID:k4q9GB5E0
そもそも学問板に人がいないってのが大きい原因


受験板→大生板(学部・研究板)→就職板
     |
     →理系板

圧倒的に上の流れだからな
情報学となると受験板の理系の中の情報系に進んだ人間の
さらにその中の一部になる
これで伸びるほうが異常と思うがw

まぁ少数でまたーりしようぜ

7 :名無しさん@お腹いっぱい。:2007/06/30(土) 01:25:24 ID:0+pQp91g0
アルゴリズム:wikipedia
http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

8 :名無しさん@お腹いっぱい。:2007/06/30(土) 09:34:50 ID:lcZrO20+0
>>7のWikiにツッコミ入れるもよし。
アルゴリズムが分野としてどんなに面白いかをこのスレに書くもよし。
専門家や専攻してる人の話を聞きたい。

9 :名無しさん@お腹いっぱい。:2007/06/30(土) 11:30:33 ID:jmZIA/GJ0
>>7 の「代表的なアルゴリズム」のリスト、
アルゴリズムとアルゴリズムで使われる技法がごっちゃになってるよね。

10 :名無しさん@お腹いっぱい。:2007/06/30(土) 20:29:42 ID:X65lkqHoO
非決定性アルゴリズムってどーゆーのなの?

11 :名無しさん@お腹いっぱい。:2007/07/01(日) 02:52:49 ID:+krnBKtF0
ランダムな要素があるアルゴリズムじゃないの?

12 :名無しさん@お腹いっぱい。:2007/07/01(日) 23:14:50 ID:VdFqOVvW0
>>9
言われてみれば、確かにごっちゃだね。

http://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E5%8F%AF%E8%83%BD%E9%96%A2%E6%95%B0
このページの“チャーチ=チューリングのテーゼ”の説明ってどうなのかな。
形式的に表現できないのが理由で、証明できない。で、証拠があれなの?

13 :名無しさん@お腹いっぱい。:2007/07/01(日) 23:41:18 ID:AB+UsW810
これでもここ2番目に勢いあるスレなんだなw

14 :名無しさん@お腹いっぱい。:2007/07/02(月) 02:44:40 ID:GxvgocZB0
アルゴリズムをアルゴリズムで導き出す研究ってアル?

15 :名無しさん@お腹いっぱい。:2007/07/02(月) 11:57:28 ID:RmquBilg0
>>12
その説明何が言いたいのかよく分からないな
こっちのは正しそうだけど
http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A3%E3%83%BC%E3%83%81%EF%BC%9D%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%81%AE%E3%83%86%E3%83%BC%E3%82%BC

ところでその項の形式言語のところにある「計算可枚挙」って用語初めて見た

16 :名無しさん@お腹いっぱい。:2007/07/03(火) 01:44:12 ID:K2rwOb3v0
>>15
>>12のページを改めて頭から読んでいたが、内容がよくわからないな。
計算可枚挙っていうのは、俺の知る単語では帰納的枚挙可能とか、そのあたりかな。
この文脈でcomputableとrecursiveは区別するものなのかな?

17 :名無しさん@お腹いっぱい。:2007/07/03(火) 11:04:40 ID:qUkoJsPE0
もしやと思って英語版見てみた
http://en.wikipedia.org/wiki/Computable_function
>>12 のってこれと同じじゃん (誤訳が目に付くが)

18 :名無しさん@お腹いっぱい。:2007/07/04(水) 01:05:08 ID:fDG8C8I20
>>17
うん。編集履歴を見たら一人で一度にあれだけの量を投稿したようだしね。
実際のところ、著作権的にまずいかもしれないな。

19 :名無しさん@お腹いっぱい。:2007/07/06(金) 21:34:27 ID:yhvhoo730
何故か計算理論のスレになっている件について。
いや、まぁ、いいんだけどね。

20 :|∀゚) ◆NSTiYTv7k6 :2007/07/11(水) 12:18:13 ID:JEyLTG94O
>>11
束の列車ダイヤのようなものか。

21 :ぶざまなコン ピュータ:2007/07/12(木) 15:25:51 ID:34y7ohIfO
コンピューターに支配された電子政府。意外と間抜け。

22 :書き込みでブラウザ:2007/07/12(木) 19:54:27 ID:34y7ohIfO
コンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしい

23 :量子すげー:2007/07/13(金) 01:54:57 ID:ceCDdmCa0
量子コンピュータは全てのアルゴリズムの基本である。信じろ。
量子コンピュータは全てのアルゴリズムの基本である。信じろ。
量子コンピュータは全てのアルゴリズムの基本である。信じろ。
量子コンピュータは全てのアルゴリズムの基本である。信じろ。
量子コンピュータは全てのアルゴリズムの基本である。信じろ。
量子コンピュータは全てのアルゴリズムの基本である。信じろ。
量子コンピュータは全てのアルゴリズムの基本である。信じろ。


24 :名無しさん@お腹いっぱい。:2007/07/16(月) 10:21:59 ID:a/s9o2Yo0
>>10
お前が道に迷ってしまったとする。
目の前に分かれ道があるが、どちらに行けばいいかわからない。
そんなときに、お前が分裂して、両方の道を辿ることができればいいと思うだろ?
そういうことができるのが、非決定性アルゴリズムだよ。

25 :名無しさん@お腹いっぱい。:2007/07/17(火) 13:55:45 ID:uOu2k0Ia0
両方に行くんじゃなくて、答えのあるほうの道に、まるで答を知っているかのように行くんだと思う
チューリングマシンのテープヘッドは1個しかなくても、非決定性的に振舞うわけじゃん

26 :名無しさん@お腹いっぱい。:2007/07/18(水) 10:43:38 ID:wUgf/QeB0
最終的にはそういう印象だろうけれども
計算途中は状態に両方の情報を含ませたような感じだからね〜

やっぱあれは不思議なものという気がする

27 :名無しさん@お腹いっぱい。:2007/07/19(木) 03:58:47 ID:oU4nSUEl0
セジウィックの本まとめ買いしました。

28 :名無しさん@お腹いっぱい。:2007/07/19(木) 05:50:20 ID:hQUgGZX20
>>26
いやーどうかなぁ?
複数のチョイスから道を選ぶのに、正しい道を選ぶための
情報がその時点であるなら、それを使って決定性的に進め
ばいいじゃない
情報がなくても正しい道を選び、後になって本当に正しい道
だったら「ああ、やっぱり当ってたw」ってことにしていいんだ
よ、非決定性ってのは

実際に非決定性アルゴリズムを記述する場合にも、あるス
テップで無条件に「この選択肢を選ぶ」って感じでやって、
最終的な段階で検証されればおkでしょ
何しろNTMは正しい道のりが存在しさえすれば受理するって
いう定義なわけだから

29 :名無しさん@お腹いっぱい。:2007/07/19(木) 14:03:36 ID:iEwrqyqk0
つーか、あれだろ
光の経路はあたかも光子が最短距離を判ってるかのように決まる。

30 :名無しさん@お腹いっぱい。:2007/07/21(土) 13:56:00 ID:M+gwqjrl0
>>18
GFDLの要件は満たしてるよ?

31 :名無しさん@お腹いっぱい。:2007/07/22(日) 00:29:35 ID:9MdIsUjZ0
>>30
あ、そうなの? じゃあ問題ないな。
Wikipediaの他言語から翻訳した場合、注釈を入れないといけないと思いこんでた。


32 :名無しさん@お腹いっぱい。:2007/08/04(土) 11:54:31 ID:3/VT65570
n個のボール、k個の横に並べた箱がある。
n=3、 k=4 (A,B,C,D) とするとき、各箱にボールを入れるパターンを考える。
この場合、組合せの総数は 20 となるが、左右対称となるパターン( A=D、B=C ) を
除く条件もある場合、全パターンは以下のような 10 パターンになる。
n、k が任意の値であるとき、同様に全パターンを生成するアルゴリズムはどのようになるか?

  A     B     C    D
○○○ |     |     |     
○○   | ○   .|     | 
○○   |    . |  ○  | 
○○   |   .  |     | ○
○    | ○○ .|     |
○    | ○   .|  ○  | 
○    | ○   .|     | ○ 
○    |     .| ○○ |
      | ○○○ |     |   
      | ○○  | ○   |

補足: ↑の10パターンは例であり、左右対称となるパターンのいずれかが生成できれば良い。
対称パターン例:  以下の (1) と (2) はどちらでも良く、等価な1パターンとみなす

(1)
  A     B     C    D
○○○ |     |     |     

(2)
  A     B     C    D
      |     .|     | ○○○

33 :名無しさん@お腹いっぱい。:2007/08/05(日) 16:19:00 ID:giDJf1ge0
>>32
効率は全然考えてないけど、こんな感じでどうでしょ?
(全角スペースでインデントしてある)
#include <stdio.h>
int comb(int n, int k); // 対称性を考慮しない組み合わせ
int sym(int n, int k); // 対称になりえる形の組み合わせ
int f(int n, int k); // 対称になるものを差し引いた組み合わせ
int main() {
 printf("%d\n", f(3, 4));
 return 0;
}
int comb(int n, int k) {
 int ret = 0;
 if (n <= 0) return 1;
 for (; k > 0; k--) ret += comb(n - 1, k);
 return ret;
}

34 :33:2007/08/05(日) 16:19:53 ID:giDJf1ge0
(続き)
int sym(int n, int k) {
 if (k % 2 == 0) { // 箱の数が偶数なので、ボールが偶数の場合のみ
  return n % 2 == 0 ? comb(n / 2, k / 2) : 0;
 } else { // ど真ん中の箱にいくつかずつ入れて対称形を数える
  int ret = 0;
  for (k /= 2; k > 0; k --) ret += comb(n / 2, k);
  return ret = 0;
 }
}
int f(int n, int k) {
 int s = sym(n, k);
 return (comb(n, k) - s) / 2 + s;
}

35 :33:2007/08/05(日) 16:26:13 ID:giDJf1ge0
ちょっと勘違いにつき訂正orz
int f(int n, int k) {
 return comb(n, k) - s / 2;
}

36 :名無しさん@お腹いっぱい。:2007/08/05(日) 17:32:35 ID:bhstdXyN0
nlogn=O(log(n!))だれか解いてくれ・・・
院試にでそうなんだ・・・

37 :名無しさん@お腹いっぱい。:2007/08/05(日) 18:16:05 ID:giDJf1ge0
Starlingの公式で n! ≒ ((n/e)^n)*sqrt(2πn) を使うと、
log(n!) = log(((n/e)^n)*sqrt(2πn))
= n(log n - log e) + (1/2)*log(2πn)
= n(log n - 1) + (1/2)log n + (1/2)log(2π)
で、一番オーダーが大きいのがn log nだから
O(log(n!)) = O(n log n)
って感じじゃないかと

38 :名無しさん@お腹いっぱい。:2007/08/05(日) 18:26:18 ID:giDJf1ge0
あーいかん、寝ぼけまくってた・・・
>>35
int f(int n, int k) {
 return comb(n, k) - sym(n, k);
}
あと、>>37はlogの底は普通2だろうから、log eは1じゃないわな
まあどっちみちこの部分は定数だから、結果は変わらないけど

39 :名無しさん@お腹いっぱい。:2007/08/05(日) 18:56:06 ID:giDJf1ge0
何度もすいません。
やっぱり最初の>>34でよかったです。
>>35-以降の訂正は全部間違いでした。
sym関数が返すのは、左右対称なものの数です。

40 :36:2007/08/05(日) 19:00:42 ID:bhstdXyN0
>>37
thx
スマン、確かに抑えられそうなのはわかったんだが、
近似を使わないで解ける方法って何かあるかな?

41 :名無しさん@お腹いっぱい。:2007/08/05(日) 21:05:30 ID:M5RdB5fn0
log(n!) = Σlog(k) ≒ ∫log(x)dx = n(log(n)-1)
で ≒ のところをもうちょっとちゃんと書く

42 :名無しさん@お腹いっぱい。:2007/08/05(日) 21:21:45 ID:M5RdB5fn0
と思いつきで書いたがわりと面倒だった
たぶん
log(n!) = nlog(n) + ΣE(k)
E(k) = log [e*(1+1/(k-1))^{k-1}]
みたいな形になってうまくいくと思うんだが。

43 :名無しさん@お腹いっぱい。:2007/08/07(火) 01:01:50 ID:CT4CapCa0
スマン返信遅れた
そこら辺やって、教授に聞いてみる
thx

44 :名無しさん@お腹いっぱい。:2007/08/07(火) 19:03:33 ID:urZfTI0r0
幼稚なハナクソたぬき憑きのバカが
恐れ多くも神様気取りは止めといた方が
身の為ってもんだぜ。

教訓垂れといてやるよ。
バカなたぬき憑きの為に。w

45 :名無しさん@お腹いっぱい。:2007/08/07(火) 23:31:56 ID:LDwqJa120
データの個数がN個でそれを2分探索で探索するときの平均比較回数が|log2N|回
となっているのですがそれはなぜでしょう?

46 :名無しさん@お腹いっぱい。:2007/08/07(火) 23:46:27 ID:RxMUNbYN0
>>45
log2Nは最悪の場合じゃないのか?

47 :名無しさん@お腹いっぱい。:2007/08/08(水) 14:59:13 ID:dQrLvuND0
>>46
最大比較回数は[log2N]+1となっています。

48 :名無しさん@お腹いっぱい。:2007/08/08(水) 15:18:53 ID:8BcfQbnV0
データがN個あって、
1回目の比較でぶちあたるデータは1個
2回目の比較でぶちあたるデータは2個
3回目の比較でぶちあたるデータは4個
・・・
で 1 + 2 + 4 +... が N になるまで考えたら、
データにぶちあたるまでの平均回数が出るだろ

49 :名無しさん@お腹いっぱい。:2007/08/08(水) 15:47:12 ID:dQrLvuND0
回答ありがとうございます。
ということは最大比較回数をx回として、1回目で見つかる確率は1/N,2回目は2/N,3回目は4/N...だから、
比較回数の期待値を求めて、
1*1/N+2*2/N+3*4/N+...+x*N/Nがlog2Nと一緒になるってことですか?

50 :名無しさん@お腹いっぱい。:2007/08/08(水) 21:49:10 ID:S1OTVNYC0
計算して一緒になるかどうかを確認するのがよいかと。

51 :名無しさん@お腹いっぱい。:2007/08/08(水) 23:01:11 ID:dQrLvuND0
計算してみました。データが8件の場合、log2 8(2が底)で平均比較回数は3回になるはずです。
1回目で見つかる確率は1/8で、2回目は2/8で、3回目は4/8で、4回目は1になると思います。
それで比較回数の期待値を求めると
1*1/8+2*2/8+3*4/8+4*1=49/8で3回にはなりませんでした。
考え方おかしいですか?

52 :名無しさん@お腹いっぱい。:2007/08/08(水) 23:25:42 ID:AqCR71uD0
一回目で見つかる確率と二回目で見つかる確率と三回目で見つかる確率と四回目で見つかる確率を足すと?

53 :名無しさん@お腹いっぱい。:2007/08/08(水) 23:31:35 ID:dQrLvuND0
全部足すと25/8でだいたい3になりました。これでいいんですか?

54 :名無しさん@お腹いっぱい。:2007/08/09(木) 00:33:33 ID:8+UGpn6A0
データが8個しかないのになんで4回目で「はじめて」みつかる確率が「1」なんだよ。
1回目: 1個
2回目: 2個
3回目: 4個
4回目: 残りの1個
合計: 8個

あと、平均は正確にはlog2(N)じゃなくて、log2(N+1)な。
N=7, 15, 31 で考えた方がわかりやすい。
Nがでかいときは+1なんて誤差だがな。

55 :名無しさん@お腹いっぱい。:2007/08/09(木) 15:25:24 ID:HIXLZk0S0
45です。いままで回答してくださったみなさんありがとうございました。
データが8個の場合、1回目で見つかる個数は1個で2回目は2個3回目は4個、
4回目は1個なので、比較回数の平均は(1*1+2*2+3*4+4*1)/8ということだったのですね。
ありがとうございました。

56 :名無しさん@お腹いっぱい。:2007/08/11(土) 15:41:33 ID:R5esghQd0
8kしかROMの無いマイコンに、半分くらいまでは使って良いので
暗号とかに使えるような強力な乱数生成関数を実装したい。

どれがベストですか?

57 :名無しさん@お腹いっぱい。:2007/08/31(金) 08:07:48 ID:od6nOfjL0
http://jp.youtube.com/watch?v=YuNIgXfErpY

58 :名無しさん@お腹いっぱい。:2008/02/02(土) 12:50:28 ID:Xi6rKQooO
初歩な質問で申し訳ないですが、「ある問題Pを解くアルゴリズムA」って何ですか?

59 :名無しさん@お腹いっぱい。:2008/02/05(火) 00:08:36 ID:CbPUSWGQ0
言葉そのままだと思うけど?

60 :名無しさん@お腹いっぱい。:2008/02/05(火) 11:09:33 ID:ToXuPv7e0
問題とは、自然数の集合
P を解くアルゴリズムとは、入力が P の要素であるかどうかを判定するチューリングマシン

とかいう定義があったような

61 :名無しさん@お腹いっぱい。:2008/02/05(火) 11:52:11 ID:xALL6pLG0
>>58
抽象的には文字通りの意味

具体的な意味を持たせるには、『問題P』、『解く』、『アルゴリズムA』、少なくともこの3つを定式化しないと意味を成さない。

例えば、
問題P = 合成数全体の集合
解く   = 与えられた合成数の素因数分解を出力する
アルゴリズムA = チューリングマシンA
とか、

問題P = 合成数全体の集合
解く   = 与えられた合成数が合成数か否かを判定する
アルゴリズムA = 論理回路A
とか

>>60
問題は、自然数の部分集合な
その書き方だと自然数全体に見える

62 :名無しさん@お腹いっぱい。:2008/02/05(火) 19:01:42 ID:JYth14xy0
>>60
おいおい・・・頭だいじょうぶか?

63 :60:2008/02/05(火) 22:23:11 ID:bWkSitqj0
>>61
フォローどうも。
一応そのつもりだったんだけど、紛らわしかったね。

64 :名無しさん@お腹いっぱい。:2008/02/06(水) 23:24:16 ID:m3Y1WBZg0
自然数の部分集合という言葉にも少し違和感を感じる

65 :名無しさん@お腹いっぱい。:2008/02/06(水) 23:46:56 ID:vC9JuQk10
もっと正確には「自然数全体の集合の部分集合」だが、ちょっとくどいな
英語なら冠詞で区別できるのだが

66 :名無しさん@お腹いっぱい。:2008/02/13(水) 21:55:07 ID:T4OM1rSMO
20世紀中に20個の名アルゴリズムが生まれた、という話を聞いたんですが、
その内訳は何かご存知ありませんか?

ちなみにひとつは高速フーリエ変換らしいんですが……

67 :名無しさん@お腹いっぱい。:2008/02/14(木) 01:17:51 ID:iD68NpKbO
>>66
関係ありそうなページをみつけた。
http://d.hatena.ne.jp/nikutaiha/20071207/1197346891
http://demonfox.spaces.live.com/blog/cns!157C572C0C367802!563.entry
20世紀のアルゴリズムBEST10はこれだ…!?
(モンテカルロとクイックソートもランクインしてます〜)

68 :名無しさん@お腹いっぱい。:2008/04/25(金) 12:44:31 ID:I7ZBq39M0
演習問題でわからん問題があるんですけど

反射濃度が0.3の記録物の上に透過濃度0.7のフィルタを置いた場合は、入射光の何分の一が反射されてくるか?

また反射濃度の幾らの記録物と等価か?

ただし入射光はフィルタの表面では反射されないものとする

またlog10 5=0.7 log10 2=0.3とする


正直授業聞いてたけどイミフなんで誰か教えてください

69 :名無しさん@お腹いっぱい。:2008/04/25(金) 13:23:23 ID:Q9BQmSr50
なんの科目だ?
なぜこの板のこのスレへ?

70 :名無しさん@お腹いっぱい。:2008/05/19(月) 13:11:19 ID:FoL74xhU0
アルゴリズムを探しています(私の頭では解けないので^^;)。
よろしくお願いします。

大きな矩形の布地から、サイズの違う小さな矩形の布地を切り取る時、
余りの布面積が一番少なくなるように、
切り取る(小さな矩形を並べる)アルゴリズムについて
書かれた書籍、HP等をご存知でしたら、教えて下さい。



71 :名無しさん@お腹いっぱい。:2008/05/20(火) 19:11:54 ID:z2aVOCiI0
これは、難しいですね・・・

72 :名無しさん@お腹いっぱい。:2008/05/22(木) 01:01:19 ID:WRHa9+uN0
「詰込み問題 長方形」でググれ

73 :名無しさん@お腹いっぱい。:2008/05/24(土) 07:29:03 ID:YxYU8Xle0
セジウィック著のアルゴリズムCの巻末問題の解答って存在するんですか?

74 :名無しさん@お腹いっぱい。:2008/06/17(火) 22:33:47 ID:WQ/s0sBE0
逐次決定法でソートをするアルゴリズムを
アクティビティ図で書け言われたんだけど
もうさっぱり、たすけて

75 :名無しさん@お腹いっぱい。:2008/06/17(火) 23:15:01 ID:8Z04S48L0
>>74
バブルソート、挿入ソートとかをアクティビティ図で書けばいいだけじゃないの?

76 :名無しさん@お腹いっぱい。:2008/06/17(火) 23:22:49 ID:WQ/s0sBE0
>>75
降順にソートしろって言われたんだけど
先頭の要素と入れ替えるべき要素をピンポイントで入れ替える方法が思いつかないの
先頭の数より大きな要素を一個ずつ入れ替えて降順に並び替える
図を書いたら、それ逐次決定法ちがうがな、といわれちゃった

77 :名無しさん@お腹いっぱい。:2008/06/30(月) 21:52:38 ID:gbr9nqqq0
ある機械言語で表現された計算を、別の機械言語での計算表現に変換するアルゴリズムってないの?
移植作業を人間がやるのは馬鹿げてると常々思っているんだが。

78 :名無しさん@お腹いっぱい。:2008/07/01(火) 00:30:21 ID:A76wBxs00
>> 77
おまえはエミュレータを知らんのか。
ほかのCPUのコード動かすエミュレータなど腐るほどあるだろ。

79 :名無しさん@お腹いっぱい。:2008/07/01(火) 10:32:08 ID:XZej7N2a0
エミュレータだとインタプリタっぽいけど、むしろコンパイラ方式というか。
無くはない。けど、一般に実用になるものを作るのは非常に難しい。

理論的には、機械についての記述を元に自動的にトランスレータを作れるかも
しれないけど、それをやった例で広く知られてるものはないんじゃないかな。

80 :名無しさん@お腹いっぱい。:2008/07/07(月) 18:26:46 ID:LaGpnrS20
アルゴリズムの教科書を見ていて思ったけど、
ソートのアルゴリズムって何で載ってるの?
学習用なの?

81 :名無しさん@お腹いっぱい。:2008/07/08(火) 00:13:28 ID:dvhcxiA60
ソートが不必要だと思う理由を挙げてみろや

82 :名無しさん@お腹いっぱい。:2008/07/08(火) 02:07:14 ID:9PXGNCb20
すいません質問です。

「n個の節点をもつ異なる二分木の個数をb(n)で表す。 n≧1に対して、
b(n)= Σ[k=0〜n-1]{b(k)b(n-1-k)}
であることを示せ。ただし、b(0)=1である。」

という問題があるのですが、対処の仕方がイマイチ…
漸化式を使うのかと思ったのですが、n=n-1のときの処理から答えに導けなくて…
方針が間違っているんでしょうか?

83 :名無しさん@お腹いっぱい。:2008/07/08(火) 03:53:29 ID:h0oJaPmR0
右辺の意味を考えるヨロシ

84 :名無しさん@お腹いっぱい。:2008/07/08(火) 22:23:56 ID:0I3Vc38E0
>>83
無事どうにかなりました、ありがとうございます。

85 :名無しさん@お腹いっぱい。:2008/07/14(月) 07:21:56 ID:vmXwhyYE0
>>80がいいたいのが「ソートはライブラリがあるから勉強不要」だと笑うよな。

86 :名無しさん@お腹いっぱい。:2008/07/25(金) 21:04:46 ID:esVK58XZ0
スレ違いかもしれんが、どっか都内の大学で社会人でも潜り込めて
最近のアルゴリズム関連の勉強ができるとこってない?

俺が大学でてから、ロックフリーアルゴリズムとか全順序マルチキャストとか、
主に分散処理関係のアルゴリズムの進展があったみたいだけど、
そういうのまとめて勉強しなおしたいんだけど。

聴講生でも授業に潜り込むだけでも研究生でも形式は問わないので、
どっか良さげなとこあったら教えて



87 :名無しさん@お腹いっぱい。:2008/07/26(土) 07:56:08 ID:tJ9ec/uX0
サイバー大学、放送大学、その他さがせばいくらでもある。

88 :名無しさん@お腹いっぱい。:2008/07/26(土) 10:56:26 ID:fDyXyvh40
>>86
東京大学の大学院に研究生として潜り込んだら?
単純にその内容を勉強したい、というだけであれば最高の場所だと思う。

ttp://www.i.u-tokyo.ac.jp/edu/inter_ex/oir/faq.shtml

89 :88:2008/07/26(土) 10:58:23 ID:fDyXyvh40
スマソ

こっちだった。
ttp://www.i.u-tokyo.ac.jp/edu/exam/guide.shtml

90 :教えて下さい:2008/08/20(水) 18:55:17 ID:LA648EyNO
ネットワーク理論のアルゴリズムのSuurballeって何て読めばいいのでしょう?
サーバル?スルベイユ?


91 :名無しさん@お腹いっぱい。:2008/08/20(水) 18:59:51 ID:YX9JNVC+0
スアバレ

92 :名無しさん@お腹いっぱい。:2008/08/21(木) 00:05:59 ID:EeZ9dndNO
ありがと

93 :名無しさん@お腹いっぱい。:2008/10/16(木) 07:41:16 ID:ylu/5reN0
アルゴリズムデザイン
http://www.amazon.co.jp/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%83%87%E3%82%B6%E3%82%A4%E3%83%B3-Jon-Kleinberg/dp/4320122178/ref=pd_sim_b_4

この本どうですか?もし読んだ方いれば感想聞かせてください

94 :名無しさん@お腹いっぱい。:2008/10/21(火) 02:18:26 ID:KX3X7UCv0
かなりいい本。
そのかわり、前提となる知識は多いので、オーソドックスなアルゴリズム本や、計算論の本を読んでからの方が読みやすい。

95 :名無しさん@お腹いっぱい。:2008/11/14(金) 21:37:50 ID:Hvo1Ldur0
スレチかもしれませんが、どのスレで聞けば良いかわからなかったので質問させてください!
ユークリッド互除法の最悪計算量をLameの定理の結果を用いずに解析せよという問題なのですが、答えていただけないでしょうか?よろしくお願いします。

96 :名無しさん@お腹いっぱい。:2009/02/25(水) 06:15:10 ID:OR+1nEj9O
初学者におすすめの参考書を教えて下さい。

97 :名無しさん@お腹いっぱい。:2009/02/25(水) 12:07:21 ID:YSUjTFta0
言語なにやってるの?
多少よみごたえがあっていいなら、「JavaScriptによるアルゴリズムデザイン」かな。
☆ひとつなのは、評者がよくわかってないと思われる。
値段のわりに内容の濃い本。
http://www.amazon.co.jp/dp/4563015695

98 :名無しさん@お腹いっぱい。:2009/02/25(水) 15:47:46 ID:OR+1nEj9O
言語はJavaをやっています。
お薦めいただいた本ですら理解できないかもしれません。
そもそも計算論がよくわからないので、そこから始めるべきですかね…

それにしてもこのレビュー酷いですねww

99 :名無しさん@お腹いっぱい。:2009/02/26(木) 02:38:07 ID:whWnfZFR0
ソートやリストをやったことないなら、「Javaによるアルゴリズム入門」とか、そのあたりをまずは。

100 :名無しさん@お腹いっぱい。:2009/02/26(木) 07:33:16 ID:Gy5/UGPWO
わかりました。
探して見てみますね。

親切にどうもありがとうございました。

101 :名無しさん@お腹いっぱい。:2009/02/27(金) 20:35:34 ID:lt68HUb10
http://www.yfcbookshelf.com/algorithms.htm
>日本では、いまだにAho,Ullmanの著書が主流とされているが、
>理論的に欠陥があり書き換えが必要なのでCormenのものをお勧めする。

ってあるけどデータ構造とアルゴリズム (情報処理シリーズ)のことを言ってるのか
アルゴリズムの設計と解析 1,2 のことを言ってるのかがわからないんだけど
どっちの本のことを言ってるの?

102 :名無しさん@お腹いっぱい。:2009/02/28(土) 09:33:59 ID:4jF8e4m00
「データ構造とアルゴリズム」はそのあとのほうで紹介してるから
設計と解析のほうのことと思われ。

103 :名無しさん@お腹いっぱい。:2009/02/28(土) 09:55:11 ID:pTWHo9Cm0
情報シリーズのほうって品切れになってるね。

104 :名無しさん@お腹いっぱい。:2009/03/05(木) 01:14:53 ID:rKTNFc+b0
ある日のこと、stl::list<自前クラス>.sort()がうまく動かない。
実は、自前クラス.operator<()は半順序関係になっていて、比較不能なときは
偽を返す仕様になっていた。そこで、stl::list.sort()はやめて、
自前のバブルソート()を利用。そしたら、うまくソートできました。
stl::list<T>.sort()は確か、クイックソートだった記憶があるのですが、
今更ながらバブルソートの利点を発見しました。O(n^2)も得する時があるんですね。


105 :名無しさん@お腹いっぱい。:2009/03/05(木) 03:45:03 ID:f4LLFY4q0
>>100
もう見てないだろうけど、「Javaデータ構造とアルゴリズム基礎講座」という最近でた本がすごくよかった。
おすすめ。

106 :名無しさん@お腹いっぱい。:2009/03/09(月) 21:34:20 ID:aR4hh/Qk0
>>104
比較不能なものをどうソートしたかったのか分からんが
stable_sort で何とかなる可能性もあった。

107 :名無しさん@お腹いっぱい。:2009/03/10(火) 08:15:47 ID:ynW76ILy0
see man tsort って昔の人は言っていた.

108 :名無しさん@お腹いっぱい。:2009/03/11(水) 17:40:57 ID:qHJTUD6E0
>>105
どの辺に感銘受けたの?

109 :104:2009/03/12(木) 00:39:11 ID:aXqonKtq0
>>107
THX!
実は、自前クラス::operator<()というのは、DAGにおけるパスの存在検査で、
要はやりたかった事はトポロジカルソートそのものでした。勉強になりました。


110 :名無しさん@お腹いっぱい。:2009/03/12(木) 03:19:23 ID:dY1jUPo+0
>>108
よくある、アルゴリズムカタログをアルゴリズム入門と銘打ってるような本ではなくて、アルゴリズム自体を勉強するための入門書。
そして、薄くてよみやすい。
ただし、そういう性質なので載ってるアルゴリズムの種類は少ないし、これで終わり?という物足りなさもある。
必要最低限の用語や考え方がまとめられてて、初学者の最初の足がかりとしておすすめ。

111 :名無しさん@お腹いっぱい。:2009/03/13(金) 11:02:16 ID:1wbuOepQ0
>>110
なるほど。
会社で新人教育用の教科書に使ってみようかな。
ありがとう。

112 :名無しさん@お腹いっぱい。:2009/03/16(月) 18:44:48 ID:iK0FXkDCO
>>102
オヤスミ…
  <⌒/ヽ-、___
/<_/____/
 ̄ ̄ ̄ ̄ ̄ ̄ ̄


113 :名無しさん@お腹いっぱい。:2009/03/17(火) 04:59:37 ID:wDgO+BWP0
>>111
教えるときには、「アルゴリズムデザイン」を本屋で立ち読みしてみて、発展させるとどうなるかイメージしておくといいと思う。

114 :名無しさん@お腹いっぱい。:2009/03/18(水) 15:16:49 ID:kwXLXzlv0
>>106
stable_sortも厳密な弱い順序 (strict weak ordering) を要求するからだめだと思う。

115 :名無しさん@お腹いっぱい。:2009/03/18(水) 23:46:40 ID:1KxdpUB20
8桁の数字があって下1桁がチェックディジットなのですが、
多数の標本があれば、
どのように算出されたチェックディジットかを判別することって可能なのでしょうか?

116 :名無しさん@お腹いっぱい。:2009/03/19(木) 01:49:55 ID:iau6idhT0
一般的にいうのであれば「どのように算出されたチェックディジットか」は判別できない。
けど、再現はできる可能性が高い。
8桁の数字なら、1億の標本があれば、どのように算出されたチェックディジットかを判別せずに再現できる。

117 :名無しさん@お腹いっぱい。:2009/03/23(月) 00:37:42 ID:XM1ttkXDO
>>112
 Z
  z
  z
 <⌒/ヽ-、___
/<_/____/
 ̄ ̄ ̄ ̄ ̄ ̄ ̄


118 :名無しさん@お腹いっぱい。:2010/06/30(水) 04:16:20 ID:YLTEwEUP0
少し聞きたいのだけど
同値類の効率化の話を解説するろきに
log*やAckerman関数をどのように使えばいいのだろうか。

31 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)