求解一类整数规划问题最优解的算法

本文给出了求解一类整数规划问题所有最优解的两个算法．一个算法较为简单，其时间复杂性为O（n）,另一个算法求解较为快速，其时间复杂性为O（log n）.     

凸二次规划基于新的核函数的大步校正原始-对偶内点算法

本文对凸二次规划提出了一种基于新的核函数的大步校正原始-对偶内点算法．这种核函数构造新的障碍函数不仅可以定义新的搜索方向，而且可以控制内迭代的过程，使得对凸二次规划提出的大步校正原始-对偶内点算法的多项式复杂性阶改善到O（√n（logn）2log（n／ε）），优于基于经典对数障碍函数的相应算法的复杂性阶．     

对等网络中一种新的非集中式查找算法

提出了一种适用于对等网络环境的非集中式查找算法，它具有可扩展、自组织、高容错等特性，能够自动适应网络中节点的加入、退出和失效．该算法的时间复杂度和空间复杂度均为O(log N)．算法的基本思想是：将有限大小的线性空间平均划分为M等份，对每等份的子空间递归划分为M等份，直到每个子空间对应一个点；采用Hash算法将网络中的数据或节点映射为线性空间中的一点，每个节点本地存储一个路由表，其内容为其各个划分层次中的对应点所在位置信息；这样，一个节点可以在不超过O(log N)次转跳的情况下找到目的节点．仿真实验结果表明：当M增大时，算法的查找性能也会提高；当M=16，网络规模为10^4个节点时，算法的平均查找长度仅是Pastry、Tapestry算法的70％左右．     

逐行(列)扫描判定点集是否在多边形内部的算法

提出一种基于点集排序,逐行（或逐列）扫描平面点集S,判定点集S中的点是否在多边形L内部的算法,该算法的时间复杂性在最坏情况下为：max(O(n log n),O(km log m)次比较和O（km)次乘法,其中n为点集S的点数,m为多边形L的顶点数,k=min(u,v),其中u,v分别为点集S中的点分布的行数和列数,该算法思路简单,易实现,且在一般情况下,效率比已有的算法高。     

树的m—路中心

提出了m—路中心的概念。对无权树和赋权树分别给出了O(n log n),O(n~2)及O(n log (d(T)/Wminee(T)))算法,其中Wminee(T)是赋权树的最小权数。     

由先序序列和结点的层数构造严格二叉树的高效算法

提出一种新的通过一棵严格二叉树的先序序列和这棵严格二叉树的结点的层数构造这棵严格二叉树的非递归算法.举例说明新算法的执行过程.对于有n个结点的严格二叉树,新算法的时间复杂度为O(n),比相应的递归算法的低,新算法的最差情况空间复杂度为O(n),与相应的递归算法的相同.     

角度约束路径法的网格曲面兴趣区域边界快速交互选取

提出角度约束路径法,快速获取三角网格曲面上任意两顶点间一条由网格边所组成的路径.该算法是一个从起始点开始不断向前传播的过程,计算量仅与两顶点间的曲面区域有关,故算法的时间复杂度(O(n))优于Dijkstra算法(O(n log n)).试验结果表明:角度约束路径法的执行快速、有效;基于该方法可实现三角网格曲面兴趣区域边界的快速交互选取.     

一种Byte查找第K个元素的算法研究

查找第K个元素的问题在计算机查找技术中占有十分重要的地位，这个问题的最直接解法是先将序列排序，从而能得到第K个元素，最少需O(nlogn)次比较，即时间复杂度为O(nlogn)．比较好的方法是采用分治策略解决该同题，但其最坏时间复杂度为O(n^2)，平均时间复杂度为O(2n)．本文提出一种Byte解决第K个元素问题的算法，该算法的平均时间复杂度为O(n n／255)，优于以前对该问题的求解方法，而且该算法可以适用于由整数、浮点数、无符号整型数、双精度数和字符型数构成的超大数集．     

基于二分法判定点集是否在多边形内部的算法

提出一种基于二分法判定点集是否在多边形内部的算法,根据多边形L的顶点和边分布的情况,分割平面的一组平面区域的有序集合R,判定R中每个区域是否在多边形L内部;对于点集S中的点p,用二分法搜索R,找到点p所属的平面区域,从而判定出点p是否在多边形内部。该算法在最坏情况下的时间复杂性为max(O(n log m),O(tm log m),其中n为点集S的点数,m为多边形L的顶点数,t为多边形L所有顶点的X坐标的不同取值个数,在一般情况下该算法比已有的算法效率更高。     

基于Grover算法的量子多用户检测

经典的多用户检测技术，其求解最优解的时间复杂度为0(2n)，这是一个NP难解问题．在Pauli算子的基础上建立量子多用户信道模型，给出利用Grover算法的多用户检测解决方法．该算法的时间复杂度为O(√2n)，并且当2n足够大时，其错误的概率趋近于0．     

图的极大匹配并行算法

对一类无向图的边极大匹配问题,在ＥＲＥＷＰＲＡＭ并行计算模型上,给出Ｏ（ｌｏｇｎ）时间、使用Ｏ（（ｎ＋ｍ）／ｌｏｇｎ）处理器的最佳、高速并行算法     

区间图上的并行算法设计

对区间图上的图问题并行求解,给出两种算法设计方法.利用这两种方法,对最小团覆盖、最大团、最大独立集、最小支配集、Hamiltonian 回路、最佳道路覆盖、最小带宽和Steiner 树的计算问题, 在EREW PRAM 模型上给出O(logn) 时间,使用O(n) 处理器的高效并行算法.     

Interior-point algorithm for linear optimization based on a new kernel function

In this paper, we design a primal-dual interior-point algorithm for linear optimization. Search directions and proximity function are proposed based on a new kernel function which includes neither growth term nor barrier term. Iteration bounds both for large-and small-update methods are derived, namely, and . This new kernel function has simple algebraic expression and the proximity function has not been used before. Analogous to the classical logarithmic kernel function, our complexity analysis is easier than the other primal-dual interior-point methods based on logarithmic barrier functions and recent kernel functions.     

外电场对双极荷电颗粒碰撞及凝聚的影响

为确定外电场对双极凝聚的影响,采用FORTRAN程序,通过计算得到颗粒在一定电流体场条件下的电荷分布统计规律,并考察外电场对双极荷电颗粒间的碰撞凝聚规律.计算结果表明,只有当荷电颗粒所受电场力与阻力的量级之比接近于1时,外电场才能起到增强双极凝聚效果的作用;在相同条件下,颗粒直径越大,外电场增强双极荷电颗粒的碰撞效果也越大.     

r—循环系统及有关算法的计算复杂性

本文引进了对称r—循环阵的新概念,给出了r—循环阵和对称r—循环阵的一些性质,并利用FFT(快速富里叶变换),证明了有关算法的计算复杂性为O(nlog_2n),这里n为矩阵的阶数。     

解Routh-Hurwitz问题的一个快速无除算法

本文给出了一个快速的无除算法来解决n次整系数多项式的Routh—Hurwitz问题，其中多项式是无平方的，首一的．该算法的复杂度为O（n^2），在算法中涉及到的整数最多有O（nlognc）位，其中c是Bezout矩阵中元素模的上界．为了强调算法的稳定性问题，本文只使用精确的算术运算．     

循环矩阵开平方的快速算法

利用快速傅立叶变换 (FFT) ,给出了 n阶循环矩阵开平方的一个快速算法 ,计算循环矩阵的同型平方根矩阵 (平方根矩阵也是循环矩阵 ) ,证明了同型平方根矩阵的个数为 2 n ,它是关于 n的指数函数 ;计算一个同型平方根矩阵的时间复杂性为 O(nlog2 n) ;计算全部同型平方根矩阵的时间复杂性为 O(n2 n) .     

关于图染色的算法

本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」.     

带有可控性维护的单机调度问题研究

为在附加费用不大的条件下,通过最小化工件完成时间之和来减小work-in-process中的库存,尽可能使工件按期交付,在将工件调度与机器维护统一进行考虑的模型基础上,提出了带有预防性维护的单机调度问题,并对其进行了建模.将机器的维护周期适当放宽,以便在保证总的附加费用不超出预先给定的一个常数的前提下,实现工件的完成时间和的最小化.对工件加工允许中断的情况给出时间复杂度为O(n*ln(n));对工件加工不允许中断的情况给出一个启发式算法,其时间复杂度为O(n2).由该启发式算法很容易得到问题的可行解,从而为问题的进一步研究打下了基础.