检索结果-南通市图书馆

系统科学与数学 2003年第1期23卷 30-37页

作者：刁科凤李继乾王志雄周惠山山东大学数学与系统科学学院曲阜师范大学运筹所华侨大学数学系 BellSouth Applied Technology 5250 Triangle ParkwayNorcrossGeorgia30092USA

证明了3-正则图的最小平分问题和最小α-分割问题都是np-完全问题.

关键词： 3-正则图 np-完全问题图最小平分问题最小α-分割问题

几类np-完全问题的DNA计算模型与计算DNA数学模型的研究

在线全文

学校读者我要写书评

暂无评论

几类NP-完全问题的DNA计算模型与计算DNA数学模型的研究

作者：聂晓艳伊犁师范学院

学位级别：硕士

DNA计算是以DNA分子和生化反应为基础的一种新型计算方法。DNA计算的巨大并行性与高度存储能力,吸引了许多来自不同领域学者的关注。到目前为止,已经有许多成果证明了DNA计算的可行性,同时这也表明了DNA计算在解决np-完全问题时体现出... 详细信息

DNA计算是以DNA分子和生化反应为基础的一种新型计算方法。DNA计算的巨大并行性与高度存储能力,吸引了许多来自不同领域学者的关注。到目前为止,已经有许多成果证明了DNA计算的可行性,同时这也表明了DNA计算在解决np-完全问题时体现出电子计算机无法比拟的优越性。根据DNA分子的生物特征与生化反应过程的规律,建立DNA粘贴模型,并利用DNA粘贴计算模型和粘贴系统给出了最大匹配问题的DNA算法、无向图最短路径的DNA算法和TSP的DNA算法,研究了DNA粘贴模型的数学性质。本文通过具体实例说明了这些DNA算法的可行性,证明了算法的复杂度为O(n)。基于DNA分子具有的Watson-Crick互补结构和多重性这两大生物特征,给出了计算DNA数学模型,即DNA有限状态自动机的定义,探究了DNA正则语言的运算封闭性,并证明了DNA正则文法与DNA有限状态自动机的等价性。

关键词： DNA计算 DNA粘贴模型 DNA粘贴系统 np-完全问题 DNA有限状态自动机 DNA正则语言 DNA正则文法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

DNA计算在求解np-完全问题的应用

科技视界 2012年第35期 236-238页

作者：周金凤安徽理工大学安徽淮南232001

基于生化反应的DNA计算模型越来越受到关注。DNA计算的研究已经成为一个热点。本文主要介绍了DNA计算在一些np-完全问题中的应用。并分析了DNA模型存在的问题。指出未来国内DNA计算研究的重点可以在三个方面:解的检测,降低空间复杂度,... 详细信息

基于生化反应的DNA计算模型越来越受到关注。DNA计算的研究已经成为一个热点。本文主要介绍了DNA计算在一些np-完全问题中的应用。并分析了DNA模型存在的问题。指出未来国内DNA计算研究的重点可以在三个方面:解的检测,降低空间复杂度,生化实验研究。

关键词： DNA计算 np-完全问题最大团最小顶点覆盖

在线全文

学校读者我要写书评

暂无评论

DNA计算原理在np-完全问题中的应用

电脑知识与技术 2011年第26期07卷 6338-6340页

作者：朱清妍李锡辉湖南信息职业技术学院

DNA计算是一种利用生物分子间的相互作用来实现并行计算的新的计算模式,具有高度的并行性、巨大的信息存储能力和极低的能耗等优点。该文对DNA计算的一般原理进行了介绍,且介绍了DNA计算原理在解决np问题方面所取得的进展,并指出了DNA... 详细信息

DNA计算是一种利用生物分子间的相互作用来实现并行计算的新的计算模式,具有高度的并行性、巨大的信息存储能力和极低的能耗等优点。该文对DNA计算的一般原理进行了介绍,且介绍了DNA计算原理在解决np问题方面所取得的进展,并指出了DNA计算中存在的问题。

关键词： DNA计算 np-完全问题有向Hamilton路问题最大团与最大独立集问题

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

一类np-完全问题在阈图上的解

计算机学报 1989年第1期12卷 44-51页

作者：马绍汉王云山东大学

本文给出了判定阈图是否为哈密顿图的多项式时间算法,并证明了阈图上STEINER树问题是np-完全的,给出解答它的多项式时间近似算法。

关键词：阈图时间算法 np-完全问题

在线全文

学校读者我要写书评

暂无评论

DNA计算原理在np-完全问题中的应用

电脑知识与技术（过刊） 2011年第9X期17卷 6338-6340页

作者：朱清妍李锡辉湖南信息职业技术学院湖南长沙410200

关键词： DNA计算 np-完全问题有向Hamilton路问题最大团与最大独立集问题

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

遗传算法用于np完全问题的求解

山东大学学报（理学版） 2001年第2期36卷 171-177页

作者：杨青马军山东公安专科学校山东济南250014 山东大学计算机系山东济南250100

讨论了如何利用遗传算法求解布尔表达式的可满足性问题 ,并给出该结果对求解其他np完全问题时的应用 .

关键词：遗传算法布尔表达式可满足问题 np-完全问题

在线全文

学校读者我要写书评

暂无评论

基因组匹配问题的复杂性与算法

基因组匹配问题的复杂性与算法

作者：宋陆山东大学

学位级别：硕士

基因,在生物学上的概念指可以产生一条多肽链或者功能RNA所需的全部核苷酸序列。基因支持着生命的基本构造和性能,储存着生命体的种族、性状、孕育、生长、凋亡的全部遗传信息。基因组则是指生物体中所有遗传物质的总和,包括了一整套基... 详细信息

基因,在生物学上的概念指可以产生一条多肽链或者功能RNA所需的全部核苷酸序列。基因支持着生命的基本构造和性能,储存着生命体的种族、性状、孕育、生长、凋亡的全部遗传信息。基因组则是指生物体中所有遗传物质的总和,包括了一整套基因。基因组学的提出和发展已经颠覆了传统生物学研究,基因组相关工程的数量迅速增加,技术研究突飞猛进。基因组匹配指通过基因组测序获得海量基因组短序列,再利用算法与目标基因组序列相匹配,最后拼接出目标基因组。在序列匹配拼接过程中,可以利用序列间的重叠信息进行匹配,即当一条序列的末端与一条序列的始端有一定长度的重叠部分时,将这两条序列拼接成一条长序列;也可以避免序列间的重叠,精确匹配到基因组的特定位置。基因组匹配可以帮助科学家得到物种的遗传物质,并预测生物性状表达、探明机体调控机制和合成重要蛋白质等。基因组匹配是基因组学领域最基础、最重要的研究方向之一,也是发展现代生物信息学的必经之路。目前基因组匹配所需要的短序列依赖基因测序产生,但是因为当下的测序技术还不完善,存在很大局限性,导致基因组在匹配时复杂度高、计算量大、准确率低。为了研究基因组匹配问题的复杂性和算法,本文引入了单侧的最小公共字符串划分问题(MCSP)来模拟基因组匹配,并根据是否允许序列间的重叠定义了重叠块覆盖问题(OBC)和精确块覆盖问题(EBC)。重叠块覆盖问题和精确块覆盖问题的输入是字符串A的划分P以及字符串B,输出则是一个含有划分P中字符块的排列Q,使得Q可以将字符串B中字符全部覆盖。在基因组匹配中,将字符串A看作被测序的基因组,字符串A的划分P看作测序生成的海量短序列,字符串B看作需要进行匹配的基因组,划分P中的元素称作字符块。如果限制字符串中出现的字符种类最多为c种,即字符集大小为c,每种字符出现的次数不做限制,则称为OBCc和EBCc问题;如果限制字符串中每种字符出现的次数最多为d次,则称为d-OBC和d-EBC问题。本文首先定义了重叠块覆盖问题,研究了 OBC3问题的复杂性,证明了其属于np-完全问题,并设计了 2-OBC问题O(n2)时间复杂度的精确算法以及一般的OBC问题近似比小于等于2时间复杂度为O(n2m2)的近似算法。然后定义了精确块覆盖问题,研究了 EBC2问题的复杂性,证明了其属于np-完全问题,并设计了 2-EBC问题O(n2)时间复杂度的精确算法。

关键词：基因组匹配块覆盖 np-完全问题多项式算法近似算法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

DNA链置换在加密和组合优化问题上的应用

DNA链置换在加密和组合优化问题上的应用

作者：罗先航广州大学

学位级别：硕士

半导体发展到现阶段,摩尔定律可能已经失效,传统计算技术的发展面临瓶颈,例如计算速度受限、能量消耗高等问题。因而迫切需要一种新的计算方法来突破这些瓶颈。DNA计算凭借着高存储、并行性、能耗低等天然优势已经成为代替半导体计算的... 详细信息

半导体发展到现阶段,摩尔定律可能已经失效,传统计算技术的发展面临瓶颈,例如计算速度受限、能量消耗高等问题。因而迫切需要一种新的计算方法来突破这些瓶颈。DNA计算凭借着高存储、并行性、能耗低等天然优势已经成为代替半导体计算的最佳选择之一,并广泛应用于数据安全领域和组合优化问题的求解。本文的研究分为以下两部分:(1)在数据安全领域,加密算法作为一种安全保护措施有着重要意义。然而,在已有的基于DNA计算的加密方法中,大多数仅仅使用DNA代码转化来实现加密,这无疑没有将DNA计算的优势真正发挥。为了解决这个问题,本文提出了一种基于DNA链置换技术的生化实验的加密方法,使用DNA计算实验的参数作为密钥的一部分,提高了破译的难度。此外,该方法将DNA链置换在加密领域的研究从模拟仿真阶段推动到了生化实验阶段。最后通过实验分析证明该方法有较高的密钥敏感性、较大的密钥空间和抵抗统计攻击的能力。(2)在数据安全领域,组合优化问题可以用于解决一系列与安全相关的问题。并且许多加密算法涉及到在数据传输和存储过程中进行组合优化问题的求解。对此,本文提出了一个DNA计算模型,将DNA计算在加密领域的应用拓展至更具一般性的数学问题——组合优化问题上。np-完全问题是组合优化问题中非常重要的问题,由于在多项式时间内无法被解决(除非P=np),因而研究人员对其始终保持着高度的研究热情。凭借DNA计算的并行性,解决np-完全问题的很多DNA计算方法已经被提出,但现有的DNA计算模型都是基于具体问题构造的,也就是说一种模型只能用于求解一种np-完全问题。尽管所有的np-完全问题已经被证明在多项式时间内可以相互规约转化,但没有一种生物方法可以实现这种复杂的规约。对此,本文基于DNA链置换技术设计了一种通用的DNA计算模型,可以用来求解一系列不同的np-完全问题,此过程完全依靠生物操作,无需借助传统计算机进行规约。最后通过仿真实验和生化实验验证了该模型求解最小控制集、最大独立集、最小点覆盖问题的能力。

关键词： DNA计算 DNA链置换 DNA加密 np-完全问题

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于质粒DNA匹配问题的分子算法

生物化学与生物物理进展 2002年第5期29卷 820-823页

作者：高琳马润年许进西安电子科技大学电子工程研究所西安710071 华中科技大学系统科学研究所武汉430074

给定无向图 ,图的最小极大匹配问题是寻找每条边都不相邻的最大集中的最小者 ,这个问题是著名的np 完全问题 .1994年Adleman博士首次提出用DNA计算解决np 完全问题 ,以编码的DNA序列为运算对象 ,通过分子生物学的运算操作解决复杂的数... 详细信息

给定无向图 ,图的最小极大匹配问题是寻找每条边都不相邻的最大集中的最小者 ,这个问题是著名的np 完全问题 .1994年Adleman博士首次提出用DNA计算解决np 完全问题 ,以编码的DNA序列为运算对象 ,通过分子生物学的运算操作解决复杂的数学难题 ,使得np 完全问题的求解可能得到解决 .提出了基于质粒DNA的无向图的最大匹配问题的DNA分子生物算法 ,通过限制性内切酶的酶切和凝胶电泳完成解的产生和最终接的分离 ,依据分子生物学的实验手段。

关键词：质粒DNA匹配问题分子算法 DNA计算 np-完全问题最大匹配