基于多线程技术的分辨函数析取范式生成算法  

Disjunction Normal Form Generation Algorithm of Discernibility Function Based on Multi-thread Technology

作　　者：蒙祖强[1] 周石泉[1] 黄柏雄[1] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机工程》2013年第1期45-48,53,共5页Computer Engineering

基　　金：国家自然科学基金资助项目(61063032);广西自然科学基金资助项目(2012GXNSFAA053225)

摘　　要：基于分辨矩阵计算信息系统的所有约简,都需要将合取范式转化为析取范式,但是该转化过程存在组合爆炸问题。为解决该问题,根据合取范式、合取运算和析取运算的特点,构建析取范式转化的并行模型,提出基于多线程技术的分辨函数析取范式生成算法,利用Windows的自动线程调度功能提高范式转换的效率。实验结果表明,该算法的析取范式转化效率会随着合取范式长度的增加而提高,适合在多核CPU计算机上运行。It is required to translate conjunction normal form into disjunction normal form when using discernibility matrix to compute all reducts of an information system.But there exists the combination explosion problem in this transformation process.Following the properties of conjunction normal form,And operator and OR operator,this paper constructs a parallel model for the transformation process,and then proposes a multi-thread technology-based algorithm for generating disjunction normal forms.The proposed algorithm improves the efficiency of transformation by using the functions of automatic thread scheduling of Windows.Experimental results show that the algorithm seems more efficient in the cases where conjunction normal forms have relatively large length,making good use of multi-core CPU resources of computers.

关 键 词：属性约简 分辨函数 多线程技术 并行模型 析取范式 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]