CAJ | 학술논문

基于信息表的求核算法存在如下不足:需要完整求出U/R后方可求核.为此,先寻求理论依据,说明U/R与U/(R-{a})的内在关系,得出了[x]R-{a}/{a}细分[x]R-{a}的结论,证明了U/(R-{a})≠U/R与"U/R元素有兄弟"的等价性.然后基于二叉树设计思想,用兄弟存储结构设计了一个新的信息表求核算法,仅需生成较小的二叉树就能求核,时间复杂度和空间复杂度分别为O(|C|2|U|)和O(|U|).算法的主要贡献是将求核问题转化为等价类生成过程中兄弟的有无判断问题.通过实例验证了算法的有效性.
기우신식표적구핵산법존재여하불족:수요완정구출U/R후방가구핵.위차,선심구이론의거,설명U/R여U/(R-{a})적내재관계,득출료[x]R-{a}/{a}세분[x]R-{a}적결론,증명료U/(R-{a})≠U/R여"U/R원소유형제"적등개성.연후기우이차수설계사상,용형제존저결구설계료일개신적신식표구핵산법,부수생성교소적이차수취능구핵,시간복잡도화공간복잡도분별위O(|C|2|U|)화O(|U|).산법적주요공헌시장구핵문제전화위등개류생성과정중형제적유무판단문제.통과실례험증료산법적유효성.
The core computation algorithms based on information table have the following shortcoming:U/R must be calculated completely before computing the core. To overcome this shortcoming, the inherent correlation between U/R and U/(R-{a}) was explained, the conclusion of [x]R-{a}/{a} subdividing [x]R-{a} was made, and the equivalence relation between U/(R-{a})≠U/R and the conclusion that an U/R element has a brother was discovered. Then based on binary tree and child-brother storage structure, a novel algorithm for computing the core of information table was designed. The core was computed only by generating a small binary tree. The time and the space complexities of the new algorithm are O(|C|2|U|) and O(|U|) respectively. Therefore, the problem to compute the core can be transformed into judging whether it has a brother during the course of generating equivalence classes. This method was verified effective by an example.