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.     

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

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

二阶Melnikov函数及其应用

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

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.     

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.     

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.     

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

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

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.     

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

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

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

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

The orbit space of the p-subgroup complex is contractible

We show that the quotient space of the p-subgroup complex of a finite group by the action of the group is contractible. This was conjectured by Webb. Received: June 28, 1996     

A Method for Converting a Class of Univariate Functions into d.c. Functions

D.c. functions are functions that can be expressed as the sum of a concave function and a convex function (or as the difference of two convex functions). In this paper, we extend the class of univariate functions that can be represented as d.c. functions. This expanded class is very broad including a large number of nonlinear and/or nonsmooth univariate functions. In addition, the procedure specifies explicitly the functional and numerical forms of the concave and convex functions that comprise the d.c. representation of the univariate functions. The procedure is illustrated using two numerical examples. Extensions of the conversion procedure for discontinuous univariate functions is also discussed.     

A tight upper bound for the number of intersections between two rectangular paths

The problem of finding the number of intersections between two geometric figures in the plane has been studied extensively in literature. In this paper, the geometric figure comprising a continuous rectilinear path (called rectangular path) is considered, and a tight (least) upper bound onI(P, Q), the number of intersections between two rectangular pathsP andQ, is given.Editors' Note: One of our referees has reported that the main result of this paper has recently been given independently by a Chinese researcher at the University of Science and Technology, Hefei, P. R. of China. His paper is under publication in the Chinese Science Bulletin. However, since this journal may not be easily accessible to our readers, and further the two papers are obviously independent of each other, theBIT Editors have decided to accept the present paper.     

Page usage in a quadtree index

This paper provides a characterization of the storage needs of a quadtree when used as an index to access large volumes of 2-dimensional data. It is shown that the page occupancy for data in random order approaches 33%. A precise mathematical analysis that involves a modicum of hypergeometric functions and dilogarithms, together with some computer algebra is presented.A brief survey of the analysis of storage usage in tree structures is included. The 33% ratio for quadtrees is to be compared to the figures for binary search trees (50%), tries (69%), and quadtries (46%).The research of this author was done while visiting INRIA, Rocquencourt, France under support from the Ministry of Education of Japanese Government.Work of this author was supported in part by the Basic Research Action of the E.C. under contract No. 3075 (Project ALCOM).     

Application of the Exp-function method for nonlinear differential-difference equations

In this paper, we established abundant travelling wave solutions for some nonlinear differential-difference equations. It is shown that the Exp-function method, with the help of symbolic computation, provides a very effective and powerful new method for discrete nonlinear evolution equations in mathematical physics.