Fp上不可约与本原多项式的高效确定算法

对于一大类整数n(n为素数乘于素数或1的积),分别给出有限域Fp上n次多项式是不可约多项式与本原多项式的一个充要条件,该条件可通过O(n3)次Fp上乘法加以验证,易于硬件实现.提出可约多项式一个充分条件,借此减少验证时间,并得到用O(n4)次Fp上乘法确定一个n次不可约多项式及一个n次本原多项式的高效算法.对于ECC中构造Fnp上椭圆曲线、序列密码中构造LFSR,有重要的应用价值.     

最大并行流问题

研究了Fleischer.L给出的求解最大并行流问题的一个近似算法,其求出的目标函数值为λ≥(1-ε)3OPT.对其算法进行了改进,给出了λ≥1/(1 3ε)OPT的最大并行流全多项式近似算法.最后给出数值例子,验证了算法的有效性.     

多面体面上任意两点间最短路径算法

提出计算多面体面上任意两点之间最短路径的算法:近似算法、最短路径或近似最短路径算法.近似算法的思想是采用将折线不断嵌入三角形串上的方法,而另2个算法则是通过特定法线寻找三角形串,而且将这些三角形旋转到同一平面上,从而得到最短路径.前者的时间复杂性为O(n),而后者的时间复杂性分别是O(n2)及低于O(2nn2).     

求一般图的最小顶点覆盖集问题的混合贪婪算法

现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大.根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法.该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为O(|V|2),执行效果较好,性能近似比不大于4/3,接近已知的可能的近似比下界1.166 6,低于2005年认为最低的近似比1.361,是图的最小顶点覆盖问题算法的一个较好的补充.     

KNA算法计算单零点多项式全部零点的复杂性

证明用KNA算法计算n次单零点多项式全部零点所需的多项式计值次数不超过O(n~3 log_2(n/ε)),其中ε是计算精度。     

一类背包问题的可解性

本文的主要结果是,对K背包问题给出了时间、空间复杂性为O(nM~k)的拟多项式算法;证明了若P≠NP,则该问题不存在完全多项式时间ε近似算法;对动态背包问题给出了时间复杂性为O(nM~k)的拟多项式算法。     

求解一类T型线性方程组的快速算法

本文首先给出一个求解一类T型线性方程组的快速串行算法,它的复杂性是O(nlogn),比目前最好的O(n~2)算法复杂性要低。接着又指出了它的并行计算方案,在n台处理机的条件下,计算步数不超过O(logn),速度倍数是O(n),效率是O(1)。     

二次锥规划的不可行内点算法

给出二次锥规划的一种不可行内点算法并证明该算法是多项式时间算法.利用本算法需O(√nlnε-1)次迭代就可找到问题的ε-近似解,其迭代复杂性界与现有的二次锥规划可行内点算法的复杂性界相同.     

一个求外平面图最小反馈点集的多项式时间算法

如果从一个图中去掉某些顶点后得到的导出子图是无圈图，则所去的那些顶点组成的集合就是原图的反馈点集。本文讨论外平面图的反馈点集并给出了一个求外平面图最小反馈点集的多项式时间算法。     

TSP的一个多项式近似算法

给出了TSP的一个多项式近似算法,其运算量为O(n3).     

基于遗传和启发式算法的混合顶点着色算法

图的着色问题是一种典型的NP-完全问题.提出了基于遗传算法和启发式算法的新型混合顶点着色算法,该算法在实现过程中涉及到染色体的编码方法、适应度函数的设计以及遗传算子的选择等.实验仿真结果表明此算法改善了求解的时间复杂度,可以获得问题高质量的解.     

单车独占性带时间窗口装卸货问题的分析与算法

提出了一类广泛存在于运输领域的NP-hard组合优化问题——独占性带时间窗口装卸货(E-PDPTW)问题,给出了它的数学描述,分析了其性质并把问题简化为不对称带时间窗口旅行商问题(TSP),提出了求解单车E-PDPTW问题的两阶段快速算法,其时间复杂度只有O(n^3),测试结果表明了该算法的有效性和快速性。     

基于Gossip算法的无线传感器网络时间同步

将Gossip算法用于实现无线传感网络的分布式时间同步,提出单Gossip同步算法和多Gossip同步算法,解决传统无线传感器网络时间同步算法中存在的计算复杂度高和同步收敛速度慢等问题.单Gossip同步算法首先利用构造生成树算法得到一个生成树,然后,依次对生成树每条边的两节点时钟信息进行Gossip运算,反复循环,最终可使网络各节点的时钟信息收敛于它们初始时钟信息的平均值.多Gossip同步算法对生成树进行边染色,相同染色的边可以同时进行Gossip运算.这2种同步算法减小了消息交换数,降低了计算复杂度,提高了同步的收敛速度.用随机矩阵理论和图论进行了理论证明,通过计算机仿真对理论分析进行了数据验证.     

找K个最小生成树的并行算法

基于SIMD 机器——一种可以同时读但不可同时写的共享计算模型(CREW-PRAM)给出了找K 个最小生成树的并行算法,此算法需O(log~2n+Klogn~*)时间及O(n~2)处理器;而基于可以同时读、写的更强计算模型(CRCW-PRAM),求K 个最小生成树仅需O(Klogn)时间及O(n~2)处理器,这里n 是图的顶点数.     

分组遗传算法用于图的着色

图的着色算法是一种典型的NP 完全问题 在系统地讨论了图的正常顶点着色、边着色以及全着色的有关理论的基础上 ,提出了基于分组遗传算法和启发式搜索的图的正常 k 点着色 ,正常k 边着色以及正常k 全着色的新型混合算法 ,提出了评价算法性能的标准 实验仿真结果表明 ,新型混合算法可以获得问题高质量的解 ,即对图进行着色所使用的颜色数接近图的色数     

一种快速单模式准确匹配算法

引入连续跳跃查找文本的思想，提出了一种新的单模式精确匹配算法，其最优条件下的时间复杂度为O[n/(m 1)]，新算法的平均时间复杂度分析表明其具有优越的查找性能，对比实验结果显示，新算法的性能优于目前所见的同类算法，特别是在模式较短的情况下，优势更为明显，这一特点非常适合于自然语言文本的检索。     

一种逻辑电路图的布局算法

本文简述了从硬件描述语言到自动生成逻辑电路图的方法和步骤。在提出了与文献所不同的数学模型的基础上,设计了一种新的自动布局算法。该算法的时间复杂性在一般情况下远小于O(p·n~2)(p为元件列数,n为所有列中最大元件数),并且使连线总长及交叉点个数同时得到改善。本文的结果已在同期研制的逻辑/电路图编辑与自动生成系统中得到应用。     

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

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