翻訳と辞書 Words near each other ・ 通信筒 ・ 通信簿 ・ 通信簿〜SARUGANSEKI SINGLES〜 ・ 通信網 ・ 通信総合研究所 ・ 通信線路 ・ 通信行政板 ・ 通信衛星 ・ 通信表 ・ 通信装置 ・ 通信複雑性 ・ 通信課程 ・ 通信講座 ・ 通信販売 ・ 通信費 ・ 通信路 ・ 通信路容量 ・ 通信速度 ・ 通信陸上 ・ 通元寺村 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 通信複雑性 ： ウィキペディア日本語版 通信複雑性[つうしんふくざつせい] 通信複雑性（つうしんふくざつせい、Communication Complexity、CC）は、1979年にアンドリュー・チーチー・ヤオによって導入された用語。ヤオは2つの個体間の通信問題を研究していた。アリスは n ビットの文字列 x を受信し、ボブも別の n ビットの文字列 y を受信する。目標は両者のいずれかが最小限の通信によって関数 f(x,y) を計算することである。ここでは、計算のステップ数を問題にしているのでも、計算に必要なメモリ量を問題にしているのでもない。通信複雑性とは、このような分散計算で必要となる通信の量を測るものである。 もちろん、上記の例でアリスが n ビットの文字列全体をボブに送ってしまえば、ボブがその関数を計算でき、問題は解決する。しかし、ここで考えているのは、n ビットより少ない通信量で関数を計算する賢い手法の探索である。 この抽象的な問題は様々な場面で応用できる。VLSIの回路設計では、消費電力を低減させるために、ある部分から別の部分に流れる信号の量を最小化したい場合がある。他にもデータ構造の研究やコンピュータネットワークの最適化にも関連する。応用に関しては、参考文献にある Kushilevitz と Nisan の著書に詳しい。 == 形式的定義 == $f$: X $\backslash times$ Y $\backslash rightarrow$ Z としたとき、一般に $X=Y=\backslash ^n$ および $Z=\backslash$ と仮定する。アリスは n ビットの文字列 $x$ $\backslash in$ X を持ち、ボブは n ビットの文字列 $y$ $\backslash in$ Y を持つ。一度に 1ビットずつ両者間で通信を行い（何らかの通信プロトコルが適用される）、アリスとボブは最終的にいずれかが $f(x,y)$ の値を計算できるようにしたい。取り決めとして、一方で答えが判明したらもう一方にあと 1ビットの通信をするだけで全通信が完了するものとする。この通信プロトコルの最悪の通信複雑性（$D(f)$ で表される）は次のように定義される。 ここで関数 $f$ を行列 $A$（入力行列と呼ぶ）として考えるのが便利である。この行列の行は $x$ $\backslash in$ X に対応して並んでおり、列は $y$ $\backslash in$ Y に対応して並んでいる。入力行列の各要素は $A\_=f(x,y)$ である。初期状態でアリスもボブも行列 A 全体を知っている（つまり、両者は関数 $f$ を知っている）。そうすると、関数の値の計算問題は対応する行列の要素を選び取る問題に変換される。この問題はアリスかボブのどちらかが $x$ と $y$ の両方を知った時点で答えがわかる。通信を開始するとき、答えとしてありうるのは行列の全要素なので $n^2$ 個存在する。その後、互いに 1ビットずつ通信すると、解ではあり得ない行や列が除外されていく。 より形式的に表現すると、集合 R $\backslash subseteq$ X $\backslash times$ Y があり、$(x\_1,y\_1)$ $\backslash in$ R かつ $(x\_2,y\_2)$ $\backslash in$ R のとき常に $(x\_1,y\_2)$ $\backslash in$ R ならば、R を長方形であるという。また、R を R = M $\backslash times$ N （ただし、M $\backslash subseteq$ X かつ N $\backslash subseteq$ Y）であるような A の部分行列と見ることもできる。既に $k$ ビットの情報をやり取りした状態を考えて見よう。ある $h$ $\backslash in$ $\backslash ^k$ について、次のように行列が定義される。 ここで、$T\_$ $\backslash subseteq$ X $\backslash times$ Y であり、$T\_$ は長方形であると同時に A の部分行列である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「通信複雑性」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.