抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
クエリゲームは,質問のセットQと関数のセットF,または符号語f:Q→Zのペアである。これを2層ゲームとして考えた。1つのプレーヤー,コーデーカーは隠れ符号語f∈Fをピックアップする。他のプレーヤー,コードブレーカーは,各コードメーカーが値f(q)で応答しなければならない後に,質問q∈Qのシーケンスを問うことによりfを決定することを試みる。コードブレーカーの目標は,できるだけ少ないクエリを用いてfを一意的に決定することである。そのようなゲームの2つの古典的用例は,スプリングスケール,および,レクリエーションゲームとして,そして,情報理論へのそれらの接続の両方として興味があるMastermindとのコイン-weighingである。本論文では,クエリゲームに対する短い解を見つけるための一般的フレームワークを提示した。応用として,著者らは,コイン-weighing問題の変動の質問複雑性の新しい自己含有証明を与えて,黒-peg情報だけを与えるならば,n位置とk色を有するMastermindの決定論的問い合わせ複雑性がΘ(nlogk/logn+k)であることを証明して,もし黒-と白-peg情報の両方が提供されるならば,Θ(nlogk/logn+k/n)を提供した。決定論的設定では,これらは任意のk≧n ̄1-o(1)で知られているMastermindに対する一定因子最適解である。【JST・京大機械翻訳】