決定論的および非決定性決定木の時間および空間複雑性【JST・京大機械翻訳】

Moshkov Mikhail

プレプリント

J-GLOBAL ID：202202211667327070 整理番号：22P0023250

決定論的および非決定性決定木の時間および空間複雑性【JST・京大機械翻訳】

Time and space complexity of deterministic and nondeterministic decision trees

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (1件)：
資料名：
発行年： 2022年01月04日プレプリントサーバーでの情報更新日： 2022年01月04日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

本論文では,母集団と呼ばれる無限集合と,宇宙上で定義された2値関数(属性)の無限集合から成る任意の無限二値情報システムを研究した。属性の有限数および属性値の各タプルに対する決定に対応するマッピングにより記述される情報システム上の問題の概念を考察した。問題解決のためのアルゴリズムとして,決定論的および非決定論的決定木を用いた。時間と空間の複雑性として,決定木におけるノードの深さと数を研究した。最悪の場合,問題記述における属性数の成長により,(i)決定論的決定木の最小深度は,対数または線形的に,(ii)非決定論的決定木の最小深度は,一定または線形的に,(iii)決定論的決定木におけるノードの最小数は,多項式または指数関数的成長のいずれかを持ち,そして(iv)非決定論的決定木における最小ノード数は,多項式または指数関数的成長のいずれかを持った。これらの結果に基づいて,著者らは,すべての無限バイナリ情報システムのセットを5つの複雑性クラスに分割して,ディシジョンツリーのための時間-空間トレードオフに関連した各々のクラス問題を研究した。【JST・京大機械翻訳】

, , , , , , , , , , , ,
, , , 【Automatic Indexing@JST】

人工知能

, ,

前のページに戻る