膜计算中的逻辑运算及其应用研究

发布时间：2017-05-21 11:22

  本文关键词：膜计算中的逻辑运算及其应用研究，由笔耕文化传播整理发布。

【摘要】：膜计算是生物计算中一个新的分支，，它是从生物体活细胞的结构和功能中抽象出来的计算模型。膜计算也被称为膜系统或P系统。这个研究方向由罗马尼亚科学家Gheorghe.P un于1998年创立后，就迅速发展为拥有巨大潜力的研究领域，它给很多领域的重点难点问题带来了新的求解思路。由于细胞膜数量极其庞大，以及生物驱动所需能源非常小，因此此类计算系统最大的优势就是可以以极大的并行度来实现计算，从而获得远远超过传统电子计算机的计算能力。已经有研究证明，该模型可以在多项式时间内解决NP-完全问题。 如何实现算术、布尔和关系运算都是计算模型中最基本的问题。目前，算术运算在类细胞P系统中已有了一定的研究成果。但是布尔运算和关系运算在膜计算领域的实现还相对匮乏。因此本论文通过对逻辑运算、逻辑表达式求值以及对逻辑运算应用P系统的研究，来扩展逻辑P系统的使用范围，为生物计算机的实现奠定一定的基础。下面就简单介绍一下本论文所完成的研究工作。本文研究的主要工作包括以下几点： ①根据膜计算的基础思想及执行特点，设计基于规则优先级的逻辑运算P系统，为逻辑表达式求值的实现奠定基础。 ②通过逻辑运算进化规则，设计了基于逻辑表达式膜结构的构造算法，根据该算法构造了逻辑表达式求值P系统。 ③由于逻辑命题的可满足性问题是理论计算机科学和人工智能中的著名问题，特别是关于命题中合取范式的可满足性(SAT)问题的研究。因此在以上研究的基础上，本文选择NP难问题中的可满足性问题作为其应用进行研究，设计并构造了两个求解可满足性问题全部解(All-SAT)的P系统，其中一个属于半统一类型的，另一个属于统一类型的P系统。 ④利用电子计算机实现了逻辑表达式求值、可满足性问题全部解P系统的模拟仿真实验，对所构造的P系统进行了验证。 本文的研究成果进一步丰富了膜计算中逻辑运算及表达式求值研究的理论，并选择可满足性问题作为研究实例，扩大了逻辑运算P系统的应用范围，可以作为今后解决其他问题的参考。
【关键词】：逻辑运算 表达式求值 SAT/All-SAT问题 P系统 膜计算
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP38
【目录】：

• 摘要3-4
• ABSTRACT4-8
• 1 绪论8-12
• 1.1 引言8
• 1.2 国内外研究现状综述8-10
• 1.3 研究的目的及意义10-11
• 1.4 本文结构及安排11-12
• 2 研究基础12-20
• 2.1 研究概述12-13
• 2.2 SAT 问题13-14
• 2.3 All-SAT 问题14-15
• 2.4 P 系统一般模型15-17
• 2.5 P 系统求解 SAT 的一般流程17-19
• 2.6 P 系统仿真平台19
• 2.7 本章小结19-20
• 3 逻辑运算在膜系统中的实现20-24
• 3.1 布尔和关系运算膜的定义20-21
• 3.2 基本逻辑运算规则21-22
• 3.3 基本关系运算规则22-23
• 3.4 本章小结23-24
• 4 逻辑表达式求值 P 系统24-35
• 4.1 Π_(LE)的构造算法24-26
• 4.2 Π_(LE)的初始化和转移规则26-27
• 4.3 Π_(LE)的实例分析27-29
• 4.4 Π_(LE)的系统仿真29-34
• 4.5 本章小结34-35
• 5 求解 All-SAT 的半统一 P 系统35-44
• 5.1 求解 All-SAT 的半统一方法35-36
• 5.2 Π_(S(All-SAT))定义与设计36-39
• 5.2.1 Π_(S(All-SAT))的定义36-37
• 5.2.2 Π_(S(All-SAT))的输入输出37-38
• 5.2.3 Π_(S(All-SAT))的进化规则38-39
• 5.3 Π_(S(All-SAT))的时间复杂度39-40
• 5.4 Π_(S(All-SAT))实例分析40-41
• 5.5 Π_(S(All-SAT))系统仿真41-43
• 5.6 本章小结43-44
• 6 求解 All-SAT 的统一 P 系统44-58
• 6.1 求解 All-SAT 的统一方法44-50
• 6.1.1 统一方法的思想44-47
• 6.1.2 统一方法的算法47-50
• 6.2 Π_(U(All-SAT))的定义与设计50-52
• 6.2.1 Π_(U(All-SAT))的定义50
• 6.2.2 Π_(U(All-SAT))的进化规则50-52
• 6.3 Π_(U(All-SAT))的时间复杂度52
• 6.4 Π_(U(All-SAT))的实例分析52-55
• 6.5 Π_(U(All-SAT))系统仿真55-57
• 6.6 本章小结57-58
• 7 总结与展望58-60
• 7.1 总结58-59
• 7.2 展望59-60
• 致谢60-61
• 参考文献61-64
• 附录64
• A. 作者在攻读学位期间发表的论文目录64
• B. 作者在攻读学位期间参与的科研项目64

【参考文献】

中国期刊全文数据库 前5条

1 邢洁清;郭平;朱庆生;王春腾;;基于膜系统的逻辑运算研究[J];电脑知识与技术;2009年13期

2 毕忠勤;陈光喜;单美静;;可满足性问题全部解的求解算法[J];计算机工程与应用;2009年03期

3 张德富,黄文奇,汪厚祥;求解SAT问题的拟人退火算法[J];计算机学报;2002年02期

4 张葛祥;潘林强;;自然计算的新分支——膜计算[J];计算机学报;2010年02期

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

  本文关键词：膜计算中的逻辑运算及其应用研究，由笔耕文化传播整理发布。

本文编号：383515