代数运算的DNA实现

论文摘要

1996 年,Frank 发表在Science 上的“DNA 加法”一文开创了利用DNA 解决数值运算的先河,同时,文中提出的“全列举与自装配”成为DNA 代数运算工作的基础思想。在这一基础思想的指导下,又先后出现了其他解决代数运算的算法模式。电子计算机只是用串行思路解决问题,DNA 计算机(现在还只是处于理论研究中)则是以并行的思路解决问题。我们的思想就是以并行代替串行,先从理论上来验证DNA 计算机的优越性。本文是对应用DNA 计算机解决代数运算中的减法、除法问题进行了研究,主要给出了三种算法分别解决减法、除法。减法的DNA 算法理论主要是来源于串行思路中的算法,它是将每一位上的两个减数对的所有可能进行全列举,同时考虑每一位上的两种借位信息,使得运算进行自动选择,一步即可得到最终结果的算法;除法中一位数除多位数的算法还是从我们平时所进行的串行运算中得到启发而设计的算法;而除法的多位计算思路则来源于史丰收速算法,将算法中的口诀及技巧应用到DNA 链当中,使得传统中的代数运算能够并行的得到最终的结果,这三种算法的设计都使得计算步骤减少,从根本上改变了算法的运算机制。本文同时还计算了各种算法的复杂度,从理论上验证了DNA 计算在并行计算上的优越性;同时也进行了编程的处理,编码方式十分简单、直观,编码具有规律性,易于实现,在实践中验证了算法的正确性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 DNA代数运算的发展现状
• 1.2 基本文献简介
• 1.3 问题引入及论文结构
• 1.4 本章小结
• 第2章 十进制减法 DNA 运算模型
• 2.1 减法算法理论
• 2.2 DNA 运算的模型
• 2.2.1 DNA 编码设计
• 2.2.2 算法的具体操作
• 2.3 具体实例
• 2.4 本章小结
• 第3章 除法并行运算 DNA 运算模型
• 3.1 十进制一位数除多位数的 DNA 运算模型
• 3.1.1 十进制一位数除多位数的算法理论
• 3.1.2 DNA 运算的模型描述
• 3.1.3 DNA 运算的具体操作
• 3.1.4 具体实例操作
• 3.2 多位数除法
• 3.2.1 算法简介
• 3.2.2 DNA 编码
• 3.2.3 算法分析
• 3.2.4 DNA 运算的具体操作过程
• 3.3 本章小结
• 第4章 编码实现
• 4.1 DNA 计算的计算机模拟
• 4.2 文本算法的计算机实现
• 4.2.1 算法描述
• 4.2.2 算法演示
• 4.3 本章小结
• 总结
• 参考文献
• 致谢