产生2元de Bruijn序列的一个新算法

de Bruijn序列是一类最长的非线性伪随机序列。本文给出了2元de Bruijn序列的一种新的生成算法,该算法能产生2~(δ·N(n,s))个n级de Bruijn序列,其中,0≤s≤2 (n-7)/2;当2~(l-1)相似文献   

一种生成k元de Bruijn序列的算法

目前,已有很多生成全长的移位寄存器序列(又称de Bruijn序列)的方法,他们的共同思想是先通过某种简单的移位寄存器生成所有不同的圈,然后再把它们联接为一个全长圈。在这篇文章中,我们先定义一个项链的周期约化,进而提出一种新的生成任意k元de Bruijn序列的方法。这种方法把这类算法从域推广到整数模上,而且在n≥3和k≥4时,这种算法能生成一大批de Bruijn序列。     

非线性互补约束均衡问题的一个SQP算法

提出了一个求解非线性互补约束均衡问题(MPCC)的逐步逼近光滑SQP算法.通过一系列光滑优化来逼近MPCC.引入l<,1>精确罚函数,线搜索保证算法具有全局收敛性.进而,在严格互补及二阶充分条件下,算法是超线性收敛的.此外,当算法有限步终止,当前迭代点即为MPEC的一个精确稳定点.     

m序列的移位相减性

ｍ序列是一类最重要的线性移位寄存器序列．文献［１］证明了移位相加是２元ｍ序列的特有性质，本文证明了任意的ｑ元ｍ的序列都具有移位相减性，并说明了移位相加是移位相减的特例。     

m序列的移位相加性

本文用反例说明一般的q(q>2)元m序列不具有移位相加性,指出了文[1]的一个疏忽,证明了移位相加是二元m序列所具有的特性。     

序列的一种无组合系数的根表示

本文在讨论了组合数C_x~k等在GF(q)上的多元多项式表示的基础上,给出了序列的一种避免组合系数的根表示法,并利用它对两个有重根的反馈多项式生成序列之积的线性复杂性进行了讨论.     

一个改进的SQP型算法

本文建立非线性等式和不等式约束规划问题的一个序列二次规划(SQP)型算法.算法的每次迭代只需解一个确实可解的二次规划，然后对其解进行简单的显式校正，便可产生关于罚函数是下降的搜索方向，克服Maratos效应.在适当的假设条件下，还论证了算法的全局收敛性和超级收敛性.     

前馈序列与反馈序列的关系

本文引入移位寄存器序列的向量值表示讨论了线性移位寄存器的前馈序列与反馈序列同时为ｍ序列时的关系,得到了它们在向量值表示下的一个关系式。     

基于种群分类排序的约束优化遗传算法

针对约束优化问题,提出了一类将种群中的个体分类排序的思想.算法的特点在于:先将种群中的解分为可行解和不可行解两类,然后分别按照不同的标准排序.由于很多约束优化问题的最优解位于可行域的边界上或附近,所以排序时并不认为可行解一定优于不可行解.基于此分类排队思想,特别设计了只允许同等级个体进行交叉的新的交叉算子,称之为同等级交叉算子,以及基于一维搜索的变异算子.算法同时采用了保证固定比例不可行解的自适应策略.4个标准测试函数的数值仿真结果验证了算法的有效性.     

颤振分析中的特征值排序问题

颤振分析中判断颤振临界速度的重要依据是系统V-g和V-f图,即系统特征值随参数的变化曲线.在几乎所有商用软件及自编程序的输出结果中,有时会出现所谓的"窜支"现象,这给颤振临界速度和颤振穿越分支及耦合形式的判断带来很大不便.通过隐函数定理可以证明,除重特征值点以外,系统特征值连续依赖于系统参数变化.依据多元向量值函数连续性,建立对特征值的排列算法,给出系统特征根轨迹的正确曲线,再输出V-g和V-f图数据,从而避免"窜支"现象.编制应用程序,通过几个典型算例对算法进行了验证.该工作能够有效简化颤振分析的后处理工作,提高分析效率.     

建筑废料现场分拣协调调度优化研究

工程项目施工现场废料分拣的效率对施工进度具有重要的影响。通过分析现场废料分拣实施过程,建立了带有限中间缓冲的混合流水车间调度模型。提出了收集阶段作业排序的动态自适应算法和后续设备分配问题的考虑缓冲区的设备分配规则,在此基础上设计了废料分拣模型的启发式算法,平衡各分区工作量,进一步搜索最优解,并推导了问题的一个低界。实验结果表明,所提出算法能很好地对施工现场废料分拣问题进行求解,具有良好的收敛性和较高的时间效率。     

A Faster Algorithm for Computing Motorcycle Graphs

We present a new algorithm for computing motorcycle graphs that runs in \(O(n^{4/3+\varepsilon })\) time for any \(\varepsilon >0\) , improving on all previously known algorithms. The main application of this result is to computing the straight skeleton of a polygon. It allows us to compute the straight skeleton of a non-degenerate polygon with \(h\) holes in \(O(n \sqrt{h+1} \log ^2 n+n^{4/3+\varepsilon })\) expected time. If all input coordinates are \(O(\log n)\) -bit rational numbers, we can compute the straight skeleton of a (possibly degenerate) polygon with \(h\) holes in \(O(n \sqrt{h+1}\log ^3 n)\) expected time. In particular, it means that we can compute the straight skeleton of a simple polygon in \(O(n\log ^3n)\) expected time if all input coordinates are \(O(\log n)\) -bit rationals, while all previously known algorithms have worst-case running time \(\omega (n^{3/2})\) .     

偏序集上的一种拓扑排序

拓扑排序是有向图的一种重要运算.用一种线性的算法得到有向无圈图的一个更趋于合理的拓扑序列.     

Sorting in linear expected time

A new sorting algorithm, Double Distributive Partitioning, is introduced and compared against Sedgewick's quicksort. It is shown that the Double Distributive Partitioning algorithm runs, for all practical purposes, inO(n) time for many distributions of keys. Furthermore, the combined number of comparisons, additions, and assignments required to sort by the new method on these distributions is always less than quicksort.     

A Faster Katz Status Score Algorithm

A new graph theoretical algorithm to calculate Katz status scores reduces computational complexity from time O(n³) to O(n + m). Randomly-generated graphs as well as data from a large empiric study are used to test the performance of two commercial network analysis packages (GRADAP and UCINET V), compared to the performance achieved by the authors' algorithm, implemented in Visual Basic.     

A Faster Deterministic Maximum Flow Algorithm

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n² log²n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(log_{m/n log n}n)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(n^ε) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n).     

Fault Tolerant Sorting—Theoretical and Empirical Analyses of the Randomized QuickMergesort Algorithm

This paper introduces a new paradigm in the design of sorting algorithms, viz., fault tolerance. Fault tolerance is an important concept in modern day computing and design workflows must accommodate this need. In general, there are a number of avenues for faults to occur and techniques to address the same; this paper focusses on only one source of faulty behavior, viz., process termination. Process termination, as a cause of faulty behavior, is important from the perspective of various applications in real-time scheduling. In order to measure the effectiveness of a fault tolerant protocol, it is necessary to define a suitable metric and analyze the performance of the protocol with respect to that metric. We measure the “unsortedness” of an array, as characterized by the number of inversion pairs that remain when the sorting algorithm (process) terminates. This paper proposes a new algorithm for sorting called the Randomized QuickMergesort (RQMS) algorithm. RQMS has a higher degree of fault tolerance than either Randomized Quicksort (RQS) or Mergesort (MS), in that fewer inversion pairs remain when it terminates. Likewise, RQMS has a lower comparison overhead than RQS and is more space-efficient than MS. Our empirical analysis, which was conducted over a wide variety of distributions, conclusively establishes that RQMS is the algorithm of choice, when fault tolerance is paramount in the application. This research was supported in part by the Air Force Office of Scientific Research under Contract FA9550-06-1-0050.