关于排列集p（n,r）的几种有效算法

本文在按字典排序的前提下，给出了生成排列集ｐ（ｎ，ｒ）的枚举算法，为建立ｐ（ｎ，ｒ）与它的反相集合的映射及逆映射，提供了一对编解码算法；在此编解码算法的基础上，为建立ｐ（ｎ，ｒ）与ｚ＝｛１，２，…，│ｐ（ｎ，ｒ）│｝之间的一一映射关系，还给出了相应的排序和逆排序算法。实际上，我们给出的这些算法，与已知的算法相比，更具有普遍性和优越性。     

基于索引数组与集合枚举树的最大频繁项集挖掘算法

由于其内在的计算复杂性,挖掘密集型数据集的全部频繁项集非常困难,解决方案之一是挖掘最大频繁项集。集合枚举树是最大频繁项集挖掘算法中常用的数据结构,最大频繁项集的挖掘过程也可以看作是集合枚举树的搜索过程。为缩小集合枚举树的搜索空间,采用宽度优先和深度优先相结合的混合搜索策略,提出了一种新的最大频繁项集的挖掘算法Index-MaxMiner。该算法首先设计了索引数组这种新的数据结构,并给出了一个基于二进制位图技术的索引数组的计算方法。通过为每个频繁项增加包含索引,Index-MaxMiner利用一次宽度优先搜索得到了候选最大频繁项集,使集合枚举树的第一层结点个数大幅度减少。然后在候选最大频繁项集中通过深度优先搜索,得到全部最大频繁项集,从而实现了集合枚举树的跳跃式搜索,大大缩小了搜索空间。实验结果表明,该算法可有效提高最大频繁项集的挖掘效率。     

SQL Server BI Development Studio使用技巧系列（一）

Foreach循环容器定义包中的重复控制流。循环的实现与编程语言中的Foreach循环结构类似。在包中，通过使用Foreach枚举器启用循环。Foreach循环容器将重复指定枚举器的每个成员的控制流。本期文章中。我们介绍其中两种常用的枚举器使用方法：Foreach文件枚举器、ForeachADO枚举器。[编者按]     

一种频繁核心项集的快速挖掘算法

传统的频繁核心项集挖掘需多次生成和反复扫描数据库,导致生成效率低下。为此,提出一种快速生成频繁核心项集算法FMEP。该算法使用Rymon枚举树作为搜索空间,并采用分而治之的策略选择特定的路径进行剪枝。利用频繁核心项集特有的反单调性质,可以快速地判断某一个候选项集是否为频繁核心项集,而无需和所有直接子集的析取支持度进行比较。通过上述方法,可以达到快速挖掘的目的。实验结果证明,该算法能够在挖掘出所有的频繁核心项集精简表示元素的同时,降低消耗时间,与MEP算法相比,在密集型数据集上的时间可缩短2倍以上,在稀疏型数据集上时间至少缩短30%。     

基于枚举策略的三倍体个体单体型重建算法

求解三倍体个体单体型对于探索三倍体物种的遗传特性和表型差异等方面的研究具有重要的推动作用。针对带基因型信息的最少错误更正(MEC/GI)模型,提出了一种基于枚举策略的三倍体个体单体型重建算法EHTR。该算法依次重建3条单体型上的每一个单核苷酸多态性位点取值,对于给定位点,首先根据其基因型取值枚举该位点的3种单体型取值情况,然后选择片段支持度最高的取值作为该位点的重建值,算法的总时间复杂度为O(mn+mlogm+cnl)。采用CELSIM和MetaSim两种测序片段模拟生成器生成实验测试数据,在片段覆盖率、错误率、单片段长度、单体型长度和单体型海明距离等参数的不同设置下,对算法EHTR,GTIHR,W-GA和Q-PSO的重建率和运行时间进行对比分析。实验结果显示,算法EHTR在不同的参数设置下均能以更短的运行时间获得更高的重建率。     

基于量子逻辑的图灵机及其通用性

基于量子逻辑的自动机理论是量子计算模型的一个重要研究方向.该文研究了基于量子逻辑的图灵机(简称量子图灵机)及其一些变形,给出了包括非确定型量子图灵机l-VTM,确定型量子图灵机l-VDTM以及相应类型的多带量子图灵机,并引入量子图灵机基于深度优先与宽度优先识别语言的两种不同定义方式,证明了这两种定义方式在量子逻辑意义下是不等价的.进一步证明了l-VTM、l-VDTM与相应类型的多带量子图灵机之间的等价性.其次,给出了量子递归可枚举语言及量子递归语言的定义,并给出了二者的层次刻画,证明了l-VTM与l-VDTM不等价,但两者作为量子递归语言的识别器是等价的.最后,文中讨论了基于量子逻辑的通用图灵机的存在性问题,给出了一套合理编码系统,证明了基于量子逻辑的通用图灵机在其所取值的正交模格无限时不存在,而在其所取值的正交模格有限时是存在的.     

上下文无关语言句子的反向自然枚举

在测试基于复杂数据结构的程序时,需要用到上下文无关语言句子的枚举.基于上下文无关语言按推导树高度的分层构造,提出了句子的反向自然枚举算法.通过堆、层、簇和长方体将句子划分为有穷集合序列,该算法的时间效率为O(n),n是被枚举句子的长度.实验数据表明,该算法是高效的,且应用更加便利.     

基于故障行为的模型诊断方法

提出一种利用故障行为求解所有极小诊断的新方法,并结合带有终止节点的集合枚举树形式化地表达计算过程,逐步生成所有的极小诊断.该方法不用求解冲突集及冲突集的碰集,一次直接求出所有的极小诊断,避免了由于调用基于假设的真值维护系统时的组合爆炸而引起的NP-完全问题.在集合枚举树中添加了终止节点,从而避免了非极小诊断的产生,且不会因剪枝而丢失正确的解.实验结果表明,该算法程序容易编制,且效率较好,可以满足复杂的被诊断对象的实时性要求.     

RAIN-128算法的中间相遇攻击

RAIN是一族SPN结构的轻量级分组密码算法,该算法具有软硬件实现效率高、安全性强等特点。中间相遇攻击被广泛应用于分组密码算法的安全性分析中。该文通过分析RAIN-128的结构特性和截断差分特征,利用差分枚举技术分别构造了4轮和6轮中间相遇区分器,给出了8轮及10轮的中间相遇攻击。当攻击轮数为8轮时,预计算阶段的时间复杂度为$ {2^{68}} $次8轮RAIN-128加密,存储复杂度为$ {2^{75}} $ bit,在线攻击阶段的时间复杂度为$ {2^{109}} $次8轮加密,数据复杂度是$ {2^{72}} $个选择明文;当攻击轮数为10轮时,预计算阶段的时间复杂度为$ {2^{214}} $次10轮加密,存储复杂度为$ {2^{219}} $ bit,在线攻击阶段的时间复杂度为$ {2^{109}} $次10轮加密,数据复杂度是$ {2^{72}} $个选择明文,分析结果显示,RAIN-128可以抵抗中间相遇攻击,并具有较高的安全冗余。     

基于PDIUSBD12的USB设备固件程序开发

介绍了基于PDIUSBD12芯片的USB设备硬件组成,详细论述了USB枚举的具体过程和基于PDIUSBD12的MCU固件编程思想,给出了部分单片机C程序代码,分析了制约实际数据传输速率的原因,并提出了解决方法。