アルゴリズム　Algorithm

アルゴリズム全般の話題はここでやれ!

このスレは伸びない。

この板にあるスレはみんな伸びない。

勢いトップが３．９だぜｗｗｗｗ
どんだけｗｗｗｗ

おいおい、何で伸びないんだ
情報学の根幹は論理とアルゴリズムだろ

そもそも学問板に人がいないってのが大きい原因


受験板→大生板（学部・研究板）→就職板
　　　　 ｜
　　　　　→理系板

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

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

アルゴリズム：wikipedia
http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

>>7のWikiにツッコミ入れるもよし。
アルゴリズムが分野としてどんなに面白いかをこのスレに書くもよし。
専門家や専攻してる人の話を聞きたい。

>>7 の「代表的なアルゴリズム」のリスト、
アルゴリズムとアルゴリズムで使われる技法がごっちゃになってるよね。

非決定性アルゴリズムってどーゆーのなの？

ランダムな要素があるアルゴリズムじゃないの？

>>9
言われてみれば、確かにごっちゃだね。

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

これでもここ２番目に勢いあるスレなんだなｗ

アルゴリズムをアルゴリズムで導き出す研究ってアル？

>>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

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

>>15
>>12のページを改めて頭から読んでいたが、内容がよくわからないな。
計算可枚挙っていうのは、俺の知る単語では帰納的枚挙可能とか、そのあたりかな。
この文脈でcomputableとrecursiveは区別するものなのかな？

もしやと思って英語版見てみた
http://en.wikipedia.org/wiki/Computable_function
>>12 のってこれと同じじゃん (誤訳が目に付くが)

>>17
うん。編集履歴を見たら一人で一度にあれだけの量を投稿したようだしね。
実際のところ、著作権的にまずいかもしれないな。

何故か計算理論のスレになっている件について。
いや、まぁ、いいんだけどね。

>>11
束の列車ダイヤのようなものか。

コンピューターに支配された電子政府。意外と間抜け。

コンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしい

量子コンピュータは全てのアルゴリズムの基本である。信じろ。
量子コンピュータは全てのアルゴリズムの基本である。信じろ。
量子コンピュータは全てのアルゴリズムの基本である。信じろ。
量子コンピュータは全てのアルゴリズムの基本である。信じろ。
量子コンピュータは全てのアルゴリズムの基本である。信じろ。
量子コンピュータは全てのアルゴリズムの基本である。信じろ。
量子コンピュータは全てのアルゴリズムの基本である。信じろ。

>>10
お前が道に迷ってしまったとする。
目の前に分かれ道があるが、どちらに行けばいいかわからない。
そんなときに、お前が分裂して、両方の道を辿ることができればいいと思うだろ？
そういうことができるのが、非決定性アルゴリズムだよ。

両方に行くんじゃなくて、答えのあるほうの道に、まるで答を知っているかのように行くんだと思う
チューリングマシンのテープヘッドは１個しかなくても、非決定性的に振舞うわけじゃん

最終的にはそういう印象だろうけれども
計算途中は状態に両方の情報を含ませたような感じだからね〜

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

セジウィックの本まとめ買いしました。

>>26
いやーどうかなぁ？
複数のチョイスから道を選ぶのに、正しい道を選ぶための
情報がその時点であるなら、それを使って決定性的に進め
ばいいじゃない
情報がなくても正しい道を選び、後になって本当に正しい道
だったら「ああ、やっぱり当ってたｗ」ってことにしていいんだ
よ、非決定性ってのは

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

つーか、あれだろ
光の経路はあたかも光子が最短距離を判ってるかのように決まる。

>>18
GFDLの要件は満たしてるよ?

>>30
あ、そうなの？ じゃあ問題ないな。
Wikipediaの他言語から翻訳した場合、注釈を入れないといけないと思いこんでた。

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
　　　　 　|　　　　　.|　　　　　| ○○○

>>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;
}

（続き）
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;
}

ちょっと勘違いにつき訂正orz
int f(int n, int k) {
　return comb(n, k) - s / 2;
}

nlogn=O(log(n!))だれか解いてくれ・・・
院試にでそうなんだ・・・

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)
って感じじゃないかと

あーいかん、寝ぼけまくってた・・・
>>35は
int f(int n, int k) {
　return comb(n, k) - sym(n, k);
}
あと、>>37はlogの底は普通2だろうから、log eは1じゃないわな
まあどっちみちこの部分は定数だから、結果は変わらないけど

何度もすいません。
やっぱり最初の>>34でよかったです。
>>35-以降の訂正は全部間違いでした。
sym関数が返すのは、左右対称なものの数です。

>>37
ｔｈｘ
スマン、確かに抑えられそうなのはわかったんだが、
近似を使わないで解ける方法って何かあるかな？

log(n!) = Σlog(k) ≒ ∫log(x)dx = n(log(n)-1)
で ≒ のところをもうちょっとちゃんと書く

と思いつきで書いたがわりと面倒だった
たぶん
log(n!) = nlog(n) + ΣE(k)
E(k) = log [e*(1+1/(k-1))^{k-1}]
みたいな形になってうまくいくと思うんだが。

スマン返信遅れた
そこら辺やって、教授に聞いてみる
ｔｈｘ

幼稚なハナクソたぬき憑きのバカが
恐れ多くも神様気取りは止めといた方が
身の為ってもんだぜ。

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

データの個数がN個でそれを２分探索で探索するときの平均比較回数が|log2N|回
となっているのですがそれはなぜでしょう？

>>45
log2Nは最悪の場合じゃないのか？

>>46
最大比較回数は[log2N]+1となっています。

データがN個あって、
1回目の比較でぶちあたるデータは1個
2回目の比較でぶちあたるデータは2個
3回目の比較でぶちあたるデータは4個
・・・
で 1 + 2 + 4 +... が N になるまで考えたら、
データにぶちあたるまでの平均回数が出るだろ

回答ありがとうございます。
ということは最大比較回数をx回として、１回目で見つかる確率は1/N,2回目は2/N,３回目は4/N...だから、
比較回数の期待値を求めて、
1*1/N+2*2/N+3*4/N+...+x*N/Nがlog2Nと一緒になるってことですか？

計算して一緒になるかどうかを確認するのがよいかと。

計算してみました。データが８件の場合、log2 8(2が底)で平均比較回数は３回になるはずです。
１回目で見つかる確率は1/8で、２回目は2/8で、３回目は4/8で、４回目は1になると思います。
それで比較回数の期待値を求めると
1*1/8+2*2/8+3*4/8+4*1=49/8で３回にはなりませんでした。
考え方おかしいですか？

一回目で見つかる確率と二回目で見つかる確率と三回目で見つかる確率と四回目で見つかる確率を足すと？

全部足すと25/8でだいたい3になりました。これでいいんですか？

データが8個しかないのになんで4回目で「はじめて」みつかる確率が「1」なんだよ。
1回目： 1個
2回目： 2個
3回目： 4個
4回目： 残りの1個
合計： 8個

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

45です。いままで回答してくださったみなさんありがとうございました。
データが８個の場合、１回目で見つかる個数は１個で２回目は２個３回目は４個、
４回目は１個なので、比較回数の平均は(1*1+2*2+3*4+4*1)/8ということだったのですね。
ありがとうございました。

8kしかROMの無いマイコンに、半分くらいまでは使って良いので
暗号とかに使えるような強力な乱数生成関数を実装したい。

どれがベストですか？

http://jp.youtube.com/watch?v=YuNIgXfErpY

初歩な質問で申し訳ないですが、「ある問題Ｐを解くアルゴリズムＡ」って何ですか？

言葉そのままだと思うけど？

問題とは、自然数の集合
P を解くアルゴリズムとは、入力が P の要素であるかどうかを判定するチューリングマシン

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

>>58
抽象的には文字通りの意味

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

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

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

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

>>60
おいおい・・・頭だいじょうぶか？

>>61
フォローどうも。
一応そのつもりだったんだけど、紛らわしかったね。

自然数の部分集合という言葉にも少し違和感を感じる

もっと正確には「自然数全体の集合の部分集合」だが、ちょっとくどいな
英語なら冠詞で区別できるのだが

20世紀中に20個の名アルゴリズムが生まれた、という話を聞いたんですが、
その内訳は何かご存知ありませんか？

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

>>66
関係ありそうなページをみつけた。
http://d.hatena.ne.jp/nikutaiha/20071207/1197346891
http://demonfox.spaces.live.com/blog/cns!157C572C0C367802!563.entry
20世紀のアルゴリズムBEST10はこれだ…！？
（モンテカルロとクイックソートもランクインしてます〜）

演習問題でわからん問題があるんですけど

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

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

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

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


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

なんの科目だ？
なぜこの板のこのスレへ？

アルゴリズムを探しています（私の頭では解けないので^^;）。
よろしくお願いします。

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

これは、難しいですね・・・

「詰込み問題　長方形」でググれ

セジウィック著のアルゴリズムCの巻末問題の解答って存在するんですか？

逐次決定法でソートをするアルゴリズムを
アクティビティ図で書け言われたんだけど
もうさっぱり、たすけて

>>74
バブルソート、挿入ソートとかをアクティビティ図で書けばいいだけじゃないの？

>>75
降順にソートしろって言われたんだけど
先頭の要素と入れ替えるべき要素をピンポイントで入れ替える方法が思いつかないの
先頭の数より大きな要素を一個ずつ入れ替えて降順に並び替える
図を書いたら、それ逐次決定法ちがうがな、といわれちゃった

ある機械言語で表現された計算を、別の機械言語での計算表現に変換するアルゴリズムってないの？
移植作業を人間がやるのは馬鹿げてると常々思っているんだが。

>> 77
おまえはエミュレータを知らんのか。
ほかのCPUのコード動かすエミュレータなど腐るほどあるだろ。

エミュレータだとインタプリタっぽいけど、むしろコンパイラ方式というか。
無くはない。けど、一般に実用になるものを作るのは非常に難しい。

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

アルゴリズムの教科書を見ていて思ったけど、
ソートのアルゴリズムって何で載ってるの？
学習用なの？

ソートが不必要だと思う理由を挙げてみろや

すいません質問です。

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

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

右辺の意味を考えるヨロシ

>>83
無事どうにかなりました、ありがとうございます。

>>80がいいたいのが「ソートはライブラリがあるから勉強不要」だと笑うよな。

スレ違いかもしれんが、どっか都内の大学で社会人でも潜り込めて
最近のアルゴリズム関連の勉強ができるとこってない？

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

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

サイバー大学、放送大学、その他さがせばいくらでもある。

>>86
東京大学の大学院に研究生として潜り込んだら？
単純にその内容を勉強したい、というだけであれば最高の場所だと思う。

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

スマソ

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

ネットワーク理論のアルゴリズムのSuurballeって何て読めばいいのでしょう？
サーバル？スルベイユ？

スアバレ

ありがと

アルゴリズムデザイン
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

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

かなりいい本。
そのかわり、前提となる知識は多いので、オーソドックスなアルゴリズム本や、計算論の本を読んでからの方が読みやすい。

スレチかもしれませんが、どのスレで聞けば良いかわからなかったので質問させてください！
ユークリッド互除法の最悪計算量をLameの定理の結果を用いずに解析せよという問題なのですが、答えていただけないでしょうか？よろしくお願いします。

初学者におすすめの参考書を教えて下さい。

言語なにやってるの？
多少よみごたえがあっていいなら、「JavaScriptによるアルゴリズムデザイン」かな。
☆ひとつなのは、評者がよくわかってないと思われる。
値段のわりに内容の濃い本。
http://www.amazon.co.jp/dp/4563015695

言語はJavaをやっています。
お薦めいただいた本ですら理解できないかもしれません。
そもそも計算論がよくわからないので、そこから始めるべきですかね…

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

ソートやリストをやったことないなら、「Javaによるアルゴリズム入門」とか、そのあたりをまずは。

わかりました。
探して見てみますね。

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

http://www.yfcbookshelf.com/algorithms.htm
>日本では、いまだにAho,Ullmanの著書が主流とされているが、
>理論的に欠陥があり書き換えが必要なのでCormenのものをお勧めする。

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

「データ構造とアルゴリズム」はそのあとのほうで紹介してるから
設計と解析のほうのことと思われ。

情報シリーズのほうって品切れになってるね。

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

>>100
もう見てないだろうけど、「Javaデータ構造とアルゴリズム基礎講座」という最近でた本がすごくよかった。
おすすめ。

>>104
比較不能なものをどうソートしたかったのか分からんが
stable_sort で何とかなる可能性もあった。

see man tsort って昔の人は言っていた．

>>105
どの辺に感銘受けたの？

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

>>108
よくある、アルゴリズムカタログをアルゴリズム入門と銘打ってるような本ではなくて、アルゴリズム自体を勉強するための入門書。
そして、薄くてよみやすい。
ただし、そういう性質なので載ってるアルゴリズムの種類は少ないし、これで終わり？という物足りなさもある。
必要最低限の用語や考え方がまとめられてて、初学者の最初の足がかりとしておすすめ。

>>110
なるほど。
会社で新人教育用の教科書に使ってみようかな。
ありがとう。

>>102
ｵﾔｽﾐ…
　 ＜⌒／ヽ-、_＿_
／＜_/＿＿＿＿／
￣￣￣￣￣￣￣

>>111
教えるときには、「アルゴリズムデザイン」を本屋で立ち読みしてみて、発展させるとどうなるかイメージしておくといいと思う。

>>106
stable_sortも厳密な弱い順序 (strict weak ordering) を要求するからだめだと思う。

８桁の数字があって下１桁がチェックディジットなのですが、
多数の標本があれば、
どのように算出されたチェックディジットかを判別することって可能なのでしょうか？

一般的にいうのであれば「どのように算出されたチェックディジットか」は判別できない。
けど、再現はできる可能性が高い。
8桁の数字なら、1億の標本があれば、どのように算出されたチェックディジットかを判別せずに再現できる。

>>112
　Z
　 z
　　z
　＜⌒／ヽ-､_＿_
／＜_/＿＿＿＿／
￣￣￣￣￣￣￣

少し聞きたいのだけど
同値類の効率化の話を解説するろきに
log*やAckerman関数をどのように使えばいいのだろうか。