- 1 名前：デフォルトの名無しさん [2008/05/31(土) 15:57:02 ]
- やばい！論文書きます
- 156 名前：デフォルトの名無しさん mailto:sage [2012/01/20(金) 22:33:47.52 ]
- >>153
まあ数学者は計算が有限時間で終わるかどうかにしか興味ないから
- 157 名前：デフォルトの名無しさん mailto:sage [2012/01/20(金) 22:53:10.42 ]
- >>145
対応できる入力のサイズに上限があるからそもそもO記法の適用範囲ではない。
(データに応じてテーブルを大きくするんじゃなくて、どんなサイズのデータにも
対応できるテーブルをあらかじめ用意していないとダメ)
チューリングマシンのテープの長さは無限だけど、あらかじめ書きこんでおける
空白以外の記号は高々有限個だけ。
つまりあらかじめ用意しておけるテーブルのサイズも高々有限
- 158 名前：デフォルトの名無しさん [2012/01/22(日) 17:45:39.00 ]
- >>156
んなわけないだろ、だったらＰとかＮＰとかの発想出てこねえよ
ＰだってＮＰだって有限時間で終わるけど興味の対象だろうがよ
- 159 名前：デフォルトの名無しさん [2012/01/22(日) 17:47:10.56 ]
- ΩとかΘ記号の話が出てこないようじゃ話してる人のレベルが知れるな
記号はＯだけじゃないぞ
- 160 名前：デフォルトの名無しさん mailto:sage [2012/01/22(日) 19:22:33.28 ]
- >>159
いずれの記号もnを無限に大きくできなければ適用できない
- 161 名前：デフォルトの名無しさん mailto:sage [2012/01/22(日) 19:26:15.84 ]
- >>158
「数学者は」というのは一般化しすぎだったけど計算可能解析学のマイナーさを考えたら
大半の数学者が興味持ってないのは事実だろ。
有限時間内での計算量を扱う分野は数学ではなくて計算機科学に分類されることが多いし
- 162 名前：デフォルトの名無しさん mailto:sage [2012/01/23(月) 15:40:36.27 ]
- >>161
多くの数学者にとっても計算時間は重要じゃね？
無限に時間を使っていいならこの世どころかあの世も含め
すべての事象は計算可能なわけだし。
- 163 名前：デフォルトの名無しさん mailto:sage [2012/01/23(月) 20:55:50.37 ]
- >>162
またまたー
じゃあ停止問題解いてみろよ
- 164 名前：デフォルトの名無しさん mailto:sage [2012/01/23(月) 21:50:40.32 ]
- 問題を解くのに無限の時間がかかるってのは解けるって言うのか
- 165 名前：デフォルトの名無しさん mailto:sage [2012/01/26(木) 22:18:27.41 ]
- >>163
無限時間チューリング機械なら停止問題は解けるよ
そもそも無限に時間を使っていいなんて言った覚えはないけど。
数学者は無限でなければ気にしないとは言ったが
- 166 名前：デフォルトの名無しさん mailto:sage [2012/01/30(月) 20:12:24.96 ]
- 英語版Wikipediaにはちゃんと中央値を求める線形時間アルゴリズムが載ってた
https://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm
わかってたことだがやっぱ日本語版はうんこだ
- 167 名前：デフォルトの名無しさん mailto:sage [2012/01/30(月) 21:03:23.16 ]
- >>166
それじゃ、日本語版を改善してやってくれ。
- 168 名前：デフォルトの名無しさん mailto:sage [2012/01/30(月) 21:51:36.13 ]
- 日本語版「ん？」
選択アルゴリズム - Wikipedia
ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
|
 |
