一种优化BITONIC算法:"并行-优化-串行"合并和分类向量算法

串行算法并行化是发挥各种巨型机的效率的关键技术之一。“并行－优化－串行”归并向量算法（OSVM），是一种串行算法并行化的优化方法，它用O（N／p)时间把总长为N的两个有序序列归并或把总长为N的一个Bitonic序列排序。“并行－优化－串行”排序向量算法（POSVS）用O（NlogN)/p）时间在实际SIMD机上把N个数排序，这些是第1个满足以下两个条件的向量Optimal算法（加速比＝O（p))，（1）它能在实际SIMD计算机上实现，处理机的台数p的范围很宽1≤N^1-ε，这里，ε是任意的小的正数。（2）它统一了3种不同类的合并算法：Batcher的Bitonic算法（最快但效率随参数变大而向于0），优化(Optimal)算法（效率为常数的算法）和最佳的串行算法。而且综合了3个算法的优点，“并行－优化－串行”（POS）方法是一个通用方法，它还可以应用到其它类型问题上。     

基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。     

基于立方体剖分的传感器网络快速三维k-覆盖判定算法

提出了一种传感器网络中基于立方体剖分的三维k 覆盖快速判定算（CP-RTCDA）和三维最大k 覆盖问题的快速求解算法（CP-RTMCDA）。算法首先把感兴趣区域剖分为立方体区域，从而将复杂的空间区域覆盖问题转化为简单的立方体区域覆盖问题。理论分析与仿真实验表明, 针对具有n个节点的传感器网络, 新算法的计算时间复杂度为O(n)，远低于已有算法O(n3logn)的计算时间复杂度。     

DCLC路由的选择函数法DCLC-SF

QoS路由的DCLC(Delay-Constrained Least-Cost Routing)路由问题是一个NP--完全问题。本文提出了一种多项式复杂度的启发式算法DCLC-SF(Delay-Constrained Least-Cost Routing Based on Selective Function），DCLC-SF算法基于简单的选择函数，属于源路由算法，算法最坏情况的计算复杂度为O（3ne)。仿真实验证明DCLC-SF算法是一种精确的启发式算法。     

一种剖分平面多边形的通用算法描述

提出了一种用梯形来剖分非单调平面多边形的通用算法，算法包括三部分：初始化，梯形化和优化（后处理），所处理的多边形可以包含孔，孔可以嵌套。本算法的时间复杂度是O(n^2log2n).     

一种Trie结构

本文描述了一种Ｔｒｉｅ结构，给出了这种Ｔｒｉｅ结构的插入，查找算法，查找算法的时间复杂度为O(log_nK），与以前的工作相比，这是一个改进。本文也给出了将Ｔｒｉｅ结构存放在一维数组后的查找算法。     

一个基于决策表的快速属性约简算法

在目前已出现的基于Rough Set的属性约简算法中，认为以近似质量为启发信息并非十分理想，以快速缩小搜索空间为目的设计了一个新的较为合理的度量属性重要性的计算公式，并给出了该公式的递归计算方法，计算该公式的算法的复杂度被降低到O（｜C-P｜｜U—UP｜），然后给出了一个时间复杂度为max（O｜C｜｜U｜log｜U｜，O（｜C｜^2｜U｜））的快速属性约简算法，最后用一个实例说明了算法的有效性．     

一种改进的量子搜索算法

Rrover提出的对无序数据库进行搜索的量子算法，可以将搜索时间复杂度从经典计算机上的O（N）降低为O（N的平方根）。该算法显示了量子计算的强大能力，在量子计算研究中具有重要地位。但是，我们在研究Grover算法中发现Grover算法存在搜索失效等问题。本文分析了Grover算法中存在的问题，针对其不足之处进行了改进，并证明了改进后量子搜索算法的有效性。     

在量子计算机上求解0/1背包问题

在Ｇｒｏｖｅｒ算法和量子指数搜索算法的基础上,提出了一个量子算法去求解０／１背包问题。这个算法在没有使用任何可以提高搜索效率的经典策略的情况下,能够在Ｏ（ｃ＾２ｎ／２）步以至少１－１／２＾ｃ的概率求解问题规模为ｎ的０／１背包问题。     

Deterministic Resource Discovery in Distributed Networks

The resource discovery problem was introduced by Harchol-Balter, Leighton, and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model. This model is a directed logical graph that represents the vertices’ knowledge about the topology of the underlying communication network. The current paper proposes a deterministic algorithm for the problem in the same model, with improved time, message, and communication complexities. Each previous algorithm had a complexity that was higher at least in one of the measures. Specifically, previous deterministic solutions required either time linear in the diameter of the initial network, or communication complexity $O(n^3)$ (with message complexity $O(n^2)$), or message complexity $O(|E_0| \log n)$ (where $E_0$ is the arc set of the initial graph $G_0$). Compared with the main randomized algorithm of Harchol-Balter, Leighton, and Lewin, the time complexity is reduced from $O(\log^2n)$ to\pagebreak[4] $O(\log n )$, the message complexity from $O(n \log^2 n)$ to $O(n \log n )$, and the communication complexity from $O(n^2 \log^3 n)$ to $O(|E_0|\log ^2 n )$. \par Our work significantly extends the connectivity algorithm of Shiloach and Vishkin which was originally given for a parallel model of computation. Our result also confirms a conjecture of Harchol-Balter, Leighton, and Lewin, and addresses an open question due to Lipton.     

A Simple and Efficient Randomized Byzantine Agreement Algorithm

A new randomized Byzantine agreement algorithm is presented. This algorithm operates in a synchronous system of n processors, at most t of which can fail. The algorithm reaches agreement in 0(t/log n) expected rounds and O(n2tf/log n) expected message bits independent of the distribution of processor failures. This performance is further improved to a constant expected number of rounds and O(n2) message bits if the distribution of processor failures is assumed to be uniform. In either event, the algorithm improves on the known lower bound on rounds for deterministic algorithms. Some other advantages of the algorithm are that it requires no cryptographic techniques, that the amount of local computation is small, and that the expected number of random bits used per processor is only one. It is argued that in many practical applications of Byzantine agreement, the randomized algorithm of this paper achieves superior performance.     

Parallel Parsing Algorithms and VLSI Implementations for Syntactic Pattern Recognition

Earley's algorithm has been commonly used for the parsing of general context-free languages and the error-correcting parsing in syntactic pattern recognition. The time complexity for parsing is 0(n3). This paper presents a parallel Earley's recognition algorithm in terms of an ``X*' operator. By restricting the input context-free grammar to be ?-free, the parallel algorithm can be executed on a triangular-shape VLSI array. This array system has an efficient way of moving data to the right place at the right time. Simulation results show that this system can recognize a string with length n in 2n + 1 system time. We also present a parallel parse-extraction algorithm, a complete parsing algorithm, and an error-correcting recognition algorithm. The parallel complete parsing algorithm has been simulated on a processor array which is similar to the triangular VLSI array. For an input string of length n the processor array will give the correct right-parse at system time 2n + 1 if the string is accepted. The error-correcting recognition algorithm has also been simulated on a triangular VLSI array. This array recognizes an erroneous string of length n in time 2n + 1 and gives the correct error count. These parallel algorithms are especially useful for syntactic pattern recognition.     

针对CSC系列流密码算法的区分攻击

研究CSC-(n,N)序列流密码算法簇的安全性,证明产生的第1个密钥字节为0的概率约为2-n~2-2n,利用模拟实验验证其正确性,据此提出对CSC-(n,N)的区分攻击。该区分攻击只需利用23n+2个密钥产生的第1个密钥字就能以0.84以上的正确率将CSC-(n,N)产生的密钥流序列与随机序列进行区分。     

Least Squares Policy Evaluation Algorithms with Linear Function Approximation

We consider policy evaluation algorithms within the context of infinite-horizon dynamic programming problems with discounted cost. We focus on discrete-time dynamic systems with a large number of states, and we discuss two methods, which use simulation, temporal differences, and linear cost function approximation. The first method is a new gradient-like algorithm involving least-squares subproblems and a diminishing stepsize, which is based on the -policy iteration method of Bertsekas and Ioffe. The second method is the LSTD() algorithm recently proposed by Boyan, which for =0 coincides with the linear least-squares temporal-difference algorithm of Bradtke and Barto. At present, there is only a convergence result by Bradtke and Barto for the LSTD(0) algorithm. Here, we strengthen this result by showing the convergence of LSTD(), with probability 1, for every [0, 1].     

Convex Drawings of 3-Connected Plane Graphs

We use Schnyder woods of 3-connected planar graphs to produce convex straight-line drawings on a grid of size The parameter depends on the Schnyder wood used for the drawing. This parameter is in the range The algorithm is a refinement of the face-counting algorithm; thus, in particular, the size of the grid is at most The above bound on the grid size simultaneously matches or improves all previously known bounds for convex drawings, in particular Schnyder's and the recent Zhang and He bound for triangulations and the Chrobak and Kant bound for 3-connected planar graphs. The algorithm takes linear time. The drawing algorithm has been implemented and tested. The expected grid size for the drawing of a random triangulation is close to For a random 3-connected plane graph, tests show that the expected size of the drawing is      

A refinement of a spherical decomposition algorithm

A refinement is suggested to the O'Rourke-Badler spherical decomposition algorithm which reduces its complexity from 0(n3) to 0(n2)     

背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2^n/4)^1-ε个并行处理机单元,0≤ε≤1,O(2^n/2)个存储单元,在O(2^n/4(2^n/4)^ε)时间内求解n维背包问题,算法的成本为O(2^n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.     

A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths

We present an -time algorithm for the All Pairs Shortest Paths (APSP) problem for directed graphs with real edge lengths. This slightly improves previous algorithms for the problem obtained by Fredman, Dobosiewicz, Han, and Takaoka.