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

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

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

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

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