本原?-LFSR序列距离向量性质研究

根据不同类距离向量的分量大小关系,对本原?-LFSR的距离向量进行分类,每一个距离向量有n!个等价类。通过研究距离向量的基本性质,得到一类Z本原?-LFSR的距离向量的期望为(0, T/2, T/2,…, T/2),在此基础上给出2种Z本原?-LFSR的构造方法。对距离向量和线性复杂度之间的关系进行讨论,得出距离向量到线性复杂度是一个满射的结论。     

广义Legendre序列线性复杂度的分布

对广义Legendre序列线性复杂度的分布进行了估计,发现绝大多数广义Legendre序列有大的线性复杂度.给出了一个方法以得到具有大线性复杂度的广义Legendre序列.     

F_p上周期序列S~∞与~∞的线性复杂度分析

研究了有限域Fp上周期序列S∞的极小多项式、生成函数和它的对偶序列S∞的极小多项式及生成函数之间的关系,并建立了明确的关系式。这一结果对研究流密码密钥序列线性复杂度有一定的应用价值。     

赫夫曼树遍历算法的优化

对数据结构中赫夫曼树和赫夫曼遍历的算法问题进行探讨,针对传统使用的遍历算法存在循环次数较多、算法时间复杂度较大问题,通过修改参数和循环体结构对原有算法进行改进,从而减少循环次数,降低算法时间复杂度,同时也提出了动态编码算法等的优点和可行性。     

Dm-KDE: dynamical kernel density estimation by sequences of KDE estimators with fixed number of components over data streams

In many data stream mining applications, traditional density estimation methods such as kernel density estimation, reduced set density estimation can not be applied to the density estimation of data streams because of their high computational burden, processing time and intensive memory allocation requirement. In order to reduce the time and space complexity, a novel density estimation method Dm-KDE over data streams based on the proposed algorithm m-KDE which can be used to design a KDE estimator with the fixed number of kernel components for a dataset is proposed. In this method, Dm-KDE sequence entries are created by algorithm m-KDE instead of all kernels obtained from other density estimation methods. In order to further reduce the storage space, Dm-KDE sequence entries can be merged by calculating their KL divergences. Finally, the probability density functions over arbitrary time or entire time can be estimated through the obtained estimation model. In contrast to the state-of-the-art algorithm SOMKE, the distinctive advantage of the proposed algorithm Dm-KDE exists in that it can achieve the same accuracy with much less fixed number of kernel components such that it is suitable for the scenarios where higher on-line computation about the kernel density estimation over data streams is required.We compare Dm-KDE with SOMKE and M-kernel in terms of density estimation accuracy and running time for various stationary datasets. We also apply Dm-KDE to evolving data streams. Experimental results illustrate the effectiveness of the proposed method.     

一类两阶段杂交流水作业的近似算法

讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务:第1个任务可以在任何一台机器上加工,第2个任务只能在第1个任务完成后在第2台机器上加工.如果要求在加工同一个工件的两个任务时,两个任务之间不能有停顿,则称其为不可等待的模型,记作NSHFS.如果第2个任务可以在第1个任务完成后的任意时间加工,则称其为允许等待的模型,记作SHFS.对于SHFS模型,在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5的多项式时间近似算法.对于NSHFS模型,首先证明它是NP-难的,并且给出了一种最坏情况界为5/3的多项式时间近似算法.     

一类本原σ-LFSR 序列的构造与计数

有限域GF(2k)上本原σ-LFSR序列的分量序列均是二元域上具有相同极小多项式的m-序列,已知一条GF(2k)上本原σ-LFSR序列的距离向量,就可以用二元域上的m-序列构造它.研究了一类本原σ-LFSR序列——Z本原σ-LFSR序列距离向量的计算问题.给出了一种GF(2k)上n级Z本原σ-LFSR序列距离向量的计算方法,其主要思想是,利用GF(2k)上1级Z本原σ-LFSR序列的距离向量来计算n级Z本原σ-LFSR序列的距离向量.与其他现有方法相比,该方法的效率更高.更有价值的是,该方法也适用于GF(2k)上n级m-序列距离向量的计算.最后给出了GF(2k)上n级Z本原σ-LFSR序列的计数公式,说明其个数比GF(2k)上n级m-序列更多.     

m子序列的密码学性质研究*

文中所提m子序列是根据m序列的状态转换特征,通过交叉改变状态转换次序而形成新的序列。通过随机性测试软件（NIST）验证m子序列具有和m序列相似的随机性,使用BM算法可以得出这种伪随机序列具有非常高的线性复杂度,同时验证了其补序列也具有非常高的线性复杂度,并说明m子序列具有良好的线性复杂度谱,抗线性攻击能力强。m子序列的数量庞大,一个周期为 的m序列,改变反馈函数就可以至少产生 个m子序列。产生m子序列的反馈函数经证明具有良好的代数免疫度,抗代数攻击能力较强。m子序列具有良好的密码学性质,应用前景良好。     

值域增长约束满足问题的无回溯与随机行走策略的算法复杂性分析

值域增长的约束满足问题模型是计算复杂性理论中一类重要的实际问题模型,针对解决这类问题的算法研究仍然很少。通过研究RB模型这一典型的值域增长约束满足问题,发现当问题规模很大时,无回溯策略比随机行走策略更加有效。这与典型的值域确定的约束满足问题如SAT问题不同,是值域增长的约束满足问题所特有的性质。通过实验研究了两种策略的表现,并进一步对两种策略的表现进行了分析。     

基于过程蓝图的程序环路复杂性度量方法

提出一种基于过程蓝图的程序环路复杂性度量实现方法。将传统基于程序控制流图的度量信息抽取变为对过程蓝图的实现层表示-抽象实现结构图的信息抽取，避免程序源代码的语法分析和控制流图的构造，简化度量过程和实现，并提高度量处理的效率。