基于有序差别集的高效属性约简算法

基于可分辨矩阵的属性约简算法需要占用大量的存储空间,可分辨矩阵中许多元素项对约简是多余的;并且随着问题规模的增大,该类算法的效率并不理想。针对上述不足,提出一种基于有序差别集的属性约简算法,该算法不需要创建可分辨矩阵和生成多余的元素项,大大降低了存储量和计算量,从而提高了属性约简效率,使算法的时间复杂度和空间复杂度分别降为max{O（|C|² |U/C|²）,O（|C|²|MsCount|）}和O（|MsCount|）。实验表明该算法是有效的、高效的。     

基于二进制可分辨矩阵的快速求核算法

目前,求核算法存在以下不足：求得的核与正区域的核不一致,求核算法的时间复杂度和空间复杂度不理想。针对上述问题,给出一种二进制可分辨矩阵的定义及其求核性质,并证明了由该性质获得的核与正区域的核是等价的,然后设计求核算法,该算法的时间复杂度为max{O（|C||U/C|²）,O（|C||U|）},空间复杂度为O（|C||U/C|²）。最后实例说明该方法的可行性和有效性。     

基于RS码的可重构有限域乘法器的设计与实现

为了提高伽罗华有限域乘法器的通用性,降低实现的复杂度,采用自然基算法,用简单的逻辑门电路实现乘法运算过程。提出可重构的迭代计算结构,能满足域长m为3～8的乘法器,并用FPGA实现。结果表明,可重构有限域乘法器能够满足多种标准RS码的乘法运算的需要。     

可重构电子系统芯片级在线自主容错方法研究

可重构电子系统芯片固定型故障的传统容错设计往往采用集中式控制方法,存在测试时间长、硬件资源利用率低、对外部控制器依赖性高等问题。因此,设计了一种具有分布式自主容错能力的可重构细胞阵列,通过将细胞内部查找表输出与参考值进行比较的方式进行循环检测,并利用冗余存储单元对故障查找表进行修复。以四位并行乘法器为例进行仿真验证,实验结果表明,新型可重构阵列的自主容错设计方法,比现有设计的硬件开销小,修复时间短,容错能力强,且设计复杂度不受阵列规模影响。     

单位处理时间的多处理机任务调度近似算法

研究多处理机任务调度模型P_m|fix,p_j=1|C_max,即在m个处理机系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。其更一般的问题是P_m|fix|C_max,在网络并行计算、多播系统及工程规划等领域都有广泛的应用。该问题早已证明为NP难问题,而且也不存在常数近似算法。基于部分调度和宽度优先原则构造了该问题的一个多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为2m+1,优于已有文献中2m的目前最好结果。     

一种新的信息熵属性约简算法

给出一个区分对象对的属性约简定义,同时证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出区分对象对集,首先给出了一个快速求简化决策表的算法,其时间复杂度为O（|C||U|）。然后在简化决策表的基础上,设计了基于区分对象对集的信息熵属性约简算法,其时间复杂度和空间复杂度分别为O（|C||U|）+O（|C||U/C|²）和O（|U/C|²）+O（|U|）,最后用一个实例说明了新算法的高效性。     

应用团划分方法改进多处理机任务近似调度

研究多处理机任务调度模型P_m|fix,p_j=1|C_max,即在m个处理机系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。这类问题在网络并行计算、多播系统及工程规划等领域都有广泛的应用,但早已被证明为NP难问题,而且也不存在常数近似算法。基于团划分方法构造了该问题的多项式时间近似算法,通过模拟实验进行了验证,和最大宽度优先（LWF）算法相比,该算法花费时间较长,近似比性能要好。     

改进的多目标元素量子搜索算法

Grover量子搜索算法解决了未加排序的数据库搜索问题,在2ⁿ个元素中搜索M个目标元素,其计算复杂度为O（（2ⁿ/M）^-2）,相对于经典算法实现了二次加速,但是,当目标元素个数接近2ⁿ/2时该算法成功率只达到50%。从任意相位的Grover变换从发,给出一种改进的多目标元素量子搜索算法,该算法在目标元素个数M≥2ⁿ/4时,只用一次Grover变换就能以概率1完成搜索。     

基于互补电阻开关的忆阻乘法器设计

现有的忆阻算术逻辑多采用单个忆阻器作为存储单元,在忆阻交叉阵列中易受到漏电流以及设计逻辑电路时逻辑综合复杂度高的影响,导致当前乘法器设计中串行化加法操作的延时和面积开销增加。互补电阻开关具有可重构逻辑电路的运算速度和抑制忆阻交叉阵列中漏电流的性能,是实现忆阻算术逻辑的关键器件。提出一种弱进位依赖的忆阻乘法器。为提升忆阻器的逻辑性能,基于互补电阻开关电路结构,设计两种加法器的优化方案,简化操作步骤。在此基础上,通过改进传统的乘法实现方式,并对进位数据进行拆解,降低运算过程中进位数据之间的依赖性,实现并行化的加法运算。将设计的乘法器映射到混合CMOS/crossbar结构中,乘法计算性能得到大幅提高。在Spice仿真环境下验证所提乘法器的可行性。仿真实验结果表明,与现有的乘法器相比,所提乘法器的延时开销从O(n²)降低为线性级别,同时面积开销降低约70%。     

分组排序算法

提出了分组排序算法,详细分析了算法的原理及其时间与空间复杂度,得出了在最坏情况下的时间复杂度是θ（mn）;最好情况和平均情况下的时间复杂度均是θ（nlog（n/m^k））;在最坏情况下的空间复杂度是O（mn-m²＋m）;最好情况和平均情况下的空间复杂度均是O（m^klog（n/m^k））;并用多组随机数据与效率较高的快速算法进行仿真对比实验,试验结果说明了文中结论的正确性。这一结果,将有助于进一步设计高效的海量数据分析方法。     

扩展在上GF（3）新型自缩序列模型及研究

自收缩序列是一类重要的伪随机序列,而周期和线性复杂度是序列伪随机性的经典量度。如何构造自缩序列的新模型,使生成序列具有大的周期和高的线性复杂度是一个重要的问题。针对这一问题,构造了GF（3）上一种新型的自缩序列模型,利用有限域理论,研究了生成序列的周期和线性复杂度,得到一些主要结论：周期上界3ⁿ,下界3^2[n/3];线性复杂度上界3ⁿ,下界3^2[n/3]-1。进一步讨论了基于GF（3）上本原三项式和四项式的自缩序列的周期和线性复杂度。     

基于改进的差别矩阵的快速属性约简算法

为了解决基于差别矩阵属性约简的计算效率问题,首先以计数排序的思想设计了一个新的计算U/C的高效算法,其时间复杂度降为O(|C||U|)。其次分析了基于差别矩阵的属性约简算法的不足,提出了改进的差别矩阵的定义,利用快速计算核属性算法生成的核属性和出现频率最多的属性来降低差别矩阵的大小,并设计了基于改进的差别矩阵的快速属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为max(O|C|2Σ0≤i相似文献   

快速提高NSGA-Ⅱ算法双目标优化效率的方法

NSGA-Ⅱ是一种性能优良的多目标进化算法,近年来非常流行。为了进一步改进NSGA-Ⅱ在双目标优化时的效率,采取了按需分层的策略,提出了一种新的非支配前沿集分层方法以替代NSGA-II原有的分层方法。与NSGA-Ⅱ的时间复杂度O(N2)相比,新方法的时间复杂度减少为O(kN+NlogN),k为所分前沿层数(k<相似文献   

快速的属性约简算法

属性约简的效率是粗糙集等软计算理论的核心问题之一。为了提高约简效率,在分析不可分辨关系和基数排序特点的基础上,提出了一种时间复杂度为O（|C||U|）的求核算法。然后,运用改进的属性重要度作为启发信息,得到一种快速的属性约简算法,时间复杂度为O（|C|²|U|）。最后,通过UCI机器学习库中的一些数据集对算法进行测试,证明了算法对大型的数据集进行属性约简的高效性。     

一类具有低相关特性和较大线性复杂度的序列集

对于p=3和偶数n=2k,构造了一类周期为3ⁿ-1大容量序列集S^(r),这里r与3^k-1互素。这类序列集的相关函数取-1±3^k,-1,-1+2&#8226;3^k四值,并完全确定了相关值的分布。通过选取适当的参数r,证明了这类序列集具有较大的线性复杂度下界。     

一种基于Voronoi图的高效异常检测方法

提出了一种新的基于Voronoi图的异常检测方法。采用Voronoi图来确定对象间的邻近关系,定义了一种新的异常因子,算法的时间复杂性为O（nlogn）。实验结果表明,同现有的算法相比具有较高的检测效率和准确性。     

高速可配置RS纠删解码器的VLSI设计

目前对可配置纠错与删除(纠删)解码器研究较少。为此,采用性能优异的RS编码方法,提出一种高速可配置RS纠删解码器的超大规模集成电路(VLSI)架构,并详述可配置纠删BM模块的构成。该架构通过折叠技术,使解码器在保证高速的前提下降低硬件复杂度。通过0.18 μm工艺和Design Complier工具综合测试结果表明,与同类解码器研究相比,该解码器在硬件复杂度吞吐率和可配置性方面,均具有较大优势。     

单体型组装MEC问题的参数化算法研究

单体型组装MEC问题指如何利用个体的DNA测序片断数据,翻转最少的SNP位点值以确定该个体单体型的计算问题。根据片段数据的特点提出了一个时间复杂度为 O（nk₂2^k₂+mlogm+mk₁）的参数化算法,其中m为片段数,n为单体型的SNP位点数,k1为一个片断覆盖的最大SNP位点数（通常小于10）,k₂为覆盖同一SNP位点的片段的最大数（通常不大于10）。对于实际DNA测序中的片段数据,即使m和n都相当大,该算法也可以在较短的时间得到MEC问题的精确解,具有良好的可扩展性和较高的实用价值。