基于膜計(jì)算的算術(shù)運(yùn)算研究.pdf

1、膜系統(tǒng)的基本模型由膜結(jié)構(gòu)組成，膜結(jié)構(gòu)又由一些細(xì)胞膜構(gòu)成，它們分層地嵌套在稱(chēng)為皮膚的主膜里，我們一般用廣義表來(lái)表示膜結(jié)構(gòu)。膜劃分區(qū)域，并包含了一些物質(zhì)在里面，每種物質(zhì)通常不只一種。用多重集來(lái)表示膜中的物質(zhì)，多重集的表示是無(wú)序的。
　　 膜結(jié)構(gòu)由一些類(lèi)細(xì)胞的膜組成，嵌套地分布在稱(chēng)為“皮膚”的特殊膜里。在由膜劃分的區(qū)域里存在著多種物質(zhì)，這些的物質(zhì)進(jìn)化包括：一種物質(zhì)可以轉(zhuǎn)變?yōu)槠渌囊环N或多種物質(zhì)，它們可以到達(dá)某個(gè)特定的膜。進(jìn)化過(guò)程中，可

2、以產(chǎn)生新的膜，已存在的膜可以被溶解。生物細(xì)胞膜的這些特征被模擬出來(lái)，成為一種分布的、并行的基于膜結(jié)構(gòu)中的進(jìn)化規(guī)則的計(jì)算模型，稱(chēng)為P系統(tǒng)。
　　 對(duì)P系統(tǒng)的研究開(kāi)始于羅馬尼亞Gheorghe Paun教授2000年發(fā)表的著名論文“Computing with membranes”。本文首先對(duì)P系統(tǒng)進(jìn)行了綜述，討論了膜結(jié)構(gòu)的表示方法。其次，介紹了幾種基本的膜結(jié)構(gòu)計(jì)算模型，包括轉(zhuǎn)移P系統(tǒng)、重寫(xiě)P系統(tǒng)和剪接P系統(tǒng)。簡(jiǎn)要討論了帶活性膜的P

3、系統(tǒng)。最近的研究指出，帶有活性膜的P系統(tǒng)可以在線(xiàn)性時(shí)間內(nèi)解決NP完全問(wèn)題。第三，給出了用膜計(jì)算進(jìn)行算術(shù)運(yùn)算的有效方法，討論了相應(yīng)的膜結(jié)構(gòu)和計(jì)算原理。第四，設(shè)計(jì)并實(shí)現(xiàn)了基于膜計(jì)算的算術(shù)運(yùn)算仿真程序。在模擬的過(guò)程中最主要的是表示數(shù)字的物質(zhì)表示，進(jìn)化規(guī)則的執(zhí)行，以及進(jìn)化規(guī)則對(duì)物質(zhì)改變。第五，總結(jié)了膜計(jì)算中進(jìn)一步研究的問(wèn)題。
　　 對(duì)P系統(tǒng)的研究，目前僅僅是一個(gè)開(kāi)端。已有的研究成果表明：P系統(tǒng)是一種性能良好的并行計(jì)算模型，在解決NP類(lèi)問(wèn)