アルゴリズム理論
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
2006/01/22(日) 19:36:14グラフ、近似、量子、オンライン、ゲーム理論、Embedding,
アルゴリズムに関連する話題ならなんでもOK。
STOC, FOCS などの最近の結果について語れたらうれしいなぁ。
0002１３２人目の素数さん
2006/01/22(日) 19:39:02今丁度マイアミでSODAが開かれていますね。
プログラムを見た感じでは、最近の流行は
* Algorithmic Game Theory
* Graph Embedding
* Property Testing
ってところでしょうか。
Exact Algorithm の結果が増えてきているのも注目です。
0003１３２人目の素数さん
2006/01/22(日) 20:02:07アルゴリズムイントロダクション
http://www.kindaikagaku.co.jp/bookdata/ISBN4-7649-0245-1.htm
近似アルゴリズム
http://www.springer-tokyo.co.jp/content/isbn4-431-70991-6.html
組合せ最適化
http://www.springer-tokyo.co.jp/content/isbn4-431-71183-X.html
離散幾何学講義
http://www.springer-tokyo.co.jp/content/ISBN4-431-71041-8.html
下の二つは最近でた訳書。
0004１３２人目の素数さん
2006/01/22(日) 20:25:220005１３２人目の素数さん
2006/01/22(日) 20:50:07上に上げた
> * Algorithmic Game Theory
> * Graph Embedding
> * Property Testing
や近似不可能性の理論なんかは、十分数学的に深みのある分野だと思っている。
0006１３２人目の素数さん
2006/01/22(日) 23:23:240007１３２人目の素数さん
2006/01/23(月) 00:00:490008１３２人目の素数さん
2006/01/23(月) 00:33:21http://science4.2ch.net/infosys/
0009１３２人目の素数さん
2006/01/23(月) 03:27:460010１３２人目の素数さん
2006/01/23(月) 03:36:180011１３２人目の素数さん
2006/01/23(月) 08:39:20同じ内容を扱った、より良い本が出ていないのか？
という意味なら、無いと思う。
これだけの質と量の本は見たことが無い。
内容が古びてないか、という意味なら、それも無い。
アルゴリズムやる上での必修科目みたいなもんだからね。
0012１３２人目の素数さん
2006/01/23(月) 08:40:590013１３２人目の素数さん
2006/01/23(月) 22:33:21↑アルゴリズムこうしん
http://sidhes.hp.infoseek.co.jp/alg3.htm
↑アルゴリズムたいそう
0014１３２人目の素数さん
2006/01/25(水) 00:21:41数学だよ。 (ry
6 名前：１３２人目の素数さん[sage] 投稿日：2006/01/22(日) 23:23:24
数学ではないかもしれないけど (ry
どっちよ？
0015１３２人目の素数さん
2006/01/25(水) 19:59:410016１３２人目の素数さん
2006/01/25(水) 20:02:310017１３２人目の素数さん
2006/01/25(水) 20:43:550018１３２人目の素数さん
2006/01/25(水) 22:26:330019１３２人目の素数さん
2006/01/27(金) 19:53:290020１３２人目の素数さん
2006/01/28(土) 06:48:00キャッシュをするかどうかはこっちの自由だから、
「できない」っことは無いんじゃない？
0021１３２人目の素数さん
2006/01/28(土) 13:04:090022１３２人目の素数さん
2006/01/28(土) 22:18:500023１３２人目の素数さん
2006/01/29(日) 12:14:510024１３２人目の素数さん
2006/01/29(日) 12:59:540025１３２人目の素数さん
2006/02/05(日) 07:32:430026１３２人目の素数さん
2006/02/21(火) 22:16:28まず、簡潔に表現するために、以下の図形を付け加えます。
2，3，4，5，6，7，8，9
さらに、通常の数項の表し方と同じ記号で紛らわしいですが、0，1をあわせて、数字とでも呼んでおきましょう。
次に、数図形というものを、以下のように帰納的に定義します。
（１）数字は数図形である。
（２）Ａが0でない数図形で、qが数字の時、Ａqは数図形である。
数図形は１つ以上の数字が並んだ図形で、一番左が0でないものになります。
この並んでいる数字の個数を数図形の長さと呼びましょう。
数図形の長さが1の時、数図形は数字であり、数図形Ａの長さが1でない時、
Ａ＝Ａ｀q，Ａは0でない数図形。
と表すことができます。このとき、Ａ｀の長さはＡの長さより小さくなります。
0027１３２人目の素数さん
2006/02/21(火) 22:18:23自然数に数項ってのがありますよね。
（１）0，1は数項である。
（２）xが0でない数項の時、x＋1も数項である。
で帰納的に定義されるものです。（書いてないですが、慣例的に『以上でできるもののみが数項である』という意味も含まれています）以下では、数項は必ず（）で括って書くことにします。
（（0），（1），（1＋1＋1）,（x）のように）
実は、この数項を短く簡潔に表現するアルゴリズムを考えました。ちょっと見てみてください。
まず、簡潔に表現するために、以下の図形を付け加えます。
2，3，4，5，6，7，8，9
さらに、通常の数項の表し方と同じ記号で紛らわしいですが、0，1をあわせて、数字とでも呼んでおきましょう。
次に、数図形というものを、以下のように帰納的に定義します。
（１）数字は数図形である。
（２）Ａが0でない数図形で、qが数字の時、Ａqは数図形である。
数図形は１つ以上の数字が並んだ図形で、一番左が0でないものになります。
この並んでいる数字の個数を数図形の長さと呼びましょう。
数図形の長さが1の時、数図形は数字であり、数図形Ａの長さが1でない時、
Ａ＝Ａ｀q，Ａは0でない数図形。
と表すことができます。このとき、Ａ｀の長さはＡの長さより小さくなります。
0028１３２人目の素数さん
2006/02/21(火) 22:19:15s^*（0）＝1
s^*（1）＝2
s^*（2）＝3
s^*（3）＝4
s^*（4）＝5
s^*（5）＝6
s^*（6）＝7
s^*（7）＝8
s^*（8）＝9
s^*（9）＝10
と定めます。
このs^*を用いて、数図形間の対応sを、以下のように定めます。
s（Ａ）＝s^*（Ａ） （Ａが数字の時）
s（Ａ）＝Ａ｀s（q）（Ａ＝Ａ｀q、qはq≠9である数字の時）
s（Ａ）＝s（Ａ｀）0（Ａ＝Ａ｀9の時）
0029１３２人目の素数さん
2006/02/21(火) 22:20:55（１）Rep（(0)）＝0
（２）Rep（(1)）＝1
（３）Rep（(x＋1)）＝s（Rep（(x)））
例えば、
Rep（(1＋1＋1)）＝s（Rep（(1＋1)））＝s（s（Rep（(1)）））＝s（s（1））＝s(2)＝3
となり、
0030１３２人目の素数さん
2006/02/21(火) 22:22:57＝s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)））
＝s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)）））
＝s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)））））
＝s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)）））））
＝s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)））））））
＝s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)）））））））
＝s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)））））））））
＝s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)）））））））））
＝s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)））））））））））
＝s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1)）））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1)））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1)）））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1＋1)）））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1＋1)）））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1＋1)））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1＋1)）））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1＋1)））））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1＋1)）））））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1＋1)））））））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（Rep（(1)）））））））））））））））））））））
0031１３２人目の素数さん
2006/02/21(火) 22:24:34＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（2）））））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（3））））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（4）））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（5））））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（s（6）））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（s（7））））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（s（8）））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（s（9））））））））））））
＝s（s（s（s（s（s（s（s（s（s（s（10）））））））））））
0032１３２人目の素数さん
2006/02/21(火) 22:25:30＝s（s（s（s（s（s（s（s（s（s（11））））））））））
＝s（s（s（s（s（s（s（s（s（1s（1））））））））））
＝s（s（s（s（s（s（s（s（s（12）））））））））
＝s（s（s（s（s（s（s（s（1s（2）））））））））
＝s（s（s（s（s（s（s（s（13））））））））
＝s（s（s（s（s（s（s（1s（3））））））））
＝s（s（s（s（s（s（s（14）））））））
＝s（s（s（s（s（s（1s（4）））））））
＝s（s（s（s（s（s（15））））））
＝s（s（s（s（s（1s（5））））））
＝s（s（s（s（s（16）））））
＝s（s（s（s（1s（6）））））
＝s（s（s（s（17））））
＝s（s（s（1s（7））））
＝s（s（s（18）））
＝s（s（1s（8）））
＝s（s（19））
＝s（s（1）0）
＝s（20）
＝2s（0）
＝21
となります。
0033１３２人目の素数さん
2006/02/21(火) 22:27:25Rep（(1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1）＝114
となります。
特に下の例のように、多くの場合、数項(x)をRep（(x)）で表せば、
非常に短く簡単に数項が表現できます。実際には、メモリーに記憶
させておくなど、さらに効率を上げる手段を併用しておくといいか
と思います。
私はこの発明を広く世界中の人に使ってもらいたいと思います。特
許をとればおそらくボロ儲けでしょうが、そんなせこいことは言い
ません。私のこの大発明を、みんなで人類の財産として使って欲し
いと思います。
0034１３２人目の素数さん
2006/02/21(火) 22:31:360035１３２人目の素数さん
2006/02/21(火) 22:48:21O(log n) (ラージオーダ) だったら全然必要ないんですけど。
0036１３２人目の素数さん
2006/02/22(水) 06:10:28全然必要ない？驚きました。あなたは
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋
1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1
と書く方がいいとおっしゃるのでしょうか？私は、簡潔に
100
と書く方が楽だし、わかりやすいと思います。
そうですねえ。記憶の活用ですが、このような方法は如何でしょうか？
まず、各数字について、
call（0）＝れい
call（1）＝いち
call（2）＝に
call（3）＝さん
call（4）＝よん
call（5）＝ご
call（6）＝ろく
call（7）＝なな
call（8）＝はち
call（9）＝きゅう
と定義しましょう。そして、長さが1でない数図形に対しては、
その図形の長さに対応して同じく文字列を対応させます。
そうですねえ。長さが1の次に短いときは、”じゅう”とでもしましょか。
その次に短いときは”ひゃく”なんていいかも。
で、Ａに対応するこのような文字列をketa（Ａ）としましょう。
0037１３２人目の素数さん
2006/02/22(水) 06:11:34たものを、準数図形と呼ぶことにしましょう。準数図形Ａに対し、
st（Ａ）を以下のように定めます。
st（0）＝φ
st（Ａ）＝Ａ（Ａが0でない数図形の時）
st（Ａ）＝st（Ａ｀）（Ａ＝0Ａ｀の時）
このとき、数図形Ａ＝qＡ｀に対して、(qは0でない数字、Ａ｀は準数図形）
call（Ａ）＝keta（Ａ）call（Ａ｀）（q＝1のとき）
call（Ａ）＝call（q）keta（Ａ）（q≠1で、st（Ａ｀）＝φのとき）、
call（Ａ）＝call（q）keta（Ａ）call（st（Ａ｀））（q≠1で、st（Ａ｀）≠φのとき）、
とさだめます。例えば、
call（124）＝keta（124）call（24）＝ひゃくcall（2）keta（24）call（st（4））
＝ひゃくにじゅうcall（4）＝ひゃくにじゅうよん
call（203）＝call（2）keta（203）call（st（03））＝にひゃくcall（st（3））
＝にひゃくcall（3）＝にひゃくさん
call（50）＝call（5）keta（50）＝ごじゅう
となります。
このような方法で数項を表現する数図形に対し文字列を対応させます。
そして、ここからが提案なんですが、小さい子供の頃から、数項の小さい方から順に
読む習慣をつけてみたらどうでしょうか？たとえば、お風呂に入ったら、
「call（1）からcall（100）まで読まないと、お風呂から出てはいけませんよ。」
と躾てあげるのです。最初は嫌がるでしょうが、これによってしっかりとお風呂で暖まる
ことができ、また、数項に対応した数図形を、対応する文字列を通じて記憶することがで
きるのです。どうでしょうか、このアイデア？
003835
2006/02/22(水) 11:36:24方法を既に知ってますので、無理に別の方法を使う必要は感じません。
0039１３２人目の素数さん
2006/02/22(水) 12:58:03数項nですね。間違えないようにしましょう。
で。具体的にそのアルゴリズムを正確に書いてみてくれませんか？
0040１３２人目の素数さん
2006/02/22(水) 17:57:42ということを面倒に言い直しただけだろ
0041１３２人目の素数さん
2006/02/22(水) 18:28:23実行してみてください。もちろん、……で誤魔化したりしないでね。
0042１３２人目の素数さん
2006/02/22(水) 18:30:37理論にないsuccessorを使うなら、まずはきちんと定義しましょうね。
0043１３２人目の素数さん
2006/02/22(水) 20:01:500044１３２人目の素数さん
2006/02/22(水) 20:48:120045１３２人目の素数さん
2006/02/22(水) 21:19:08ところでそれのどこが「アルゴリズム」なの？
>>1 で例示されてるものとあまりにも乖離してない？
0046１３２人目の素数さん
2006/02/22(水) 21:23:56せっかく苦労して書いた甲斐がないよw
0047１３２人目の素数さん
2006/02/22(水) 23:04:09嬉しがって準数図形とやらを導入したならちゃんと使ってくれんかね？
stの定義が読みにくくてしょうがない。やりなおせ。
0048１３２人目の素数さん
2006/02/22(水) 23:19:230049１３２人目の素数さん
2006/02/22(水) 23:40:29ketaの定義があいまいで全くなってない。もっと形式的にやってもらわないと
アルゴリズムとは言えない。
call（50）＝call（5）keta（50）＝ごじゅう
とあるが、正直なところcallが数字をわりあてる基底段階がおお過ぎて何がし
たいのかわからない。
俺のみたとことでは、古典的な算術の劣化変形版にしか見えない。
ペアノ算術と比較して、数学的になんの成果が期待できるの？
実際に使うなら、ペアノ算術のほうが規則が少なく、かつ登場人物も少ないの
で、研究のためにはいいわな。
子供のころから「数項」がうんぬんは気違いの冗談にしか思えない。
0050１３２人目の素数さん
2006/02/22(水) 23:59:15call(100)を計算してみたら変なことになったよ。
ちゃんと定義できてないじゃん。
> このとき、数図形Ａ＝qＡ｀に対して、(qは0でない数字、Ａ｀は準数図形）
>
> call（Ａ）＝keta（Ａ）call（Ａ｀）（q＝1のとき）
> call（Ａ）＝call（q）keta（Ａ）（q≠1で、st（Ａ｀）＝φのとき）、
> call（Ａ）＝call（q）keta（Ａ）call（st（Ａ｀））（q≠1で、st（Ａ｀）≠φのとき）、
> とさだめます。
ＡとＡ｀は丁重に使いわけてもらわないと使いものにならない。
call(100)=keta(1)call(00)=keta(1)call(0)keta(00)call(st(0))
=keta(1)れいじゅうcall(φ)
=いちれいじゅうcall(φ) (しかたがないからketa(1)を「いち」と簡約した)
=...
で、call(φ)はどうやって簡約するの？
0051１３２人目の素数さん
2006/02/23(木) 04:23:11やっとまともっぽい突っ込みが来たな。ただ、これがダメなら数学基礎論で使うような
ある種のアルゴリズムはアルゴリズムでないってことにもなる。有限の立場の数学って
勉強したことある？
それと。これを劣化板と言うからには、君はもちろん普段から
5×4＝20
と書かず
（1＋1＋1＋1＋1）・（1＋1＋1＋1）＝（1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1＋1）
と書いてるってことだよねw僕にはまねできないな。
>>50
定義を見て再現できないなら、あんまり偉そうな口を利かない方がいいと思うぞ。
見ている方が恥ずかしくなる。俺なら、call（300）とかに突っ込みを入れるがw
0052１３２人目の素数さん
2006/02/23(木) 05:13:24# call(100000) と call(110000) は？
0053１３２人目の素数さん
2006/02/23(木) 05:48:08まだそこまで定義できてないから百までで誤魔化してたの。読みの部分は思い付きみたいにその場で書いたんで、かなりツメは甘い。なのにまともな突っ込みがなくて寂しかったよw
しかしどうすればいいかね？4つずつ区切ればいいんだが、それをキチンと定義するのは面倒なんだわ。誰かやってみない？
0054１３２人目の素数さん
2006/02/23(木) 06:53:410055１３２人目の素数さん
2006/02/23(木) 09:42:46やり直して出直してくるわ。
0056１３２人目の素数さん
2006/02/23(木) 18:44:23もしかして「数n」を計算機が蓄えるときに、
本当にn個の記憶素子が使われてると思ってるんですか？
>>35さんは、今の（というか何十年も大昔から）計算機では
数は普通に2進数で格納されてるから必要ないよ、と言ってるのかな、と思うんですが
万が一、10進位取り表記法をあなたが一から再発見したなら確かにすごいけどｗ
その割には説明中で普通に使ってますからねえ。。
そもそも「数項」ってのはキソロンとやらでは使うかもしれないけど
アルゴリズムの理論で使うのかなあ。。
>>38
数項nを表記して何の役に立つんですか？
0057１３２人目の素数さん
2006/02/23(木) 23:20:57いまいちノリが悪いヤツだな。まあいいや。
ところで、
>万が一、10進位取り表記法をあなたが一から再発見したなら確かにすごいけどｗ
>その割には説明中で普通に使ってますからねえ。。
これどこ？相当気をつけたつもりだったんだけど。
0058１３２人目の素数さん
2006/02/24(金) 01:37:43> アルゴリズムの理論で使うのかなあ。。
基礎論でもnumeral termなんていう単語は使わない。
ShoenfieldもTroelstraも松本和夫も使ってない。
彼の脳内でしか通用しない造語だろう。
しかもあまり日本語も達者ではないようで、数図形だのなんだの言ってるね。
> 自然数に数項ってのがありますよね。
こんなこと言われても困る。
0059１３２人目の素数さん
2006/02/24(金) 01:57:04日本人では廣瀬・横田の『ゲーデルの世界』とか
田中一之の『数の体系と超準モデル』はnumeralの訳語に「数項」という単語を当てている
倉田の『入門数学基礎論』でも使ってる（p124など）
まあ数を表す項だから「数項」は訳語として合格じゃないのかな
ただそれならnumeralwiseも数項ごとに、とか任意の数項が、どの数項も、
となるべきと思うが
高橋昌一郎は「数値」という語を当てているけどこれは明らかにまずいような
0060１３２人目の素数さん
2006/02/24(金) 02:34:290061１３２人目の素数さん
2006/02/24(金) 06:59:52> 数項nを表記して何の役に立つんですか？
ここが気になる。
数項でもなんでもいいけど、文字列変換して何がしたいわけ？
0062１３２人目の素数さん
2006/02/24(金) 10:56:28そうか。サンクス。俺は畑違いでその手の感覚はわからないんで。数項って一般的じゃないんだ。勉強になったよ。
まあ、>>59の言ってるような本で俄か勉強したクチなんで勘弁してくれw
分野が違えば複数の人が書いている用語を一般的と思うのは許容範囲でしかたないだろ？一応定義は書いたから誤解もされないだろうし。
しかし、ネタでもなんでも書いてみるもんだな。思わぬ収穫だったよ。ありがとう、お二人さん。
0063１３２人目の素数さん
2006/02/24(金) 15:19:35索引にも載っている。
0064１３２人目の素数さん
2006/02/26(日) 00:39:010065１３２人目の素数さん
2006/02/26(日) 00:43:28numeralって単語は知ってたっぽい
0066１３２人目の素数さん
2006/02/26(日) 10:01:310067１３２人目の素数さん
2006/02/26(日) 18:22:53ここにもお仲間がいるようだしな。恥ずかしがる必要はない。
0068１３２人目の素数さん
2006/02/26(日) 18:54:27松本和夫はnumeralを数字と訳している。
竹内外史が数項という単語を使っていた記憶はない。
国内の研究集会でnumeralを数項と訳していたことはない。
現在この分野は日本が後手に回っているので、正確を期すときには
英語のまま「ニューメラル」などと言う場合が多い。
以上を踏まえて、数項とか数図形という単語について私見を述べた。
0069１３２人目の素数さん
2006/02/26(日) 18:57:49なら、
>彼の脳内でしか通用しない造語だろう。
なんて勝ち誇ったようなセリフを言わなければ済んだことだろうよ。
もう少し謙虚になろうや、お互いに。
0071１３２人目の素数さん
2006/02/26(日) 19:18:05やたら横文字をそのまま使う人ってイメージがあるんだけど
007269
2006/02/26(日) 19:42:08もう少し頭を柔らかくしろよ。そんなんじゃ良い
研究者になれないぞ
0073１３２人目の素数さん
2006/02/26(日) 23:03:310074１３２人目の素数さん
2006/02/26(日) 23:05:43俺も冷静さが足りなかったようだ。申し分けない。
0075１３２人目の素数さん
2006/03/02(木) 19:11:180076１３２人目の素数さん
2006/03/04(土) 06:44:390077１３２人目の素数さん
2006/03/06(月) 15:45:100078１３２人目の素数さん
2006/03/26(日) 14:11:500079１３２人目の素数さん
2006/04/03(月) 18:28:050080１３２人目の素数さん
2006/04/05(水) 22:08:130081１３２人目の素数さん
2006/04/08(土) 23:28:49又聞きしたんだが、
「NP-Completeな問題には実用的な近似解アルゴリズムが比較的
多くある。PSPACE-Completeな問題には実用的な近似解アルゴ
リズムはほとんど見つからない。」
だそうだ。そんなもん?
PSPACE-Completeな問題なんて、その辺にいくらでも転がってる
気がするんだけど、みんな実用的時間じゃ解けないの?
0082１３２人目の素数さん
2006/04/10(月) 11:44:25PSPACE-Complete(ATIME(poly)-Complete)。
オセロが後手必勝かどうかは 6x6 では分かってるけど、
8x8はまだ未解決だと思う。
0083１３２人目の素数さん
2006/04/15(土) 12:02:110084１３２人目の素数さん
2006/04/15(土) 13:11:070085１３２人目の素数さん
2006/04/29(土) 04:00:420086１３２人目の素数さん
2006/04/29(土) 04:03:180087１３２人目の素数さん
2006/05/13(土) 21:26:240088１３２人目の素数さん
2006/05/21(日) 23:45:23> 2 人ゲームの先手(後手)必勝判定問題はゲームにループがなければ
> PSPACE-Complete(ATIME(poly)-Complete)。
すごいいいきりようだな
俺は2人ゲームで先手必勝判定問題がPに属するようなループのないゲームを
いくらでも設計できるが
0089１３２人目の素数さん
2006/05/22(月) 04:14:350090１３２人目の素数さん
2006/05/22(月) 09:57:32そうそう。f(x)=x とか自明な充足可能性問題もあるもんね。
インスタンスと問題の区別がつかないと、計算量理論は理解不能だよね。
0091１３２人目の素数さん
2006/06/15(木) 23:54:370092１３２人目の素数さん
2006/06/17(土) 21:33:43将棋はループはないが多項式じゃ無理だぞ。
EXPSPACEあれば十分だけど、EXPやNEXPで解けるのかな。
0093１３２人目の素数さん
2006/06/18(日) 05:39:240094１３２人目の素数さん
2006/07/07(金) 10:34:32一応マジレスしとくと将棋は定数時間で解けるね
あとはどう一般化するかしだいでしょ
0095１３２人目の素数さん
2006/07/07(金) 13:43:550096１３２人目の素数さん
2006/07/08(土) 21:01:31釣りか？
0097１３２人目の素数さん
2006/07/09(日) 11:03:44定数時間で解けるわけねーじゃんという意味なのか
定数時間で解けるのは当り前だけど>>92がいいたいのはそういうことじゃねーだろという意味か
0098１３２人目の素数さん
2006/07/10(月) 04:46:290099１３２人目の素数さん
2006/07/28(金) 17:03:570100１３２人目の素数さん
2006/08/30(水) 15:25:590101１３２人目の素数さん
2006/08/30(水) 15:43:350102１３２人目の素数さん
2006/10/02(月) 23:58:420103１３２人目の素数さん
2006/10/25(水) 05:46:510104１３２人目の素数さん
2006/11/13(月) 01:51:18■ このスレッドは過去ログ倉庫に格納されています