学位论文 > 优秀研究生学位论文题录展示

网状结构膜系统的计算能力研究

作　者: 江赟
导　师: 潘林强
学　校: 华中科技大学
专　业: 系统分析与集成
关键词: 膜计算膜系统网状结构膜系统计算通用性计算有效性
分类号: TP399-C8
类　型: 博士论文
年　份: 2011年
下　载: 61次
引　用: 0次
阅　读: 论文下载

内容摘要

随着科学的不断发展,目前的科学研究经常涉及到多个不同的学科领域,打破经典学科的分类,进行交叉学科的研究成为大势所趋。在计算机科学领域,生物学一直对其发展有重大的影响,许多计算思想、模型、方法都是受生物系统的启发而来,如自然计算中为大家所熟悉的遗传算法和神经计算等。1998年,Gh. Paun教授首次提出了膜计算的概念。膜计算是自然计算的一个新的分支,是计算机科学、生物学、数学等多学科交叉的研究领域,其目的是从细胞的结构和功能,以及从组织和器官等细胞群相互协作处理信息的方式中,获得新的思想,设计新的模型。膜计算是根据细胞处理化学物质的机理提出的一种新的计算模式,膜计算系统(由于Gh. Paun院士对膜计算领域的巨大贡献,也称为P系统)具有良好的分布式结构和巨大的并行性,并且为生物系统的建模与仿真提供了新的工具。根据膜结构的不同,膜系统分为嵌套结构膜系统和网状结构膜系统。本文研究网状结构膜系统,它包括组织膜系统和脉冲神经膜系统。组织膜系统是依据组织中细胞之间通过蛋白质通道进行通信的生物事实构造的计算模型,而脉冲神经膜系统则是基于大脑中神经元之间通过突触相互协作、处理脉冲信息的生物现象而抽象出来的计算模型。由于其强大的计算能力及其在解决困难问题方面显示的潜力,网状结构膜系统引起越来越多学者的关注。本文从语言的产生能力及数的识别能力、小通用性以及计算有效性三个方面研究了网状结构膜系统的计算能力,主要工作如下：首先研究了网状结构膜系统的语言产生能力和数的识别能力。计算设备的语言产生及数的识别能力是研究计算设备计算能力的基本问题之一。本文研究了穷举使用规则的脉冲神经膜系统产生二进制字符串语言的能力,以及前瞻模式下的组织膜系统识别数的能力。对于穷举使用规则的脉冲神经膜系统,研究了它在使用扩展规则时的二进制语言产生能力,证明了扩展脉冲神经膜系统在穷举使用规则的模式下可以刻画有限语言和递归可枚举语言。另外研究了前瞻模式下的组织膜系统作为数的识别装置时的识别能力,证明了在前瞻使用规则的模式下,包含3个细胞的组织膜系统可以刻画递归可枚举数集。其次对具有反脉冲的脉冲神经膜系统的小通用性进行了研究。计算模型的小通用性是计算机科学中经典的研究问题之一,小通用系统具有良好的通用性和扩展性,可以直接作为实用系统的一个核心部件,也可以协助开发系统,节约系统成本,缩短研发周期。对于脉冲神经膜系统而言,研究小通用性问题除了具有计算机科学意义外,还有其生物学意义：给出某种小通用“脑”的度量。本文对脉冲神经膜系统的小通用性进行了如下研究：在作为计算函数的装置的情形下,本文分别构造了使用规则产生反脉冲和使用抑制突触产生反脉冲的小通用脉冲神经膜系统,并通过考虑共用附属神经元的方式,优化了所得到的小通用系统的神经元个数。这一结论给出了具有反脉冲,并且使用纯规则的小通用“脑”的度量。最后研究了组织膜系统的计算有效性。由于组织膜系统的拓扑结构是固定的,因此在计算过程中无法由组织膜系统本身来生成计算空间,从而实现空间换时间。本文研究了组织膜系统在具有细胞分割性质时的计算有效性。利用这种类型的系统,求解了一个著名的NP完全问题—子集和问题。所构造的具有细胞分割性质的组织膜系统,可以在(与问题规模相关的)多项式时间内求解给定规模的子集和问题的所有算例。此外还研究了前瞻模式下组织膜系统求解三着色问题时的计算有效性,在前瞻使用规则的模式下,该组织膜系统可以在(与图的顶点数相关的)线性时间内求解三着色问题。这些结论证实了细胞分割的确是有效的以空间换时间的手段,并且前瞻可以有效地降低膜系统固有的非确定性。

全文目录

摘要  4-6
Abstract  6-9
目录  9-12
1 绪论  12-34
  1.1 研究背景  12-13
  1.2 膜计算简介  13-15
  1.3 膜系统介绍  15-28
  1.4 研究涉及的定义和概念  28-31
  1.5 研究内容与创新点  31-32
  1.6 本文的内容安排  32-34
2 穷举使用规则的脉冲神经膜系统的语言产生能力  34-47
  2.1 穷举使用规则的脉冲神经膜系统  34-36
  2.2 穷举使用规则的脉冲神经膜系统的二进制字符串语言产生能力  36-46
  2.3 本章小结  46-47
3 前瞻模式下组织膜系统的计算通用性  47-55
  3.1 前瞻模式下的组织膜系统  47-49
  3.2 前瞻模式下的组织膜系统的计算通用性  49-54
  3.3 本章小结  54-55
4 具有反脉冲的小通用脉冲神经膜系统  55-72
  4.1 具有反脉冲的脉冲神经膜系统  55-58
  4.2 具有反脉冲的小通用脉冲神经膜系统  58-66
  4.3 具有抑制突触的小通用脉冲神经膜系统  66-71
  4.4 本章小结  71-72
5 具有细胞分割的组织膜系统求解子集和问题  72-90
  5.1 子集和问题  72
  5.2 具有细胞分割的组织膜系统  72-75
  5.3 子集和问题的求解  75-82
  5.4 形式化证明  82-88
  5.5 主要结论  88-89
  5.6 本章小结  89-90
6 前瞻模式下具有细胞分割的组织膜系统求解三着色问题  90-101
  6.1 三着色问题  90
  6.2 前瞻模式下具有细胞分裂的组织膜系统  90-91
  6.3 三着色问题的线性解  91-99
  6.4 本章小结  99-101
7 总结与展望  101-104
  7.1 全文总结  101-102
  7.2 尚待研究的工作  102-104
致谢  104-106
参考文献  106-114
附录1 攻读学位期间发表的学术论文  114-115
附录2 博士学位论文章节内容与博士期间发表论文的关系  115-116
附录3 攻读博士学位论文期间参加的科研课题  116

网状结构膜系统的计算能力研究

内容摘要

全文目录

相似论文