论文部分内容阅读
计算复杂度由计算时间复杂度和计算空间复杂度组成。算法对时间的需要量称为算法的时间复杂度;算法对空间的需要量称为算法的空间复杂度。现实生活中存在许多难计算问题,使用传统的电子计算机求解这些难计算问题通常需要指数的计算时间。既然传统的电子计算机求解这些难计算问题显得无能为力,那么就有必要提出一种新的计算方法。已经有十几年发展历史的DNA计算正是在这样的背景下产生的。高度的并行计算处理、极大的空间存储密度是DNA计算的两大突出优点。DNA计算正是凭借这两个优点,使用天然的空间优势,通过高度的并行计算处理,发挥着它的巨大计算潜能。从某种意义上说,这种计算潜能是传统的电子计算机所无法比拟的。论文以分组密码与图论中的几个难计算问题为研究对象,展开了基于粘贴模型、剪接模型的DNA算法研究、设计与分析。破译分组密码国际数据加密算法或破译数据加密标准都是难计算问题,同时,二进制串逻辑运算是分组密码算法中频繁使用的运算。论文设计了一个二进制串循环左移运算的DNA粘贴算法;然后,提出了一个二进制串异或运算的DNA粘贴算法;并且结合两个具体实例,对粘贴算法过程进行了详细地描述;最后,对所提算法进行了复杂性分析,分析结果表明DNA计算用于破译分组密码具有可行性。论文设计了一个破译国际数据加密算法的递归式DNA剪接算法。该算法首先对国际数据加密算法的异或、加模、乘模运算进行了DNA剪接算法设计;然后,对国际数据加密算法的8轮迭代采用了递归方式并行计算处理,控制了生成链的长度,降低了DNA操作的难度。同时,论文设计了一个破译数据加密标准的递归式DNA粘贴、剪接算法。首先,该算法使用递阶方式生成了完备的初始密钥,保证了算法的理论成功率为百分之百;然后,使用同样的方式对数据加密标准的16轮迭代采用了递归处理,控制了生成链的长度,降低了DNA操作的难度,提高了算法的可靠性。求解最大团问题或构造对角Ramsey图也是两个难计算问题。使用穷举搜索算法来解决这两个问题,必然导致计算量的指数爆炸,穷举搜索DNA算法也不例外。论文设计了一个求解最大团问题的递阶法DNA粘贴、剪接算法。该算法使用递阶方式的并行计算处理,利用分层剪枝法来分离问题的非解,最终删除这些非解,在一定程度上缓解了算法的空间计算量的指数爆炸。同时,论文提出了一个构造对角Ramsey图的递阶法DNA粘贴、剪接算法。该算法通过逐个添加顶点的递阶方法,逐步删除了问题的绝大部分非解,在一定程度上缓解了问题解空间的指数爆炸。特别地,专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算量分析,分析结果充分地肯定了该算法的有效性。