DNA计算在两类特殊应用问题上的研究

论文摘要

DNA计算的海量存储和巨大并行运算能力,使其成为NP完全问题和其它难解问题的潜在解决方案之一,在理论上已成功的在多项式时间下解决了许多著名的NP完全问题。DNA计算的特点使其在复杂的调度问题上有了新的解决方案,许多复杂的调度问题均基于难解的NP完全数学问题,DNA计算的并行运算潜力为这些调度问题提供了可能,倍受关注。另一方面,DNA计算模型尚不似传统计算机中的通用,求解一个问题的DNA计算模型或算法通常很难不作修改地用于其它类似问题的求解,因此,不管基于DNA计算的何种模型,目前几乎所有的基于DNA超级计算的算法均使用完全穷举方式。这种方法的直接后果是DNA计算算法中呈纯指数量级增长的DNA链数。随着DNA计算研究的逐渐深入,现有的基于穷举方法的DNA计算算法中存在的解空间指数爆炸问题日益突出,已成为限制DNA超级计算应用的瓶颈。因此考虑将传统电子计算机并行处理的策略、方法和技术引入DNA超级计算是降低DNA链数的重要途径之一。本文采用Chang等提出的DNA计算模型对于多处理机独立任务调度问题,采用粘贴模型解空间及Adleman的生物操作集合,给出了一种新的该类问题的DNA计算模型及相应的独立任务调度算法。同时本文对如何减少DNA解空间问题做了一些尝试。从电子计算机中传统并行计算和并行处理的模型出发,将传统并行处理的策略和DNA计算的特点相结合,将电子计算机并行计算中的具有普适性的分治算法设计技术应用于求解子集和问题的DNA计算中,提出一种求解子集和问题的质粒DNA算法,理论分析表明:新算法在不提高算法的时间复杂度的前提下,可将求解子集和问题所需的DNA链数从穷举算法的O(2n)减少至O(2n/2)。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 研究目的与意义
• 1.2 生物分子计算的基本思想和基本方法
• 1.3 DNA 计算机理
• 1.4 DNA 计算研究的国内外现状、水平与发展趋势
• 1.5 论文主要工作
• 1.6 论文组织结构
• 1.7 小结
• 第2章 相关理论背景
• 2.1 任务调度问题
• 2.2 NP 完全问题
• 2.3 DNA 计算模型
• 2.4 计算复杂性概念
• 2.5 小结
• 第3章 多处理机独立任务调度问题的 DNA 计算机算法
• 3.1 引言
• 3.2 基于粘贴的计算模型
• 3.3 基于粘贴模型独立任务调度问题 DNA 算法
• 3.3.1 问题描述
• 3.3.2 基于 Sticker 模型解空间的独立任务调度问题的初始任务分配
• 3.3.3 基于 Sticker 模型解空间的独立任务调度问题的任务时间开销构造
• 3.3.4 独立任务调度问题 DNA 计算机算法
• 3.4 算法实现
• 3.5 结论
• 第4章 基于质粒模型的子集和DNA 计算机算法
• 4.1 引言
• 4.2 质粒模型
• 4.3 背包问题的DNA 计算机算法
• 4.4 算法实现
• 4.5 小结
• 结论
• 1.本文工作总结
• 2.下一步工作展望
• 参考文献
• 致谢
• 附录A （攻读硕士期间发表论文目录）