基于粗糙集的试卷分析

数理统计法无法判断试题是否冗余，也无法算出试题的重要程度。为此，运用粗糙集理论对试卷进行分析，揭示隐藏其中的冗余信息和重要度信息。主要的价值在于找出试卷分析的一种新方法．并实例说明分析的过程。     

新的等价类划分算法—计数法

目前,基于基数排序的等价类划分算法有较低的时间复杂度但存在以下不足：属性值跳跃性大时会产生大量空队列;排序后仍需O（|P‖U|）的时间才实现划分,求出等价类,排序没能发挥应有作用。为此,设计了一种新算法,通过属性值映射避免大量空队列产生,通过增加一个记录等价类长度信息的计数数组,排序后仅需O（|U|）就可实现划分,求出等价类。整个算法时间复杂度为O（|C‖U|）,空间复杂度为O（|U|）,为求等价类划分提供了一个新的解决办法。     

新的等价类生成算法—生成支法*

目前,基于排序的等价类生成算法存在以下不足:排序后仍需高达 O（|B| |U|）的时间复杂度重复进行 运算才求得等价类,为此,设计了一种新算法。新算法采用孩子兄弟表示法,将生成等价类的过程定义为一棵二 叉树,主要采取了边生成节点边访问,一旦求得某个等价类便释放相应分支节点空间的方法。其时间复杂度为 O（|C| |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|).算法的主要贡献是将求核问题转化为等价类生成过程中兄弟的有无判断问题.通过实例验证了算法的有效性.     

基数比较法—高效的信息表求核方法

目前的求核方法大多基于决策表,基于信息表的报道不多。为此,先寻找理论依据,说明了U/C与U/（C-{a}）的内在关系,证明了U/（C-{a}）≠U/C与真细分的等价性,证明了可以通过比较等价类和它子类的基数来判断是否真细分。然后基于最高位优先基数排序思想,应用正整数有序分拆特性定义了一个用于记录和比较等价类基数的数组,接着设计了一个信息表求核算法,时间复杂度为O（|C|2|U|）,空间复杂度为O（|U|）。算法的主要贡献是将求核问题转化为等价类生成过程中的集合基数比较问题。通过实例验证了算法的正确性。