0-1原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/06/01 06:18 UTC 版)
「ソーティングネットワーク」の記事における「0-1原理」の解説
挿入ソートやバブルソートのネットワークのように、簡単に正当性を示せるソーティングネットワークも存在するが、正当性が常に簡単に示せるとは限らない。n 本のワイヤからなるネットワークに対し、 n ! {\displaystyle n!} 通り全ての場合を試すには、（大きなネットワークでは特に）時間がかかる。しかし、いわゆる0-1原理（zero-one principle）によれば、実際には遥かに少ない試行で十分である。 0-1原理とは、「あるネットワークが0と1からなる 2 n {\displaystyle 2^{n}} 通りの数列全てをソートすることが出来れば、それは正当なソーティングネットワークである」というものである。0-1原理によって、ソーティングネットワークの正当性を確かめるのに必要な試行の回数は大幅に減る。0-1原理は、様々なソーティングネットワークを構成するためにも有用である。 この原理の証明の大枠は次の通り。 初めに、今、正当性を証明したいn本のワイヤからなるあるネットワークが、n個の数列a1, ..., anを入力された時、b1, ..., bnと出力すると考える。この時、この入力列に対して単調増加関数fを適用し、入力列をf(a1), ..., f(an)に変換しても、このネットワークの出力はf(b1), ..., f(bn)の順となるはずである。これを示すには、まずx,yの2つの値が入力されるネットワーク（2本のワイヤと1つのコンパレータからのみ構成されている）について考える。この入力列にfを適用（つまりx,yをf(x),f(y)に変換）し、対象のネットワークに入力すれば出力はmin(f(x), f(y)) = f(min(x, y)),max(f(x), f(y)) = f(max(x, y))を満たす。これは、元の入力列と同じ順序を守っていることに他ならない。これを数学的帰納法によって拡張し、n本のワイヤについて証明できる。 このようにfによって出力の順番は保たれることを考えれば、今考えているネットワークがこの入力列を正しくソートできない時、同様に変換後の入力列f(a1), ..., f(an)も正しくソートできないはずである。この対偶によって、単調増加関数fについてf(a1), ..., f(an)が正しくソートできることを示すことができれば、元の入力列も正しくソートできることになる。ここで、入力列a1, ..., anについて、列中のいずれかの値より小さくなる値、つまりあるjに対してai < ajとなるようなiを選び、fを f ( x ) = { 1 if x> a i 0 otherwise. {\displaystyle f(x)={\begin{cases}1\ &{\mbox{if }}x>a_{i}\\0\ &{\mbox{otherwise.}}\end{cases}}} とする。これは単調増加関数であるため上記の条件を満たし、かつ、変換後の入力列は0と1のみからなる。 以上より、0と1のみからなる数列が対象のネットワークで正しくソートできていることが示されていれば、任意の入力値に対しても正しくソートできることの証明となる。 0-1原理は、W. G. Bouriciusによって1954年に証明されたBouriciusの定理の特別な場合である。
※この「0-1原理」の解説は、「ソーティングネットワーク」の解説の一部です。
「0-1原理」を含む「ソーティングネットワーク」の記事については、「ソーティングネットワーク」の概要を参照ください。
- 0-1原理のページへのリンク
