检索结果-南通市图书馆

非线性存储方案设计问题——一个np完全问题

在线全文

学校读者我要写书评

暂无评论

小型微型计算机系统 2000年第5期21卷 452-454页

作者：佟冬方滨兴胡铭曾哈尔滨工业大学计算机科学与工程系哈尔滨150001

本文证明了为任意模板集设计存储访问无冲突非线性存储方案的问题是一个 np完全问题 .另外设计同时满足存储访问无冲突和互联网络无冲突的存储方案设计问题也是一个 np完全问题 .

关键词：非线性存储方案多级互连网 np完全问题存储器

在线全文

学校读者我要写书评

暂无评论

CAM中一类新的np完全问题

计算机学报 1991年第3期14卷 199-205页

作者：王介生李凤森中国科学院计算技术研究所CAD开放实验室北京100080

本文提出了计算机辅助制造(CAM)中的一类作业调度问题并证明了它的np完全性。

关键词： CAM np完全问题计算机

在线全文

学校读者我要写书评

暂无评论

一种三值逻辑的np完全问题与判定问题

计算机学报 1990年第8期13卷 561-568页

作者：李祥贵州大学计算机科学系

本文建立了一种三值逻辑——中介逻辑的三值语义,证明了其命题演算MP与MP的可满足问题是np完全的且其谓词演算(带或不带等词)MF,MF与ME的判定问题是算法不可解的。

关键词：三值逻辑 np完全问题数理逻辑

在线全文

学校读者我要写书评

暂无评论

np完全问题研究及前景剖析

武汉工程大学学报 2015年第10期37卷 73-78页

作者：杜立智陈和平符海东武汉科技大学计算机科学与技术学院湖北武汉430065

P ***是理论计算机领域最重要的课题之一,而其中的核心是np完全问题.由于该问题所涉及的概念复杂抽象,对它们的理解存在不少谬误,许多已发表的研究论文都包含着这些谬误.主要是:np、np完全概念理解谬误,确定性及非确定性图灵机的概念模... 详细信息

P ***是理论计算机领域最重要的课题之一,而其中的核心是np完全问题.由于该问题所涉及的概念复杂抽象,对它们的理解存在不少谬误,许多已发表的研究论文都包含着这些谬误.主要是:np、np完全概念理解谬误,确定性及非确定性图灵机的概念模糊不清,P与np关系的误读,np问题研究方向的误导等.本文分析了这些谬误,并揭示了相关概念的实质.通过不同角度多方位分析,对np完全问题可能的解决途径和研究方向,提供了启发式思路.

关键词：确定性图灵机非确定性图灵机 np完全问题

基于DNA计算模型的几个np完全问题的研究

在线全文

学校读者我要写书评

暂无评论

基于DNA计算模型的几个NP完全问题的研究

作者：赵瑞敏太原理工大学

学位级别：硕士

DNA计算,又称为生物分子计算,是基于生化反应的一种全新的计算模式。对于复杂的np完全问题,DNA计算机与传统晶体管计算机相比,具有其无可比拟的优势,如:高度并行性、巨大的存储容量、超低的能耗和快的运行速度。因此,DNA计算方法及计算... 详细信息

DNA计算,又称为生物分子计算,是基于生化反应的一种全新的计算模式。对于复杂的np完全问题,DNA计算机与传统晶体管计算机相比,具有其无可比拟的优势,如:高度并行性、巨大的存储容量、超低的能耗和快的运行速度。因此,DNA计算方法及计算理论的研究对分子计算机的实现具有重要意义,近期的研究也表明,DNA计算在特定的复杂问题或领域里已显示出极大的潜力,并具有光明的应用前景。1994年,美国南加州大学的Adleman教授用生化实验开创性地解决了七个顶点的有向哈密尔顿路径问题(Directed Hamilton Path Problem,DHPP)。之后,DNA计算迅速成为活跃的科学研究领域,有关DNA计算的科研工作也迅速在许多国家展开。研究的内容涉及DNA计算模型、一些np问题的DNA算法、数据加密、智能控制、DNA数据存储、DNA计算的复杂性、分子高级语言、DNA计算方法与各种软科学的结合或集成等等。不但受跨学科研究所限,而且由于生物实验过程的复杂性,实验环境难以搭建,因此,虽然众多研究中已取得较为丰硕的成果,但目前的研究还是以理论研究居多。但仅在DNA计算的理论研究领域,就有许多经典的图论问题、组合优化问题、数学问题等可以用DNA计算方法来解决,即便有些问题已有DNA计算方法,但仍有可改进之处。但是,研究DNA计算方法最终是为了研制出有应用价值的DNA计算机。所以,DNA计算中生物实验操作、实验装置、实验环境、理论与实践的联接与融合就显得尤为重要,这也应该是DNA计算领域里众多专家、学者进一步努力的方向。粘贴模型和剪接模型是DNA计算中的两种最主要的模型。粘贴模型是一种通用计算机系统,该模型有着与剪接模型同样的计算能力,而且具有不需要延伸DNA链、不需要酶的参与以及材料可以重复利用等优点。因此,有关粘贴模型的研究开展得比较快,许多问题的粘贴DNA算法也相继被提出。本文就是以DNA计算的粘贴模型为基础,解决了一些困难的np完全问题,并对这些问题的算法进行了实验仿真。(1)基于Adleman解决Hamilton问题的思路详细求解顶点的最小覆盖(Minimun Vertex Cover Problem,MVCP)问题。该算法首先生成了满足顶点覆盖的所有可满足解,然后在可满足解中直接分离出最小顶点覆盖的解,这样大大提高了实验的效率与分离解的准确性。(2)基于DNA计算的粘贴模型,通过把逻辑演算问题转化为对应的开关网络图和Lipton模型的接触网络图,借鉴Lipton模型求解可满足性问题的方法解决了一个经典的逻辑演算问题,进一步开阔了DNA计算解决离散数学中各种问题的思路。(3)粘贴系统是将Watson-Crick互补原理用于DNA计算的抽象的计算模型,是一种基于粘贴运算的语言生成器。基于粘贴系统将旅行商(TravalSalesman Problem,TSP)问题转化为求赋权图中权值最小的Hamilton圈问题,按照这一思路详细求解了此np完全问题。同时,对问题编码进行了进一步完善。在解决以上三个问题时,文中都给出了具体问题的实例模型、编码、算法的详细描述,并对TSP问题进行仿真试验得出问题的正确解,从而,说明了算法的可行性和有效性。声明:由于DNA计算涉及生物实验,受实验环境所限,本文偏向理论研究,请诸位能予以谅解。

关键词： DNA计算 np完全问题粘贴模型 SAT问题 MVCP问题逻辑演算粘贴系统 TSP问题

为处理np完全问题的MANIP并行计算机系统的研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

为处理NP完全问题的MANIP并行计算机系统的研究

作者：关旭湖北大学

学位级别：硕士

在计算机科学的理论领域中,有一个尚未解决的著名的难题：np(Non-deterministic Polynomial)问题,也就是多项式复杂程度的非确定性问题。一些计算问题可以通过公式的推导得出计算结果,这些问题被称之为确定性的。但是有些问题是无法通... 详细信息

在计算机科学的理论领域中,有一个尚未解决的著名的难题：np(Non-deterministic Polynomial)问题,也就是多项式复杂程度的非确定性问题。一些计算问题可以通过公式的推导得出计算结果,这些问题被称之为确定性的。但是有些问题是无法通过计算来得到结果的,只能通过间接的方式,比如“猜想”来得到结果,这一类问题就称之为非确定性的。虽然非确定性问题没有算法可以为其来解答,但是对于某个可能的结果是正确的还是错误的仍然是有算法可以判断的。如果这个算法可以在多项式时间内计算出来,该问题就叫做多项式非确定性问题。而如果这个问题的所有可能答案,都是可以在多项式时间内进行正确与否的验算的话,该问题就叫完全多项式非确定问题。完全多项式非确定性问题可以用穷举法得到计算结果,但是这样算法的复杂程度是指数级了,因此计算的时间随问题的复杂程度成指数倍的增长,很快便变得不可计算了。为了研究这个问题,本篇论文从对np完全问题研究的发展和国内外情况入手,提出并研究MANIP网络结构——一个处理完全多项式非确定问题的并行机。接着引出分支界定算法的概念,通过对分支界定算法的前序准备工作的筹备以及算法本生基本特征的研究分析得出单处理系统是用来解决广泛多样的np完全问题最通用的技术,并且在np完全问题中融入并行的思想,得出并行的分支界定算法。并行分支界定算法要求组合排序和合并,但是一个普通内存进行大量处理器的排序可能成为系统的瓶颈,针对这一问题,论文对并行分支界定算法的两种体系配套支持进行分析与讨论,并以urn模型为实例,对该实例的性能做出分析。通过对系统中完整式分布下限的复杂度的计算与分析,进行硬件优先队列的网络优化,最后得出一个分布式智能系统,以便可以进行分布式的排序,从而达到MANIP网络体系在处理np完全问题效率上的改进。

关键词：单向环网分支界定算法分布式智能系统 np完全问题 MANIP并行计算机系统

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

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

DNA计算在NP完全问题中的应用

作者：李高安徽理工大学

学位级别：硕士

np完全问题是传统图灵计算机很难完美解决的计算问题,这类问题的解会随变量的增加呈指数增长。对于更大规模的np问题,传统图灵计算机的计算能力捉襟见肘。而DNA计算的高度并行性、高精确度和高容量储存等优点赋予了解决np完全问题新的... 详细信息

np完全问题是传统图灵计算机很难完美解决的计算问题,这类问题的解会随变量的增加呈指数增长。对于更大规模的np问题,传统图灵计算机的计算能力捉襟见肘。而DNA计算的高度并行性、高精确度和高容量储存等优点赋予了解决np完全问题新的思路。因为DNA计算不在局限于类似图灵机的线性式计算,DNA计算是基于生化反应进行的,它具有高度并行性,计算能力远超传统的电子计算机。本文研究的是基于DNA计算设计解决np完全问题的计算模型,首先对DNA分子的背景知识做了综述;同时介绍了 np完全问题的一些经典问题,如0-1整数规划问题,可满足问题,最大团问题等;然后介绍了前人设计的一些基于DNA计算的模型,并给出模型的算法。最后在前人模型的基础上提出了 DNA镊子计算模型,并将该模型运用于求解0-1整数规划问题和可满足问题,该计算模型具有较好的可行性。由于DNA计算机实现的基础就是逻辑门运算,所以在论文前面章节利用DNA镊子计算模型解决了 0-1整数规划问题和可满足问题之后,又基于DNA镊子计算模型解决了或门的运算。同时,重新建立了一个基于DNA折纸基底的链置换或门计算模型,该模型通过荧光明灭来显示运算结果的真假。通过仿真软件Visual DSD的模拟,该计算模型具有很高的可行性,而且反应过程中,很少发现错配现象,该模型在更大组合逻辑门中的应用将是可能的。图[37]表[1]参[44]

关键词： np完全问题 DNA计算 DNA链置换 DNA折纸术

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

利用光纤网络求解典型的np完全问题

利用光纤网络求解典型的NP完全问题

作者：孙翀翚北京交通大学

学位级别：硕士

随着信息时代人们对通信容量及通信质量要求的日益提高,光纤通信的重要地位日益凸显,为了能够将光纤传输的特性应用于更多的领域,在本文中,通过搭建由LD,调制器,脉冲发生器,光耦合器,EDFA,普通光纤等组成的光纤网络,选择了 np完全问题... 详细信息

随着信息时代人们对通信容量及通信质量要求的日益提高,光纤通信的重要地位日益凸显,为了能够将光纤传输的特性应用于更多的领域,在本文中,通过搭建由LD,调制器,脉冲发生器,光耦合器,EDFA,普通光纤等组成的光纤网络,选择了 np完全问题这一数学界的代表性难题进行求解,具体的工作如下:(1)以哈密尔顿回路和旅行商问题这两个典型np完全问题为代表,搭建由LD,调制器,脉冲发生器,光耦合器,EDFA,普通光纤等组成的光纤网络,利用该网络分别求解了 6节点和9节点的哈密尔顿回路,以及6节点和9节点的旅行商问题。利用输入脉冲代表行人,不同的耦合器则代表不同的城市。(2)通过设置各个耦合器的输入光纤长度不同而引进不同的时间延迟来代表到达不同城市所需的时间的不同,输入的脉冲经所给定地图输出,通过输出脉冲的延迟时间以及振幅的变化来分析问题并寻求问题的最终解。(3)本文的第二章和第三章分别利用该方法从实验的角度上求解了哈密尔顿回路问题和旅行商问题,并通过穷举法验证了该方法的准确性及可行性,为求解np完全问题提供了又一新的方法思路。同时,旅行商问题作为组合优化问题中的典型难题,通过求解TSP这一典型的组合优化问题,为现实生活中的组合优化问题,如波长分配和路由选择问题提供了理论上的又一方案。

关键词：光纤网络 np完全问题哈密尔顿回路问题旅行商问题最优问题光耦合器

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

DNA计算方法在求解np完全问题中的应用

华北工学院学报 2003年第4期24卷 282-285页

作者：韩腊萍李燕广东职业技术师范学院计算机系广东广州510065 浙江师范大学计算机科学与工程学院浙江金华321004

　DNA计算是应用分子生物技术进行计算的新方法.本文主要介绍了DNA计算的基本思想及解决np完全问题的DNA模型,讨论了目前DNA计算存在的问题和今后的发展方向.

关键词： np完全问题 DNA计算 Hamilton路径分子生物技术图论