基于关系的最粗粒度划分问题的并行算法

关系最粗粒度的划分问题ＰＣＰＰ在并发系统的验证方面起着重要的作用。本文提出了ＲＣＰＰ问题的一种有效的并行算法,其中假设标号转移系统中有ｍ个转移和ｎ个状态,利用ｍ／ｎ＾∈个ＣＲＥＷ处理器算法所需的运行时间为Ｏ（ｎ＾１＋∈）（对于任意固定的∈〈１）。     

UP,βn和FewP完全问题的相对同构性

本文引进相对的多项式化归和相对多一多项式同构等概念，对ＵＰ、βｎ的ＦｅｗＰ的相对完全集讨论它们的相对同构问题。并得到如下结果：１（１）对任何≤ｍ＾Ｐ，Ｂｎ－βｎ＾Ｂｎ完全集Ｃ，Ｃ≈Ｐ＾ＢｎＡｎ←→Ｃ为Ｐ＾Ｂｎ柱。（２）对任何≤ｍ＾Ｐ，Ｂ－ＦｅｗＰ＾Ｂ完全集Ｃ，Ｃ≈Ｐ＾Ｂ∪Ａｎ←→Ｃ为Ｐ＾Ｂ柱，其中Ｂ＝ＳＡＴ－∪Ａｎ。 ｎ∈Ｎ ｎ∈Ｎ     

货郎担问题最优并行启发式算法

本文给出了满足三角不等式的货郎担问题的并行启发式算法，在ＳＩＭＤ ＣＲＥＶ ＰＲＡＭ并行机上该算法使用Ｏ（ｎ＾３／ｌｏｇ＾２ｎ）台处理器需Ｏ熄ｌｏｇ＾２ｎ）时间，这里ｎ是给定城市的个数，因而该并行算法是最优的。     

判定点集是否在多边形内部的算法

本文提出了判定ｎ个点的点集Ｓ是否落入多边形Ｌ内部的算法，该算法的复杂性为：ｍａｘ（Ｏ（ｍｎ），Ｏ（ｌｎ ｌｏｇ ｎ））比比较和Ｏ（ｌｎ）次乘法，其中ｍ是Ｌ的顶点数，ｌ为Ｓ的凸包层数。     

并行归并排序算法

构造效率为Ｏ（１）的并行算法是一个引人注目的问题。［１］和［２］分别提出了并行度为Ｏ（ｌｏｇｎ）和Ｏ（ｎ＾１／２）的、效率为Ｏ（１）的并行排序算法。本文提出一种新的并行排序算法，其效率为Ｏ（１），而并行步数小于［１］和［２］的算法的并行步数。经过改进后，在保持效率为Ｏ（１）的情况下，可进一步将并行度扩大到Ｏ（ｎ＾１／２ｌｏｇ ｎ）。     

一个多元选择算法

本文基于数排序的思想，从高位关键字开始，对ｍ位关键字的ｎ个记录进行扫描，给出了一个多元选择算法，算法的最坏复杂度为Ｏ（ｍ（ｎ＋ｒ）），但平均复杂度为Ｏ（ｎ＋ｒ）。     

完全欧几里德距离变换的最优算法

欧几里德距离变换（ＥＤＴ）对由黑白素构成的二值图象中所有象素找出其到最近黑素的距离，应用于图象分析，计算机视觉，在本文之前，该问题的最好复杂度为Ｏ（ｎ＾２ｌｏｇｎ）。本文提出了一个复杂度为Ｏ（ｎ＾２）的算法，使复杂度达到最优，该算法可以并行化，在有ｒ个处理单元的ＥＲＥＷＰＲＡＭ计算模型上，若ｒｌｏｇｒ≤２２／６ｎ，则时间复杂度为Ｏ（ｎ／ｒ）否则为Ｏ（ｎｌｏｇｒ）。     

快速分布式数据库数据分布模型求解算法

针对我们提出的以最小代价为目标的分布式数据库数据分布模型，进行适当的数据分组，并对部份组进行排序，使单目运算，双目运算的计算复杂度分别提高了Ｏ（ｎ）和Ｏ（ｎ＾２）。更新运算分解后计算复杂度提高Ｏ（ｎ）。     

关于迷宫排序问题的研究

本文首先把迷宫排序问题推广为ｍ×ｎ迷宫（ｍ＞１，ｎ＞１）的排序问题，证明了ｍ×ｎ迷宫的任一初始状态能经过有限步移动转变成目标状态的充要条件，然后给出了一个ｍ×ｎ迷宫排序的算法，该算法的时间复杂度是Ｏ（ｍｎ（ｍ＋ｎ）），空间复杂度是Ｏ（ｍｎ）．最后还指出了它的时间复杂度的一个下界．这样，关于迷宫排序问题就基本上得到了圆满地解决．     

Z^＊pq中离散对数问题的安全谓词

本文讨论了Ｚ＾＊ｎ（ｎ＝ｐｑ，ｐ和ｑ未知）中离散对数问题的一些基本概念及问题本身的难度；定义了Ｚ＾＊ｎ中离散对数问题中关于判断主平方根的谓词Ｂｎ，ａ（ｘ），证明了谓词Ｂｎ，ａ（ｘ）即为Ｚ＾＊ｎ中离散对数问题的安全谓词。     

A Fault-tolerant model for tuple space coordination in distributed environments

In distributed systems, tuple space is one of the coordination models that significantly maximizes system performance against failure due to its space and time decoupling features. With the growing popularity of distributed computing and increasing complexity in the network, host and link failure occurs frequently, resulting in poor system performance. This article proposes a fault-tolerant model named Tuple Space Replication (TSR) for tuple space coordination in distributed environments. The model introduces a multi-agent system that consists of multiple hosts. Each host in a multi-agent system comprises an agent space with a tuple space for coordination. In this model, we introduce three novel fault-tolerant algorithms for tuple space primitives to provide coordination among hosts with tolerance to multiple links and hosts failure. The first algorithm is given for out() operation to insert tuples in the tuple space. The second algorithm is presented for rdp() operation to read any tuple from the tuple space. The third algorithm is given for inp() operation to delete or withdraw tuples from the tuple space. These algorithms use less number of messages to ensure consistency in the system. The message complexity of the proposed algorithms is analyzed and found O(n) for out(), O(1) for rdp(), and O(n) for inp() operations which is comparable and better than existing works, where n is the number of hosts. The testbed experiment reveals that the proposed TSR model gives performance improvement up to 88%, 70.94%, and 63.80% for out(), rdp(), and inp() operations compared to existing models such as FT-SHE, LBTS, DEPSPACE, and E-DEPSPACE.     

一种基于密度的并行聚类算法

针对微阵列基因表达数据聚类的高维复杂性,提出了一种基于密度的并行聚类算法,在APRAM模型的分布式存储系统中,通过欧几里德距离矩阵和密度函数两次时间复杂度为O（■）的计算,可使聚类过程的时间复杂度为O（■）,以增加一次计算的代价来降低聚类过程的时间复杂度。基于8结点的机群计算实验表明：本算法能够达到较同类算法更高的并行加速比,提高高维生物数据的聚类速度。     

一种伪随机数生成算法的研究与实现

对常用随机数生成算法作简要介绍。以Visual Basic语言做为工具。对目前应用最为广泛的“素数模乘法线性同余随机数生成算法”和VB中的Rnd函数组成进行实现．并就该算法进行了统计检验。     

基于Facet模型的边缘检测算法

使用CCD的影像测量系统进行精加工零件尺寸检测时,零件轮廓边缘的定位精度和处理速度是优先考虑的2个问题。该文介绍了一种基于Facet模型的综合梯度边缘检测算法,并针对其边缘定位精度低和执行效率低的问题,给出一种提高边缘定位精度的算法和加速计算Facet模型的算法。该改进算法使用动态闽值定位边缘以提高边缘定位精度,同时将Facet模型的二维卷积分解为2个一维卷积核,使算法的复杂度从D（i^2）降低到O（2i）。通过对理想影像和实际工件影像的边缘检测,说明该算法在影像测量中可以有效抑制工件影像的噪声,获得较好的边界特征,且执行效率较高。     

H.264编解码软件JM8.6的核心编码函数研究

H.264编解码软件JM通常被作为算法研究或者实际应用的平台.理解JM的程序结构是在其基础上进行进一步研究工作的前提.JM中的编码函数encode_one_maeroblock在程序实现编码算法的过程中起到核心的作用.通过对程序中开销计算,关键全局变量及编码一个宏块的算法的分析,查明了JM核心编码函数encode_one_maeroblock()的结构,给出了该函数的流程.     

基于ARM920T的AES算法实现方案

为了提高高级加密标准(AES)算法在ARM上执行的效率,提出AES算法在ARM处理器上的高效实现方案,并在ARM920T处理器上得以实现。密钥扩展采用一次性生成方式。在算法实现上,将字节替换和列混合定义成T表进行存储,可以提高运行速度。采用C语言编程,在ARM Develop v1.2平台上进行了仿真及调试。对算法的不同实现方式所占的存储空间和运算速度进行了比较,并给出了不同密钥长度算法的各种性能指标。实验表明,算法执行速度得到了明显提高。     

评价目标前提的逻辑框架

多前提决策问题是决策领域中重要的研究内容,其决策质量可反映决策理论研究的成果。在多前提决策中,目标会有多种实现方式,每种实现方式都有相应的实现难度。在多前提决策研究中,定义了目标的条件集,提出了将条件集分解到最简单形式的算法,并证明了算法的输出为目标的极小最简不完备条件集。然后,提出了条件集可信度的概念及其计算方式,利用可信度评估目标的所有极小最简不完备条件集的实现难度,并以此确定实现该目标的最优条件集。最后,给出了评价目标前提的逻辑框架O的形式定义,证明了框架O的可计算性和推理能力,并用逻辑程序Prolog实现了框架O的原型,通过对框架O的原理性实验和具体的工程应用验证了框架O的有效性。     

灰度图像质心快速算法

对矩因子x^py^q。做差分变换为函数Fl()，将图像函数f(x，y)做累进求和变换为函数F2()．用Fl()和F2()相乘求取质心．由于0阶和1阶矩因子中的P，q不大于1，经差分后的F1()除右端点外，其值都为1，乘1的运算当然可以不做，从而消去了乘法运算．对任意大小和任意级别的灰度图像，乘除法运算次数仅为3次，而加法运算次数也有降低．文中算法计算结果精确，其运算效率高于已有其他算法．     

基于CPLD的S+P逆变换的硬件实现方案

讨论与具有良好性能的子带变换－S＋P正变换相对应的S＋P产变换硬件实现方案，结果表明，S＋P（逆）变换不仅在LZC（Listless Zerotree Clding,无列表零树压缩编码算法）中起着非常重要的作用，而且与其它子带变换方法相比，该变换所涉及的运算都可以用逻辑移位和算术加减来实现，这种使硬件的实现成为可能。     

一种基于VB环境下组合随机数发生器的构建

由于随机数是离散事件系统计算机仿真的核心所在，所以随机数列的性能好坏直接影响仿真结果的有效性。该文叙述了采用构造的线性同余发生器和Visual Basic环境中Rnd()函数结合起来，构建组合发生器的方法。比较了单独使用RIM()函数得到的随机数列与使用组合发生器得到的随机数列的性能指标，后者在保持随机数列均匀性的同时，大大提高了随机数列的独立性。