基于EREW的最优并行背包算法

背包问题属于著名的NP完全问题，在信息密码学领域和数论研究中具有极重要的应用。分枝限界算法对于某些背包实例的求解表现了较好的性能，但其在最坏情形下的时间复杂性为O(2^n)。Horowitz和Sahni利用分治方法，提出了著名的二表算法，算法的时间和空间复杂性被分别降至O(n2^n／2)和O(2^n／2)。虽然二表算法是迄今为止串行求解背包问题最有效的算法，但对于实践应用中维数稍大的问题实例，该算法仍难在合理的时间内对其求解。     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。     

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

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

一种求解背包问题的自适应算法

针对二表算法和动态二表算法求解背包问题,提出一个并行自适应算法,能用 个处理机、 的时间、 的空间求解背包问题 ,根据处理机的数目以及存储器的容量来选择参数,充分利用已有的硬件资源,以求得最快的求解速度。实验结果证明了该算法的有效性。     

背包问题的量子计算算法

背包问题属于NP完全问题,经典算法对规模为n的背包问题求解的时间复杂度为O（n²）。给出了基于固定相位的背包问题量子计算算法,证明了该算法在多解的情况下,能够以不低于98%的成功率在O（√N/M）步完成对规模为n的背包问题求解（M是解的数目）,而基于原始Grover算法的背包问题量子计算算法计算复杂度为O（√N/M）,成功率是50%～100%。     

一种求解背包问题的改进遗传算法

背包问题是计算机算法研究中NP完备类的一个困难问题．使用传统的优化方法在求解较大规模的背包问题时．都存在计算量大、迭代时间长的缺陷。为了克服传统优化方法的不足,提高求解的速度和精度,将人类繁育方式引入遗传算法中,形成一种求解背包问题的改进遗传算法（IGA）。介绍算法的基本思想以及使用该算法求解背包问题的方法．并通过实例证明该方法的可行性和有效性。     

基于分治的背包问题DNA计算机算法

如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数,已成为DNA计算机研究的重要内容.将分治策略应用于背包问题的DNA分子计算中,提出一种求解背包问题的新的DNA计算机算法.算法由n位并行减法器、n位数据搜索器和其他4个子算法组成.算法的DNA链数可达到亚指数的O(2\\+\\{q/2\\}),其中q为背包问题的维数.与最近文献结论进行的对比分析表明：算法将求解背包问题所需的DNA链数从O(2\\+q)减少至O(2\\+\\{q/2\\}),最大链长度减少为原来的1/2,因此,理论上新算法在试管级水平上能将可破解的背包公钥的维数从60提高到120.     

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

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

高维空间球集覆盖问题的改进1+ε近似算法

高维空间球集的覆盖问题是指对高维空间中多个球构成的集合S,构造一个直径最小的球来覆盖S中所有已知球。本文提出了球集直径的概念,给出求解球集直径的1/3~(1/2)近似算法。基于此算法求解球集实例集合S的初始核心集,进而给出高维空间球集覆盖问题的1+ε近似算法,算法时间复杂度为O(nd/ε+d2/ε3/2(1/ε+d)lg1/ε)。算法保证核心集中球的个数为O(1/ε),与S中球的个数和空间维数无关。     

子集和问题的改进算法

Due to the importance of the subset sum problem in cryptosystem,in the past two decade,much ellort has been done in order to find techniques that could lead to practical algorithms with reasonable running time. Based on the two-list four-table algorithm ,this paper proposes an improved algorithm for the solution of subset sum problem. To find a solution for the n-element subset problem,the proposed algorithm needs O(2^n/2-g) memory,1≤ε≤n/4,and in O(ε(2^n/2)) time. The theoretic analysis and the computational experiments show that our proposed algorithm can solve the subset problem instances that can‘t be solved before ,thus it is an improved result over the past researches.     

Only connect: teaching, technology and telesis

Abstract This paper describes an approach to the design of interactive multimedia materials being developed in a European Community project. The developmental process is seen as a dialogue between technologists and teachers. This dialogue is often problematic because of the differences in training, experience and culture between them. Conditions needed for fruitful dialogue are described and the generic model for learning design used in the project is explained.     

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.     

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

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

Avoiding semantic and temporal gaps in developing software intensive systems

Development of software intensive systems (systems) in practice involves a series of self-contained phases for the lifecycle of a system. Semantic and temporal gaps, which occur among phases and among developer disciplines within and across phases, hinder the ongoing development of a system because of the interdependencies among phases and among disciplines. Such gaps are magnified among systems that are developed at different times by different development teams, which may limit reuse of artifacts of systems development and interoperability among the systems. This article discusses such gaps and a systems development process for avoiding them.     

Designing economic np control charts: A programmed simulation approach

This paper presents control charts models and the necessary simulation software for the location of economic values of the control parameters. The simulation program is written in FORTRAN, requires only 10K of main storage, and can run on most mini and micro computers. Two models are presented - one describes the process when it is operating at full capacity and the other when the process is operating under capacity. The models allow the product quality to deteriorate to a further level before an existing out-of-control state is detected, and they can also be used in situations where no prior knowledge exists of the out-of-control causes and the resulting proportion defectives.     

The development of robot art

Going through a few examples of robot artists who are recognized worldwide, we try to analyze the deepest meaning of what is called “robot art” and the related art field definition. We also try to highlight its well-marked borders, such as kinetic sculptures, kinetic art, cyber art, and cyberpunk. A brief excursion into the importance of the context, the message, and its semiotics is also provided, case by case, together with a few hints on the history of this discipline in the light of an artistic perspective. Therefore, the aim of this article is to try to summarize the main characteristics that might classify robot art as a unique and innovative discipline, and to track down some of the principles by which a robotic artifact can or cannot be considered an art piece in terms of social, cultural, and strictly artistic interest. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

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.