一个基于分治法的快速多精度乘法

多精度运算中,乘法的设计与实现非常复杂,传统的多精度乘法的时间复杂度为O(n2),基于分治法介绍了一种改进的快速乘法,通过理论分析,改进算法的时间复杂度为O(nlog23).     

基链分治算法与Voronoi区的面积计算定理研究

基于一般曲线多边形Voronoi图的面向对象数据结构,提出了一种改进的Voronoi图生成算法——基链分治算法.该算法与经典的分治法相比更容易被实现.同时,在欧氏米制中,由于Voronoi区的边界包含抛物线或双曲线,因而Voronoi区的面积很难被计算.为此提出了Voronoi区的面积计算定理,并给出了定理证明和算例,从而为某些工程应用中的面积计算提供了一种方法.     

A General Method for Geometric Feature Matching and Model Extraction

Popular algorithms for feature matching and model extraction fall into two broad categories: generate-and-test and Hough transform variations. However, both methods suffer from problems in practical implementations. Generate-and-test methods are sensitive to noise in the data. They often fail when the generated model fit is poor due to error in the data used to generate the model position. Hough transform variations are less sensitive to noise, but implementations for complex problems suffer from large time and space requirements and from the detection of false positives. This paper describes a general method for solving problems where a model is extracted from, or fit to, data that draws benefits from both generate-and-test methods and those based on the Hough transform, yielding a method superior to both. An important component of the method is the subdivision of the problem into many subproblems. This allows efficient generate-and-test techniques to be used, including the use of randomization to limit the number of subproblems that must be examined. Each subproblem is solved using pose space analysis techniques similar to the Hough transform, which lowers the sensitivity of the method to noise. This strategy is easy to implement and results in practical algorithms that are efficient and robust. We describe case studies of the application of this method to object recognition, geometric primitive extraction, robust regression, and motion segmentation.     

非线性反馈移存器型序列密码的完全性通用算法

非线性反馈移存器型序列密码被使用于智能卡、射频识别标签（RFID）和无线传感器等硬件资源受限设备的信息加密中,其典型代表为Trivium算法、Grain v1算法和Mickey算法,然而现有的完全性算法在应用于此类序列密码时存在分析轮数较少及对依赖关系区分不清楚等问题.本文提出了一种考察此类序列密码完全性的通用算法,将算法内部状态表示成线性集合和非线性集合,将序列密码每轮更新转化为集合的运算,通过迭代计算可给出算法达到非线性完全性所需轮数的下界,克服了现有完全性算法的不足.应用此通用算法给出Trivium算法更优的1比特差分区分器并完成对Trivium-B算法的实时攻击.本方法可为此类序列密码的设计提供一定的理论依据.     

Internet环境下并行群组数据挖掘模型

随着Internet技术的发展,分布式数据挖掘越来越受到重视。分布式数据挖掘急需一种能聚合多种网络功能为通信媒介,松耦合、并行的数据挖掘架构。以分析经典并行数据挖掘模型PADMA和BODHI为基础,结合现实需要给出了一种新的并行分布式数据挖掘模型——PADMAN。模型采用分治策略,将数据挖掘任务进行划分并分配给数据挖掘组,群组之间并行挖掘;基于Agent,使各基本数据挖掘单元具有自治性;群组客户端和全局客户端可实现无线接入,使用户端的使用和接入更加灵活。分治策略的应用,使模型具有良好的模块化和可扩展性。     

面向图像内补与外推问题的迭代预测统一框架

目的 图像内补与外推可看做根据已知区域绘制未知区域的问题,是计算机视觉领域研究热点。近年来,深度神经网络成为解决内补与外推问题的主流方法。然而,当前解决方法多分别对待内补与外推问题,导致二者难以统一处理;且模型多采用卷积神经网络(convolutional neural network,CNN)构建,受到视野局部性限制,较难绘制远距离内容。针对这两个问题,本文按照分而治之思想联合CNN与Transformer构建深度神经网络,提出图像内补与外推统一处理框架及模型。方法 将内补与外推问题的解决过程分解为“表征、预测、合成”3个部分,表征与合成采用CNN完成,充分利用其局部相关性进行图像到特征映射和特征到图像重建;核心预测由Transformer实现,充分发挥其强大的全局上下文关系建模能力,并提出掩膜自增策略迭代预测特征,降低Transformer同时预测大范围未知区域特征的难度;最后引入对抗学习提升绘制图像逼真度。结果 实验给出在多种数据集下内补与外推对比评测,结果显示本文方法各项性能指标均超越对比方法。通过消融实验发现,模型相比采用非分解方式具有更佳表现,说明分而治之思路功效显著。此外,对掩膜自增策略进行详细的实验分析,表明迭代预测方法可有效提升绘制能力。最后,探究了Transformer关键结构参数对模型性能的影响。结论 本文提出一种迭代预测统一框架解决图像内补与外推问题,相较对比方法性能更佳,并且各部分设计对性能提升均有贡献,显示了迭代预测统一框架及方法在图像内补与外推问题上的应用价值与潜力。     

Coalition-based downlink resource allocation for LTE system with divide-and-conquer approach

To take advantage of the multiuser diversity resulted from the variation in channel conditions among the users,it has become an interesting and challenging problem to efficiently allocate the resources such as subcarriers,bits,and power.Most of current research concentrates on solving the resource-allocation problem for all users together in a centralized way,which brings about high computational complexity and makes it impractical for real system.Therefore,a coalitional game framework for downlink multi-user resource allocation in long term evolution(LTE) system is proposed,based on the divide-and-conquer idea.The goal is to maximize the overall system data rate under the constraints of each user’s minimal rate requirement and maximal transmit power of base station while considering the fairness among users.In this framework,a coalitional formation algorithm is proposed to achieve optimal coalition formation and a two-user bargaining algorithm is designed to bargain channel assignment between two users.The total computational complexity is greatly reduced in comparison with conventional methods.The simulation results show that the proposed algorithms acquire a good tradeoff between the overall system throughout and fairness,compared to maximal rate and max-min schemes.     

An optimal parallel algorithm for triangulating a set of points in the plane

This paper presents an optimal parallel algorithm for triangulating an arbitrary set ofn points in the plane. The algorithm runs inO(logn) time usingO(n) space andO(_n) processors on a Concurrent-Read, Exclusive-Write Parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is (logn) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into subproblems is employed.     

基于分治策略的组块分析

组块分析的主要任务是语块的识别和划分,它使句法分析的任务在某种程度上得到简化。针对长句子组块分析所遇到的困难,该文提出了一种基于分治策略的组块分析方法。该方法的基本思想是首先对句子进行最长名词短语识别,根据识别的结果,将句子分解为最长名词短语部分和句子框架部分;然后,针对不同的分析单元选用不同的模型加以分析,再将分析结果进行组合,完成整个组块分析过程。该方法将整句分解为更小的组块分析单元,降低了句子的复杂度。通过在宾州中文树库CTB4数据集上的实验结果显示,各种组块识别结果平均F1值结果为91.79%,优于目前其他的组块分析方法。     

对XW混沌密码算法的分割攻击*

分析了徐淑奖等人提出的一类混沌迭代加密算法的安全性,发现该加密算法由混沌映射产生的量化序列的前几个量化值对混沌初始值低位比特的变化不够敏感,据此提出了在选择明文攻击条件下由量化序列恢复混沌初始值的先攻击高位比特再攻击低位比特的分割攻击方法。在参数r= 4已知且密钥长度为64 bit的条件下,分割攻击算法仅需1个选择明密对,其成功率为0.930 5,计算复杂性约为219.7,存储复杂性约为211.6。