首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 125 毫秒
1.
本文讨论了动态矩形交查询算法.文中介绍了两个半动态矩形查询的新算法,它们分别基于一维数据结构和二维数据结构.一维查询算法的查询时间复杂度是O(logMk′),更新时间复杂度是O(logMlogn),空间复杂度是OnlogM/).二维查询算法的查询时间复杂度是O(log2Mk),更新时间复杂度是O(log2Mlogn),空间复杂度是Onlog2M).本文分别实现了这两个算法,通过对它们的性能进行比较,发现一维查询算法是一种高效、实用的算法.  相似文献   

2.
杨勃  陈虎  陈国良 《软件学报》1998,9(2):115-120
本文提出了一种把图象中边界转换成区域四分树的并行方法.该方法基于MIMD模型,并在曙光1000上实际运行.整个算法用P个处理器可以在时间O((B×logB)/P)内完成其中B是循环代码长度.该算法可应用于图象处理、计算机图形学、模式识别等领域.  相似文献   

3.
沈一飞  陈国良  张强锋 《软件学报》2007,18(11):2683-2690
分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n2)处理器,时间复杂度为O(log2n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n3)处理器,计算时间复杂度为O(logn).  相似文献   

4.
分布式存储的并行串匹配算法的设计与分析   总被引:7,自引:0,他引:7  
陈国良  林洁  顾乃杰 《软件学报》2000,11(6):771-778
并行串匹配算法的研究大都集中在PRAM(parallel random access machine)模型上,其他更为实际的模型上的并行串匹配算法的研究相对要薄弱得多.该文采用将最优串行算法并行化的技术,利用模式串的周期性质,巧妙地将改进的KMP(Knuth-Morris-Pratt)算法并行化,提出了一个简便、高效且具有良好可扩放性的分布式串匹配算法,其计算复杂度为O(n/p+m),通信复杂度为O(ulogp相似文献   

5.
在EREW PRAM(exclusive-read and exclusive-write parallel random access machine)并行计算模型上,对范围很广的一类无向图的边极大匹配问题,给出时间复杂性为O(logn),使用O((n+m)/logn)处理器的最佳、高速并行算法.  相似文献   

6.
在可实现的基于身份加密体系IBE(Identity-Based Encryption)中,椭圆曲线上的双线性对可用于IBE加解密算法的构造。目前尚无关于IBE加密体系软件实现中Tate对的计算及化简的研究。针对这一事实,提出一种基于软件实现的IBE体系架构。从算法层次深入研究了BF-IBE加密方案的加解密流程以及椭圆曲线上双线性对Tate对的计算方法,完成了BF-IBE中Tate对的化简,在Windows VC++6.0软件环境下实现了IBE加解密运算。  相似文献   

7.
管丽 《软件学报》1996,7(Z1):249-253
本文在一个EREW PRAM(exclusive read exclusive write paralled random accessmachine)上提出一个并行快速排序算法,这个算法用k个处理器可将n个项目在平均O((n/k+logn)logn)时间内排序.所以平均来说算法的时间和处理器数量的乘积对任何kn/lognO(nlogn).  相似文献   

8.
一类实际网络中的最小截算法   总被引:9,自引:0,他引:9  
讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为O(n2logn)(其中n为网络的节点数).给出了可以充分利用网络平面性的方法.对源和汇共面的s-t平面网络,把最小截问题转化为平面图上两点间的最短路径问题,从而可以得到O(n)时间的算法;对一般的平面网络,给出了新的将节点和边都有容量的问题转化为仅边有容量问题的方法,这种转化方法不破坏网络的平面性,从而可以利用平面网络中仅边有容量问题的计算方法,使原问题在O(nlogn)时间内获得解决.  相似文献   

9.
杨智应  朱洪  宋建涛 《软件学报》2004,15(5):650-659
算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n3).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设-A为任意矩阵,A是-A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差σ2≤1.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了Pr[K(A)≥α]≤(3.64n(1+4√log(α)))/ασ.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为m+71og2(n)+3log2(1/σ)+log2log2n+7.在上述结果的证明过程中存在错误,将其纠正后得到以下结果:m+71og2n+3log2(1/σ)+4√2+log2n+log2(1/σ)+7.367.通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到Pr[K(A)≥α]≤(6√2n2)/α·σ.部分地解决了Sankar等人提出的猜想:Pr[K(A)≥α]≤O(n/α·σ).并将运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度降低到m+81og2n+3log2(1/σ)+7.实验结果表明,所得到的平滑复杂度更好.  相似文献   

10.
数据仓库系统中层次式Cube存储结构   总被引:11,自引:0,他引:11       下载免费PDF全文
高宏  李建中  李金宝 《软件学报》2003,14(7):1258-1266
区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(logdn),综合性能为O((logn)2d)(使用CqCu模型)或O(K(logn)d)(使用Cqnq+Cunu模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.  相似文献   

11.
Implementation of Cryptosystems Based on Tate Pairing   总被引:1,自引:1,他引:0       下载免费PDF全文
Tate pairings over elliptic curves are important in cryptography since they can be used to construct efficient identity-based cryptosystems, and their implementation dominantly determines the efficiencies of the cryptosystems. In this paper, the implementation of a cryptosystem is provided based on the Tate pairing over a supersingular elliptic curve of MOV degree 3. The implementation is primarily designed to re-use low-level codes developed in implementation of usual elliptic curve cryptosystems. The paper studies how to construct the underlying ground field and its extension to accelerate the finite field arithmetic, and presents a technique to speedup the time-consuming powering in the Tate pairing algorithm.  相似文献   

12.
In this paper, we investigate the relationship between the squared Weil/Tate pairing and the plain Weil/Tate pairing. Along these lines, we first show that the squared pairing for an arbitrary chosen point can be transformed into the plain pairing for a trace zero point which has a special form to compute them more efficiently. Then the optimizations made for computing squared pairings are combined with the computation of pairings on these trace zero points, to achieve even better performance for the computation of the 4th powered Weil pairing.  相似文献   

13.
A note on the Ate pairing   总被引:1,自引:0,他引:1  
The Ate pairing has been suggested since it can be computed efficiently on ordinary elliptic curves with small values of the traces of Frobenius t. However, not all pairing-friendly elliptic curves have this property. In this paper, we generalize the Ate pairing and find a series of the variations of the Ate pairing. We show that the shortest Miller loop of the variations of the Ate pairing can possibly be as small as r 1/φ(k) on some special pairing-friendly curves with large values of Frobenius trace, and hence speed up the pairing computation significantly. This work is supported by the National Natural Science Foundation of China (No. 60773202, 60633030) and 973 Program (No. 2006CB303104).  相似文献   

14.
Efficient Tate pairing computation using double-base chains   总被引:2,自引:0,他引:2  
Pairing-based cryptosystems have developed very fast in the last few years. The efficiencies of these cryptosystems depend on the computation of the bilinear pairings, In this paper, a new efficient algorithm based on double-base chains for computing the Tate pairing is proposed for odd characteristic p 〉 3. The inherent sparseness of double-base number system reduces the computational cost for computing the Tate pairing evidently. The new algorithm is 9% faster than the previous fastest method for the embedding degree k = 6.  相似文献   

15.
The aim of this work is to show the feasibility of the primitives of the identity based cryptosystems for applications in Smart-Cards. Several observations are applied to easily choose many supersingular elliptic curves over a prime field , in such a way that the size of the torsion subgroup, the curve order and the finite field characteristic are of minimal Hamming weight. We modify the Chudnovsky elliptic curve point representation to settle a dedicated coordinate system for pairings and to minimize the number of operations in the finite field. The encouraging timing results obtained for ST22 Smart-Card architecture show the feasibility of pairing primitives for embedded devices.  相似文献   

16.
双线性配对在密码学中得到了越来越广泛的应用,用它来构建的签名方案具有速度快、密钥短和签名短等优点。针对双线性配对基础算法中的点乘和求有理函数,本文提出两种基于椭圆曲线的双线性配对算法。这两种双线性配对算法与Miller算法、三进制Miller算法相比,所需乘除法次数少、效率高。  相似文献   

17.
An algorithm is described which sorts n numbers in place with the property of stability, i.e., preserving the original order of equal elements. The algorithm requires absolutely minimum storage 0 (log2n) bits for program variables and a computation time at most 0 (n (log2n)2).  相似文献   

18.
结合椭圆曲线上的Tate配对和混合加密体制,提出了一种新的签名加密算法,它集密钥交换、数字签名和数据加密解密功能干一体,能完全抵抗生日攻击,既安全又实用,特别适用于电子商务系统。  相似文献   

19.
In this study, we solve a robust version of the airline crew pairing problem. Our concept of robustness was partially shaped during our discussions with small local airlines in Turkey which may have to add a set of extra flights into their schedule at short notice during operation. Thus, robustness in this case is related to the ability of accommodating these extra flights at the time of operation by disrupting the original plans as minimally as possible. We focus on the crew pairing aspect of robustness and prescribe that the planned crew pairings incorporate a number of predefined recovery solutions for each potential extra flight. These solutions are implemented only if necessary for recovery purposes and involve either inserting an extra flight into an existing pairing or partially swapping the flights in two existing pairings in order to cover an extra flight. The resulting mathematical programming model follows the conventional set covering formulation of the airline crew pairing problem typically solved by column generation with an additional complication. The model includes constraints that depend on the columns due to the robustness consideration and grows not only column-wise but also row-wise as new columns are generated. To solve this difficult model, we propose a row and column generation approach. This approach requires a set of modifications to the multi-label shortest path problem for pricing out new columns (pairings) and various mechanisms to handle the simultaneous increase in the number of rows and columns in the restricted master problem during column generation. We conduct computational experiments on a set of real instances compiled from local airlines in Turkey.  相似文献   

20.
The center of area of a convex polygonP is the unique pointp * that maximizes the minimum area overlap betweenP and any halfplane that includesp *. We show thatp * is unique and present two algorithms for its computation. The first is a combinatorial algorithm that runs in timeO (n 6 log2 n). The second is a numerical algorithm that runs in timeO(GK(n+K)) whereK represents the number of desired bits of precision in the output coordinates andG the number of bits used to represent the coordinates of the input polygon vertices. We conclude with a discussion of implementation issues and related results.Research partially supported by the second author's NSF grant CCR-8351468, at Johns Hopkins University and Smith College.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号