著者

徳丸 雄一 藤原 暁宏

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.23, pp.25-32, 2007-03-09

参考文献数

20

---

本研究では DNA計算を用いて浮動小数点数の演算を行うアルゴリズムを提案する. まずはじめに DNAによる浮動小数点表現を定義する. 本研究で取り扱う浮動小数点数は符号部 指数部 仮数部から構成され 符号部は1ビットの2進数であり また 指数部と仮数部は それぞれqビットとmビットの2進数であるものとする. 次に 浮動小数点数対に対して加算を行う2つのアルゴリズムを提案する. 1つ目のアルゴリズムはO(m^{2})種類のDNAを用いることによりO(log m)ステップで実行可能であり 2つ目のアルゴリズムはO(m^{2}2^{m})種類のDNAを用いることによりO(1)ステップで実行可能である. また O(n)個の対に対する浮動小数点数の加算を行うアルゴリズムも提案する. このアルゴリズムは O(nm^{2}2^{m})種類のDNAを用いることにより O(1)ステップで実行可能である. また最後に 浮動小数点数の乗算を行うアルゴリズムを提案する. このアルゴリズムO(m^{2})種類のDNAを用いることによりO(log m)ステップで実行可能である.In this paper, we consider procedures for floating point arithmeticoperations with DNA molecules. We first propose data structure for representing floating point numbers with DNA molecules. The floatingpoint number consists of a sign bit, an exponent and a mantissa. We assume that the exponent and the mantissa are binary numbers of q andm bits, respectively. We next propose two procedures for an addition of floating point numbers. The first procedure executes an addition inO(log m) steps using O(m^{2}) DNA strands, and the second procedure executes an addition in O(1) steps using O(m^{2}2^{m}) DNA strands. Wealso propose a procedure for additions of O(n) pairs of two floating point numbers. The procedure executes O(n) additions simultaneously inO(1) steps using O(nm^{2}2^{m}) DNA strands. We finally propose a procedure for a multiplication of a pair of two floating pointnumbers. The procedure executes a multiplication in O(log m) steps using O(m^{2}) DNA strands.

著者

牛島 瑞恵 藤原 暁宏

出版者

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

雑誌

電子情報通信学会技術研究報告. 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)ステップでソートを実行可能である.

著者

藤原 暁宏 石水 隆 井上 美智子 増澤 利光 藤原 秀雄

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. PRO, [プログラミング]

巻号頁・発行日

vol.98, no.30, pp.129-136, 1998-03-23

---

本稿では, 近年注目されている並列計算モデルであるCGMモデル及びBSPモデル上で, 要素数nの選択及びソートを行う決定性の並列アルゴリズムを提案する.まず最初に, 内部計算時間がO(n/p)時間, 通信ラウンド数がO(min(log p, loglog n)のコスト最適な選択を行う並列アルゴリズムを提案する.次に内部計算時間がO(n/p log p)時間, 定数通信ラウンド数の通信ラウンド数が最適な並列アルゴリズムを提案する.上記の2つのアルゴリズムは, n/p≥P^εかつε>0を満たすプロセッサ数pに対して動作する.最後に, 2つ目の選択アルゴリズムの拡張として, n/p≥P^2を満たすpに対して, O(n/p log n)時間, 定数通信ラウンド数でソートを行うアルゴリズムを提案する.

著者

中島 孝明 藤原 暁宏

出版者

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

雑誌

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

巻号頁・発行日

vol.101, no.431, pp.1-6, 2001-11-09

参考文献数

9

---

本稿では, 並列化困難な問題として知られているP完全問題の一つである, スタックを用いた幅優先探索の並列性について検証する.まず, 入力グラフの最大次数が3であるようなスタックを用いた幅優先探索もP完全となることを示す.次に, スタックを用いた幅優先探索のP完全性を表す尺度として最長経路距離を導入し, この尺度を用いて, 効率の良い並列アルゴリズムの提案を行う.このアルゴリズムの計算量により, l=O(log^n)の場合, スタックを用いた幅優先探索がクラスNCに属することを示す.ここで, n, lはそれぞれ入力サイズおよび最長経路距離であり, kは正の整数とする.また, このアルゴリズムはl=O(n^ε), 0<ε<1の場合にコスト最適な並列アルゴリズムとなる.