计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2009年
22期
34-37
,共4页
粗糙集%信息表%等价类%真细分%基数比较
粗糙集%信息錶%等價類%真細分%基數比較
조조집%신식표%등개류%진세분%기수비교
rough set%information table%equivalence class%real subdivision%comparing radix
目前的求核方法大多基于决策表,基于信息表的报道不多.为此,先寻找理论依据,说明了U/C与E/(C-{a})的内在关系,证明了U/(C-{a})≠U/C与真细分的等价性,证明了可以通过比较等价类和它子类的基数来判断是否真细分.然后基于最高位优先基数排序思想,应用正整数有序分拆特性定义了一个用于记录和比较等价类基数的数组,接着设计了一个信息表求核算法,时间复杂度为O(|C|2|U|),空间复杂度为0(|U|).算法的主要贡献是将求核问题转化为等价类生成过程中的集合基数比较问题.通过实例验证了算法的正确性.
目前的求覈方法大多基于決策錶,基于信息錶的報道不多.為此,先尋找理論依據,說明瞭U/C與E/(C-{a})的內在關繫,證明瞭U/(C-{a})≠U/C與真細分的等價性,證明瞭可以通過比較等價類和它子類的基數來判斷是否真細分.然後基于最高位優先基數排序思想,應用正整數有序分拆特性定義瞭一箇用于記錄和比較等價類基數的數組,接著設計瞭一箇信息錶求覈算法,時間複雜度為O(|C|2|U|),空間複雜度為0(|U|).算法的主要貢獻是將求覈問題轉化為等價類生成過程中的集閤基數比較問題.通過實例驗證瞭算法的正確性.
목전적구핵방법대다기우결책표,기우신식표적보도불다.위차,선심조이론의거,설명료U/C여E/(C-{a})적내재관계,증명료U/(C-{a})≠U/C여진세분적등개성,증명료가이통과비교등개류화타자류적기수래판단시부진세분.연후기우최고위우선기수배서사상,응용정정수유서분탁특성정의료일개용우기록화비교등개류기수적수조,접착설계료일개신식표구핵산법,시간복잡도위O(|C|2|U|),공간복잡도위0(|U|).산법적주요공헌시장구핵문제전화위등개류생성과정중적집합기수비교문제.통과실례험증료산법적정학성.
At present,approaches to compute the core based on decision table are in the overwhelming majority,and based on information table are in the tiny minority.For this reason,beginning with seeking theoretical basis,the inherent correlation between UIC and UI(C-{a}) is explained,and the equivalence relation between UI(C-{a})≠U/C and real subdivision is discovered,and so is that real subdivision can be judged whether it is true or not by comparing an equivalence class radix with its subelass's.Then basing on principle of most significant ditital radix sorting,and applying property of positive integer ordered partition,an array used for recording and comparing the radix of equivalence classes is defined,and then an algorithm for computing the core of information table is designed.Its time complexity is O(|C|2|U|),and the space complexity is O(|U|).Tbe important contribution that it made is the way to get the core is transformed into comparing set radix during the course of generating equivalence classes.lts correctness is verified by the example.