摘要：电子计算机的发展给人类社会进步带来了极大的推动作用,但是随着电子计算机制造工艺趋于极限,人们迫切需要找到一种新的计算体系来满足日益增长的计算需求。DNA计算因其超强的信息存储、大规模的并行计算能力和超低的能耗而受到了广泛的关注。自1994年Adleman博士在实验室利用DNA完成了一个6顶点哈密尔顿路求解问题开始,各种计算模型纷纷涌现。本文首先对DNA计算的基本原理和实验操作手段进行了简单的介绍,然后对DNA相关的理论进行了阐述,包括DNA计算中序列编码设计的理论、DNA计算模型复杂度分析与通用计算能力的证明;在此基础上,对突破性的DNA计算模型进行了概括,进而根据实验操作的具体手段将所有已知模型进行了分类,按照类别进行了综述,并随后挑选了该类别中经典的模型进行更为直观的分析。更进一步,在文章的最后,结合笔者的工作对DNA计算领域的前景进行了展望。

摘要：Ramsey数问题是一个著名的组合优化问题,同时也是一个NP完全问题。构造对角Ramsey图是一个难处理的计算问题,使用穷举的算法来构造对角Ramsey图必然导致计算量的指数爆炸,穷举的DNA算法也不例外。提出了一个构造对角Ramsey图的递阶式DNA粘贴—剪接算法,该算法通过逐个添加顶点的思想,逐步删除了问题的绝大部分非解,在一定程度上缓解了问题解的空间扩散。特别地,专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算分析,分析结果充分地肯定了该算法的有效性。