经典Ramsey数DNA计算模型(Ⅱ):基于位序列的DNA计算模型

• 作者: 范月科 许进
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 经典Ramsey数 DNA计算 位序列DNA计算模型
• 年，卷（期）: 2008,（12）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 2081-2089
• 页数: 9页
• 分类号: TP301
• 字数: 5225字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2008.12.002

摘要

Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域,也是最困难的数学问题之一.对于经典Ramsey数,至今只有9个Ramsey数得到解决.按照传统的算法.其搜索空间太大,当前的电子计算机无法胜任.研究表明,DNA计算在求解困难的NP-完全问题上优于电子计算机.目前已经建立了众多求解NP-完全问题的DNA计算模型,但未见到用于求解Ramsey数的DNA计算模型.作者建立了一种新颖的DNA计算模型,用于一般经典Ramsey数的求解.全文共分两篇,该文属第二篇,在首篇工作的基础上,建立了所谓的经典Ramsey数位序列DNA计算模型,文中对模型的存储库的建立、解的检测子系统以及运算子系统等问题展开了较为详细地讨论,并给出了使用该模型求解经典Ramsey数详细的方法与步骤.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许进	北京大学信息科学技术学院高可信软件技术教育部重点实验室	117	2149	25.0	39.0
5	范月科	华中科技大学分子生物计算机研究所	6	150	6.0	6.0