微分方程并行迭代法及线性递归

本文提供一个微分方程并行算法——迭代法,进行了收敛性和稳定性证明,并给出在YH-1机上的试算实例及精度分析,其最大加速比为7.7。     

二维离散付氏变换快速向量算法

本文从向量机向量计算的特点出发,研制了一个适合于在向量机上计算的二维离散付氏变换的快速算法。该算法的基本思想是研究和选取一维离散快速付氏变换算法作为二维计算的基本公式,利用频率函数的周期性和对称性减少基本公式乘、加运算次数,在此基础上组织长向量运算。该算法的特点是精度好、速度快、程序结构简便。应用本算法编写的FORTRAN程序在YH-1机上计算,并和YH-1现有二维离散付氏变换程序比较,计算效率比行列算法汇编程序平均提高53％,比行列算法FORTRAN程序平均提高3.2倍,比快速卷积算法和多项式变换算法则提高10倍以上。     

改进的二分法查找

当前有很多的查找算法,其中在对有序数列的查找算法中二分法查找（binary search）是最常用的。利用二分法,在含有n个元素的有序数列中查找一个元素的最大比较次数为[logn]＋1。在很多情况中,在查找之前有序数列分布的很多信息为已知,比如说如果知道了有序数列中每相邻两个元素之差的最大值的一个上界,就可以有比二分法更加有效的查找算法。文章给出了一个称之为改进的二分法查找算法。改进的二分法查找性能明显优于二分法查找,受数列分布的影响,其最坏情况下查找一个元素的最大比较次数在1和[logn]＋1之间,明显优于二分查找的[logn]＋1。在实际应用中利用改进的二分法可以极大地提高查找效率。     

一种改进的二分查找算法

当前在有序数列查找中二分查找最为常用,但是二分查找在一些特殊情况下,其查找效率很低,如查找元素是数列中的第一个元素和最后一个元素。针对这种情况,结合数列特性,设计了一种改进的二分查找算法。改进的二分查找算法经理论和实验证明,其平均查找长度介于1和n+1/nlog2(n+1)-1之间,明显优于二分查找的平均查找长度n+1/nlog2(n+1)-1,实现难度比参考文献[1]要容易。     

一种新的二分路由查找方法

分析路由表前缀间的覆盖关系特征,证明了前缀覆盖级别集合符合二分查找特性,提出一种基于前缀覆盖级别的二分路由查找算法,和传统基于前缀长度或者前缀值的线性或者二分查找算法相比,在查找性能、路由更新和存储空间方面具有优势,本方法可以在O(log2max_level+1)个TCAM时钟周期内完成1次路由查找,其中max_level为最大的前缀覆盖级别,目前max_level不超过7;本方法无需前缀扩展和排序,支持路由增量更新;另外,传统TCAM路由查找相比,可以节省功耗约50%.     

一种改进的查找表逆半调算法

边缘和平滑区域是图像的重要组成部分,人眼对边缘特征和平滑区域的噪声比较敏感。文中提供了一种改进的查找表逆半调算法,该算法在查找表逆半调算法的基础上考虑了边缘在图像处理中的作用,并对图像边缘分类,然后,按照半调图及图像边缘的类型重构连续色调图像。通过由误差分散类半调图构成的不同频率特征的训练集、测试集进行实验,表明当训练集为平滑图像集时基于边缘的查找表逆半调算法处理平滑图像,在主、客观评价方面的效果都好于查找表逆半调算法处理的图像;而改进的方法在处理细节图像时与查找表逆半调算法相比没有优势。     

一种Trie结构

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

适用于向量机的物面点算法

本文给出了一个物面边界计算的新方法,它既用了特征概念,又避免了作特征线的迭代过程。特别适宜于在 YH-1机上实现并行运算。从而对提高用非定常差分方法求解混合型方程的初边值问题的速度有着明显的作用。     

超音速理想流绕钝体有攻角问题的差分解法

本报告提出了解超音速理想流问题的一种差分方法,所考虑的物体是具有各种烧蚀外形的钝头旋转体,气流是有攻角的,因而是一个三维问题。这里给出了详细的计算公式,介绍了计算过程。对于这种算法在 YH-1机上的实现效能给出了一般的分析,说明了是可以达到高效的。     

一个对半查找的新算法

<正> 在计算机的信息检索方面,对半查找是极其重要的一种方法。一个文件的n个记录已经按记录的关键码排序,当,n=2~M-1(M为正整数)时,对半查找对应着一棵完全二叉分类树。当n≠2~M-1时,所对应的就不是一棵完全树。此时,对半查找的最佳分类树是一棵对称二叉分类树(本文所讨论的,都是查找概率为平均值的情况,即对统一记录有Pi=1/n),因其平均查找路径最短。 本文将讨论一个对半查找的新算法。计算法对任一个n都可以形成一棵对称二叉分类树。     

面向Internet的CFR算法的研究

针对Internet上资源量巨大，查找有用资源较困难的问题，基于Internet的小世界特征和无尺度特征，提出了一个新的资源查找算法一连接度优先路由查找算法（CFR），该算法利用Internet上：帝点间平均最短路径短以及少量节点的连接度较高，而大量的节点连接度较小的特点，通过将查询信息包转发给连接度较高的节点的方法，实现了在Internet上高效的资源查找．最后，通过实现的Internet拓扑生成器，仿真验证了该算法具有查找效率较高、时间开销和造成的网络流量较小的特点．     

M+树:一种新型、高效的动态哈希算法

通常哈希函数只支持等值查找，这给哈希函数的应用带来了很大的限制。该文提出了一种新型的哈希索引算法——M 树索引。该算法能够支持等值和范围查找，实验表明，该算法无论在查询效率还是可维护性方面都优于同类索引算法。     

一种基于DHT的资源查找算法

提出了一种基于DHT的资源查找定位算法,算法中每个网络节点在维护O（n×N1/n）其他节点信息的情况下,可以在n逻辑路由跳内查找定位任意网络资源,通过n的不同设置,本算法可适用于不同的对等网络。     

矩阵平衡及策略

矩阵平衡是一般矩阵求解特征值问题的一个重要处理过程。它不仅可以提高求解的全程效率,而且可以改善计算结果的精度。本文论述了矩阵平衡的算法结构及实施策略,并对其充要条件给予证明。该算法在YH-2 EISPACK中得以应用。     

分类问题的一种可伸缩特征选择算法

特征选择是数据挖掘分类中的一个重要问题．该文推导出一种新的衡量特征与类别相关度的测度SCD即描述特征取值序列类分布的CV系数,利用该测度给出一种线性的可伸缩特征选择算法StaFSOS,并证明了在类别数为2时,SCD测度满足分支界限法的单调性;给出了StaFSOS的一个完备形式——BBStaFS．在12个标准数据集中,StaFSOS算法得出的结果和目标集几乎一致,而StaFSOS的效率高于其它算法;而在另1个中,BBStaFS算法得出了准确结果．在用1000个样本20个特征的真实数据进行的测试中,StaFSOS运行时间是目前较快的GRSR的1／2,得出的特征集准确有效．     

EBMT中高效的维吾尔语单词散列表构造算法

基于实例的机器翻译(EBMT)是一种高效的机器翻译方法,如何快速地从海量实例模式库中找出与待翻译句子相似的候选实例,是EBMT研究的关键技术之一。统计分析维吾尔语单词字母的分布特征,构造了基于维吾尔语单词的倒排索引散列表,在等概率条件下,平均查找长度为1.59;依据散列冲突的同义词在维吾尔语料中出现的频率作为权值,提出了一种新颖的解决散列冲突的算法同义词次优树算法。实验显示,算法的性能比传统的顺序查找和二分查找算法分别高出了27.5 %,21.8%,证明了该算法在EBMT中有较高的检索效率。     

空间离群点的模型与跳跃取样查找算法

目前无论是查找一般的离群点，还是空间离群点，都强调非空间属性的偏离，但在图像处理、基于位置的服务等许多应用领域，空间与非空间属性要综合考虑。为此，首先提出了一个综合考虑两者的空间离群点定义，然后提出了一种新的基于密度的空间离群点查找方法——基于密度的跳跃取样空间离群点查找算法DBSODLS。由于已有的基于密度的离群点查找方法对每一点都要求进行邻域查询计算，故查找效率低，而该算法由于可充分利用已知的邻居信息，即不必计算所有点的邻域，从而能快速找到空间离群点。分析与试验结果表明，该算法时间性能明显优于目前已有的基于密度的算法。     

关于二分法查找算法的历史研究

本文讨论了包括J.J.Donovan在内的26名作者在设计二分法查找算法时的某些历史情况。指出了这些算法的某些错误推导。文中分析了四种典型的正确算法,即(1)关于T项单调递增序列的单纯的二分法查找算法,其中T=2~n-1,n≥1;(2)关于T项单调递增序列的二分法查找算法;(3)关于T项单调递增序列的“双向检验”的二分法查找算法,其中T≥1;(4)关于T项单调递增序列的通用二分法查找算法。 文中还指出了二分法查找算法的历史教训。     

基于资源属性空间的网格资源查找算法

提出了一种基于资源属性空间的网格资源查找算法,资源之间通过属性的相似度来确立彼此之间的邻接关系,每个邻居代表属性的一种变化趋势,这样在资源查找时可以沿着与目标资源属性越来越近的方向查找,因此具有较高的查找效率.在理论上证明了算法的完备性;通过试验验证了算法的查找效率.     

SIP终端中拓扑感知的P2P中继查找机制实现①

由于Internet采用尽力而为的服务,VoIP系统存在QoS问题。为改善QoS,多数系统采用“应用层路由”方案,该方案关键是如何查找拓扑最优中继节点。结合P2P技术,提出一种拓扑感知的P2P中继查找机制。首先构建一个Cluster Overlay网络来模拟真实的Internet拓扑;在Cluster Overlay网络上设计一种拓扑感知的中继查找算法;最后在SIP终端中实现这种方案。在NS2平台上对Cluster Overlay网络和中继查找机制进行了仿真实验。结果表明：Cluster Overlay网络和真实的Internet拓扑相似度很高,中继查找算法能查找到最优中继结点,从而改进了路径质量。