@misc{oai:uec.repo.nii.ac.jp:00008473,
 author = {古川, 智裕},
 month = {2017-03-13, 2017-03-13},
 note = {2016, ソーティングネットワークとは、並列的に比較演算を行う演算モデルである比較ネットワークの一種でどのような数列を入力しても必ずソートされた数列を出力するものである。ソーティングネットワークは入出力を行う複数のワイヤ、2つのワイヤの数値を比較し小さい値を上のワイヤ、大きい値を下のワイヤに出力する比較器という二つのものからなる。
　ソーティングネットワークの評価基準としては比較器の数、すなわち全体の比較演算の回数を表すサイズ、並列的な比較演算の単位時間を表す深さの二種類があるが、本研究ではサイズを扱うものとする。Ŝ(n)はn入力ソーティングネットワークを構成するのに必要な最小サイズを表す。
　ソーティングネットワークの最小サイズに対する研究は1964年～1966年のFloydとKnuthの研究に始まり、2014年にCodishらが9入力および10入力について最小サイズを決定した。さらに電気通信大学の平成27年度の修士論文で望月がŜ(11)≧34の証明を行ったが、場合分けが非常に多く250ページ超の膨大なものとなってしまった。
　そこで本研究では、Ŝ(11)≧34の証明を見直し、場合分けのパターンを単純化すること、またその証明手法を用いて他の入力数のソーティングネットワークの下界について新結果を得ることを目的とした。結論として、Ŝ(11)≧34の証明については最小値の通る経路min木に対してt値という値を定義して場合分けの削減を行い、また13入力、15入力、16入力ソーティングネットワークに対してそれぞれŜ(13)≧43、Ŝ(15)≧52、Ŝ(16)≧57という新結果を得た。
　論文の構成としては、第2章ではソーティングネットワークについての簡単な説明および先行研究を示す。第3章では平成27年度からの課題のŜ(11)≧34の証明の単純化に取り組む。第4章および第5章では単純化した証明手法を用いて13入力および15入力ソーティングネットワークの最小サイズの下界についてそれぞれ解析を行う。第6章では16入力ソーティングネットワーク最小サイズの下界を更新している。第7章では研究の中で予想を立てたが重要な結果は得られなかったいくつかの事柄に触れる。最後に第8章では今後の研究への展望を述べ、結びとする。},
 title = {ソーティングネットワークの最小サイズに対する下界},
 year = {},
 yomi = {フルカワ, トモヒロ}
}