著者

牛島 瑞恵 藤原 暁宏

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.104, no.339, pp.25-32, 2004-10-08

---

近年の高性能計算に関する研究において,非シリコン型計算の1つとしてDNA分子を用いて計算を行うDNA計算が注目を集めている.本研究では,DNAを用いて表現された2進数の集合に対してソートを行うアルゴリズムを2つ提案する.これらのアルゴリズムに対する入力は, O(mn)種類の一本鎖DNAで表現されているn個のmビットの2進数の集合である.本研究では,まず最初に2つのソートアルゴリズムの基本演算として,2つの数を比較し昇順に並べる比較交換操作を定義し,この比較交換操作を効率よく行うアルゴリズムを提案する.このアルゴリズムの計算量はO(n)個の対のmビットの2進数に対してO(1)ステップで実行可能である.次に前述の比較交換操作を用いて奇偶転換ソートに基づくソートアルゴリズムを提案する.このアルゴリズムは,O(mn^2)種類のDNAを用いることによりO(n)ステップでソートを実行可能である.最後に,前述の比較交換操作を用いてシェアソートに基づくソートアルゴリズムを提案する.このアルゴリズムは,O(√n log n)種類のDNAを用いることにより O(mn√n log n)ステップでソートを実行可能である.