遍历从N个相异元素中取M个元素可能排列的新算法

给出了遍历从N个相异元素中取M个(N≥M)元素可能排列的新算法．新算法中放弃了首先将全部可能节点进行字典排序，然后按序逐个生成的传统思想，实现了每进行一次数据交换即产生一个新节点，从而极大地提高了遍历的效率。     

PMkSK:一种空间关键字移动近邻查询并行处理方法

为了提高空间关键字移动k近邻查询处理效率,提出关键字影响集的概念,并设计了一种基于关键字影响集的空间关键字移动近邻查询并行处理方法.该方法包含一种并行查询算法和一种并行验证算法.首先,采用并行查询算法计算近邻结果;然后,确定查询区域,并在区域内查找包含的关键字影响集;最后,在查询者移动时不断通过并行验证算法验证影响集,以实现空间关键字移动近邻查询处理.实验结果表明:这2种算法的时间复杂度分别为O((log D+k)/k)和O(logk),均为现有对应算法的O(1/k),其中D为空间对象数目.在多核系统上,这2种算法的运行时间均比现有算法低一个数量级.基于影响集的并行查询处理方法避免了基于安全区域的移动k近邻查询处理方法中更新代价和更新频率难以同时取得最优的固有缺点,可以高效地处理关键字移动k近邻查询.     

基于语义单元表示树剪枝的关键字过滤方法

传统的关键字过滤技术满足了人们一定的需要,但是其灵活性差,效果有限,难以识别和过滤变形过的关键字. 本文将语义单元应用在网络监测中,提出了一种新的关键字过滤方法. 这种方法可以有效地识别和过滤网络中经过变形的关键字,其时间复杂度为O(L)而非O(LN),其中L是文本的长度,N是关键字集的规模,即无论关键字集有多么大的规模,算法消耗的时间是固定不变的,这对网络监测和信息过滤有着较强的实用性.     

关于辗转相除法所进行的次数问题的探讨

设a,b∈N(N为自然数集),且a>b,对a,b进行转转相除,则其中所进行的辗转相除求得r_a的次数为n。将任意a,b∈N进行辗转相除,对其可进行的最多次数的估计,有下述定理。定理,设a,b∈N,a>b>1,它们辗转相除所进行的次数为n,则     

量子K-近邻算法

为了提高经典K-近邻算法的效率,引入量子计算理论,将Grover算法中的Oracle算子以及相位估计算法嵌入经典K-近邻算法,提出一种量子K-近邻算法.该算法首先将样本点和待分类点的向量信息制备成量子叠加态,采用可逆的量子控制交换门并行计算待分类点和样本点的相似度,然后利用相位估计算法将相似度信息存储到量子比特中,最后使用Grover算法一次性搜索出最相似的k个点.对嵌入的量子计算部分的理论分析结果表明,量子K-近邻算法可以明显降低经典计算复杂度,且提出的算法在已有算法计算复杂度O(RkM)的基础上,再次带来了k值的二次加速O(RkM),其中R为Oracle算子的执行次数,M为样本全局个数.     

关于二进制GCD算法的注记

求两个正整数a、b的最大公因子 gcd (a ,b)通常使用经典的Euclid算法 .因共需O(lnN)次带余除法 ,每次带余除法耗时O(ln2 N) ,所以Euclid算法耗时O(ln \% 3 N) ,这里N =max(a ,b) ,文献 [1 ,Corollary 2 .1 ]和 [2 ,例 5]就是这样粗略估算的 .然而 ,如果在实现算法时考虑到每步带余除法被除数的位数在不断下降 ,总运行时间将仅为O(ln2 N) ,文献 [3,p .32 8]和文献 [4,p .1 3]指出并证明了这一点 ,在文献 [5]定理 1的证明中也提到了这个事实 .1 96 1年Stein发明了一种求 gcd的新算法 (见 [J .Comp .Phys .1 (1 96 7) ,397- 40 5]) ,简…     

一道难题征解的简证及引申

浙江师大主办《中学数学教研》1992年第10期上有如下一道难题征解:28*　设N为自然数集,N0,1为由数字0和1组成的所有正整数的集合.证明或否定:对a∈N,b∈N,有ab∈N0,1.下面利用集合中元素的无穷性构造b给出一个简证.证明　令M={n|n=10i,i∈N}N0,1,显然为无穷集.a∈N,M中的每个元素用a取模,分成a个子集,其中第k个表示为:Ma,k={s|s∈M,k=s(moda),(0≤k≤a-1)}(1)若Ma,0非空,则结论显然成立;(2)若Ma,0为空集,则Ma,1,Ma,2,…,Ma,a-1中至少存在一无穷集,否则,M将为有穷集,矛盾.不妨设Ma,k为无穷集.从Ma,k中任取a个两两互不相同的元素10im(…     

基于扩展Dewey编码的XML文档关键字查询算法研究

为实现XML关键字查询,提出一种基于扩展Dewey编码快速求解SLCA的新算法:FEDA.算法利用Dewey扩展编码快速命中含有N个关键字的集合,将最终交集看做一棵简化的XML树,所有的叶节点即为求解的SLCA.该算法与经典的ILE算法进行对比,效率优于ILE算法.     

Hankel矩阵的离散Cosine变换的快速算法

在图像和信号处理研究邻域．经常会涉及到结构矩阵的离散sine、快速傅里叶变换(FFT)及离散cosine变换．献[6]的作利用FFT给出了离散cosine变换的一个算法．计算变换矩阵的M个元素所需的计算量和存贮空间分别为O(N^2log N) O(M)和O(N^2)．本利用Hankel矩阵的结构特点导出一递推关系式(见式(8))．给出了Hankel矩阵的离散cosine变换(DCT)的一个快速算法．该算法所需要的存贮空间为O(N)．计算变换矩阵的M个元素所需的计算量为O(NlogN) O(M)．     

分次根N_G(R)和■_G(R)的刻划

在本文中,M总代表一个Monoid,即有单位元e的半群．R总代表一个一般M一分次环,未必有1．关于M一分次环的基本概念可参见文献［2」．1分次素根的刻划设R是一个M一分次环,P是R的一个分次理想．P称为R的一个分次素理想,如果对R的任何2个分次理想I,J,当IJMP时就有IMP或JMP．易证,R的分次理想P是分次素理想ed对Va,b6h（R）,只要aRbMP,就有a6P或b6P．定义1．1设R是M一分次环．我们称N。（R）一uP。,其中P。取遍R的一切分次素理想,为R的分次素根．定义1．2设R是M一分次环,R的一个齐次元素序列al,a。,a;,…,称…     

遍历从N个元素中取M个元素可能组合的最佳算法

从N个相异元素中取M个元素(M≤N)的可能组合的遍历问题是组合数学中重要的基础性问题．关于该问题的现行算法是建立在对于搜索到的每一个节点的诸元素首先进行排序，然后搜索下一个节点．本文对于该问题给出一个全新的算法．新算法中放弃了对于节点诸元食的排序，实现每进行一次数据交换即搜索到一个新的节点，因而成为解决该问题的最佳算法．使用该算法编辑计算机程序，有编程简短、占用机器内存小的特点。     

《关于自然数的定义》一文的意见

人们在给出自然数体系的定义上做了一些工作,《关于自然数的定义》一文介绍了G.Peano自然数公理体系的一个不重要变形: 设N是一个非空的集合,它的元素叫自然数,如果对于N中某些元素a与b存在着关系: “b是a的后继者”,(a的后继者记为a′)并且满足下列公理: I.N中存在这样一个元素,它不是任何元素的后继者。记这个元素为θ(*),即     

基于散列技术的快速子串归并算法

用统计方法研究东西方语言的多词单元问题和东方语言的未登录词问题时需要删除同频子串(子串归并)．传统的子串归并算法时间复杂度为O(n^2),在大规模语料库的处理中效率低下．提出一种基于散列技术的时间复杂度为O(n^2)的子串归并算法,并用数学方法证明其与O(n^2)复杂度的算法等价,即输入相同时输出也相同．不同规模语料上的实验结果表明新算法能够大大缩短子串归并所需时间,适用于大规模语料库的处理．     

一种基于数据块交换的快速稳定原地归并算法

与其它排序算法相比,二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个有序子表,经典算法有2种。第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动。第二种算法是原地的,但完成归并需要O(m+n)次比较和O(m×n)次移动。提出了一种基于块交换的快速稳定原地二路归并算法。实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数。     

一种基于数据块交换的快速稳定原地归并算法

与其它排序算法相比.二路归并最适合于对2个有序子表进行排序。归并长度分别为m和n的2个 有序子表,经典算法有2种/第一种算法完成归并需要附加O(m+n)的空间,O(m+n)次比较和移动/第 二种算法是原地的.但完成归并需要O(m+n)次比较和O(m*n)次移动,提出了一种基于块交换的快速 稳定原地二路归并算法.实验证明,该算法与以前的原地算法相比,大大降低了元素的移动次数.     

对偶完全模糊线性系统的模糊近似解

讨论对偶完全模糊线性系统(DFFLS)M～(×)x～+a～=N～(×)+b～(其中M～、N～是由LR模糊数组成的n×n型模糊方阵,x～、a～、b～是由LR模糊数组成的n维模糊向量)的模糊近似解,给出其模糊近似解的直接算法和Cramer规则算法,并通过具体算例验证两种算法的可行性.     

部分可重构系统布局的一种新算法

针对动态部分可重构系统的瓶颈,即布局算法必须在保证运行速度的基础上,尽可能增加可重构芯片利用率的问题,提出了一种布局算法KVIT(keeping the vertexes information of tasks).其核心思想是尝试将新到达的硬件任务放置在已布局硬件任务的顶点处,并通过对可重构芯片内部计算单元进行编码迅速判断新任务是否可放置在该顶点.该算法的时间复杂度为O(N),N是可重构系统中当前运行的硬件任务的数目.仿真实验结果表明,KVIT算法的布局质量与现有的O(N2)时间复杂度布局算法基本一致,而其执行速度则明显高于已有算法.     

基于变异算子的云计算任务调度算法

为了高效调度云计算中海量的任务,提出一种改进遗传算法(IGA),将变异操作分为两种:变异操作a和变异操作b。变异操作a为随机位置的基因值变异,而变异操作b则是先找出满足一定条件的基因位置,再将该位置的基因值变异成目标基因值,使得每次变异后的染色体都优于变异前的染色体。在算法的前期使用变异操作a,在算法后期即将收敛于最优解时,采用变异操作b以加快收敛的速度。为了避免改进变异操作使算法陷入局部解,在种群初始化时,采用染色体匹配率的方式选择初始化种群,使其均匀的分布在整个解空间上。实验仿真结果表明,改进算法不但使最终完成时间更短,收敛效率更高,而且可以在一定程度上均衡负载,能更有效地实现任务调度。     

基于变异算子的云计算任务调度算法

为了高效调度云计算中海量的任务,提出一种改进遗传算法(IGA),将变异操作分为两种:变异操作a和变异操作b。变异操作a为随机位置的基因值变异,而变异操作b则是先找出满足一定条件的基因位置,再将该位置的基因值变异成目标基因值,使得每次变异后的染色体都优于变异前的染色体。在算法的前期使用变异操作a,在算法后期即将收敛于最优解时,采用变异操作b以加快收敛的速度。为了避免改进变异操作使算法陷入局部解,在种群初始化时,采用染色体匹配率的方式选择初始化种群,使其均匀的分布在整个解空间上。实验仿真结果表明,改进算法不但使最终完成时间更短,收敛效率更高,而且可以在一定程度上均衡负载,能更有效地实现任务调度。     

一种新型民用船舶数字气象仪

国内外民用气象监测设备的控制单元都是基于单片机的系统,存在测量参数少,显示界面单一,数据处理能力差等问题。该仪器采用Ubuntu作为操作系统,利用动态指针跟踪算法模拟传感器实时数据值;通过移动锯齿算法解决了动态指针移动中锯齿现象;将SQLITE数据库编译进系统,实现了复杂数据的查询、编辑等功能;并实现硬件接口协议的插头协议混插功能,为民用气象监测设备的更新换代奠定技术基础。