区间上非线性程序的终止性判定

分析了如下类型程序的终止性:While x∈Ω do {x:=f(x)} end.其中,x是程序变量,Ω是一个区间,f是一个连续函数.这类程序被称为区间上非线性程序.证明了上面程序不终止的必要条件是函数在区间内部或边界上有不动点.如果不动点不在区间的边界,则上述结果是充要条件.仅仅在区间边界上有不动点的情况下,对函数略加限制,也建立了相应结果.特别地,对逐段多项式连续函数程序的终止性给出了完备判定算法.     

网格多处理机的一种改进的子网分配算法

子网分配问题是指识别并分配一个空闲的、满足指定大小要求的节点机.首先,提出了网格结构中一种新的具有O(N²_a·1og₂N_a)时间复杂度的空闲子网搜索算法,它优于现有的O(N³_a)时间复杂度的搜索算法.然后,用该算法对基于保留因子的最佳匹配类子网分配算法——RF(reservation factor)算法进行了改进,得到了     

Multi-log2N交换网络的性能分析模型及控制算法

高速多平面交换网络解决了其内部冲突问题,但需要相应的路由控制算法的辅助,否则,内部冲突不能彻底解决.这是因为包在输入级路由平面的选择不够恰当,容易导致路由冲突的产生.因此,根据冲突链路集的思想,给出一种Multi-log₂N交换网络的控制算法.该算法控制分组在路由平面间的选择,不仅能够适用于RNB和SNB,还能实现单播和多播的控制,保障Multi-log₂N完全实现无阻塞.另一方面,Multi-log₂N消除了内部的链路冲突,提高了交换速率,但对其交换性能缺乏系统的理论分析.给出一种基于嵌入式马尔可夫链的分析模型,对Multi-log₂N网络中队列的使用及分组在队列中的平均等待时间、平均队长等相关性能指标进行了系统的分析,为基于Multi-log₂N的光交换节点的设计提供了良好的理论依据.     

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2ⁿ个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2^n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.     

用擂台赛法则构造多目标Pareto最优解集的方法

针对多目标进化的特点,提出了用擂台赛法则(arena's principle,简称AP)构造多目标Pareto最优解集的方法,论证了构造方法的正确性,分析了其时间复杂度为O(rmN)(0＜m/N＜1).理论上,当AP与Deb的算法以及Jensen的算法比较时(它们的时间复杂度分别为O(rN²)和O(Nlog^(r-1)N)),AP优于Deb的算法;当目标数r较大时(如r≥5),AP优于Jensen的算法;此外,当m/N较小时(如m/N≤50%),AP的效率与其他两种算法比较具有优势.对比实验结果表明,AP具有比其他两种算法更好的CPU时间效率.在应用中,AP可以被集成到任何基于Pareto的MOEA中,并能在较大程度上提高MOEA的运行效率.     

一类有限域丢番图方程的解及其应用

对一类有限域线性丢番图方程c≡x+by(mod N)进行了研究,求出了其通解及域中有效解的对数,并证明其能将部分曲线密码方案求解用户私钥的计算量降低为N/z, z为子群<-b>的最小非零元.指出了5个应用该类型方程曲线密码方案,最后以一个环Z_n上广义圆锥曲线多重数字签名方案私钥的求解为例进行说明.     

面向时序数据的矩阵分解

研究一类特殊的矩阵分解问题:对由多个对象在一组连续时间点上产生的数据构成的矩阵R,寻求把它近似地分解为两个低秩矩阵U和V的乘积,即R≈U^T×V.有为数众多的时间序列分析问题都可归结为所研究问题的求解,如金融数据矩阵的因子分析、缺失交通流数据的估计等.提出了该问题的概率图模型,进而由此导出了其约束优化模型,最终给出了模型的求解算法.在不同的数据集上进行实验验证了该模型的有效性.     

一类基于混沌函数的分组密码的安全性评估

评估了一类基于混沌函数的分组密码(generalized Feistel structure,简称GFS)抵抗差分密码分析和线性密码分析的能力.如果轮函数是双射且它的最大差分特征概率和线性逼近概率分别是p和q,则r轮GFS的最大差分特征和线性逼近的概率分别以p^r-1和q^r-1为其上界.     

一种基于图像灰度的快速匹配算法

在图像模板匹配问题中,基于像素灰度值的相关算法尽管已经十分普遍,并得到广泛的应用,但目前此类算法都还存在有时间复杂度高、对图像亮度与尺寸变化敏感等缺点.为了克服这些缺点,提出一种新的基于图像灰度值的编码表示方法.这种方法将图像分割为一定大小的方块(称为R-块),计算每个R-块图像的总灰度值,并根据它与相邻R-块灰度值的排序关系进行编码.然后通过各个R-块编码值的比较,实现图像与模板的匹配新算法中各个R-块编码的计算十分简单;匹配过程只要对编码值进行相等比较,而且可以采用快速的比较算法新算法对像素灰度的变化与噪声具有鲁棒性,其时间复杂度是O(M²log(N)).实验结果表明,新算法比现有的灰度相关算法的计算时间快了两个数量级.     

一个基于抽象解释的部分演绎过程

本文提出一种新的基于抽象解释的逻辑程序部分演绎方法．在一遍预处理里，针对给定的程序Ｐ和目标Ｇ，同时进行Ｐ∪｛Ｇ｝的部分演绎和抽象解释，以抽象解释控制部分演绎的展开过程．只要抽象论域是有穷的，部分演绎必定终止，而且Ｐ＇带有抽象解释估算出的关于其运行性质的信息，便于对Ｐ作进一步优化．     

Example‐based Authoring of Procedural Modeling Programs with Structural and Continuous Variability

Procedural models are a powerful tool for quickly creating a variety of computer graphics content. However, authoring them is challenging, requiring both programming and artistic expertise. In this paper, we present a method for learning procedural models from a small number of example objects. We focus on the modular design setting, where objects are constructed from a common library of parts. Our procedural representation is a probabilistic program that models both the discrete, hierarchical structure of the examples as well as the continuous variability in their spatial arrangements of parts. We develop an algorithm for learning such programs from examples, using combinatorial search over program structures and variational inference to estimate continuous program parameters. We evaluate our method by demonstrating its ability to learn programs from examples of ornamental designs, spaceships, space stations, and castles. Experiments suggest that our learned programs can reliably generate a variety of new objects that are perceptually indistinguishable from hand‐crafted examples.     

The stochastic finite-element method

A generic stochastic finite-element method for modeling structures is proposed as a means to analyze and design structures in a probabilistic framework. Stochastic differential and difference equation theory is applied in structures discretized with the finite-element methodology.Transient structural loads, idealized as stochastic processes, are incorporated into finite-element dynamic models with uncertain parameters. An estimate of the probability of failure based on known and established procedures in second-moment reliability analysis can be made with the aid of a transformation to gaussian space of the random variables that define structural reliability.The stochastic finite-element method will facilitate the use of probabilistic mathematical structural models for structural code development or design of important structures. It will also permit better estimation of structural reliability, which, when combined with risk analysis, could lead to improved decision-making processes.     

Proofs of randomized algorithms in Coq

Randomized algorithms are widely used for finding efficiently approximated solutions to complex problems, for instance primality testing and for obtaining good average behavior. Proving properties of such algorithms requires subtle reasoning both on algorithmic and probabilistic aspects of programs. Thus, providing tools for the mechanization of reasoning is an important issue. This paper presents a new method for proving properties of randomized algorithms in a proof assistant based on higher-order logic. It is based on the monadic interpretation of randomized programs as probabilistic distributions (Giry, Ramsey and Pfeffer). It does not require the definition of an operational semantics for the language nor the development of a complex formalization of measure theory. Instead it uses functional and algebraic properties of unit interval. Using this model, we show the validity of general rules for estimating the probability for a randomized algorithm to satisfy specified properties. This approach addresses only discrete distributions and gives rules for analyzing general recursive functions.We apply this theory to the formal proof of a program implementing a Bernoulli distribution from a coin flip and to the (partial) termination of several programs. All the theories and results presented in this paper have been fully formalized and proved in the Coq proof assistant.     

Uncertain inheritance and recognition as probabilistic default reasoning

This paper proposes probabilistic default reasoning as a suitable approach to uncertain inheritance and recognition for fuzzy and uncertain object-oriented models. The uncertainty is due to the uncertain membership of an object to a class and/or the uncertain applicability of a property, i.e., an attribute or a method, to a class. First, we introduce a logic-based uncertain object-oriented model where uncertain membership and applicability are measured by support pairs, which are lower and upper bounds on probability. The probability for a property being applicable to a class is interpreted as the conditional probability of the property being applicable to an object given that the object is a member of the class. Each uncertainty applicable property is then a default probabilistic logic rule, which is defeasible. In order to reduce the computational complexity of general probabilistic default reasoning, we propose to use Jeffrey's rule for a weaker notion of consistency and for local inference, then apply them to uncertain inheritance of attributes and methods. Using the same approach but with inverse Jeffrey's rule, uncertain recognition as probabilistic default reasoning is also presented. © 2001 John Wiley & Sons, Inc.     

Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms

This article presents an overview of Probabilistic Automata (PA) and discrete Hidden Markov Models (HMMs), and aims at clarifying the links between them. The first part of this work concentrates on probability distributions generated by these models. Necessary and sufficient conditions for an automaton to define a probabilistic language are detailed. It is proved that probabilistic deterministic automata (PDFA) form a proper subclass of probabilistic non-deterministic automata (PNFA). Two families of equivalent models are described next. On one hand, HMMs and PNFA with no final probabilities generate distributions over complete finite prefix-free sets. On the other hand, HMMs with final probabilities and probabilistic automata generate distributions over strings of finite length. The second part of this article presents several learning models, which formalize the problem of PA induction or, equivalently, the problem of HMM topology induction and parameter estimation. These learning models include the PAC and identification with probability 1 frameworks. Links with Bayesian learning are also discussed. The last part of this article presents an overview of induction algorithms for PA or HMMs using state merging, state splitting, parameter pruning and error-correcting techniques.     

广义量子Loop程序初探

在经典计算中,Loop程序是非常重要的程序。对量子计算中Loop程序进行研究非常必要。定义了体为量子运算的广义量子Loop程序,给出了量子Loop程序在输入态上终止,几乎终止以及不终止的定义基于任意的初始态。并证明了量子Loop程序在给定输入态上终止的充要条件以及程序终止的充要条件。作为应用,验证了体为酉运算的量子Loop程序嵌套是一个广义的量子Loop程序。     

单分支线性约束循环程序的终止性分析

秩函数法是循环终止性分析的主要方法,秩函数的存在表明了循环程序是可终止的.针对单分支线性约束循环程序,提出一种方法对此类循环的终止性进行分析.基于增函数法向空间的计算,该方法将原程序空间上的秩函数计算问题归结为其子空间上的秩函数计算问题.实验结果表明,该方法能有效验证现有文献中大部分循环程序的终止性.     

可燃气云爆炸事故后果的概率分析

对事故后果进行分析．是安全评价的重要内容。可燃气体泄漏后发生蒸气云爆炸是一种重要的事故类型,由于人们对事故后果认识的局限、环境的影响、以及事故发展过程的复杂性,VCE后果分析中许多参数未能准确定义,部份输入参数取值具有随机性,不同取值使最终的分析结果相差很大。本文提出了一种事故后果的概率分析方法。通过事故的后果(死亡半径)及其发生的概率来反映后果严重程度,并基于蒙特卡罗模拟方法来计算事故后果的发生概率。本文对给定发生概率时如何确定死亡半径也进行了分析,采用基于支持向量机(SVM)的非线性回归估计方法对死亡半径进行估计。分析了VCE后果分析模型中的随机性参数及其取值,结合具体的应用实例,说明了该方法在LPG储罐蒸气云爆炸后果分析中的应用。     

Bayesian population decoding of motor cortical activity using a Kalman filter

Effective neural motor prostheses require a method for decoding neural activity representing desired movement. In particular, the accurate reconstruction of a continuous motion signal is necessary for the control of devices such as computer cursors, robots, or a patient's own paralyzed limbs. For such applications, we developed a real-time system that uses Bayesian inference techniques to estimate hand motion from the firing rates of multiple neurons. In this study, we used recordings that were previously made in the arm area of primary motor cortex in awake behaving monkeys using a chronically implanted multielectrode microarray. Bayesian inference involves computing the posterior probability of the hand motion conditioned on a sequence of observed firing rates; this is formulated in terms of the product of a likelihood and a prior. The likelihood term models the probability of firing rates given a particular hand motion. We found that a linear gaussian model could be used to approximate this likelihood and could be readily learned from a small amount of training data. The prior term defines a probabilistic model of hand kinematics and was also taken to be a linear gaussian model. Decoding was performed using a Kalman filter, which gives an efficient recursive method for Bayesian inference when the likelihood and prior are linear and gaussian. In off-line experiments, the Kalman filter reconstructions of hand trajectory were more accurate than previously reported results. The resulting decoding algorithm provides a principled probabilistic model of motor-cortical coding, decodes hand motion in real time, provides an estimate of uncertainty, and is straightforward to implement. Additionally the formulation unifies and extends previous models of neural coding while providing insights into the motor-cortical code.     

Causal independence for probability assessment and inference usingBayesian networks

A Bayesian network is a probabilistic representation for uncertain relationships, which has proven to be useful for modeling real-world problems. When there are many potential causes of a given effect, however, both probability assessment and inference using a Bayesian network can be difficult. In this paper, we describe causal independence, a collection of conditional independence assertions and functional relationships that are often appropriate to apply to the representation of the uncertain interactions between causes and effect. We show how the use of causal independence in a Bayesian network can greatly simplify probability assessment as well as probabilistic inference