论文部分内容阅读
生物计算在当今计算机科学研究领域蓬勃发展,倍受关注。很多生物计算模型已经开始被应用于实际生活中,解决一些实际问题。比如DNA计算,神经网络等。这些从生物结构或概念中抽象出来的计算模型具有广泛而深刻的表达能力,并且它们相对于普通的计算模型有它们特有的优势。
膜计算(又称P系统)是一个新兴的生物计算模型,它在1999年由Gh.P?aun提出。由于这种计算模型的高度并发性和结构特殊性,在它提出后的几年,很多针对它的研究相继展开并取得了不错的进展。这其中包括了对它的计算通用性的研究,分类研究,以及系统改进研究等。
由于P系统具有高度的并行性,这使得它可以相对高效的解决很多复杂的问题。但是,到目前为止,针对如何利用P系统解决实际问题的研究还相对甚少。在这个背景下,本文先从如何利用P系统来解决简单的排序问题入手,接着提取出P系统的最大并行性质做深入的研究,最后对P系统的进化规则做出了巧妙的修改。通过这三个部分,本文希望能找出一些如何利用P系统解决实际问题的通用方法。这些方法在计算机科学中通常称为程序设计。所以,本文研究的主要内容是如何利用P系统进行程序设计。
在研究过程中,本文定义了P系统的时间复杂性,并用这个概念来分析P系统的计算性能。同时,在不影响原有系统的图灵等价性基础上,本文改进了原始P系统的规则模型,使得改进后系统的规则具有更强的表达能力,更适合进行程序设计。