基于DNA計算的算術(shù)P系統(tǒng)研究.pdf

1、根據(jù)“摩爾定律”，傳統(tǒng)計算機(jī)的計算速度日益接近瓶頸，科學(xué)家開始尋找代替?zhèn)鹘y(tǒng)電子計算機(jī)的新型計算模型。目前為止，研究人員已經(jīng)從各種自然現(xiàn)象中抽象出許多計算模型，例如自然計算。DNA計算和膜計算是屬于自然計算的兩個分支。DNA計算是從DNA分子的Watson-Crick互補(bǔ)性和生化反應(yīng)的并行性抽象出來的計算模型。在DNA計算領(lǐng)域，許多NP難問題能夠在多項式時間內(nèi)得到解決。膜計算（也稱P系統(tǒng)）是通過借鑒和模擬生物活細(xì)胞、組織處理化學(xué)物質(zhì)的方式

2、，以建立具有良好計算性能的分布式并行計算模型。已證明膜計算具有和圖靈機(jī)等價的計算能力，可以在多項式時間內(nèi)解決NP難問題。
　　目前，對于DNA計算和膜計算的研究，主要側(cè)重于模型計算能力的研究，即主要考慮NP難問題的解決。但是，在現(xiàn)實生活中的應(yīng)用系統(tǒng)多是解決以數(shù)值計算為主的計算問題，而非NP難問題。算術(shù)運算在自然計算模型中已有一定的研究成果，但是，自然計算模型中算術(shù)運算的并行性，特別是除法并行性的研究還相對匱乏。因此，研究基于DNA

3、和膜計算的計算系統(tǒng)是非常有必要的。本文通過設(shè)計算術(shù)運算口訣表，利用自然計算的并行性，分別實現(xiàn)基于DNA計算和基于膜計算的算術(shù)運算系統(tǒng)，提高了算術(shù)運算的并行性。然后，將DNA計算和膜計算進(jìn)行結(jié)合，探討了基于DNA計算的算術(shù)P系統(tǒng)。本文所完成的研究內(nèi)容如下：
　?、贋樘岣逥NA計算中算術(shù)運算的并行性，我們設(shè)計了算術(shù)運算口訣表（包括加法口訣表、減法口訣表、乘法口訣表和除法口訣表），用于單位數(shù)（單位數(shù)x的取值范圍為0≤x≤9）的四則運算。

4、然后，基于Adleman–Lipton模型，設(shè)計出十進(jìn)制操作數(shù)和四則運算口訣表的DNA編碼方法。在此基礎(chǔ)上，設(shè)計出能夠較好利用DNA計算并行性的四則運算操作。
　?、诨谒阈g(shù)運算口訣表，我們設(shè)計出一種新的算術(shù)P系統(tǒng)。在該系統(tǒng)中，單位數(shù)的算術(shù)運算的進(jìn)化規(guī)則依據(jù)算術(shù)運算口訣表進(jìn)行設(shè)計。相比現(xiàn)有的算術(shù)運算P系統(tǒng)，基于算術(shù)運算口訣表的P系統(tǒng)減少了在乘法和除法的實驗步。
　?、刍诮Y(jié)構(gòu)化對象P系統(tǒng)，我們將結(jié)構(gòu)化對象實例化為DNA鏈，設(shè)