universal distributionの構成について
スポンサーリンク
概要
- 論文の詳細を見る
計算の理論における重要な概念の1つにuniversal distributionの概念がある.universal distributionは,ビット列χに非負実数μ(x)を対応させるある種の関数μであり,長さnのビット列xを確率μ(χ)/(Σ_<|y|=n>μ(y))で入力としてアルゴリズムに与えると,どのようなアルゴリズムにおいてもその最悪実行時間と平均実行時間が入力の長さnの関数として同じオーダーの関数になる,という性質を持つ.universal distributionμ(χ)は,universal prefix-free partial functionをビット0,1が等確率で独立に生成されるようなランダム無限ビット列に適用したときに値がxとなる確率,として定義することができる.本発表では,より一般的な分布のランダム無限ビット列の場合について,同様の確率がuniversal distributionになるか,という問題を考え,次の2つの結果を示す:(1)ある種の分布のランダム無限ビット列の場合には,対応する確率がuniversal distributionにならない;(2)このような確率がuniversal distributionになるためには,Shannonの符合化定理を変形したある命題が成り立つことが必要十分である.
- 社団法人電子情報通信学会の論文
- 1994-09-26
著者
関連論文
- universal distributionの構成について
- 42. あつかいにくい問題 (アルゴリズムの最近の動向)
- 低いKolmogorov complexityを持つ無限ビット列の特徴付け
- On Malign Input Distributions for Algorithms(Mathematical Logic and Applications'92)
- malign measureによるa priori measureの特徴づけについて(理論計算機科学とその周辺)
- A Note on Collapsing Bounded Query Classes
- 無限列の圧縮可能性 (数理情報科学の研究)
- 野下浩平, 高岡忠雄, 町田 元 著, 岩波講座, 情報科学 10, "基本的算法", 岩波書店, A5判, 267p., \2,500, 1983
- 有沢 誠 著, "プログラミングレクリエーション" : ソフトウェア実習のガイド, 近代科学社, A5判, 188p, \1,800, 1978
- List処理およびEmbeddingによる言語の使いやすさの拡大
- C-86. 剰余類の理論による計算機の性能向上
- B-81. Syntaxに基づくコンパイリング
- D-72. Stringを処理する有限オートマトンよりなるシステムによる細胞のシミュレーション