【摘要】：分子計(jì)算又稱DNA計(jì)算，具有高度并行性、巨大存儲容量和極低的能耗，理論上能快速求解NPC（Non-deterministic Polynomial complete problem）問題，是一種全新的多值編碼和并行計(jì)算方法，它突破了圖靈機(jī)和馮諾曼體系限制，有指數(shù)的加速比、空間交換時間、指數(shù)的并行度和獲得全體解集等特點(diǎn)。本文研究了一個新的并行系統(tǒng)，即廣義分子計(jì)算模型，該模型運(yùn)用了sopc（片上系統(tǒng)）技術(shù)和分子計(jì)算思想結(jié)合的方法，是一種電子DNA模型，該模型實(shí)現(xiàn)了以空間換時間的目的，能夠在多項(xiàng)式時間內(nèi)解決完全NP問題。 論文主要研究工作如下： （1）討論了基于分子計(jì)算的電子方式的并行處理機(jī)模型的結(jié)構(gòu)和特征，系統(tǒng)地對分子計(jì)算方法、原理、主要實(shí)現(xiàn)方式和優(yōu)缺點(diǎn)等方面進(jìn)行了比對和總結(jié)； （2）論文提出了一種基于大規(guī)模集成電路設(shè)計(jì)的DNA計(jì)算實(shí)現(xiàn)方式，構(gòu)建了一個完整的計(jì)算機(jī)系統(tǒng)，該系統(tǒng)相對于傳統(tǒng)的計(jì)算機(jī)具有自己獨(dú)特的優(yōu)勢，它克服了傳統(tǒng)計(jì)算機(jī)解決NPC問題的時間并行性，使得它能夠同時搜索獲得所有的結(jié)論； （3）運(yùn)用VHDL編寫硬件語言，解決了具有可擴(kuò)展性的解決SAT問題的算法，并用實(shí)例問題對算法的正確性進(jìn)行了驗(yàn)證； （4）運(yùn)用廣義分子計(jì)算模型，探討了0-1背包問題，并在FPGA上實(shí)現(xiàn)，，驗(yàn)證了算法的正確性。
[Abstract]:Molecular computing, also known as DNA computing, has high parallelism, huge storage capacity and extremely low energy consumption. It can solve NPC (Non-deterministic Polynomial complete problem) problem quickly in theory, which is a new multi-value coding and parallel computing method. It breaks through the limitation of Turing machine and von Norman system, and has the characteristics of exponential speedup, space exchange time, parallel degree of exponent and obtaining all solution sets. In this paper, a new parallel system, the generalized molecular computing model, is studied. The model combines sopc (system on Chip) technology with the idea of molecular computing. It is an electronic DNA model, which realizes the purpose of exchanging time by space. It can solve the complete NP problem in polynomial time. The main work of this paper is as follows: (1) the structure and characteristics of the parallel processor model based on the electronic method of molecular computing are discussed, and the methods and principles of molecular computing are systematically discussed. The main ways of implementation and advantages and disadvantages are compared and summarized; (2) in this paper, a DNA computing implementation method based on LSI is proposed, and a complete computer system is constructed, which has its own unique advantages compared with the traditional computer. It overcomes the time parallelism of the traditional computer to solve the NPC problem, and makes it possible to simultaneously search and obtain all the conclusions. (3) using VHDL to write hardware language, the extensible algorithm for solving SAT problem is solved, and the correctness of the algorithm is verified by an example problem. (4) the 0-1 knapsack problem is discussed by using the generalized molecular model and implemented on FPGA to verify the correctness of the algorithm.
【學(xué)位授予單位】：北京理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP301.6;TN791

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 高琳,許進(jìn),張軍英;DNA計(jì)算的研究進(jìn)展與展望[J];電子學(xué)報;2001年07期

2 殷志祥,張鳳月,許進(jìn);0-1規(guī)劃問題的DNA計(jì)算[J];電子與信息學(xué)報;2003年01期

3 張慶友,許祿;DNA編碼序列的圖形表示及相似度計(jì)算[J];高等學(xué)�；瘜W(xué)學(xué)報;2002年07期

4 周康;殷燕芳;李玉華;覃磊;;DNA編碼的模型分析[J];華中科技大學(xué)學(xué)報(自然科學(xué)版);2007年07期

5 王子成;周康;羅亮;強(qiáng)小利;;DNA計(jì)算中編碼序列的過濾函數(shù)研究[J];計(jì)算機(jī)工程與應(yīng)用;2008年32期

6 李人厚,余文;關(guān)于DNA計(jì)算的基本原理與探討[J];計(jì)算機(jī)學(xué)報;2001年09期

7 許進(jìn),張雷;DNA計(jì)算機(jī)原理、進(jìn)展及難點(diǎn)(Ⅰ):生物計(jì)算系統(tǒng)及其在圖論中的應(yīng)用[J];計(jì)算機(jī)學(xué)報;2003年01期

8 許進(jìn),李三平,董亞非,魏小鵬;粘貼DNA計(jì)算機(jī)模型(Ⅱ):應(yīng)用[J];科學(xué)通報;2004年04期

9 李源,方辰,歐陽頎;最大集團(tuán)問題的DNA計(jì)算機(jī)進(jìn)化算法[J];科學(xué)通報;2004年05期

10 李艷梅;余文;寧建國;;一種廣義分子計(jì)算模型及其在NP問題中的應(yīng)用[J];計(jì)算機(jī)應(yīng)用研究;2014年11期

本文編號：2389560