共查询到10条相似文献,搜索用时 171 毫秒
1.
粗糙集计算方法及应用研究 总被引:1,自引:0,他引:1
研究总结了粗糙集计算方法新进展,同时对它们的计算复杂性进行了分析,并给出了这些计算方法之间的逻辑关系结构图,然后讨论了粗糙集在模型方面的扩展,最后对粗糙集计算方法的应用进行了论述. 相似文献
2.
陈文彬 《广州大学学报(综合版)》2012,(2):6-9
证明了逼近MAX 3SAT-2问题在某个常数因子内是计算难解的.首先引进了一种保留近似算法难解性的K-归约的概念;然后给出了一个从MAX 3SAT问题到MAX 3SAT-2问题K-归约.因为逼近MAX 3SAT问题在某个常数因子内是计算难解的,所以逼近MAX 3SAT-2问题在某个常数因子内是计算难解的.这样作为推论也可以得到逼近MAX 3SAT-3问题在某个常数因子内是计算难解的,简化了以前关于逼近MAX 3SAT-3问题难解性的证明. 相似文献
3.
我们知道一个计算机程序是由数据结构和算法所组成的,即可以描述为数据结构十算法一程序一个被求解问题所处理的对象,总存在着一种或几种相应的数据结构作为程序代码的一部分。然而,求解问题所采用的算法就不是那么简单了,它要涉及到算法的可计算性和计算复杂性的问题。所谓可计算性是相对于函数而言的一种性质。如果一个n元函数f是一个完全函数,并且是部分可计算的,那么称它为可计算函数。函数的这种性质称为可计算性。不同的计算问题具有不同的计算复杂性,或者说不同的计算难度。对于计算机来说,计算复杂性一般是以计算时间长短或… 相似文献
4.
5.
6.
7.
算法复杂性函数等价类A[F]中的分解性定理 总被引:1,自引:1,他引:0
证明了算法复杂性函数渐近优超等价类数学结构A[F]中的分解性定理。对任意非免费算法复杂性函数类[f]∈A[F]及正整数n,存在类[g1],[g2],…,[gn]∈A[F]满足[gi]〈[f](i=1,2,…,n)且[f]=Vi=1^n[gi]。 相似文献
8.
模糊聚类分析的传递方法 总被引:7,自引:0,他引:7
针对常规模糊聚类分析在履行模糊相似关系时存在的复杂矩阵害虫乘运算问题,提出了模糊聚类递算法,通过设置主水平λ,直接从模糊相似关系获得聚类结果,并证明该方法与传递闭包法等价,但时间复杂度和空间复杂度都要远远小于传递闭法。 相似文献
9.
计算时间下界的传统的方法是直接从算法的ADT高度来分析或借助于问题的变换来分 析.本文提出估计算法计算时间下界的一条新思路,借助于问题的嵌入来分析计算时间下界.由此 可获得一些传统方法不易得到的结果. 相似文献
10.
陈文彬 《广州大学学报(自然科学版)》2014,(1)
证明了逼近4正则图的最小顶点覆盖问题在某个常数因子内是计算难解的.相似地,对于5正则图、6正则图等的最小顶点覆盖问题,这个结论也成立.已知逼近3正则图的最小顶点覆盖问题在某个常数因子内是计算难解的,文章扩展了这个结果到4正则图情况,用K-归约证明这个结果,给出了一个从3正则图的最小顶点覆盖问题到4正则图的最小顶点覆盖问题的K-归约. 相似文献