本文關(guān)鍵詞：膜計(jì)算中的邏輯運(yùn)算及其應(yīng)用研究，由筆耕文化傳播整理發(fā)布。

【摘要】：膜計(jì)算是生物計(jì)算中一個(gè)新的分支，，它是從生物體活細(xì)胞的結(jié)構(gòu)和功能中抽象出來的計(jì)算模型。膜計(jì)算也被稱為膜系統(tǒng)或P系統(tǒng)。這個(gè)研究方向由羅馬尼亞科學(xué)家Gheorghe.P un于1998年創(chuàng)立后，就迅速發(fā)展為擁有巨大潛力的研究領(lǐng)域，它給很多領(lǐng)域的重點(diǎn)難點(diǎn)問題帶來了新的求解思路。由于細(xì)胞膜數(shù)量極其龐大，以及生物驅(qū)動(dòng)所需能源非常小，因此此類計(jì)算系統(tǒng)最大的優(yōu)勢就是可以以極大的并行度來實(shí)現(xiàn)計(jì)算，從而獲得遠(yuǎn)遠(yuǎn)超過傳統(tǒng)電子計(jì)算機(jī)的計(jì)算能力。已經(jīng)有研究證明，該模型可以在多項(xiàng)式時(shí)間內(nèi)解決NP-完全問題。 如何實(shí)現(xiàn)算術(shù)、布爾和關(guān)系運(yùn)算都是計(jì)算模型中最基本的問題。目前，算術(shù)運(yùn)算在類細(xì)胞P系統(tǒng)中已有了一定的研究成果。但是布爾運(yùn)算和關(guān)系運(yùn)算在膜計(jì)算領(lǐng)域的實(shí)現(xiàn)還相對匱乏。因此本論文通過對邏輯運(yùn)算、邏輯表達(dá)式求值以及對邏輯運(yùn)算應(yīng)用P系統(tǒng)的研究，來擴(kuò)展邏輯P系統(tǒng)的使用范圍，為生物計(jì)算機(jī)的實(shí)現(xiàn)奠定一定的基礎(chǔ)。下面就簡單介紹一下本論文所完成的研究工作。本文研究的主要工作包括以下幾點(diǎn)： ①根據(jù)膜計(jì)算的基礎(chǔ)思想及執(zhí)行特點(diǎn)，設(shè)計(jì)基于規(guī)則優(yōu)先級的邏輯運(yùn)算P系統(tǒng)，為邏輯表達(dá)式求值的實(shí)現(xiàn)奠定基礎(chǔ)。 ②通過邏輯運(yùn)算進(jìn)化規(guī)則，設(shè)計(jì)了基于邏輯表達(dá)式膜結(jié)構(gòu)的構(gòu)造算法，根據(jù)該算法構(gòu)造了邏輯表達(dá)式求值P系統(tǒng)。 ③由于邏輯命題的可滿足性問題是理論計(jì)算機(jī)科學(xué)和人工智能中的著名問題，特別是關(guān)于命題中合取范式的可滿足性(SAT)問題的研究。因此在以上研究的基礎(chǔ)上，本文選擇NP難問題中的可滿足性問題作為其應(yīng)用進(jìn)行研究，設(shè)計(jì)并構(gòu)造了兩個(gè)求解可滿足性問題全部解(All-SAT)的P系統(tǒng)，其中一個(gè)屬于半統(tǒng)一類型的，另一個(gè)屬于統(tǒng)一類型的P系統(tǒng)。 ④利用電子計(jì)算機(jī)實(shí)現(xiàn)了邏輯表達(dá)式求值、可滿足性問題全部解P系統(tǒng)的模擬仿真實(shí)驗(yàn)，對所構(gòu)造的P系統(tǒng)進(jìn)行了驗(yàn)證。 本文的研究成果進(jìn)一步豐富了膜計(jì)算中邏輯運(yùn)算及表達(dá)式求值研究的理論，并選擇可滿足性問題作為研究實(shí)例，擴(kuò)大了邏輯運(yùn)算P系統(tǒng)的應(yīng)用范圍，可以作為今后解決其他問題的參考。
【關(guān)鍵詞】：邏輯運(yùn)算 表達(dá)式求值 SAT/All-SAT問題 P系統(tǒng) 膜計(jì)算
【學(xué)位授予單位】：重慶大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP38
【目錄】：

• 摘要3-4
• ABSTRACT4-8
• 1 緒論8-12
• 1.1 引言8
• 1.2 國內(nèi)外研究現(xiàn)狀綜述8-10
• 1.3 研究的目的及意義10-11
• 1.4 本文結(jié)構(gòu)及安排11-12
• 2 研究基礎(chǔ)12-20
• 2.1 研究概述12-13
• 2.2 SAT 問題13-14
• 2.3 All-SAT 問題14-15
• 2.4 P 系統(tǒng)一般模型15-17
• 2.5 P 系統(tǒng)求解 SAT 的一般流程17-19
• 2.6 P 系統(tǒng)仿真平臺19
• 2.7 本章小結(jié)19-20
• 3 邏輯運(yùn)算在膜系統(tǒng)中的實(shí)現(xiàn)20-24
• 3.1 布爾和關(guān)系運(yùn)算膜的定義20-21
• 3.2 基本邏輯運(yùn)算規(guī)則21-22
• 3.3 基本關(guān)系運(yùn)算規(guī)則22-23
• 3.4 本章小結(jié)23-24
• 4 邏輯表達(dá)式求值 P 系統(tǒng)24-35
• 4.1 Π_(LE)的構(gòu)造算法24-26
• 4.2 Π_(LE)的初始化和轉(zhuǎn)移規(guī)則26-27
• 4.3 Π_(LE)的實(shí)例分析27-29
• 4.4 Π_(LE)的系統(tǒng)仿真29-34
• 4.5 本章小結(jié)34-35
• 5 求解 All-SAT 的半統(tǒng)一 P 系統(tǒng)35-44
• 5.1 求解 All-SAT 的半統(tǒng)一方法35-36
• 5.2 Π_(S(All-SAT))定義與設(shè)計(jì)36-39
• 5.2.1 Π_(S(All-SAT))的定義36-37
• 5.2.2 Π_(S(All-SAT))的輸入輸出37-38
• 5.2.3 Π_(S(All-SAT))的進(jìn)化規(guī)則38-39
• 5.3 Π_(S(All-SAT))的時(shí)間復(fù)雜度39-40
• 5.4 Π_(S(All-SAT))實(shí)例分析40-41
• 5.5 Π_(S(All-SAT))系統(tǒng)仿真41-43
• 5.6 本章小結(jié)43-44
• 6 求解 All-SAT 的統(tǒng)一 P 系統(tǒng)44-58
• 6.1 求解 All-SAT 的統(tǒng)一方法44-50
• 6.1.1 統(tǒng)一方法的思想44-47
• 6.1.2 統(tǒng)一方法的算法47-50
• 6.2 Π_(U(All-SAT))的定義與設(shè)計(jì)50-52
• 6.2.1 Π_(U(All-SAT))的定義50
• 6.2.2 Π_(U(All-SAT))的進(jìn)化規(guī)則50-52
• 6.3 Π_(U(All-SAT))的時(shí)間復(fù)雜度52
• 6.4 Π_(U(All-SAT))的實(shí)例分析52-55
• 6.5 Π_(U(All-SAT))系統(tǒng)仿真55-57
• 6.6 本章小結(jié)57-58
• 7 總結(jié)與展望58-60
• 7.1 總結(jié)58-59
• 7.2 展望59-60
• 致謝60-61
• 參考文獻(xiàn)61-64
• 附錄64
• A. 作者在攻讀學(xué)位期間發(fā)表的論文目錄64
• B. 作者在攻讀學(xué)位期間參與的科研項(xiàng)目64

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前5條

1 邢潔清;郭平;朱慶生;王春騰;;基于膜系統(tǒng)的邏輯運(yùn)算研究[J];電腦知識與技術(shù);2009年13期

2 畢忠勤;陳光喜;單美靜;;可滿足性問題全部解的求解算法[J];計(jì)算機(jī)工程與應(yīng)用;2009年03期

3 張德富,黃文奇,汪厚祥;求解SAT問題的擬人退火算法[J];計(jì)算機(jī)學(xué)報(bào);2002年02期

4 張葛祥;潘林強(qiáng);;自然計(jì)算的新分支——膜計(jì)算[J];計(jì)算機(jī)學(xué)報(bào);2010年02期

5 賀思敏,張鈸;Solving SAT by Algorithm Transform of Wu's Method[J];Journal of Computer Science and Technology;1999年05期

  本文關(guān)鍵詞：膜計(jì)算中的邏輯運(yùn)算及其應(yīng)用研究，由筆耕文化傳播整理發(fā)布。

本文編號：383515