基于排列图的优化广播报文算法

文章就一种特殊的图——排列图的广播算法展开讨论。首先,给出了关于排列图的一些定义。根据排列图的定义,可以知道排列图的结构具有层次性。从这一点出发,作者得出一个把排列图分成一些子图,在子图中分别广播报文的递归算法。之后,作者考虑时间复杂度和报文复杂度,得出递归算法的两点改进。最后,给出了最后的广播算法。     

Modeling of a New Telerobot

This paper deals with the modeling of a robot with a new kinematicdesign. All joint movements in this robot are transmitted via concentrictubes and bevel gears. D'Alembert's principle is used to derivethe equations of motion for rigid and elastic models, consideringthe elastic deflections of the arms and inner tubes. Implementing therecursive algorithm, both symbolical and numerical methods were tested.The advantages and problems are discussed. In order to verify the model,simulation results are compared with measurements.     

全连接回归神经网络的稳定性分析

讨论全连接回归神经网络的稳定性,具体来说,就是分析网络输入和网络权值的扰动对网络输出的影响,得到了上述扰动下,网络输出误差不累积的条件,即整个网络稳定的分析。     

Recursive algorithm and accurate computation of dyadic Green’s functions for stratified uniaxial anisotropic media

A recursive algorithm is adopted for the computation of dyadic Green＇s functions in three-dimensional stratified uniaxial anisotropic media with arbitrary number of layers. Three linear equation groups for computing the coefficients of the Sommerfeld integrals are obtained according to the continuity condition of electric and magnetic fields across the interface between different layers, which are in correspondence with the TM wave produced by a vertical unit electric dipole and the TE or TM wave produced by a horizontal unit electric dipole, respectively. All the linear equation groups can be solved via the recursive algorithm. The dyadic Green＇s functions with source point and field point being in any layer can be conveniently obtained by merely changing the position of the elements within the source term of the linear equation groups. The problem of singularities occurring in the Sommerfeld integrals is efficiently solved by deforming the integration path in the complex plane. The expression of the dyadic Green＇s functions provided by this paper is terse in form and is easy to be programmed, and it does not overflow. Theoretical analysis and numerical examples show the accuracy and effectivity of the algorithm.     

Performance analysis of stochastic gradient algorithms under weak conditions

By using the stochastic martingale theory, convergence properties of stochastic gradient （SG） identification algorithms are studied under weak conditions. The analysis indicates that the parameter estimates by the SG algorithms consistently converge to the true parameters, as long as the information vector is persistently exciting （i.e., the data product moment matrix has a bounded condition number） and that the process noises are zero mean and uncorrelated. These results remove the strict assumptions, made in existing references, that the noise variances and high-order moments exist, and the processes are stationary and ergodic and the strong persis- tent excitation condition holds. This contribution greatly relaxes the convergence conditions of stochastic gradient algorithms. The simulation results with bounded and unbounded noise variances confirm the convergence conclusions proposed.     

Approximation and universality of fuzzy Turing machines

Fuzzy Turing machines are the formal models of fuzzy algorithms or fuzzy computations. In this paper we give several different formulations of fuzzy Turing machine, which correspond to nondeterministic fuzzy Turing machine using max-＊ composition for some t-norm＊ （or NFTM＊, for short）, nondeterministic fuzzy Turing machine （or NFTM）, deterministic fuzzy Turing machine （or DFTM）, and multi-tape versions of fuzzy Turing machines. Some distinct results compared to those of ordinary Turing machines are obtained. First, it is shown that NFTM＊, NFTM, and DFTM are not necessarily equivalent in the power of recognizing fuzzy languages if the t-norm＊ does not satisfy finite generated condition, but are equivalent in the approximation sense. That is to say, we can approximate an NFTM＊ by some NFTM with any given accuracy; the related constructions are also presented. The level characterization of fuzzy recursively enumerable languages and fuzzy recursive languages are exploited by ordinary r.e. languages and recursive languages. Second, we show that universal fuzzy Turing machine exists in the approximated sense. There is a universal fuzzy Turing machine that can simulate any NFTM＊ on it with a given accuracy.     

循环赛日程表的递归和非递解

介绍了算法设计技术分治法的应用。使用分治法实现了循环赛日程表的递归和非递归解,并作了较为详细的说明,供《算法设计与分析》课程教学参考。     

A new approach to pointer analysis for assignments

Pointer analysis is a technique to identify at copile-time the potential values of the pointer expressions in a program,which promises significant benefits for optimzing and parallelizing complilers.In this paper,a new approach to pointer analysis for assignments is presented.In this approach,assignments are classified into three categories:pointer assignments,structure(union)assignents and normal assignments which don‘t affect the point-to information.Pointer analyses for these three kinds of assignments respectively make up the integrated algorithm.When analyzing a pointer assigemtn.a new method called expression expansion is used to calculate both the left targets and the right targets.The integration of recursive data structure analysis into pointer analysis is a significant originality of this paper,which uniforms the pointer analysis for heap variables and the pointer analysis for stack variables.This algorithm is implemented in Agassiz,an analyzing tool for C programs developed by Institute of Parallel Processing,Fudan University,Its accuracy and effectiveness are illustrated by experimental data.     

Constructive Membership Predicates as Index Types

In the constructive setting, membership predicates over recursive types are inhabited by terms indexing the elements that satisfy the criteria for membership. In this paper, we motivate and explore this idea in the concrete setting of lists and trees. We show that the inhabitants of membership predicates are precisely the inhabitants of a generic shape type. We show that membership of x (of type T) in structure S, (x_TS) can not, in general, index all parts of a structure S and we generalize to a form ρS where ρ is a predicate over S. Under this scheme, (λx.True)S is the set of all indexes into S, but we show that not all subsets of indexes are expressible by strictly local predicates. Accordingly, we extend our membership predicates to predicates that retain state “from above” as well as allow “looking below”. Predicates of this form are complete in the sense that they can express every subset of indexes in S. These ideas are motivated by experience programming in Nuprl's constructive type theory and examining the constructive content of mechanically checked formal proofs involving membership predicates.     

On mind &; Turing’s machines

Turing’s notion of human computability is exactly right not only for obtaining a negative solution of Hilbert’s Entscheidungsproblem that is conclusive, but also for achieving a precise characterization of formal systems that is needed for the general formulation of the incompleteness theorems. The broad intellectual context reaches back to Leibniz and requires a focus on mechanical procedures; these procedures are to be carried out by human computers without invoking higher cognitive capacities. The question whether there are strictly broader notions of effectiveness has of course been asked for both cognitive and physical processes. I address this question not in any general way, but rather by focusing on aspects of mathematical reasoning that transcend mechanical procedures.Section 1 discusses Gödel’s perspective on mechanical computability as articulated in his [193?], where he drew a dramatic conclusion from the undecidability of certain Diophantine propositions, namely, that mathematicians cannot be replaced by machines. That theme is taken up in the Gibbs Lecture of 1951; Gödel argues there in greater detail that the human mind infinitely surpasses the powers of any finite machine. An analysis of the argument is presented in Section 2 under the heading Beyond calculation. Section 3 is entitled Beyond discipline and gives Turing’s view of intelligent machinery; it is devoted to the seemingly sharp conflict between Gödel’s and Turing’s views on mind. Their deeper disagreement really concerns the nature of machines, and I’ll end with some brief remarks on (supra-) mechanical devices in Section 4.