可扩展DNA计算模型的研究与应用

来源 :湖南大学 | 被引量 : 0次 | 上传用户:wei2006006
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
计算机技术被认为是20世纪三大科学革命之一,电子计算机为社会的发展起到了巨大的促进作用,但是量子物理学己经成功地预测出芯片微处理能力的增长不能长期地保持下去。基于这一原因,科学家们正在寻找其他全新的计算机结构,如人工神经网络计算机、量子计算机、光学计算机以及DNA计算机模型等其中DNA计算机在近几年倍受科学界的关注。分子计算操作的高度并行性与高密度给DNA计算带来了海量存储和并行运算的能力,从理论上可克服电子计算机存储量与运算速度上的不足,成为NP完全问题和其它难解问题的潜在解决方案之一,并且在理论上已成功的在多项式时间下解决了许多著名的NP完全问题。然而,由于目前几乎所有的基于DNA超级计算的算法均使用完全穷举方式。这种方法的直接后果是DNA计算算法中呈纯指数量级增长的DNA链数。随着DNA计算研究的逐渐深入,现有的基于穷举方法的DNA计算算法中存在的解空间指数爆炸问题日益突出,已成为限制DNA超级计算应用的瓶颈。本文以减小DNA计算中问题的解空间为主线。从电子计算机中传统并行计算和并行处理的模型出发,将传统并行处理的策略和DNA计算的特点相结合,对图着色问题,最大团问题及划分问题的DNA计算模型进行了研究。对于图着色问题和最大团问题,根据问题自身的特点并借鉴传统计算机中的剪枝策略,提出了图着色问题和最大团问题的可扩展DNA计算机算法。对于划分问题,基于电子计算机中具有普适性的分治算法设计技术设计了划分问题的可扩展DNA计算机算法。理论分析表明:提出的可扩展新算法在不提高算法的时间复杂度的前提下,将求解图着色问题所需的DNA链数从穷举算法的O(3n)减少至O(2n);最大团问题所需的DNA链数由O(2n)减少至O( 3 n);划分问题的DNA链数由O(2n)减少至O(2n/2)。
其他文献
对等网络(Peer-to-Peer,简称P2P)是目前流行于国际网络技术研究领域的一种新兴网络模型。与传统的客户机/服务器结构不同,P2P中所有的结点都是平等的,没有严格的网络服务提供
决策支持系统主要由数据仓库和决策推理两个部分组成,这两部分的有机结合再加上结果展示组成了一个完整的决策过程。而OLAP(On-Line Analysis Processing)作为一个基本的归纳
三维模型的孔洞修补问题,一直是计算机图形学和可视化研究中的一个热点问题。由于颅骨模型的特殊性,现有算法并不适用于颅骨模型的修补。三维颅骨孔洞修补是一个崭新的研究课
WMN(Wireless Mesh Network,无线网状网)是一种全新的无线网络技术,其核心是让网络中每个节点都可以发送和接收信号。WMN是网状结构的多跳系统,从源节点到目的节点存在多条冗余
本文研究了现有国内外二维条码的种类、优势及相关识别技术;剖析移动端主流操作系统Symbian OS体系结构及其应用程序的开发平台;并在此基础上搭建移动端二维条码识别系统。首
AVS(Audio video coding standard)是我国数字音视频编解码技术标准工作组于2003年自主制定的具有自主知识产权的数字音视频编解码技术标准,其专利池管理策略成功地解决了我
随着人类基因组计划的开展,以及各种生物基因序列的研究,产生了越来越多的分子序列数据。对这些序列数据进行科学的分析、处理可以推动生物信息学的发展。序列分析是生物信息
长久以来,企业界一直在信息化建设和资金投入间艰难的寻找平衡点。近几年来,随着x86体系结构计算机性能的飞速提升,软件人员开始将过去应用在大中型计算机上的虚拟化技术带到x86
随着我国加入WTO以及市场经济体制的逐渐完善,高校间的竞争日益凸现。决策支持系统在高校中的应用研究将充分利用现有的高校信息资源,从更高的层面优化学校资源配置,从整体、宏