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

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

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

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

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