Toeplitz矩阵,Hankel矩阵求逆的固有复杂度

对于一类问题P,如果能找到一个算法(对串行计算而言)其计算复杂性为f_1(u),则称f_1(n)为问题P固有复杂度的上界,若问题P的所有算法(对串行计算而言)其计算复杂性不小于f_2(n),则称f_2(u)为问题P固有复杂度下界.问题P的固有复杂度介于上     

基于Kronecker型替换的黑盒多项式稀疏插值

本文基于新的Kronecker型替换,给出两个由黑盒表示的稀疏多项式的新确定性插值算法.令f∈R[x1,……,xn]是一个稀疏黑盒多项式,其次数上界为D.当R是C或者是有限域时,相对于已有算法,新算法具有更好的计算复杂度或者关于D的复杂度更低.特别地,对于一般黑盒模型,D是复杂度中的主要因素,而在所有的确定性算法中,本文的第二个算法的复杂度关于D是最低的.     

ω-范畴完全理论的特征

在一阶理论的型中建立了拓扑空间,证明了该拓扑空间的基本性质;利用上述性质,证明了ω－范畴完全理论的新特征。     

完全二叉树模型中元素的CB秩

本文以完全二叉树理论的可量词消去为基础,介绍了该理论的可数原子模型 及饱和模型,并计算了一元、二元完全型的CB秩,从而给出了CB秩在该理论中的 几何解释.     

完全二叉树模型中元素的CB秩

本文以完全二叉树理论的可量词消去为基础,介绍了该理论的可数原子模型 及饱和模型,并计算了一元、二元完全型的CB秩,从而给出了CB秩在该理论中的 几何解释.     

优化算法的复杂度分析

优化算法的收敛性分析是优化中很重要的一个领域,然而收敛性并不足以作为比较不同算法效率的标准,因此需要另外一套衡量优化问题难易程度以及优化算法效率高低的理论,这套理论被称为优化算法的复杂度分析理论.本文共分为5个部分.第1节介绍复杂度分析的背景和理论框架,给出复杂度分析的定义、方法和例子,并总结本文中的复杂度结论.第2节介绍光滑优化问题的复杂度分析,给出不同优化问题的复杂度上界和下界,并给出加速梯度法收敛性分析的框架.第3节介绍非光滑优化问题的复杂度上界,介绍次梯度法、重心法、椭球法和近似点梯度法的复杂度分析.第4节介绍条件梯度法的复杂度分析,介绍条件梯度法的复杂度上界和下界,以及加速条件梯度法的框架.第5节介绍随机优化算法的复杂度分析,比较随机优化算法在凸和非凸问题下收敛的置信水平和复杂度.     

两字母代换序列复杂度的计算 献给余家荣教授100华诞

两字母代换序列的复杂度的计算对于等长代换已经解决,然而非等长代换的复杂度计算要复杂得多,此前并没有完全解决.本文讨论一般的可不等长的两字母代换,通过研究几种类型的特殊词,证明只需计算出一些初始值,复杂度可用相应特征多项式的递归公式完全表示出来.     

四阶不完全对称张量M-特征值的新包含域及应用

四阶不完全对称张量的M-特征值在非线性弹性材料分析中有着广泛的应用.本文的目的是给出四阶不完全对称张量M-特征值的新包含域,得到最大M-特征值上界更精确的估计,并将得到的上界估计值应用到计算最大M-特征值的WQZ算法中,数值例子验证了结果的有效性.最后,基于得到的包含域,给出了四阶不完全对称张量正定性判定的充分条件.     

树图对完全图的多色Ramsey数

首先证明了关于一般图的多色Ramsey数的一个下界,该下界是一类星图对完全图的多色Ramsey数的精确下界;其次证明了关于星图对完全图的多色Ramsey数的上界,该上界是一类星图对完全图的多色RamSey数的精确上界;最后证明关于树图对完全图的多色Ramsey数的上界.     

采用二叉树编码的遗传算法实现数据拟合

针对采用数值分析方法进行数据拟合求解复杂度高、运算最大而精度较低的缺陷 ,本文给出一种基于二叉树编码的遗传算法来进行数据拟合 ,取得了较好的效果     

On the complexity of online computations of real functions

A reasonable computational complexity theory for real functions is obtained by using the modified infinite binary representation with digits 0, l, and −1 for the real numbers and Turing machines which transform with one-way output modified binary input sequences into modified binary output sequences. As the main result of this paper it is shown that there is a trade-off between the input lookahead, i.e., the deviation of online computation and the computational complexity for machines computing certain real functions.     

A note on the cubical dimension of new classes of binary trees

The cubical dimension of a graph G is the smallest dimension of a hypercube into which G is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with 2 ⁿ vertices, n ? 1, is n. The 2-rooted complete binary tree of depth n is obtained from two copies of the complete binary tree of depth n by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice a 2-rooted complete binary tree and prove that every such balanced tree satisfies the conjecture of Havel.     

Remembering Ervin Fried and Jiří Sichler

In this paper, we exhibit a relation algebra reduct of any diagonal-free cylindric algebra of dimension 3 having sufficiently strong projection and equality parameters. We also offer a complete (and corrected) proof that full first-order logic can be formalized in the calculus of binary relations (a result due to Maddux and Tarski). Finally, we use these constructions to recursively define a translation function from the sentences of first-order logic to the equational theory of Df₃, which preserves validity.     

Choice functions and well-orderings over the infinite binary tree

We give a new proof showing that it is not possible to define in monadic second-order logic (MSO) a choice function on the infinite binary tree. This result was first obtained by Gurevich and Shelah using set theoretical arguments. Our proof is much simpler and only uses basic tools from automata theory. We show how the result can be used to prove the inherent ambiguity of languages of infinite trees. In a second part we strengthen the result of the non-existence of an MSO-definable well-founded order on the infinite binary tree by showing that every infinite binary tree with a well-founded order has an undecidable MSO-theory.     

Minimum average congestion of enhanced and augmented hypercubes into complete binary trees

We study the embedding problem of enhanced and augmented hypercubes into complete binary trees. Using tree traversal techniques, we compute the minimum average edge congestion of enhanced and augmented hypercubes into complete binary trees.     

Invariant subsets of scattered trees and the tree alternative property of Bonato and Tardif

A tree is scattered if it does not contain a subdivision of the complete binary tree as a subtree. We show that every scattered tree contains a vertex, an edge, or a set of at most two ends preserved by every embedding of T. This extends results of Halin, Polat and Sabidussi. Calling two trees equimorphic if each embeds in the other, we then prove that either every tree that is equimorphic to a scattered tree T is isomorphic to T, or there are infinitely many pairwise non-isomorphic trees which are equimorphic to T. This proves the tree alternative conjecture of Bonato and Tardif for scattered trees, and a conjecture of Tyomkyn for locally finite scattered trees.     

完全二叉树的量词消去

量词消去法已经成为计算机科学和代数模型论中最有力的研究工具之一.本 文针对完全二叉树理论所独有的特性,给出了它的基本公式集,然后利用分布公式及 有限覆盖证明了完全二叉树的理论可以量词消去.     

Turing pattern formation in a predator–prey–mutualist system

In this paper, we develop a theoretical framework about spatial patterns in a three-species predator–prey–mutualist system with cross-diffusion. We concentrate on three aspects of Turing pattern formation: (1) what conditions enable the occurrence of Turing patterns? (2) what are the underlying mechanisms? (3) what are the corresponding configurations? For the first two questions, by use of the stability analysis for the positive uniform solution and the Leray–Schauder degree theory, we prove that under some conditions, the system admits at least a nonhomogeneous stationary solution. For the third question, we carry out numerical simulations for a Turing pattern, and we show that the configurations of Turing pattern are stable spotted patterns, which resemble a real ecosystem.     

Spatiotemporal dynamics of a predator-prey model incorporating a prey refuge

In this paper, we investigate the spatiotemporal dynamics of a ratio-dependent predator-prey model with cross diffusion incorporating proportion of prey refuge. First we get the critical lines of Hopf and Turing bifurcations in a spatial domain by using mathematical theory. More specifically, the exact Turing region is given in a two parameter space. Also we perform a series of numerical simulations. The obtained results reveal that this system has rich dynamics, such as spotted, stripe and labyrinth patterns which show that it is useful to use the predator-prey model to reveal the spatial dynamics in the real world.     

Bifurcations of completely integrable first-order ordinary differential equations

We consider an implicit first-order ordinary differential equation with complete integral. In [3], the authors give a generic classifications of first-order ordinary differential equations with complete integral with respect to the equivalence relation which is given by the group of point transformations. The classification problem is reduced to the classification of a certain class of divergent diagrams of mapping germs. In this paper, we give a generic classifications of bifurcations of such differential equations as an application of the Legendrian singularity theory. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 33, Suzdal Conference-2004, Part 1, 2005.