论文部分内容阅读
DNA分子计算是高性能计算的新兴领域,经过学者们30年的努力,研究出了很多分子计算模型。但大多基于生物技术,在实现上有很多限制。论文引入了一种在分子计算原理和传统计算机模型基础上,新的基于图灵机的广义分子计算模型,又称广义图灵模型(GTM),该模型的具体实现不依赖于特定生物技术。模型由一台基本图灵机、一个只写带和一条工作带及读写网络这3部分组成,其中只写带和工作带之间存在一种特殊拓扑映射。模型继承分子计算大存储高并行的特点,通过时空复杂度转换,在求解NP完全问题上具有通用性。本文的研究内容可分为以下三部分：1、绪论。阐述DNA分子计算以及DNA计算机的发展历程以及研究意义,DNA分子计算和计算机的研究现状,DNA计算模型的研究难点。2、背景理论知识介绍。将论文涉及的重点理论进行分析论述,包括：DNA分子计算、粘贴模型、图灵机和NP完全问题。另外,详细介绍一个基于非生物技术的广义分子计算模型,包括该模型的组成结构、形式定义和工作过程,这个模型是本论文的理论核心。3、研究广义分子计算模型的应用与实现。将该模型应用于4个NP完全问题,分别是集合覆盖问题、可满足性问题、均分问题和0-1背包问题,进行求解算法设计、实例验证和计算机软件仿真实验。广义分子计算模型能在多项式时间内成功求解4个NP完全问题,说明该模型在求解NP完全问题上有一定通用性,通过实例和仿真验证了算法和模型的有效性。