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

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

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

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

一种利用无条件认证实现的强保密增强协议

要解决保密增强中的防主动攻击的问题,就必须对公共信道上的通信内容进行认证。文中提出并分析了一种新的用纠错码构造认证码的方法,这种认证码构造简单对域ＧＦ（ｑ）上的任意一个码都找到一个相应的认证码。如果通信双方共享一个ｎｂｉｔ的部分保密串Ｓ,则可以构造一种基于（２＾ｍ,ｋ,２＾ｍ－ｋ＋１）扩展ＲＳ码的认证码,其中ｍ＝〖ｎ／ｋ〗且２＾ｍ〉ｋ,只要双方间共享一个至少３ｍｂｉｔ的认证密钥,就有可能在一个不安     

几何算法求解货郎担问题

本文提出求解货郎担问题的一种几何算法。它的时间复杂性为：Ｏ（ｎ＾３／ｍ）次比较，Ｏ（ｎ＾２）次乘法，其中ｎ，ｍ分别是点集的点数和凸包顶点数。     

关于迷宫排序问题的研究

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

酶电极——流动注射法测定酚类

本文将抗生素激活的酪氨酸酶玻碳电极与ＦＩＡ技术相结合,在所选ＦＩＡ体系的参数下,电极测标样的线性范围为１．００×１０＾－６～１．００×１０＾－４ｍｏｌ／Ｌ,测量范围不小于５．００×１０＾－６～１．００×１０＾－４ｍｏｌ／Ｌ,在此范围内ＲＳＤ≤１．８％,ＲＥ≤２．４％（ｎ＝６）。测定某焦化厂含酚废水稀释样（Ｃ苯酚＝４．４９×１０＾－６ｍｏｌ／Ｌ）得ＲＳＤ＝２．８％,加标回收率为９８．４～１００．９％。连续７小时测定的初步结果表明,前４小时无明显的衰减,其ＲＳＤ＝３．０％,后３小时的总衰减率为１３．４％。     

可卡因化学传感器的研究

本文报道了一种以十六烷基苄基二甲基铵（ＣＢＤＭＡＣ）－可卡因为活性物，以邻苯二甲酸二丁酯（ＤＢＰ）为增塑剂的化学传感器，性能良好，其线性范围为５．０×１０＾－６￣１．０×１０＾－２ｍｏｌ·Ｌ＾－１，斜率为６０ｍＶ／ｐＣ，检测下限为１．０×１０＾－６ｍｏｌ·Ｌ＾－１，传感器寿命为５０天。     

N-Star网络中最优的点到多点平行路由算法

Ｃｈｅｎｔ等研究了ｎ－Ｓｔａｒ网络中的点到多点并行路由问题,对前人的工作做了很大的改进,给出了一个几乎最优的时间复杂度为Ｏ（ｎ＾２）的算法,由Ｃｈｅｎ的算法所给出的ｎ－１条路Ｐ２,…,Ｐｎ满足│Ｐｉ│≤ｄｉｓｔ（ｖ１,ｖｉ）＋６,其中Ｐｉ是连续ｖｉ到ｖ１的路,│Ｐｉ│表示路Ｐｉ的长度,ｄｉｓｔ（ｖ１,ｖｉ）表示ｖｉ到ｖ１的最短路的长度。     

指挥控制参考模型

指挥控制参考模型（Ｃｏｍｍａｎｄ ａｎｄ Ｃｏｎｔｒｏｌ Ｒｉｆｉｒｉｎｃｅ Ｍｏｄｉｌ,简记为Ｃ＾２ＲＭ）试图为Ｃ＾２系统的概念、术语、定义和原理等基本问题进行统一的描述,提供了一个标准的、面向对象的开放系统体系结构和开放系统互边框架,以用于Ｃ＾２系统及其下辖资源的建模和仿真,并为异构和分布的Ｃ＾２系统资源间皎互提供标准的Ｃ＾２协议和接口,以推动Ｃ＾２系统技术和应用的发展。本文阐述了Ｃ＾２ＲＭ的     

二十一世纪CMOS工艺发展趋势

本文描述了０．１μｍ沟道ＣＭＯＳ器件的设计、制造及其特点,该器件在３５Ａ经物上有双ｎ＾＋／ｐ＾＋多晶硅栅。在１．５Ｖ的电源电压下,其性能比２．５Ｖ的０．２５μｍＣＭＯＳ技术提高了２倍。此外,小于１Ｖ的供电电压可使每个电路中的有源功耗降低２０倍,而其延迟仍与０．２５μｍＣＭＯ析相同。这些结果证明,这项高性能、低功耗的室温０．１μｍＣＭＯＳ技术是可行的。当沟道长度小于０．１μｍ时,我们还必须重新探讨一     

Parallel algorithms for relational coarsest partition problems

Relational Coarsest Partition Problems (RCPPs) play a vital role in verifying concurrent systems. It is known that RCPPs are P-complete and hence it may not be possible to design polylog time parallel algorithms for these problems. In this paper, we present two efficient parallel algorithms for RCPP in which its associated label transition system is assumed to have m transitions and n states. The first algorithm runs in O(n^1+ϵ) time using m/n^ϵ CREW PRAM processors, for any fixed ϵ<1. This algorithm is analogous to and optimal with respect to the sequential algorithm of P.C. Kanellakis and S.A. Smolka (1990). The second algorithm runs in O(n log n) time using m/n CREW PRAM processors. This algorithm is analogous to and nearly optimal with respect to the sequential algorithm of R. Paige and R.E. Tarjan (1987)     

支持对象间关系的程序设计语言研究

在论述了面向对象技术中对象间的关系作为第一级建模概念的重要性之后,该文设计并实现了显式支持对象间关系的RCPP(relational C++)语言.它提供了显式描述对象间关系特性和语义的机制,利用关系来动态地控制对象行为的作用和传播.它的运行是通过一个转换器把RCPP代码翻译成C++代码,再经C++环境编译后,形成可执行程序而实现的.文章对RCPP语言的模型、语言提供的服务以及具体系统的描述和实现作了深入阐述.     

求解最小闭包球问题改进的SMO-型算法

研究n维空间中m个点的最小闭包球(MEB)问题。通过结合确定并删除内部点的技术到序列最小最优化(SMO)方法中,提出一种近似求解MEB问题的改进的SMO-型算法。证明了该算法具有线性收敛性。数值结果表明对于一些mn的大规模数据集,改进的算法与原算法相比速度可以提高10倍以上。尤其,当n等于100且m等于100000时,改进的SMO-型算法仅需执行8s。此外,对于n等于10000且m等于1000的大规模数据集,改进的算法也仅需执行150s。     

Minimizing Makespan in Batch Machine Scheduling

We study the scheduling of a set of n jobs, each characterized by a release (arrival) time and a processing time, for a batch processing machine capable of running at most B jobs at a time. We obtain an O(n log n)-time algorithm when B is unbounded. When there are only m distinct release times and the inputs are integers, we obtain an O(n(BR_max)^m-1(2/m)^m-3)-time algorithm where R_max is the difference between the maximum and minimum release times. When there are k distinct processing times and m release times, we obtain an O(n log m + k^k+2 B^k+1 m² log m)-time algorithm. We obtain even better algorithms for m=2 and for k=1. These algorithms improve most of the corresponding previous algorithms for the respective special cases and lead to improved approximation schemes for the general problem.     

行满秩Toeplitz型矩阵Moore-Penrose逆的快速算法

通过构造对称分块矩阵给出了秩为m的m×n阶Toeplitz型矩阵Moore-Penrose逆的快速算法。该算法计算复杂度为O（mn）+O（m²）,而由T^T（TT^T）^-1直接求解所需运算量为O（m²n）+O（m3）。数值算例表明了该快速算法的有效性。     

An optimal distributed ear decomposition algorithm withapplications to biconnectivity and outerplanarity testing

We present an asynchronous distributed algorithm to determine an ear decomposition of an arbitrary, connected, bidirectional network containing n-nodes and m-links which uses O(m) messages and which can be completed in O(n) time. Using the ear decomposition, we obtain the following results for a distributed network: 1) The distributed ear decomposition algorithm can be used to test biconnectivity, determine biconnected components, find cutpoints and bridges using O(m) messages in O(n) time. 2) The distributed ear decomposition algorithm can be used to test if a biconnected network is outerplanar using O(n) messages in O(n) time, and if the network is outerplanar, the embedding is also given using the same message and time complexity     

Least Squares Policy Evaluation Algorithms with Linear Function Approximation

We consider policy evaluation algorithms within the context of infinite-horizon dynamic programming problems with discounted cost. We focus on discrete-time dynamic systems with a large number of states, and we discuss two methods, which use simulation, temporal differences, and linear cost function approximation. The first method is a new gradient-like algorithm involving least-squares subproblems and a diminishing stepsize, which is based on the -policy iteration method of Bertsekas and Ioffe. The second method is the LSTD() algorithm recently proposed by Boyan, which for =0 coincides with the linear least-squares temporal-difference algorithm of Bradtke and Barto. At present, there is only a convergence result by Bradtke and Barto for the LSTD(0) algorithm. Here, we strengthen this result by showing the convergence of LSTD(), with probability 1, for every [0, 1].     

An Efficient Systolic Algorithm for the Longest Common Subsequence Problem

A longest common subsequence (LCS) of two strings is a common subsequence of the two strings of maximal length. The LCS problem is to find an LCS of two given strings and the length of the LCS (LLCS). In this paper, a fast linear systolic algorithm that improves on previous systolic algorithms for solving the LCS problem is presented. For two given strings of length m and n, where m n, the LLCS and an LCS can be found in m + 2n – 1 time steps. This algorithm achieves the tight lower bound of the time complexity under the situation where symbols are input sequentially to a linear array of n processors. The systolic algorithm can be modified to take only m + n steps on multicomputers by using the scatter operation.     

Efficient parallel binary search on sorted arrays, withapplications

Let A be a sorted array of n numbers and B a sorted array of m numbers, both in nondecreasing order, with n⩽m. We consider the problem of determining, for each element A(j), j=1, 2, …, n, the unique element B(i), 0⩽i⩽m, such that B(i)⩽A(j)相似文献