| 講演抄録／キーワード |
| 講演名 |
2004-10-15 15:05
DNA計算における対数時間ソートアルゴリズム
○蘆塚正一・藤原暁宏（九工大） |
| 抄録 |
（和） |
近年の高性能計算に関する研究において，非シリコン型計算の1つとして，DNA分子を用いて計算を行うDNA計算が注目を集めている．本研究では，基本操作の1つである$n$要素のソートに対する対数時間のアルゴリズムを提案する．このソートアルゴリズムの入力は，$O（mn）$種類の一本鎖DNAで表現された$n$個の$m$ビットの2進数の集合である．この入力に対して，提案アルゴリズムは，$O（mn^{2}）$種類の一本鎖DNAを用いることにより，$O（\log n）$ステップでソートを実行することができる． |
| （英） |
In this paper, we propose a polylogarithmic procedure for sorting of $n$ elements. An input of the procedure is a set of $n$ binary numbers of $m$ bits, and each number is stored in $O(m)$ DNA strands. For the input, the proposed procedure runs in $O(log n)$ step using $O(mn^{2})$ DNA strands. |
| キーワード |
（和） |
DNA計算 / ソート / / / / / / |
| （英） |
DNA computing / sort / / / / / / |
| 文献情報 |
信学技報, vol. 104, no. 339, COMP2004-48, pp. 33-40, 2004年10月. |
| 資料番号 |
COMP2004-48 |
| 発行日 |
2004-10-07 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|