An algebraic certificate for Budan’s theorem

The existing algorithms to construct the real closure of an ordered field involve very high complexities. These algorithms are based on Sturm’s theorem which we suspect to be one reason for the complexities since all known proofs of Sturm’s theorem use Rolle’s theorem which is problematic in a constructive context.Therefore we propose to replace the use of Sturm’s theorem by Budan’s theorem. In this paper we present as a first step in this direction an algebraic certificate for Budan’s theorem. An algebraic certificate is a certain kind of proof of a statement. In particular, it is an algorithm which produces, from an arbitrary data in the premise of the statement, explicit (in)equalities which express the conclusion.     

关于Fuzzy度量点式刻画的一点注记

本文中重新定义由一个点式Ｆｕｚｚｙｐ．ｑ．度量ｄ所诱导的Ｆｕｚｚｙｐ．ｑ．度量｛Ｄｒ｜ｒ＞０｝（代替［１］中的相关重域映射族）．在新的定义下，点式Ｆｕｚｚｙｐ．ｑ．（ｐ．）度量与Ｆｕｚｚｙｐ．ｐ．（ｐ．）度量之间有令人满意的──对应关系．     

Evaluations of Parameters for the Optimization of S.S.O.R. and A.D.I. Preconditioning

The main goal of this paper is to give two ways to estimate the needed parameters in order to obtain the condition number of S.S.O.R. preconditioned matrices, namely, the algebraic matricial formulation of convexity Riesz theorem and the tridiagonal Fourier analysis. The improvement with respect to Axelsson's approach is explicitly given. Estimations of the condition number in the case of A.D.I. preconditioning is also considered.     

A Geometrical Proof of Shiota's Theorem on a Conjecture of S. P. Novikov

We give a new proof of Shiota's theorem on Novikov's consecture, which states that the K.P. equation characters Jacobians among all indecomposable principally polarized abelian varieties.     

AHP在师范院校毕业生质量评价中的应用

陶凤梅，杨启昌．ＡＨＰ在师范院校毕业生质量评价中的应用．数理统计与管理，１９９８，１７（４），４～９．本文介绍了运用带概率条件的层次分析法确定师范院校毕业生质量综合评价中各评价指标重要度的方法，建立了师范院校毕业生质量综合评价层次结构     

Approximation of the eigenvalues of a fourth order differential equation with non-smooth coefficients

The eigenvalues of a fourth order, generalized eigenvalue problem in one dimension, with non-smooth coefficients are approximated by a finite element method, introduced in an earlier work by the author and A. Lutoborski, in the context of a similar source problem with non-smooth coefficients. Error estimates for the approximate eigenvalues and eigenvectors are obtained, showing a better performance of this method, when applied to eigenvalue approximation, compared to a standard finite element method with arbitrary mesh.     

二阶Melnikov函数及其应用

在Ｍｅｌｎｉｋｏｖ函数的种种应用中，目前常见到的仅是一阶形式。本文具体推导了二阶Ｍｅｌｎｉｋｏｖ函数的分析表达，提出了临界情况下考察双曲鞍点的稳定流形与不稳定流形相对位置的二阶判据，并成功地用于环面ｖａｎｄｅｒＰｏｌ方程的研究中。     

一类非拟Newton算法及其收敛性

本文对求解无约束最优化问题提出一类非拟Ｎｅｗｔｏｎ算法，此方法同样具有二次终止性，产生的矩阵序列保持正定对称传递性，并证明了新类中的任何一种算法的全局收敛和超线性收敛性。     

时间随机环境中一维紧邻随机游动的常返性质

设环境q={q(n)}∞0是取值于[0,1]上一列独立同分布的随机变量列,且Eq(0)=p;{Sn}∞0是随机环境q中取整数值随机游动,S0=0,且满足:对任意的整数xi(i≥0),x,y,P(Sn+1=y|S1=x1,…,Sn-1=xn-1,Sn=x,q)={q(n),y=x+1,1-q(n),y=x-1,0,其他.我们证明了:p>1/2时,Sn→+∞,a.e.,n→∞;p<1/2时,Sn→-∞,a.e.,n→∞;p=1/2时,-∞=(lim infSn)/(n→+∞)<(lim supSn)/(n→+∞)=+∞,a.e.,n→∞.     

关于图的导出森林独立系统

本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图G的导出森林独立系统是拟阵当且仅当G是块森林.文中同时给出了在强弦图上求最大导出森林的多项式算法.     

Optimal dynamic multi-attribute hashing for range queries

This paper examines a partial match retrieval scheme which supports range queries for highly dynamic databases. The scheme relies on order preserving multi-attribute hashing. In general, designing optimal indexes is NP-hard. Greedy algorithms used to determine the optimal indexes for simple partial match queries are not directly applicable because there are a larger number of queries to consider in determining the optimal indexes. In this paper we present heuristic algorithms which provide near-optimal solutions. The optimisation scheme we propose can be used to design other dynamic file structures such as the grid file, BANG file and multilevel grid file to further enhance their retrieval performance taking into consideration the query distribution.     

Performance bounds on multiprocessor scheduling strategies for statically allocated programs

In multiprocessors with static allocation of processes to processors, scheduling can be done locally for each processor. The scheduling strategy may have dramatic effect on the execution time of a parallel program. It is an NP-hard problem to find an optimal schedule, and very little is known of how close the heuristic solutions get.The major result here is a theorem stating that if certain program parameters, which can be obtained from an execution of the program on a single-processor, are known, the execution time of the optimal schedule can be calculated within a factor equal to the largest number of border processes on one processor. Border processes are processes which communicate with other processors. The program parameters are obtained using a previously developed tool.Due to the generality of this theorem, the proof is rather complex because it has to cover a large range of situations. The theorem itself, however, is easy to apply, making it possible to compare the performance of different scheduling strategies with the optimal case. The proof also gives important hints on how to design efficient scheduling algorithms for statically allocated programs.     

AHP最小二乘排序方法及其算法研究

本文研究AHP中的最小二乘排序方法(LSM)及其算法实现,给出了一种简单的收敛性迭代算法,并进行了理论分析和仿真运算。     

On Stable Local Bases for Bivariate Polynomial Spline Spaces

Stable locally supported bases are constructed for the spaces \cal S _d ^r (\triangle) of polynomial splines of degree d≥ 3r+2 and smoothness r defined on triangulations \triangle , as well as for various superspline subspaces. In addition, we show that for r≥ 1 , in general, it is impossible to construct bases which are simultaneously stable and locally linearly independent. February 2, 2000. Date revised: November 27, 2000. Date accepted: March 7, 2001.     

The paradox of trees in type theory

We show how to represent a paradox similar to Russell's paradox in Type Theory withW-types and a type of all types, and how to use this in order to represent a fixed-point operator in such a theory. It is still open whether such a construction is possible without theW-type.This research was partly supported by ESPIRIT Basic Research Action Logical Frameworks.     

Thinking and Turing's test

The questions raised by A. M. Turing in his paper on thought and machines are discussed. Human thought is considered in turn as a concept of normal language usage, as a basic concept of psychology, and as the basis of intellectual activity. It is concluded that neither of these notions of thought identifies something specific that a human being can or cannot do. The imitation game proposed by Turing for deciding whether a machine can think is found to result from an arbitrary empoverishment of the channel of communication between the interrogator and the item under investigation. Turing's notions of thinking are shown to lead to logical difficulties. An alternative view of consciousness, that would place it beyond the reach of any finite test, is finally discussed.     

Time considered irrelevant for real-time systems

Various manifestations of the time-as-a-proxy phenomenon in specification of computing problems are considered. It is argued that unless the time-related considerations constitute an essential part of natural (physical) problems, safer specifications are obtained from avoiding short-cuts offered by introduction of time-related notions. This methodological principle is illustrated by examples from several fields: digital control and simulation, design of operator's interface and communication protocols.Dedicated to Peter Naur on the occasion of his 60th birthday