基于简化的二进制差别矩阵的快速求核算法  

Quick Computing Core Algorithm Based on Simply Binary Discernibility Matrix

作　　者：徐章艳[1] 杨炳儒[2] 宋威[2] 

机构地区：[1]广西师范大学计算机系,桂林541004 [2]北京科技大学信息工程学院,北京100083

出　　处：《小型微型计算机系统》2006年第9期1711-1714,共4页Journal of Chinese Computer Systems

摘　　要：目前,基于二进制差别矩阵的求核算法有如下不足:算法的时间和空间复杂度不理想;所得到的核与基于正区域的核不一致.叶东毅教授提出了一个新的二进制差别矩阵并证明了在新的二进制差别矩阵中定义的核与基于正区域的核是一致的,但计算新的二进制差别矩阵除了具有和原方法相同的存储空间外,还增加了额外的计算.本文给出一个简化的二进制差别矩阵和相应的求核算法,并证明了所求的核是基于正区域的核.新算法的时间复杂度和空间复杂度分别被降为m ax{O(C(U’p os‖U/C)),O(C‖U)}和m ax{O(U),O(C(U’p os‖U/C))}.At present, the computing core algorithm based on binary discernibility matrix has the following shortcomings： the time complexity and space complexity is not good; the core acquired from this algorithm is not the core based on positive region. The professor Ye Dong-yi provided a new binary discernibility matrix and correspondence computing core algorithm, and proved that the core acquired from Ye＇ s algorithm is the core based on positive region. The space complexity of computing the new binary discernibility matrix is the same as the old method, but computation of Ye＇ s method is more than computation of the old method. In this paper, a simply binary discernibility matrix and correspondence computing core algorithm are provided. It is also proved that the core acquired from new algorithm is the core based on positive region. The time complexity and space complexity of the new algorithm are cut down max {O（ ｜C｜（ ｜U′pos‖U/C｜））,O（｜C‖U ｜）}and max{O（ ｜U｜）,O（｜C｜（ ｜U′pos‖ U/C｜）） } respectively.

关 键 词：粗糙集 二进制差别矩阵 简化的二进制差别矩阵 核 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]