多层次-跨尺度物理中并行DVM-DAC算法

多尺度现象及相关理论方法是复杂物质系统研究中重要的科学问题.单一的量子力学或分子动力学方法无法解释多尺度体系中存在的现象.第一原理离散变分线性标度（DVM-DAC）算法是一种有效的大尺度体系计算方法.它采用分而治之方案,获得了O（n）的计算复杂性.但由于需要求解大量的特征方程,实现中存在严重的计算瓶颈.发展了一种并行DVM-DAC算法并付诸实现,有效地解决了原有算法的计算瓶颈问题.测试结果表明,并行DVM-DAC算法具有很好的可扩展性,并成功完成104碳纳米管原子体系的计算,为多尺度体系研究提供重要工具.     

非完全无线报文重传分析研究及其分治策略

网络编码为无线网络报文重传问题WPRTPs(Wireless Packet ReTransmission Problems)提供了有效解决途径.现有关于WPRTP问题的研究主要针对完全无线网络报文重传问题P-WPRTPs(Perfect WPRTPs),而尚未发现对非完全无线网络报文重传问题IP-WPRTPs（ImPe...     

Two algorithms for constructing a Delaunay triangulation

This paper provides a unified discussion of the Delaunay triangulation. Its geometric properties are reviewed and several applications are discussed. Two algorithms are presented for constructing the triangulation over a planar set ofN points. The first algorithm uses a divide-and-conquer approach. It runs inO(N logN) time, which is asymptotically optimal. The second algorithm is iterative and requiresO(N ²) time in the worst case. However, its average case performance is comparable to that of the first algorithm.This work was supported in part by the National Science Foundation under grant MCS-76-17321 and the Joint Services Electronics Program under contract DAAB-07-72-0259.     

基于最长名词短语分治策略的神经机器翻译

神经机器翻译自兴起以来,不断给机器翻译领域带来振奋人心的消息。但神经机器翻译没有显式地利用语言学知识对句子结构进行分析,因此对结构复杂的长句翻译效果不佳。该文基于分治法的思想,识别并抽取句子中的最长名词短语,保留特殊标识或核心词,与其余部分组成句子框架。通过神经机器翻译系统分别翻译最长名词短语和句子框架,再将译文重新组合,缓解了神经机器翻译对句子长度敏感的问题。实验结果表明,该方法获得的译文与基线系统相比,BLEU分值提升了0.89。     

A note on the expected time required to construct the outer layer

The expected time E(T) of the standard divide-and-conquer algorithm for finding the outer layer of a set of points in the plane depends upon the distribution of the points. Under the mild assumption that the points are independent random vectors and have a common bounded density with compact support, it is shown that E(T) = O(n).     

基于正则互表示的无监督特征选择方法

针对高维数据含有的冗余特征影响机器学习训练效率和泛化能力的问题,为提升模式识别准确率、降低计算复杂度,提出了一种基于正则互表示（RMR）性质的无监督特征选择方法。首先,利用特征之间的相关性,建立由Frobenius范数约束的无监督特征选择数学模型;然后,设计分治-岭回归优化算法对模型进行快速优化;最后,根据模型最优解综合评估每个特征的重要性,选出原始数据中具有代表性的特征子集。在聚类准确率指标上,RMR方法与Laplacian方法相比提升了7个百分点,与非负判别特征选择（NDFS）方法相比提升了7个百分点,与正则自表示（RSR）方法相比提升了6个百分点,与自表示特征选择（SR_FS）方法相比提升了3个百分点;在数据冗余率指标上,RMR方法与Laplacian方法相比降低了10个百分点,与NDFS方法相比降低了7个百分点,与RSR方法相比降低了3个百分点,与SR_FS方法相比降低了2个百分点。实验结果表明,RMR方法能够有效地选出重要特征,降低数据冗余率,提升样本聚类准确率。     

一个混沌分组密码算法的分析*

研究了一个基于混沌设计的分组密码算法的安全性,发现该算法所产生的混沌序列具有前几个值对混沌初态和参数的低位比特变化不够敏感的性质,在选择明文攻击条件下,提出了攻击加密算法等效密钥的分割攻击方法。分组密码算法的密钥长度为106 bit,分割攻击方法的计算复杂性约为260,存储复杂性约为250,成功率为0.928 4。     

一种性能优化的防火墙规则匹配算法

设计了一种防火墙规则匹配算法,该算法基于分治思想将规则集按照协议类型分割为多个子集,并根据规则之间的关系,将各子集分为无序组和有序组,通过设计哈希函数和索引算法对两组规则进行分别匹配。分析表明,该算法的效率远优于同类算法,大大提高了防火墙的工作性能。     

对LZ混沌序列密码算法的分割攻击

分析基于混沌的伪随机序列密码算法的安全性,发现该算法具有所产生密钥流序列的前几个值对密钥低位比特的变化不够敏感的性质,不适合将混沌映射的参数作为密钥。为此,提出一个能够有效降低密钥熵的分割攻击方法,理论分析和实验结果证实了该方法的有效性。     

Rotate-N-Puzzle问题可解性分析及求解

Rotate-N-Puzzle问题与N-Puzzle问题类似，问题空间也具有组合爆炸性质。经证明，Rotate-N-Puzzle的任何一个初始布局都是可解的。在此结论的基础上，给出了解长度的上界。提出了一种分治算法，在算法中的每一步，采用贪心策略求解问题。实验结果表明，该算法能够在多项式时间内快速求解规模很大的Rotate-N-Puzzle问题。