著者
牛島 瑞恵 藤原 暁宏
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. 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)ステップでソートを実行可能である.

言及状況

Twitter (2 users, 6 posts, 1 favorites)

こんな論文どうですか? DNA計算における奇偶転換ソート及びシェアソートアルゴリズム(牛島 瑞恵ほか),2004 https://t.co/jqKQEP9N0T
こんな論文どうですか? DNA計算における奇偶転換ソート及びシェアソートアルゴリズム(牛島 瑞恵ほか),2004 https://t.co/jqKQEP9N0T
こんな論文どうですか? DNA計算における奇偶転換ソート及びシェアソートアルゴリズム(牛島 瑞恵ほか),2004 https://t.co/jqKQEP9N0T
2 2 https://t.co/I1NPVoXEz7 https://t.co/lexiSHtrK5
1 1 https://t.co/teDSFaVIT1 https://t.co/5UkO4qozQI
こんな論文どうですか? DNA計算における奇偶転換ソート及びシェアソートアルゴリズム(牛島 瑞恵ほか),2004 https://t.co/jqKQEP9N0T

収集済み URL リスト