论文部分内容阅读
根据"摩尔定律",传统计算机的计算速度日益接近瓶颈,科学家开始寻找代替传统电子计算机的新型计算模型。目前为止,研究人员已经从各种自然现象中抽象出许多计算模型,例如自然计算。DNA计算和膜计算是属于自然计算的两个分支。DNA计算是从DNA分子的Watson-Crick互补性和生化反应的并行性抽象出来的计算模型。在DNA计算领域,许多NP难问题能够在多项式时间内得到解决。膜计算(也称P系统)是通过借鉴和模拟生物活细胞、组织处理化学物质的方式,以建立具有良好计算性能的分布式并行计算模型。已证明膜计算具有和图灵机等价的计算能力,可以在多项式时间内解决NP难问题。目前,对于DNA计算和膜计算的研究,主要侧重于模型计算能力的研究,即主要考虑NP难问题的解决。但是,在现实生活中的应用系统多是解决以数值计算为主的计算问题,而非NP难问题。算术运算在自然计算模型中已有一定的研究成果,但是,自然计算模型中算术运算的并行性,特别是除法并行性的研究还相对匮乏。因此,研究基于DNA和膜计算的计算系统是非常有必要的。本文通过设计算术运算口诀表,利用自然计算的并行性,分别实现基于DNA计算和基于膜计算的算术运算系统,提高了算术运算的并行性。然后,将DNA计算和膜计算进行结合,探讨了基于DNA计算的算术P系统。本文所完成的研究内容如下:①为提高DNA计算中算术运算的并行性,我们设计了算术运算口诀表(包括加法口诀表、减法口诀表、乘法口诀表和除法口诀表),用于单位数(单位数x的取值范围为0￡x￡9)的四则运算。然后,基于Adleman–Lipton模型,设计出十进制操作数和四则运算口诀表的DNA编码方法。在此基础上,设计出能够较好利用DNA计算并行性的四则运算操作。②基于算术运算口诀表,我们设计出一种新的算术P系统。在该系统中,单位数的算术运算的进化规则依据算术运算口诀表进行设计。相比现有的算术运算P系统,基于算术运算口诀表的P系统减少了在乘法和除法的实验步。③基于结构化对象P系统,我们将结构化对象实例化为DNA链,设计出基于DNA计算的算术运算P系统。该P系统结合了DNA链的Watson-Crick互补性和膜计算中膜区域分布式的特性,简化了算术运算P系统的结构和进化规则。本文的研究成果进一步丰富了DNA计算和膜计算的算术运算理论。并且,所设计的基于DNA计算的算术P系统,将DNA计算和膜计算的原理进行结合,丰富了自然计算的算术运算模型,可以作为今后解决其他问题的参考。