学位論文 11入力ソーティングネットワークの最小サイズの解析

望月, 翔太  ,  モチヅキ, ショウタ  ,  Mochiduki, Shota

pp.1 - 250 , 2016-03-25 , The University of Electro-Communications
内容記述
ソーティングネットワークとは、任意の数列をソートするネットワークである。ソーティングネットワークは複数の入出力ワイヤーと比較器から構成される。比較器は、2つの入力と出力をもち、2つの値が入力されると、小さい方の値を上のワイヤーに、大きい方の値を下のワイヤーに出力する。本研究で扱う11入力ソーティングネットワークは、11個の値からなる任意の数列をソートするネットワークである。 ?(n)とは、n入力ソーティングネットワークを構成するために必要な最小の比較器の数のことである。1964年-1966年のFloydとKunthの研究により、n ? 8に対する?(n)の値がわかった。しかし、n > 8に対する?(n)の値はわかっていなかった。しかし近年、9入力ソーティングネットワークを構成するために必要な最小の比較器の数?(9)について、?(9) = 25 となることが示された。また、10入力ソーティングネットワークを構成するために必要な最小の比較器の数?(10)について、?(10) = 29 となることが示された。 本研究では、11入力ソーティングネットワークを構成するために必要な最小の比較器の数?(11)について解析を行った。解析では、11入力ソーティングネットワークにおける入力の最小値を決定するネットワーク部に注目した。結論として、?(11) ≧ 34 となることを示した。論文の構成としては、まず第2章で11入力ソーティングネットワークについて説明を行う。次に第3章では、11入力ソーティングネットワークにおけるmin木というものを定義し、説明を行う。第4章では、第5章以降の証明で用いる定理について説明を行う。第5章~第11章では、11入力ソーティングネットワークにおけるmin木の構造ごとに、?(11) ≧ 34 となる証明を行う。最後に今後の課題を述べて本研究の結びとする。

このアイテムのアクセス数:  回

その他の情報