Verification of Invertibility of Complicated Functions over Large Domains

A new method to decide the invertibility of a given high-dimensional function over a domain is presented. The problem arises in the field of verified solution of differential algebraic equations (DAEs) related to the need to perform projections of certain constraint manifolds over large domains. The question of invertibility is reduced to a verified linear algebra problem involving first partials of the function under consideration. Different from conventional approaches, the elements of the resulting matrices are Taylor models for the derivatives of the functions.The linear algebra problem is solved based on Taylor model methods, and it will be shown the method is able to decide invertibility with a conciseness that often goes substantially beyond what can be obtained with other interval methods. The theory of the approach is presented. Comparisons with three other interval-based methods are performed for practical examples, illustrating the applicability of the new method.     

Analysis of Asymptotic Average Characteristics for Non-Markovian Models of Unstable Random Access Networks

A mathematical non-Markovian model of a random access communication network is investigated asymptotically under the condition of a large delay. An ordinary differential equation is obtained, which determines the average number of calls in the source of repeat calls. Various expressions for it are found in the form of implicit functions, depending on relations between network parameters.     

Non-Markovian Models of Communication Networks with Adaptive Random Multiple Access Protocols

An adaptive random multiple access protocol for stabilizing bistable and unstable communication networks is designed. Non-Markovian models of these networks are studied. The traffic capacity of a network with a finite and infinite number of work stations, the asymptotic stationary distribution of state probabilities, and the main probabilistic-time characteristics of a network are determined.     

有界闭域上的线性赋值循环终止性分析

对有界闭域上的线性赋值循环程序终止性问题进行研究.利用Jordan 标准型技术将原循环程序的终止性问题约减为终止性等价的具有简单结构的循环程序的终止性问题.证明了当线性迭代映射满足一定条件时,该类循环程序不可终止的充分必要条件是：迭代映射在有界闭域上有不动点或周期轨.     

Non-Markovian control in the Situation Calculus

In reasoning about actions, it is commonly assumed that the dynamics of domains satisfies the Markov Property: the executability conditions and the effects of all actions are fully determined by the present state of the system. This is true in particular in Reiter's Basic Action Theories in the Situation Calculus. In this paper, we generalize Basic Action Theories by removing the Markov property restriction, making it possible to directly axiomatize actions whose effects and executability conditions may depend on past and even alternative, hypothetical situations. We then generalize Reiter's regression operator, which is the main computational mechanism used for reasoning with Basic Action Theories, so that it can be used with non-Markovian theories.     

一类论域函数的全性与极大性

该文研究L－论域上稳定函数的全性与极大性,由于全函数在计算机科学与技术中是不多见的,因此作者从降低函数全性的要求出发,转而要求函数是关于一类元素是全的,即将这类元素仍然映射成该类元素,另一方面,论域中元素间的序关系反映了元素包含信息多少的关系,因此包含尽可能多信息的元素,即极大元素是重要的一类元素,该文引入了极大类全函数,即将极大元映射成极大元的函数,重点研究极大类稳定全函数,同时关注稳定映射关于稳定序的极大性,即极大稳定函数,结果表明在一类的L－论域上,极大类稳定全函数与极大稳定函数是一致的。     

基于VBR业务模型的MANET DSR协议仿真性能分析

移动Ad Hoc网络(MANET)是由一组由移动节点组成的无线网络。MANET的性能已经被广泛的进行了研究,但是这些研究很多主要是针对节点的移动性和网络的规模来展开的。近年来,MANET在传输视频、音频、数据、图像等多媒体上的应用越来越多,因此对MANET在传输不同业务模型时的性能分析也引起了注意。本文中,我们主要研究分析了MANETDSR协议在传输VBR业务时的性能,并且将仿真结果和传输CBR业务时的结果进行了比较。通过进一步的分析,我们得出与传输VBR业务相比,在传输CBR业务时,MANET DSR协议性能明显提高。     

融合词向量和主题模型的领域实体消歧*

针对Skip-gram词向量计算模型在处理多义词时只能计算一个混合多种语义的词向量,不能对多义词不同含义进行区分的问题,文中提出融合词向量和主题模型的领域实体消歧方法.采用词向量的方法从背景文本和知识库中分别获取指称项和候选实体的向量形式,结合上下位关系领域知识库,进行上下文相似度和类别指称相似度计算,利用潜在狄利克雷分布(LDA)主题模型和Skip-gram词向量模型获取多义词不同含义的词向量表示,抽取主题领域关键词,进行领域主题关键词相似度计算.最后融合三类特征,选择相似度最高的候选实体作为最终的目标实体.实验表明,相比现有消歧方法,文中方法消歧结果更优.     

Collaborative Detection of DDoS Attacks over Multiple Network Domains

This paper presents a new distributed approach to detecting DDoS (distributed denial of services) flooding attacks at the traffic-flow level The new defense system is suitable for efficient implementation over the core networks operated by Internet service providers (ISPs). At the early stage of a DDoS attack, some traffic fluctuations are detectable at Internet routers or at the gateways of edge networks. We develop a distributed change-point detection (DCD) architecture using change aggregation trees (CAT). The idea is to detect abrupt traffic changes across multiple network domains at the earliest time. Early detection of DDoS attacks minimizes the floe cling damages to the victim systems serviced by the provider. The system is built over attack-transit routers, which work together cooperatively. Each ISP domain has a CAT server to aggregate the flooding alerts reported by the routers. CAT domain servers collaborate among themselves to make the final decision. To resolve policy conflicts at different ISP domains, a new secure infrastructure protocol (SIP) is developed to establish mutual trust or consensus. We simulated the DCD system up to 16 network domains on the Cyber Defense Technology Experimental Research (DETER) testbed, a 220-node PC cluster for Internet emulation experiments at the University of Southern California (USC) Information Science Institute. Experimental results show that four network domains are sufficient to yield a 98 percent detection accuracy with only 1 percent false-positive alarms. Based on a 2006 Internet report on autonomous system (AS) domain distribution, we prove that this DDoS defense system can scale well to cover 84 AS domains. This security coverage is wide enough to safeguard most ISP core networks from real-life DDoS flooding attacks.     

三角域上正交W系统的构造与应用

一维情形下的W系统是一类新的由分段多项式构成的混合正交函数系.文中对二维情形的W系统进行研究,利用Haar矩阵和一组规范正交的二元多项式,采用递归的方式,以及复制、平移、压缩的方法,构造出了三角域上的W系统,它是一类既包含连续函数又包含各个层次间断的非连续函数的规范正交函数系.三角域上W系统与V系统是等价的,然而W系统的构造过程较V系统更简捷.实验检测例子表明,利用文中给出的系统可以实现由多个分离曲面组成的曲面组的正交分解,从而实现对曲面组的精确重构.     

基于非马尔可夫随机Petri网的软件再生建模与分析

软件老化是影响软件系统可靠性的重要潜在因素,软件再生作为一种主动预防性的软件容错技术是解决软件老化问题的主要手段.以往的随机Petri网再生模型假定所有变迁的实施时间服从指数分布.针对变迁的实施时间服从确定性分布或一般性分布的情况,文中提出了一种用非马尔可夫随机Petri网建立软件再生模型的方法.该方法采用马尔可夫再生理论对模型进行分析,并给出模型的瞬态解和稳态解.仿真实验表明:选择合适的软件再生周期,可以有效地降低存在老化的软件系统的平均宕机成本,提高系统的可用性和可靠性.     

Affine-by-Statement Scheduling of Uniform and Affine Loop Nests over Parametric Domains

This paper deals with parallel scheduling techniques for uniform and affine loop nests. We deal with affine-by-statement scheduling, a powerful extension of Lamport′s hyperplane method where each statement within the loop nest is scheduled by a different timing function. We present a new, constructive and efficient method to determine the optimal (i.e., with smallest latency) affine-by-statement scheduling. We also consider parametric loop nests, where loop limits (in addition to being affine functions of outer loops) involve program variables whose values may not be known at compile-time (but are runtime constants). We then derive parameter-independent affine-by-statement schedules, and we show that these schedules are asymptotically as efficient as parameter-dependent solutions while much more regular. This theoretical result is of importance in practice, as regularity is a key factor for loop rewriting and code generation.     

Accelerated Simulation of the Steady-State Availability of Non-Markovian Systems

A general accelerated simulation method for evaluation of the steady-state availability of non-Markovian systems is proposed. It is applied to the investigation of a class of systems with repair. Numerical examples are given.     

软件可靠性预测中不同核函数的预测能力评估

基于核函数回归估计理论的软件可靠性预测建模引起诸多研究者的兴趣.此类研究中,核函数选择问题尤为重要.然而目前还很少有针对所给软件失效数据进行核函数选择或者构建核函数的工作.在14个常用软件失效数据集上应用配对t-检验对基于核函数理论的软件可靠性预测模型中核函数选择问题进行研究.使用的核函数回归估计方法包括核主成分回归算法、核偏最小二乘回归算法、支持向量回归算法、相关向量回归算法;核函数包括高斯核函数、线性核函数、多项式核函数、柯西核函数、拉普拉斯核函数、对称三角核函数、双曲正割核函数、平方正弦基核函数.实验结果表明:不同类型的核函数在不同数据集上表现差异较大,高斯核函数在所有数据集上表现较为稳定,预测结果最好.     

有限域上低差分函数研究进展

为了抵抗差分密码攻击,密码算法设计希望使用低差分函数.完全非线性函数(perfect nonli-near function, PN函数)、几乎完全非线性函数(almost perfect nonlinear function, APN函数)和4差分置换(differentially 4-uniform permutition)是最重要的几类低差分函数(low differential uniformity function).总结了近年来在PN函数、APN函数和4差分置换等低差分函数研究方面的主要进展.1)回顾了PN函数与半域等数学对象的联系,梳理了PN函数的已有构造以及伪平面函数的构造;2)分析了APN函数的性质与判定,总结了APN函数的已有构造以及它们之间等价性分析方面的结果;3)对于4差分置换,总结了其已有构造及其等价性分析结果;4)介绍了低差分函数在实际密码算法设计中的应用;5)对低差分函数的下一步研究进行了展望.     

学情分析系统中分析反馈功能的设计

目前,大部分院校的学情分析工作仍处于手工统计和借助Excel等办公软件的阶段,难以为有效教学提供可靠信息和科学保障。因此本文拟设计一款学情分析系统,着重给出系统数据分析和结果反馈这两大难点问题的解决思路,使系统能够有效地解决数据采集、统计分析的信息化、自动化问题,深度挖掘基础数据,实现对学情质量及时有效地监控、诊断和反馈。     

Analysis of Matrix-Convex Functions

The properties of matrix-convex functions, which may take values from an expanded numerical axis, are analyzed. Matrix convexity is specified by a pair of matrices, a final set of matrices, or an infinite family of matrices. The results obtained are used in the theory of differential games.     

A Moving Grid Finite Element Method for the Simulation of Pattern Generation by Turing Models on Growing Domains

Numerical techniques for moving meshes are many and varied. In this paper we present a novel application of a moving grid finite element method applied to biological problems related to pattern formation where the mesh movement is prescribed through a specific definition to mimic the growth that is observed in nature. Through the use of a moving grid finite element technique, we present numerical computational results illustrating how period doubling behaviour occurs as the domain doubles in size.     

Back-to-Front Ordering of Triangles in Digital Terrain Models over Regular Grids

Visiting triangles that conform a digital terrain model is a core operation in a number of fields like animation and video games or generating profiles, cross-sections, and contours in civil engineering. Performing the visit in an efficient manner is an issue specially when the output of the traversal depends in some way on additional parameters or information changing over time, for example, a moving point of view. In this work we report a set of rules that, given a digital terrain model defined over a regular grid and an arbitrary point of view outside the terrain, define a total back-to-front order in the set of digital terrain model triangles with respect to the point. The set of rules is minimal, complete and correct. To assess how the rules perform, we have implemented a CPU-based algorithm for realistically rendering height fields defined over regular grids. The algorithm does not make use of the z-buffer or shaders featured by our graphics card. We show how our algorithm is implemented and show visual results obtained from synthetic and real data. We further discuss the algorithm performance with respect to two algorithms: a naive algorithm that visits triangles according to grid indices and does not solve the hidden line problem, and the z-buffer provided by the graphics card featured by our computer. Our algorithm allows real-time interaction when the point of view arbitrarily moves in 3D space and we show that its performance is as good as that of the z-buffer graphics card.