一类弱支配集问题的近似算法

支配集问题和集合覆盖问题均是图论中的经典问题,尤其是集合覆盖问题,它的近似算法在许多其他问题中均有非常多的应用,如设施选址问题、服务器的安置问题等。本文研究了支配集问题和集合覆盖问题的关系,讨论了几个弱支配集问题和弱覆盖问题、弱集合覆盖问题等,给出完全支配集问题的近似比为Inn的近似算法,分析了弱完全支配集问题的不可近似比最小规模,讨论了集合击中问题和弱集合b-覆盖问题的最小规模,同时讨论了完全支配集问题、集合d-击中等问题的不可近似性。     

支配问题的研究进展

复杂性理论中,支配问题是一类重要的问题,被广泛应用于资源分配、电话交换网络和无线传感器网络等领域。支配问题主要包括点支配集(VDS)问题和边支配集(EDS)问题两大类。人们利用动态规划、加权分治等技术对VDS和EDS问题的精确算法进行设计与分析,并通过将EDS问题转化为边覆盖集问题提出了EDS问题的近似算法。近年来对参数化支配问题做了大量研究。目前已经证明了平面图中VDS问题和一般图中EDS问题都是固定参数可解的(FPT)。利用树分解和分支搜索等技术,人们分别对平面图VDS问题和一般图EDS问题提出了一系列FPT算法。文中对VDS和EDS问题进行了分类,给出了每类问题的具体定义及其相关算法介绍,此外还对矩阵支配集问题进行了简单介绍,并提出了支配问题研究中值得关注的几个方面。     

MSP问题NP完全性研究

针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。     

蚁群算法解决指派问题的研究和应用

指派问题是在生产和生活中经常出现的问题。本文建立了指派问题的数学模型,对现有的解决指派问题的蚁群算法进行了分析,并设计了一种改进的解决指派问题的蚁群算法,有效地提高了蚁群算法解决指派问题的准确性和效率,并通过实验结果验证了应用蚁群算法解决指派问题的可行性和先进性。     

局内问题算法的近似度

本文对局内问题算法给出了几个评估标准,对装箱问题设计了绝对性能比至多为2的局内问题算法,并用局内问题算法的近似度考察了 K 车服务问题。     

中文问答系统中问题理解的研究

对中文问答系统中的问题理解技术进行了研究。问题理解是问答系统的基础,问题理解的核心内容是问题分类。本文对基于规则和统计方法的问题分类体系做了介绍,提出了基于事件框架的问题语义描述模型,给出了疑问意向的形式化定义。同时借助知网,对问题空间的大小进行评测。     

排课表问题的闭环DNA计算模型的算法

排课表问题是NP-完全问题。基于闭环DNA计算模型引入多种生化实验得出求解排课表问题的DNA算法。本算法采用两部编码方式产生初始数据池,引入批删除实验解决了教师和班级的冲突问题和同班课问题;引入批分离实验解决了正常合班课问题和教师时间要求问题;引入电泳实验解决了排课的均衡分配问题;引入标记实验得到了排课表问题的全局最优解集,并给出了算法的生化实现过程。最后,对算法的正确性进行了证明,并讨论了算法的复杂性。     

反馈集问题的研究进展

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。     

对隐马尔科夫模型中动态编程的探讨

主要对隐马尔科夫模型中的三个问题（估计问题、译码问题、学习问题）中的译码问题作了研究．并对其应用进行了探讨。     

雷达铝合金铸件机加工典型问题探讨

该文总结了雷达产品中铝合金铸件在机加工中存在的典型问题：毛坯划线问题、热处理后精加工基准选择问题和基准变形问题。作者在分析了以上问题存在原因的基础上,结合相关企业的经验,给出了解决这些问题的工艺方法。     

A method of defuzzification based on the approach of areas' ratio

The new method of defuzzification of output parameters from the base of fuzzy rules for a Mamdani fuzzy controller is given in the paper. The peculiarity of the method is the usage of the universal equation for the area computation of the geometric shapes. During the realization of fuzzy inference linguistic terms, the structure changes from the triangular into a trapezoidal shape. That is why the universal equation is used. The method is limited and can be used only for the triangular and trapezoidal membership functions. Gaussian functions can also be used while modifying the proposed method. Traditional defuzzification models such as Middle of Maxima − MoM, First of Maxima − FoM, Last of Maxima − LoM, First of Suppport − FoS, Last of Support − LoS, Middle of Support − MoS, Center of Sums − CoS, Model of Height − MoH have a number of systematic errors: curse of dimensionality, partition of unity condition and absence of additivity. The above-mentioned methods can be seen as Center of Gravity − CoG, which has the same errors. These errors lead to the fact that accuracy of fuzzy systems decreases, because during the training root mean square error increases. One of the reasons that provokes the errors is that some of the activated fuzzy rules are excluded from the fuzzy inference. It is also possible to increase the accuracy of the fuzzy system through properties of continuity. The proposed method guarantees fulfilling of the property of continuity, as the intersection point of the adjustment linguistic terms equals 0.5 when a parametrized membership function is used. The causes of errors and a way to delete them are reviewed in the paper. The proposed method excludes errors which are inherent to the traditional and non- traditional models of defuzzification. Comparative analysis of the proposed method of defuzzification with traditional and non-traditional models shows its effectiveness.     

Ethical and legal issues for writing researchers in an age of media convergence

With the convergence of digital media into ever-widening social and technological networks for creation and distribution, the contexts for writing and the study of writing and writers have certainly changed. Researchers must navigate a dense matrix of ethical and legal issues in all phases of research when studying the ever-changing processes and products of digital communications. In this article, I draw from numerous sources to articulate a few of the challenges facing digital writing researchers in this age of convergence, focusing on issues of representation (researcher, participant, third-party), issues of informed consent, and issues of copyright and fair use.     

New debates on learning support

Abstract In the present debate on knowledge management and multimedia support of human learning, the word 'mediation' (of conduct) is often used as a natural correlate and rough equivalent to the word 'mediatisation' (of information). It is suggested that the distinction between the two words points to a basic difference between two types of processes which are crucial to a much needed rethinking of the conception and design of humanmachine interaction (HCI).
A redefinition of the 'appropriateness' of media support as the quality of the help to people's self-help rather than of direct control of their behaviour is proposed. Such a redefinition implies a radical shift of paradigm allowing for approaches to human learning as a cognitive activity in its own right. Another view of technological mediation is advocated, in keeping with some recent developments in HCI.     

HUYGENS' PRINCIPLE,PHYSICS AND COMPUTERS

We discuss the emergence of topology from a consideration of set extensions in General Systems Theory. Boundaries arise in a natural way, separating independent elements or regions of the system. Our aim is a unification of Etter theory, Kron's method of Tearing and Jessel's formulation of Huygens' Principle. This should make explicit the equivalence between the objective, structural, holographic and the subjective, relative definitions of information, sought in Bowden (1994b), reprinted in this Special Issue. It connects the abstract generalisations of Schrodinger's equation and Bom's rule derived in probabilistic Etter theory with the real world of electrical and other physical phenomena in General Physical Systems Theory. This paper can be considered as a continuation of Bowden (1990; 1994a) and as a response to Bowden (1994b), reprinted in this issue.

We review the ideas behind Kron's Method of Tearing and Jessel's Principle of Secondary sources (both special cases of the above theory) and their equivalence. We follow Hiley's argument in Hiley (1996) to show how Schrodinger's equation can be thought of as specifying the evolution of (a series of) tearings in continuous space. These can be shown on a commutative diagram as a series of similarity transforms. We compare this with Etter's derivation (Etter, 1998). We describe briefly a recently published derivation of Maxwell's equations from a non-commutative algebra and show how they fit onto a related commutative diagram. Finally we make some comments on applications of the general theory to computer systems. This paper is a series of vignettes of work in progress. It is designed to point the direction of work to come in Constructive Physics.     

An approach to the synthesis of fuzzy stabilization systems with a priori unknown model of an object

A method of synthesis of fuzzy stabilization systems for a broad class of dynamic objects under the assumption that the mathematical model of the object is not known a priori is proposed. The control is formulated in the form of a proportional law of adjustment as a function of a macro-variable; the square of the Euclidean norm of the phase variables is adopted as the macro-variable. An analogous variable characterizes the distance of the object from the equilibrium position. Despite the simplicity of the control law, its sign remains constant due to the fact that the macro-variable is positive-definite over the entire phase space. The switching times of the signals are determined by fuzzy identification of the system’s dynamic modes on the basis of measurement of the derivatives of the macro-variable.     

Forage quality of savannas — Simultaneously mapping foliar protein and polyphenols for trees and grass using hyperspectral imagery

Savanna covers about two-thirds of Africa, with forage quantity and quality being important factors determining the distribution and density of wildlife and domestic stock. Testing hypotheses about the distribution of herbivores is hampered by the absence of reliable methods for measuring the variability of vegetation quality (e.g. biochemical composition) across the landscape. It is demonstrated that hyperspectral remote sensing fills this gap by revealing simultaneously the spatial variation of foliar nitrogen (crude protein) as well as the total amount of polyphenols, in grasses and trees. For the first time, the pattern of resources important for feeding preferences in herbivores (polyphenols and nitrogen) is mapped across an extensive landscape and the modeled foliar concentrations are shown to fit with ecological knowledge of the area. We explain how estimates of nitrogen (crude protein) and polyphenols may be scaled up from point-based observations to reveal their spatial pattern, and how the variation in forage quality can influence the management of savannas, including farms, communal grazing areas, and conservation areas. It provides a glimpse of the choices herbivores must face in selecting food resources of different qualities.     

Innovative uses of ICT in Chilean schools

Abstract This paper presents some of the results of the study of seven cases of innovative pedagogical practices using ICT. The study was performed in the framework of the application of SITES M2 in Chile. The results are divided in two sections. First is a summary of each case, highlighting its innovative characteristics that serve as models of 'good practice' for Chilean teachers. Second, the results of the analysis of what teachers did are outlined; the impact on students and the type of teaching and learning activities in use. Results show that these projects did not provide evidence of having impact on students' learning as defined in the national curriculum. However, they show that students participating in these projects could learn other things, had the opportunity to develop abilities defined as cross-curricular and practised ICT related skills. The analysis of the teaching and learning activities highlights some deficiencies in the way that teachers implement new teaching strategies.     

动态规划求解中国象棋状态总数

中国象棋空间复杂度是分析中国象棋博弈难度的重要指标，中国象棋空间复杂度分析是一个计数问题，即求解中国象棋状态总数。根据中国象棋棋子的着法特征，该问题可分解为若干子问题，利用动态规划分别解决这些子问题，能够求出中国象棋状态总数的精确解。实验得出中国象棋状态总数约为7.54×10^39.88，过去许多文献描述的中国象棋状态总数是不准确的，远远高估了中国象棋状态总数。基于动态规划的计数方法也可以用于计算其他棋类的空间复杂度，也能够用于寻找空间复杂度较低的残局棋型，为构建中国象棋残局库提供依据。     

磁盘缓存管理机制研究

磁盘缓存是解决I/O性能的一种技术。文章主要讲述缓存管理组成、算法的种类及其管理策略。并对基于频率的替换算法的原理、实现方法做了详细阐述。