在线性处理机阵列上求MCST的并行算法

本文给出一种在P个处理机线性阵列上求MCST(最小代价生成树)的并行算法,记为OLA-MCST.证明了在整个1≤P≤n范围内其时间复杂性均为O(n~2/P);特别地,当P=n时,为O(n).这是在本模型下使用n个处理机时的最优性能.     

Hypercube多处理器上图的最优算法

已知一个无向图G(V,E),|V|=n.本文在SIMD机器-Hype-rcube上提出了计算图的连通分支和最小生成树的两个最优算法.若Hypercu-be由P个处理器组成,则上述两个算法的时间复杂性都是O(n~2/p),1≤p且PlogP≤n.     

关于Vandermonde矩阵的串行与并行复杂性

为n+1阶Vandermonde矩阵,简称V阵。 本文首先给出求解相应线性代数方程组(简称V型方程组)的递推算法。算术运算总次数为O(n~2)级,接着进一步利用快速插值算法导出求V阵逆的O(n~2)算法,并分析了这两种算法的并行时间复杂性。     

二分图最大匹配问题的分布式算法

本文基于异步通讯网络,对二分图最大匹配问题,建议了两个分布式算法。其中第一个简单算法的通讯复杂性为O(n(n~2+m))、时间复杂性为 O(n~3);第二个算法的通讯复杂性为O(n~(1/2)(n~2+m))、时间复杂性为O(n~(5/2)),这里n和m分别为二分图的结点个数及边的数目。关于这一问题的分布式算法目前尚未见诸报导,这里建议的算法很可能是此问题的第一个分布式算法。     

最佳并行排列组合算法

本文给出两个新的最佳并行排列组合算法。这里所说的排列组合均指从n个元素中取m个元素的排列和组合处理。算法可运行于一种非常简单的并行计算模型上,它由k个同步运行的处理机构成,其中1≤k≤N,N为要处理的元素个数。当1≤k≤N/n,算法需O(「N/k」·h)时间。     

三角形Toeplitz系统的并行求逆算法

<正> 本文给出了规模为n的三角形Toepfitz 系统的一种并行求逆算法。该算法所需处理机的台数p=n,并行时间步数T_p=O(log_2~2n),从而速度倍数s_p=O(n/log_2n)。另外,我们对多项式快速除法也作了相应的并行处理,并给出了三角形T 矩阵逆的一个显示表达式。     

关联维数的并行求解算法

关联维数的求解是分形理论中的一个重要问题，标准算法由于其巨大的计算量，不能满足实时任务的需要，过去的改造算法集中在串行地减少求解多个关联维数时的重复计算量，并未从根本上降低O(N^2)次的向量距离计算、距离比较和求和次数，其应用范围和性能改善程度是有限的。本文给出了两个并行算法：基于PRAM模型的花费O(N^2／p logp)时间p个处理机的算法，和基于LARPBS模型的花费O(N^2p)时间p个处理机的算法。相对纯理论的PRAM算法，LARPBS算法是实际可行的，它是目前时间复杂度最低的算法，并且是最优可扩展和成长最优的。     

背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

LCS问题的一种新算法及其推广

求解LCS(Longest Common Subsequences)的通常算法,空间和时间的复杂性为O(n~2)。本文中提出的算法,空间复杂性为O(n),时间复杂性为O(n)～O(n~2),时间复杂性取决于序列中符号的分布,本算法便于并行处理及制成微处理器。 为了应用于模式识别,推广到WLCS(Weighted Longest Common Subsequences)以及LCSM(Longest Common Submatrix)。 给出了有关的定理,及算法正确性的证明。     

多队列快速排序

快速排序算法的平均时间小于所有已知的O(nlogn)排序算法。它的平均时间是O(nlogn),最坏情况为O(n~2)本文提出的算法对n个元素的排序时间为O(nlogm),其中其最佳性能为O(n)在M 16计算机上运行的结果符合文中给出的算法分析     

European Community policy and the market

Abstract This paper starts with some reflections on the policy considerations and priorities which are shaping European Commission (EC) research programmes. Then it attempts to position the current projects which seek to capitalise on information and communications technologies for learning in relation to these priorities and the apparent realities of the marketplace. It concludes that while there are grounds to be optimistic about the contribution EC programmes can make to the efficiency and standard of education and training, they are still too technology driven.     

一种自适应子融合集成多分类器方法

融合集成方法已经广泛应用在模式识别领域,然而一些基分类器实时性能稳定性较差,导致多分类器融合性能差,针对上述问题本文提出了一种新的基于多分类器的子融合集成分类器系统。该方法考虑在度量层融合层次之上通过对各类基多分类器进行动态选择,票数最多的类别作为融合系统中对特征向量识别的类别,构成一种新的自适应子融合集成分类器方法。实验表明,该方法比传统的分类器以及分类融合方法识别准确率明显更高,具有更好的鲁棒性。     

煤矿井下安全监控分站的设计及其仿真实现

为了设计一种具有低成本、低功耗、易操作、功能强且可靠性高的煤矿井下安全分站,针对煤矿安全生产实际,文章提出了采用MCS-51系列单片机为核心、具有CAN总线通信接口的煤矿井下安全监控分站的设计方案;首先给出煤矿井下安全监控分站的整体构架设计,然后着重阐述模拟量输入信号处理系统的设计过程,最后说明单片机最小系统及其键盘、显示、报警、通信等各个组成部分的设计;为验证设计方案的可行性与有效性,使用Proteus软件对设计内容进行仿真验证,设计的煤矿井下安全监控分站具有瓦斯、温度等模拟量参数超标报警功能和电机开停、风门开闭等开关量指示功能;仿真结果表明:设计的煤矿井下安全监控分站具有一定的实际应用价值.     

基于QTE的蒙古文显示机制研究与实现

蒙古语言是中国蒙古族使用的通用语言,由于蒙古文区别于其他文字的书写方式和其自身变形机制等特点,在很多通用的文字处理引擎中都不被支持。在嵌入式产品开发与应用领域中Linux加QTE已经成为流行方式。该文给出了一种在QTE环境上实现基于标准Unicode的蒙古文点阵显示和变形算法, 并自定义了支持蒙古文的QTE组件,扩展了QTE功能,为在Linux加QTE方式的嵌入式体系结构中处理蒙古文提供了一种解决方法。     

基于AD9626的模拟信号采集存储卡设计

自然界的绝大部分信号都是以模拟的形式存在,因此模拟信号的采集转换存储在数字时代十分关键。文章讨论了在雷达信号处理领域基于AD9626的AD采集存储卡的设计原理、硬件结构和程序设计与芯片配置等问题,为今后相关领域的研究提供了可参考的方案。     

A human-computer interface for non-computer specialists

The COM teleconferencing system was designed to be easy to use for both beginners and people with much computer experience. A number of design choices in organizing the human-computer interface were considered very carefully. These design problems are not unique for teleconferencing applications, but will appear in many other developments of human-computer interfaces for non-computer specialists. This report discusses naming conventions, menu format, user commands, help facility and the treatment of ‘type ahead’ from the users.     

Explanation and prediction: an architecture for default and abductive reasoning

Although there are many arguments that logic is an appropriate tool for artificial intelligence, there has been a perceived problem with the monotonicity of classical logic. This paper elaborates on the idea that reasoning should be viewed as theory formation where logic tells us the consequences of our assumptions. The two activities of predicting what is expected to be true and explaining observations are considered in a simple theory formation framework. Properties of each activity are discussed, along with a number of proposals as to what should be predicted or accepted as reasonable explanations. An architecture is proposed to combine explanation and prediction into one coherent framework. Algorithms used to implement the system as well as examples from a running implementation are given.     

View-based model-driven architecture for enhancing maintainability of data access services

In modern service-oriented architectures, database access is done by a special type of services, the so-called data access services (DAS). Though, particularly in data-intensive applications, using and developing DAS are very common today, the link between the DAS and their implementation, e.g. a layer of data access objects (DAOs) encapsulating the database queries, still is not sufficiently elaborated, yet. As a result, as the number of DAS grows, finding the desired DAS for reuse and/or associated documentation can become an impossible task. In this paper we focus on bridging this gap between the DAS and their implementation by presenting a view-based, model-driven data access architecture (VMDA) managing models of the DAS, DAOs and database queries in a queryable manner. Our models support tailored views of different stakeholders and are scalable with all types of DAS implementations. In this paper we show that our view-based and model driven architecture approach can enhance software development productivity and maintainability by improving DAS documentation. Moreover, our VMDA opens a wide range of applications such as evaluating DAS usage for DAS performance optimization. Furthermore, we provide tool support and illustrate the applicability of our VMDA in a large-scale case study. Finally, we quantitatively prove that our approach performs with acceptable response times.     

Call for papers Special issue on Modeling and control technologies for civil,energy,and power systems

正The control of civil,energy,and power systems presents significant new challenges for modeling and control theory.The purpose of this special issue is to provide a forum for researchers and practical engineers to discuss the recent advances in modeling and control technology development for civil,energy,and power systems.Prospective authors are invited to submit their original contributions with the focus on theory or applications of modeling,control     

Information for Authors

正http://www.zju.edu.cn/jzus http://www.springerlink.com Aim The Journals of Zhejiang University-SCIENCE(A/B/C)are edited by the international board of distinguished Chinese and foreign scientists,and are aimed to present the latest developments and achievements in scientific research in China and overseas to the world’s scientific circles,especially to stimulate and promote academic exchange between Chinese and foreign scientists everywhere.