构形可约性证明的DNA算法

论文摘要

DNA 计算是一门新兴的研究领域。1994 年,Adleman 在著名杂志Science 上发表第一篇关于DNA 计算的文章,他用DNA 在试管中解决了著名的哈密尔顿路径问题。DNA 计算具有大规模并行计算的能力,而且与传统的电子计算机相比能存储更多的数据。目前DNA 计算的研究已涉及许多领域,包括生物学、数学、物理、化学、计算机科学和自动化工程等多领域,包括生物学、数学、物理、化学、计算机科学和自动化工程等具体应用,是计算概念上的一次革命。四色问题在1852 年首次提出。是一个可与费马猜想相媲美的难题,直到1976年才由哈肯和阿佩尔给出了第一个证明,随后Robertson 等人对他们的方法进行了改进。首先,他们给出了一个不可避免集,证明每个三剖分都至少包含不可避免集中的一个构形。第二步,他们证明每个构形都是可约的,这一部分的证明需要借助于计算机实现,完成第二步的证明大概需要1200个小时!本文探讨用DNA计算的方法来解决构形的可约性证明,因为DNA 计算具有大规模并行计算的能力,能够大大地减少证明所需的时间。目前还没有这方面的研究。本文首先简述了四色定理证明的证明,然后介绍了平滑三剖分三着色的一些性质和三着色的DNA 算法,在本文的最后分析了着色和符号匹配体的关系,给出了构形可约性的DNA 算法。本文的编码方式十分直观、有规律,算法简单易于实现。算法具有一定的并行性,能够大大地减少构形可约性证明的时间。

论文目录

• 摘要
• Abstract
• 目录
• 第1章 绪论
• 1.1 DNA计算概述
• 1.2 DNA计算研究现状
• 1.3 DNA计算的应用
• 1.4 研究内容和意义
• 1.5 本章小结
• 第2章 四色定理证明
• 2.1 四色定理简介
• 2.2 四色定理证明
• 2.2.1 预备知识
• 2.2.2 构形
• 2.2.3 可约性
• 2.3 本章小结
• 第3章 三着色的DNA算法
• 3.1 预备知识
• 3.2 编码
• 3.3 算法
• 3.3.1 生成脉组
• 3.3.2 提取脉组
• 3.4 *三着色的读取
• 3.4.1 着色信息在DNA芯片上的存储
• 3.4.2 DNA芯片上的杂交反应
• 3.5 本章小结
• 第4章 构形可约性证明的DNA算法
• 4.1 预备知识
• 4.2 D-可约
• 4.2.1 编码
• 4.2.2 算法实现
• 4.3 C-可约
• 4.3.1 编码
• 4.3.2 算法实现
• 4.4 本章小结
• 结论
• 参考文献
• 致谢