アルゴリズム理論

このエントリーをはてなブックマークに追加
1132人目の素数さん
アルゴリズム関連スレが無いので立ててみました。

グラフ、近似、量子、オンライン、ゲーム理論、Embedding,
アルゴリズムに関連する話題ならなんでもOK。

STOC, FOCS などの最近の結果について語れたらうれしいなぁ。
2132人目の素数さん:2006/01/22(日) 19:39:02
さっそく自分で2ゲッツ!

今丁度マイアミでSODAが開かれていますね。

プログラムを見た感じでは、最近の流行は
* Algorithmic Game Theory
* Graph Embedding
* Property Testing
ってところでしょうか。
Exact Algorithm の結果が増えてきているのも注目です。
3132人目の素数さん: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

下の二つは最近でた訳書。
4132人目の素数さん:2006/01/22(日) 20:25:22
これって数学なの?
5132人目の素数さん:2006/01/22(日) 20:50:07
数学だよ。

上に上げた
> * Algorithmic Game Theory
> * Graph Embedding
> * Property Testing
や近似不可能性の理論なんかは、十分数学的に深みのある分野だと思っている。
6132人目の素数さん:2006/01/22(日) 23:23:24
数学ではないかもしれないけど、やるとしたらこの板しかない現実。
7132人目の素数さん:2006/01/23(月) 00:00:49
確かにぬるぽだな
8132人目の素数さん:2006/01/23(月) 00:33:21
9132人目の素数さん:2006/01/23(月) 03:27:46
そこはSE板だよ
10132人目の素数さん:2006/01/23(月) 03:36:18
いまだにクヌースの本がバイブルなの?
11132人目の素数さん:2006/01/23(月) 08:39:20
いま Vol.4 書いてて、一部の章は既に出版されてるよね>Knuth御大

同じ内容を扱った、より良い本が出ていないのか?
という意味なら、無いと思う。
これだけの質と量の本は見たことが無い。

内容が古びてないか、という意味なら、それも無い。
アルゴリズムやる上での必修科目みたいなもんだからね。
12132人目の素数さん:2006/01/23(月) 08:40:59
あんま実践で使わんけどな
13132人目の素数さん:2006/01/23(月) 22:33:21
http://sidhes.hp.infoseek.co.jp/alg.htm
↑アルゴリズムこうしん

http://sidhes.hp.infoseek.co.jp/alg3.htm
↑アルゴリズムたいそう
14132人目の素数さん:2006/01/25(水) 00:21:41
5 名前:132人目の素数さん[sage] 投稿日:2006/01/22(日) 20:50:07
数学だよ。 (ry

6 名前:132人目の素数さん[sage] 投稿日:2006/01/22(日) 23:23:24
数学ではないかもしれないけど (ry

どっちよ?
15132人目の素数さん:2006/01/25(水) 19:59:41
数学だよ。
16132人目の素数さん:2006/01/25(水) 20:02:31
数学じゃないよ
17132人目の素数さん:2006/01/25(水) 20:43:55
ど、ど、どっちなんだよぉ・・ウワァァ━━━━━。゚(゚´Д`゚)゚。━━━━━ン!!!!
18132人目の素数さん:2006/01/25(水) 22:26:33
計算機代数やってる俺もここでいいのかな?
19132人目の素数さん:2006/01/27(金) 19:53:29
DP がキャッシュつき再帰にできない例ってありますか?
20132人目の素数さん:2006/01/28(土) 06:48:00
再帰で解けるってのがDPの本質だし、
キャッシュをするかどうかはこっちの自由だから、
「できない」っことは無いんじゃない?
21132人目の素数さん:2006/01/28(土) 13:04:09
それで、これは数学なの?
22132人目の素数さん:2006/01/28(土) 22:18:50
数学っすよ。
23132人目の素数さん:2006/01/29(日) 12:14:51
数学じゃないっすよ。
24132人目の素数さん:2006/01/29(日) 12:59:54
そんなのどっちでもいいじゃん。なんかネタないの?
25132人目の素数さん:2006/02/05(日) 07:32:43
692
26132人目の素数さん:2006/02/21(火) 22:16:28


まず、簡潔に表現するために、以下の図形を付け加えます。
2,3,4,5,6,7,8,9
さらに、通常の数項の表し方と同じ記号で紛らわしいですが、0,1をあわせて、数字とでも呼んでおきましょう。
次に、数図形というものを、以下のように帰納的に定義します。
(1)数字は数図形である。
(2)Aが0でない数図形で、qが数字の時、Aqは数図形である。
数図形は1つ以上の数字が並んだ図形で、一番左が0でないものになります。
この並んでいる数字の個数を数図形の長さと呼びましょう。
数図形の長さが1の時、数図形は数字であり、数図形Aの長さが1でない時、
A=A`q,Aは0でない数図形。
と表すことができます。このとき、A`の長さはAの長さより小さくなります。
27132人目の素数さん:2006/02/21(火) 22:18:23
失敗。もう一度最初から。
自然数に数項ってのがありますよね。
(1)0,1は数項である。
(2)xが0でない数項の時、x+1も数項である。
で帰納的に定義されるものです。(書いてないですが、慣例的に『以上でできるもののみが数項である』という意味も含まれています)以下では、数項は必ず()で括って書くことにします。
((0),(1),(1+1+1),(x)のように)
実は、この数項を短く簡潔に表現するアルゴリズムを考えました。ちょっと見てみてください。


まず、簡潔に表現するために、以下の図形を付け加えます。
2,3,4,5,6,7,8,9
さらに、通常の数項の表し方と同じ記号で紛らわしいですが、0,1をあわせて、数字とでも呼んでおきましょう。
次に、数図形というものを、以下のように帰納的に定義します。
(1)数字は数図形である。
(2)Aが0でない数図形で、qが数字の時、Aqは数図形である。
数図形は1つ以上の数字が並んだ図形で、一番左が0でないものになります。
この並んでいる数字の個数を数図形の長さと呼びましょう。
数図形の長さが1の時、数図形は数字であり、数図形Aの長さが1でない時、
A=A`q,Aは0でない数図形。
と表すことができます。このとき、A`の長さはAの長さより小さくなります。

28132人目の素数さん:2006/02/21(火) 22:19:15
そして、数字から数図形への対応として、

s^*(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(A)=s^*(A) (Aが数字の時)
s(A)=A`s(q)(A=A`q、qはq≠9である数字の時)
s(A)=s(A`)0(A=A`9の時)
29132人目の素数さん:2006/02/21(火) 22:20:55
以上で準備ができました。数項(x)について、Rep((x))を以下のように定義します。
(1)Rep((0))=0
(2)Rep((1))=1
(3)Rep((x+1))=s(Rep((x)))

例えば、

Rep((1+1+1))=s(Rep((1+1)))=s(s(Rep((1))))=s(s(1))=s(2)=3
となり、
30132人目の素数さん:2006/02/21(火) 22:22:57
Rep((1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1))
=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))))))))))))))))))))))
31132人目の素数さん: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(s(1))))))))))))))))))))
=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)))))))))))
32132人目の素数さん:2006/02/21(火) 22:25:30
=s(s(s(s(s(s(s(s(s(s(1s(0)))))))))))
=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

となります。
33132人目の素数さん:2006/02/21(火) 22:27:25
同様にして、
Rep((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))で表せば、
非常に短く簡単に数項が表現できます。実際には、メモリーに記憶
させておくなど、さらに効率を上げる手段を併用しておくといいか
と思います。
私はこの発明を広く世界中の人に使ってもらいたいと思います。特
許をとればおそらくボロ儲けでしょうが、そんなせこいことは言い
ません。私のこの大発明を、みんなで人類の財産として使って欲し
いと思います。
34132人目の素数さん:2006/02/21(火) 22:31:36
あっ、最後の式で後ろの括弧が一個足りないか。まあいいや。
35132人目の素数さん:2006/02/21(火) 22:48:21
それって数 n に対して、 o(log n) (スモールオーダ) になるんですか?
O(log n) (ラージオーダ) だったら全然必要ないんですけど。
36132人目の素数さん:2006/02/22(水) 06:10:28
>>35
全然必要ない?驚きました。あなたは
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の次に短いときは、”じゅう”とでもしましょか。
その次に短いときは”ひゃく”なんていいかも。
で、Aに対応するこのような文字列をketa(A)としましょう。
37132人目の素数さん:2006/02/22(水) 06:11:34
また、数図形の定義(2)で、「Aが0でない数図形で」を「Aが数図形で」に置き換え
たものを、準数図形と呼ぶことにしましょう。準数図形Aに対し、
st(A)を以下のように定めます。
st(0)=φ
st(A)=A(Aが0でない数図形の時)
st(A)=st(A`)(A=0A`の時)


このとき、数図形A=qA`に対して、(qは0でない数字、A`は準数図形)

call(A)=keta(A)call(A`)(q=1のとき)
call(A)=call(q)keta(A)(q≠1で、st(A`)=φのとき)、
call(A)=call(q)keta(A)call(st(A`))(q≠1で、st(A`)≠φのとき)、

とさだめます。例えば、
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)まで読まないと、お風呂から出てはいけませんよ。」
と躾てあげるのです。最初は嫌がるでしょうが、これによってしっかりとお風呂で暖まる
ことができ、また、数項に対応した数図形を、対応する文字列を通じて記憶することがで
きるのです。どうでしょうか、このアイデア?
3835:2006/02/22(水) 11:36:24
あなたの方法を使わなくても私は数 n を Θ(log n) の長さで書く
方法を既に知ってますので、無理に別の方法を使う必要は感じません。
39132人目の素数さん:2006/02/22(水) 12:58:03
>>38
数項nですね。間違えないようにしましょう。
で。具体的にそのアルゴリズムを正確に書いてみてくれませんか?
40132人目の素数さん:2006/02/22(水) 17:57:42
s をsuccessorとし,s(1) を 2 と書く,s(2) を 3 と書く,……,10進数表記を用いる.

ということを面倒に言い直しただけだろ
41132人目の素数さん:2006/02/22(水) 18:28:23
>>40
実行してみてください。もちろん、……で誤魔化したりしないでね。
42132人目の素数さん:2006/02/22(水) 18:30:37
あと、数項をああ書いてるんだから、PAだってわかるでしょ?
理論にないsuccessorを使うなら、まずはきちんと定義しましょうね。
43132人目の素数さん:2006/02/22(水) 20:01:50
>26 は「最後まできちんとできたね。おりこうさん」と言って欲しいだけだろ。
44132人目の素数さん:2006/02/22(水) 20:48:12
いや、偉そうに言うわりにはこの程度のこともできない厨に対し苦笑してるだけだよw
45132人目の素数さん:2006/02/22(水) 21:19:08
>>44

ところでそれのどこが「アルゴリズム」なの?
>>1 で例示されてるものとあまりにも乖離してない?
46132人目の素数さん:2006/02/22(水) 21:23:56
別に>>1の例示にこだわる必要なんか無いだろ?なんつーか、もう少しがんばってくれよ。
せっかく苦労して書いた甲斐がないよw
47132人目の素数さん:2006/02/22(水) 23:04:09
>>37
嬉しがって準数図形とやらを導入したならちゃんと使ってくれんかね?
stの定義が読みにくくてしょうがない。やりなおせ。
48132人目の素数さん:2006/02/22(水) 23:19:23
まず自分がやれよwホント口先だけで何もできないヤツだな。
49132人目の素数さん:2006/02/22(水) 23:40:29
>>37
ketaの定義があいまいで全くなってない。もっと形式的にやってもらわないと
アルゴリズムとは言えない。

call(50)=call(5)keta(50)=ごじゅう

とあるが、正直なところcallが数字をわりあてる基底段階がおお過ぎて何がし
たいのかわからない。

俺のみたとことでは、古典的な算術の劣化変形版にしか見えない。
ペアノ算術と比較して、数学的になんの成果が期待できるの?
実際に使うなら、ペアノ算術のほうが規則が少なく、かつ登場人物も少ないの
で、研究のためにはいいわな。
子供のころから「数項」がうんぬんは気違いの冗談にしか思えない。
50132人目の素数さん:2006/02/22(水) 23:59:15
>>37
call(100)を計算してみたら変なことになったよ。
ちゃんと定義できてないじゃん。

> このとき、数図形A=qA`に対して、(qは0でない数字、A`は準数図形)
>
> call(A)=keta(A)call(A`)(q=1のとき)
> call(A)=call(q)keta(A)(q≠1で、st(A`)=φのとき)、
> call(A)=call(q)keta(A)call(st(A`))(q≠1で、st(A`)≠φのとき)、
> とさだめます。

AとA`は丁重に使いわけてもらわないと使いものにならない。

call(100)=keta(1)call(00)=keta(1)call(0)keta(00)call(st(0))
=keta(1)れいじゅうcall(φ)
=いちれいじゅうcall(φ) (しかたがないからketa(1)を「いち」と簡約した)
=...
で、call(φ)はどうやって簡約するの?
51132人目の素数さん:2006/02/23(木) 04:23:11
>>49
やっとまともっぽい突っ込みが来たな。ただ、これがダメなら数学基礎論で使うような
ある種のアルゴリズムはアルゴリズムでないってことにもなる。有限の立場の数学って
勉強したことある?
 それと。これを劣化板と言うからには、君はもちろん普段から
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

52132人目の素数さん:2006/02/23(木) 05:13:24
こういうのは麻疹のようなものだけど、随分と古い病気にかかったね。

# call(100000) と call(110000) は?
53132人目の素数さん:2006/02/23(木) 05:48:08
そうそう。そういう突っ込みなら大歓迎w
まだそこまで定義できてないから百までで誤魔化してたの。読みの部分は思い付きみたいにその場で書いたんで、かなりツメは甘い。なのにまともな突っ込みがなくて寂しかったよw
しかしどうすればいいかね?4つずつ区切ればいいんだが、それをキチンと定義するのは面倒なんだわ。誰かやってみない?
54132人目の素数さん:2006/02/23(木) 06:53:41
やらねーよw
55132人目の素数さん:2006/02/23(木) 09:42:46
すまん。計算間違ってたか。情けない。
やり直して出直してくるわ。
56132人目の素数さん:2006/02/23(木) 18:44:23
>>36
もしかして「数n」を計算機が蓄えるときに、
本当にn個の記憶素子が使われてると思ってるんですか?
>>35さんは、今の(というか何十年も大昔から)計算機では
数は普通に2進数で格納されてるから必要ないよ、と言ってるのかな、と思うんですが

万が一、10進位取り表記法をあなたが一から再発見したなら確かにすごいけどw
その割には説明中で普通に使ってますからねえ。。

そもそも「数項」ってのはキソロンとやらでは使うかもしれないけど
アルゴリズムの理論で使うのかなあ。。

>>38
数項nを表記して何の役に立つんですか?
57132人目の素数さん:2006/02/23(木) 23:20:57
>>56
いまいちノリが悪いヤツだな。まあいいや。
ところで、

>万が一、10進位取り表記法をあなたが一から再発見したなら確かにすごいけどw
>その割には説明中で普通に使ってますからねえ。。

これどこ?相当気をつけたつもりだったんだけど。
58132人目の素数さん:2006/02/24(金) 01:37:43
> そもそも「数項」ってのはキソロンとやらでは使うかもしれないけど
> アルゴリズムの理論で使うのかなあ。。
基礎論でもnumeral termなんていう単語は使わない。
ShoenfieldもTroelstraも松本和夫も使ってない。
彼の脳内でしか通用しない造語だろう。
しかもあまり日本語も達者ではないようで、数図形だのなんだの言ってるね。

> 自然数に数項ってのがありますよね。
こんなこと言われても困る。
59132人目の素数さん:2006/02/24(金) 01:57:04
numeralは使いますね
日本人では廣瀬・横田の『ゲーデルの世界』とか
田中一之の『数の体系と超準モデル』はnumeralの訳語に「数項」という単語を当てている
倉田の『入門数学基礎論』でも使ってる(p124など)

まあ数を表す項だから「数項」は訳語として合格じゃないのかな
ただそれならnumeralwiseも数項ごとに、とか任意の数項が、どの数項も、
となるべきと思うが

高橋昌一郎は「数値」という語を当てているけどこれは明らかにまずいような
60132人目の素数さん:2006/02/24(金) 02:34:29
困るのは同意ね
61132人目の素数さん:2006/02/24(金) 06:59:52
> >>38
> 数項nを表記して何の役に立つんですか?
ここが気になる。
数項でもなんでもいいけど、文字列変換して何がしたいわけ?
62132人目の素数さん:2006/02/24(金) 10:56:28
>>58>>59
そうか。サンクス。俺は畑違いでその手の感覚はわからないんで。数項って一般的じゃないんだ。勉強になったよ。
まあ、>>59の言ってるような本で俄か勉強したクチなんで勘弁してくれw
分野が違えば複数の人が書いている用語を一般的と思うのは許容範囲でしかたないだろ?一応定義は書いたから誤解もされないだろうし。
しかし、ネタでもなんでも書いてみるもんだな。思わぬ収穫だったよ。ありがとう、お二人さん。
63132人目の素数さん:2006/02/24(金) 15:19:35
当然のことですが、Shoenfield の本に numeral は出てきます。
索引にも載っている。
64132人目の素数さん:2006/02/26(日) 00:39:01
>>58の脳内には別世界のキソロンがあったと言うことでFA?
65132人目の素数さん:2006/02/26(日) 00:43:28
単に訳語がどの程度使われているかを知らん買った、ってことじゃないかな
numeralって単語は知ってたっぽい
66132人目の素数さん:2006/02/26(日) 10:01:31
若いうちはこんな勇み足がままあるもの。元気があってよろすぃ。
67132人目の素数さん:2006/02/26(日) 18:22:53
http://science4.2ch.net/test/read.cgi/math/1072058641/683
ここにもお仲間がいるようだしな。恥ずかしがる必要はない。
68132人目の素数さん:2006/02/26(日) 18:54:27
>>64
松本和夫はnumeralを数字と訳している。
竹内外史が数項という単語を使っていた記憶はない。
国内の研究集会でnumeralを数項と訳していたことはない。
現在この分野は日本が後手に回っているので、正確を期すときには
英語のまま「ニューメラル」などと言う場合が多い。

以上を踏まえて、数項とか数図形という単語について私見を述べた。
69132人目の素数さん:2006/02/26(日) 18:57:49
>>58
なら、
>彼の脳内でしか通用しない造語だろう。
なんて勝ち誇ったようなセリフを言わなければ済んだことだろうよ。
もう少し謙虚になろうや、お互いに。
7069:2006/02/26(日) 19:05:06
>>58>>68の間違い。まあ、引用部分は丁度>>58ではあったが。
71132人目の素数さん:2006/02/26(日) 19:18:05
でもなんか竹内外史って滅多に訳語を使わないで
やたら横文字をそのまま使う人ってイメージがあるんだけど
7269:2006/02/26(日) 19:42:08
それから数図形なんてネタに決まってるだろうがw
もう少し頭を柔らかくしろよ。そんなんじゃ良い
研究者になれないぞ
73132人目の素数さん:2006/02/26(日) 23:03:31
竹内外史-山口人生
74132人目の素数さん:2006/02/26(日) 23:05:43
>>69
俺も冷静さが足りなかったようだ。申し分けない。
75132人目の素数さん:2006/03/02(木) 19:11:18
330
76132人目の素数さん:2006/03/04(土) 06:44:39
アルゴリズムの記述の仕方って論文によってまちまちだけど共通のスタイルファイルとかないの?
77132人目の素数さん:2006/03/06(月) 15:45:10
age
78132人目の素数さん:2006/03/26(日) 14:11:50
79132人目の素数さん:2006/04/03(月) 18:28:05
あっちむいてふたりでまえならえ
80132人目の素数さん:2006/04/05(水) 22:08:13
age
81132人目の素数さん:2006/04/08(土) 23:28:49
あるアルゴリズムの研究者(すまそ名前忘れた)が言ってたのを
又聞きしたんだが、

「NP-Completeな問題には実用的な近似解アルゴリズムが比較的
多くある。PSPACE-Completeな問題には実用的な近似解アルゴ
リズムはほとんど見つからない。」

だそうだ。そんなもん?
PSPACE-Completeな問題なんて、その辺にいくらでも転がってる
気がするんだけど、みんな実用的時間じゃ解けないの?
82132人目の素数さん:2006/04/10(月) 11:44:25
2 人ゲームの先手(後手)必勝判定問題はゲームにループがなければ
PSPACE-Complete(ATIME(poly)-Complete)。
オセロが後手必勝かどうかは 6x6 では分かってるけど、
8x8はまだ未解決だと思う。
83132人目の素数さん:2006/04/15(土) 12:02:11
age
84132人目の素数さん:2006/04/15(土) 13:11:07
可積分系とアルゴリズムが関係アルらしいね。 不思議だ。
85132人目の素数さん:2006/04/29(土) 04:00:42
うん。崖の端から外に向かってブロックをどれだけ積めるのかをアルゴリズムを使って証明。
86132人目の素数さん:2006/04/29(土) 04:03:18
log
87132人目の素数さん:2006/05/13(土) 21:26:24
380
88132人目の素数さん:2006/05/21(日) 23:45:23
>>82
> 2 人ゲームの先手(後手)必勝判定問題はゲームにループがなければ
> PSPACE-Complete(ATIME(poly)-Complete)。

すごいいいきりようだな
俺は2人ゲームで先手必勝判定問題がPに属するようなループのないゲームを
いくらでも設計できるが
89132人目の素数さん:2006/05/22(月) 04:14:35
age
90132人目の素数さん:2006/05/22(月) 09:57:32
>>88
そうそう。f(x)=x とか自明な充足可能性問題もあるもんね。
インスタンスと問題の区別がつかないと、計算量理論は理解不能だよね。
91132人目の素数さん:2006/06/15(木) 23:54:37
913
92132人目の素数さん:2006/06/17(土) 21:33:43
>>82
将棋はループはないが多項式じゃ無理だぞ。
EXPSPACEあれば十分だけど、EXPやNEXPで解けるのかな。
93132人目の素数さん:2006/06/18(日) 05:39:24
age
94132人目の素数さん:2006/07/07(金) 10:34:32
>>92
一応マジレスしとくと将棋は定数時間で解けるね
あとはどう一般化するかしだいでしょ
95132人目の素数さん:2006/07/07(金) 13:43:55
age
96132人目の素数さん:2006/07/08(土) 21:01:31
>>94
釣りか?
97132人目の素数さん:2006/07/09(日) 11:03:44
>>96がどういう意味で釣りか?といっているのが気になる

定数時間で解けるわけねーじゃんという意味なのか
定数時間で解けるのは当り前だけど>>92がいいたいのはそういうことじゃねーだろという意味か
98132人目の素数さん:2006/07/10(月) 04:46:29
もちろん後半だろ?
99132人目の素数さん:2006/07/28(金) 17:03:57
500
100132人目の素数さん:2006/08/30(水) 15:25:59
! 100 !
101132人目の素数さん:2006/08/30(水) 15:43:35
780
102132人目の素数さん:2006/10/02(月) 23:58:42
803
103132人目の素数さん:2006/10/25(水) 05:46:51
良スレage
104132人目の素数さん
602