有中断时间代价的一致并行机抢先调度问题

提出了一种具有中断时间代价的抢先调度问题(P|ptmn(δ)|C_max):在抢先调度中,一个任务发生一次中断,其总的执行时间会增加一个δ.该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.证明了这是一个NP-hard问题,给出了一个时间复杂度为O(nlogn+m)的脱线近似算法LPT-Wrap,其近似比小于等于1.40825,并分析了P|ptmn(δ)|C_max的在线特性,给出一个线性时间复杂度的在线近似算法,其竞争比为2.     

一种δ-度约束的自组网成簇算法

简单地描述了自组网的特点,分析了不相交簇、重叠簇和混合簇。对相关工作进行了比较．为了保持拓扑稳定,提出了一个基于时间因素的δ-度定义．在此基础上,提出了一个基于δ-度约束的混合簇的成簇策略(δ-DHCA)．混合簇的成簇问题可以归结为找一个最大独立集问题,而找一个最大独立集问题是一个著名的NP-难问题．提出了一个近似解法,给出了算法的正确性证明．解析性能评价和仿真结果均表明,该方法的性能优于最高节点度成簇算法HD和最低标识符成簇算法LCC．     

被动测试中观察者放置问题

在被动测试中如何放置观察者使得放置的数目最少并且能监视整个网络的运行情况是一个很有实际应用价值的问题．先证明了该问题是一个NP完全问题;接着讨论了在网络拓扑是树的特殊情形下该问题的解,并给出了针对树结构的一个线性时间算法;然后在一个已有的近似比为2的算法基础上给出了一个改进算法并证明了其近似比为2—O（1）,最后用实验来验证了改进算法的有效性,指明了进一步的研究方向．     

任意处理时间的多处理机任务调度近似算法

研究多处理机任务调度模型P_mfixC_max,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法。在E.Bampis等人提出的Split-Round技术基础上,提出了该问题的一个改进的多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为2(2m)^-2,优于E.Bampis等人给出的3m^-2的结果。     

MapReduce框架下一种负载均衡的Top-k连接查询算法

针对传统Top-k连接查询算法在处理海量数据时的时效问题,提出一种基于MapReduce框架的负载均衡的并行Top-k连接查询算法(P-TKJ)。使用直方图形式来存储数据,有助于提高CPU的利用率。同时融入了提前终止策略和磁盘数据的选择性访问,以便提高对HDFS数据访问的性能。另外,提出了一种基于最长处理时间优先(LPT)算法的负载均衡策略来均衡Reduce任务,以此设计出高效的并行Top-k连接算法。一个集群实验结果表明,该方法能够有效缩短算法的执行时间。     

线性网络上分布式任务调度算法

针对一种已有的分布式计算理论模型(单位长度的任务由处理器独立产生，没有全局控制，彼此通信需要花费时间)，研究了在线性网络上的任务有效调度问题．通过考虑算法中任务处理时间和通信时间之间的平衡，给出了一个近似比为5．88的分布式算法，该算法无需全局信息，且处理策略简单．对该问题的近似比下界也做了研究，证明了该问题不存在近似比小于1．16的算法．     

嵌入式Linux实时调度算法及应用

针对Linux2.6内核在嵌入式应用中实时性不足的问题,提出了自适应实时调度算法,并应用它构建了嵌入式Linux远程图像实时监控系统.调度算法在O(1)调度性能的基础上,为实时进程增加了截止期、带宽(即利用率,执行时间与其周期的比值)等属性,设计了实时进程插入、时钟中断、实时进程接受及带宽调节等函数,实时进程的带宽、时间片可以自适应改变.实验结果表明,该算法改善了任务的中断响应时间和上下文切换时间.     

应用团划分方法改进多处理机任务近似调度

研究多处理机任务调度模型P_m|fix,p_j=1|C_max,即在m个处理机系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。这类问题在网络并行计算、多播系统及工程规划等领域都有广泛的应用,但早已被证明为NP难问题,而且也不存在常数近似算法。基于团划分方法构造了该问题的多项式时间近似算法,通过模拟实验进行了验证,和最大宽度优先（LWF）算法相比,该算法花费时间较长,近似比性能要好。     

一般图中的最小概要表示集问题

在一般图中,通常基于图的拓扑结构来刻画任意2个节点之间的相似度。基于节点相似度提出概要表示集SRS的概念,从图中寻找最少节点数的概要表示集称为最小概要表示集问题。证明了在一般图中求解最小概要表示集问题是NP (非确定性多项式)难的,不太可能存在多项式时间复杂度的精确算法。基于次模函数提出了多项式时间复杂度的贪心近似算法,用于求解最小概要表示集问题,得出近似比结果。     

单处理器最少延误问题的双逆向调度算法

单处理器最少延误问题实际上是对任务集中每一个任务如何分配执行时间使得延误任务数量最少的问题,该问题是处理器调度问题中一类重要的基础问题.本文主要对该问题的调度算法进行研究,提出了一种基于排序的双逆向分配任务执行时间的调度算法,称为双逆向调度算法,该算法时间复杂度为O(n2),通过验证该算法是可行的.另外,还对任务关系进行了分析,并提出了任务固有冲突、任务临界冲突时刻、任务时间窗口中心点、任务间接冲突、任务冲突度等概念.     

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.     

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

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

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.     

Three Process Perspectives: Organizations, Teams, and People

This paper provides the author's personal views and perspectives on software process improvement. Starting with his first work on technology assessment in IBM over 20 years ago, Watts Humphrey describes the process improvement work he has been directly involved in. This includes the development of the early process assessment methods, the original design of the CMM, and the introduction of the Personal Software Process (PSP)^SM and Team Software Process (TSP){^SM}. In addition to describing the original motivation for this work, the author also reviews many of the problems he and his associates encountered and why they solved them the way they did. He also comments on the outstanding issues and likely directions for future work. Finally, this work has built on the experiences and contributions of many people. Mr. Humphrey only describes work that he was personally involved in and he names many of the key contributors. However, so many people have been involved in this work that a full list of the important participants would be impractical.     

基于复小波噪声方差显著修正的SAR图像去噪

提出了一种基于复小波域统计建模与噪声方差估计显著性修正相结合的合成孔径雷达(Synthetic Aperture Radar,SAR)图像斑点噪声滤波方法。该方法首先通过对数变换将乘性噪声模型转化为加性噪声模型,然后对变换后的图像进行双树复小波变换(Dualtree Complex Wavelet Transform,DCWT),并对复数小波系数的统计分布进行建模。在此先验分布的基础上,通过运用贝叶斯估计方法从含噪系数中恢复原始系数,达到滤除噪声的目的。实验结果表明该方法在去除噪声的同时保留了图像的细节信息,取得了很好的降噪效果。     

How do children do mathematics with LOGO?

Abstract  This paper considers some results of a study designed to investigate the kinds of mathematical activity undertaken by children (aged between 8 and 11) as they learned to program in LOGO. A model of learning modes is proposed, which attempts to describe the ways in which children used and acquired understanding of the programming/mathematical concepts involved. The remainder of the paper is concerned with discussing the validity and limitations of the model, and its implications for further research and curriculum development.     

Editorial: Special issue on recent advances in hybrid control theory and applications

正The demands of a rapidly advancing technology for faster and more accurate controllers have always had a strong influence on the progress of automatic control theory.In recent years control problems have been arising with increasing frequency in widely different areas,which cannot be addressed using conventional control techniques.The principal reason for this is the fact that a highly competitive economy is forcing systems to operate in regimes where     

Information for Authors

正Aim The Journals of Zhejiang University-SCIENCE(A/B/C)areedited by the international board of distinguished Chinese andforeign scientists,and are aimed to present the latest devel-opments and achievements in scientific research in China andoverseas to the world’s scientific circles,especially to stimulateand promote academic exchange between Chinese and for-eign scientists everywhere.     

Enhancing a leaf radiative transfer model to estimate concentrations and in vivo specific absorption coefficients of total carotenoids and chlorophylls a and b from single-needle reflectance and transmittance

The relative concentrations of different pigments within a leaf have significant physiological and spectral consequences. Photosynthesis, light use efficiency, mass and energy exchange, and stress response are dependent on relationships among an ensemble of pigments. This ensemble also determines the visible characteristics of a leaf, which can be measured remotely and used to quantify leaf biochemistry and structure. But current remote sensing approaches are limited in their ability to resolve individual pigments. This paper focuses on the incorporation of three pigments—chlorophyll a, chlorophyll b, and total carotenoids—into the LIBERTY leaf radiative transfer model to better understand relationships between leaf biochemical, biophysical, and spectral properties.Pinus ponderosa and Pinus jeffreyi needles were collected from three sites in the California Sierra Nevada. Hemispheric single-leaf visible reflectance and transmittance and concentrations of chlorophylls a and b and total carotenoids of fresh needles were measured. These data were input to the enhanced LIBERTY model to estimate optical and biochemical properties of pine needles. The enhanced model successfully estimated reflectance (RMSE = 0.0255, BIAS = 0.00477, RMS%E = 16.7%), had variable success estimating transmittance (RMSE = 0.0442, BIAS = 0.0294, RMS%E = 181%), and generated very good estimates of carotenoid concentrations (RMSE = 2.48 µg/cm², BIAS = 0.143 µg/cm², RMS%E = 20.4%), good estimates of chlorophyll a concentrations (RMSE = 10.7 µg/cm², BIAS = − 0.992 µg/cm², RMS%E = 21.1%), and fair estimates of chlorophyll b concentrations (RMSE = 7.49 µg/cm², BIAS = − 2.12 µg/cm², RMS%E = 43.7%). Overall root mean squared errors of reflectance, transmittance, and pigment concentration estimates were lower for the three-pigment model than for the single-pigment model. The algorithm to estimate three in vivo specific absorption coefficients is robust, although estimated values are distorted by inconsistencies in model biophysics. The capacity to invert the model from single-leaf reflectance and transmittance was added to the model so it could be coupled with vegetation canopy models to estimate canopy biochemistry from remotely sensed data.     

Mr. Twinn’s bombes

This article discusses the history and design of the special versions of the bombe key-finding machines used by Britain’s Government Code & Cypher School (GC&CS) during World War II to attack the Enigma traffic of the Abwehr (the German military intelligence service). These special bombes were based on the design of their more numerous counterparts used against the traffic of the German armed services, but differed from them in important ways that highlight the adaptability of the British bombe design, and the power and flexibility of the diagonal board. Also discussed are the changes in the Abwehr indicating system that drove the development of these machines, the ingenious ways in which they were used, and some related developments involving the bombes used by the U.S. Navy’s cryptanalytic unit (OP-20-G).