抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ソーティングは,ペアワイズ比較を用いてn要素の規則化タスクである。m=Θ(nlogn)比較は,比較の結果がノイズなしで観察されるとき,必要かつ十分であることはよく知られている。本論文では,雑音の存在におけるソーティング問題を研究した。与えられた望ましい誤差確率を達成するためにペアワイズ比較mの数を最小化することを狙った文献における一般的手法とは異なり,著者らは,質問E[M]の予想数を有するランダム化アルゴリズムを考察し,要素の規則化が漸近的に消失誤差確率で推定できるように,最大比nlogn/E[M]を特徴付けることを目指した。最大比は,雑音のあるソーティング能力と呼ばれる。本研究では,雑音のあるソーティング容量に関する上限と下限を導出した。2つの下限,1つは固定長アルゴリズム,1つは可変長アルゴリズムである。提案アルゴリズムは,フィードバックによる雑音探索とチャネル符号化の間の接続を利用し,フィードバックによるチャネル符号化のためのBurnashev-Zigangiovアルゴリズムによる挿入ソートアルゴリズムを組み込んだ。さらに,著者らは,挿入ソートに基づくアルゴリズムの達成可能な速度のために,ノイズのある分類能力と上限のための上限を引き出した。【JST・京大機械翻訳】
