素数阶群理论的量词消去及复杂性

本文中我们将研究语言,上素数阶群理论Ｔ的量词消去及相应的复杂性．我们证明理论Ｔ有量词消去性质,并利用该性质给出理论Ｔ判定问题的一个复杂性上界．     

可量词消去的带根节点的树理论

讨论了带根节点r的有向树、无向树理论的量词消去性质,找到决定理论量词消去的三类特殊公式,并给出了在语言■_0={E,r}(E为有向边或无向边)及添加二元距离关系D_(n,n)w所得膨胀语言下,可量词消去的这两类理论的完全分类.     

可量词消去的树形偏序理论的分类

提出了偏序的全序片段、序模式的概念以刻画树形偏序的结构特征,以此为基础,讨论了有最小元0的树形偏序理论的量词消去性质,给出了在语言(?)_0={,0}及其膨胀语言下可以量词消去的这类理论的完全分类。     

完全二叉树的量词消去

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

图的min-max型最优消去顺序问题

文[1]从算法复杂性的估计中提出一个图的最优标号(排序)问题-顶点的最优消去问题.本文将给出若干基本的理论结果,其中包含NP-完全性、上下界、与其它目论参数的关系及特殊图结果等.     

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

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

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

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

确定线性偏微分方程组可积系统的对合特征集方法

基于Ritt-Wu特征集方法和Riquier-Janet理论,给出一种将线性微分方程组化成简单标准形式的有效算法．该算法通过消去冗余和添加可积条件获得线性微分方程组的完全可积系统(有形式幂级数解)或不相容判定．该算法不仅适用于常系数的线性偏微分方程组,而且对于变系数(以函数为系数)仍然有效．作者还给出了完全可积系统判定定理及其严格证明．     

一类广义线性多乘积问题的完全多项式时间近似算法

本文针对一类广义线性多乘积问题提出一种求其全局最优解的完全多项式时间近似算法,并给出算法的理论分析和计算复杂性,数值结果表明本文算法有效可行.     

一个解半正定规划问题的基于广义对数障碍函数的原始对偶内点算法

本文对经典对数障碍函数推广,给出了一个广义对数障碍函数.基于这个广义对数障碍函数设计了解半正定规划问题的原始-对偶内点算法.分析了该算法的复杂性,得到了一个理论迭代界,它与已有的基于经典对数障碍函数的算法的理论迭代界一致.同时,并给出了一个数值算例,阐明了函数的参数对算法运行时间的影响.     

Theories in Classical Propositional Logic and the Converse of Substitution

We study theories based on the classical propositional logic. As follows from the Sushko lemma, for any classical propositional theory T and any substitution ε (where formulas stand in place of propositional variables), the set ε−1(T) is also a classical propositional theory. In this paper, we strengthen this assertion, namely, we prove that for any consistent finitely axiomatizable classical propositional theory T there exists a substitution e such that T is the inverse image of the set of all tautologies under ε. We propose an algorithm for constructing such a substitution for a given axiom of the theory.     

基于T2FCM-FE-HMMs的隐马氏模型参数估计算法

把2型模糊集的思想引入到了基于模糊聚类的离散HMM参数训练中,提出了改进的T 2FCM-FE-HMM s算法。     

基于Shadowed Sets的连续属性离散化

基于Shadowed Sets理论研究了粗糙集连续属性离散化问题,提出一种新的基于Shadowed Sets 理论的候选断点集提取算法.该算法根据实例在单属性上的分布,对数据样本进行分类,采用Shadowed Sets计算出各类的上下近似,最终提取出候选断点集.使用多组UCI数据对此算法的性能进行检验,同时还与其它候选断点集提取算法做了对比实验.实验结果表明,此算法能有效地减少数据集候选断点的数目,提高离散化算法运行速度和识别率.     

Parallel Interior-Point Method for Linear and Quadratic Programs with Special Structure

This paper concerns the use of iterative solvers in interior-point methods for linear and quadratic programming problems. We state an adaptive termination rule for the inner iterative scheme and we prove the global convergence of the obtained algorithm, exploiting the theory developed for inexact Newton methods. This approach is promising for problems with special structure on parallel computers. We present an application on Cray T3E/256 and SGI Origin 2000/64 arising in stochastic linear programming and robust optimization, where the constraint matrix is block-angular and extremely large.     

Convergence bounds for nonlinear programming algorithms

Bounds on convergence are given for a general class of nonlinear programming algorithms. Methods in this class generate at each interation both constraint multipliers and approximate solutions such that, under certain specified assumptions, accumulation points of the multiplier and solution sequences satisfy the Fritz John or the Kuhn—Tucker optimality conditions. Under stronger assumptions, convergence bounds are derived for the sequences of approximate solution, multiplier and objective function values. The theory is applied to an interior—exterior penalty function algorithm modified to allow for inexact subproblem solutions. An entirely new convergence bound in terms of the square root of the penalty controlling parameter is given for this algorithm.     

树的补图的区间图完全化问题

一个图G的区间图完全化问题包含两类子问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G),其中侧廓问题是寻求G的一个边数最小的区间超图;路宽问题是寻求G的一个团数最小的区间超图.这两类子问题分别在数值代数、VLSI-设计和算法图论等学科领域中有重要的应用.对一般图来说,两类子问题都是NP-完全问题;但是对一些特殊图类来说,它们在多项式时间内可解.本文给出了树T的补图的具体侧廓和路宽值.     

The extrapolation of band-limited signals in L2 with sampling errors

In this paper we will provide a theory for an extrapolation algorithm of band-limited signals with sampling errors or low noises. The main result is as follows: Suppose thatf(t) is in L² and is a continuous Ω band-limited signal. Then for any positive numbers T, A(>T) and ε, there exists a δ>0 such that when the sampling errors (or noises) off(t) on [−T, T] is less than δ we can extrapolate the values off(t) on the interval [−A, A] such that the difference between the extrapolated value and the exact value off(t) does not exceed ε.     

On a matroid defined by ear-decompositions of graphs

A. Frank described in [1] an algorithm to determine the minimum number of edges in a graph G whose contraction leaves a factor-critical graph and he asked if there was an algorithm for the weighted version of the problem. We prove that the minimal critical-making edge-sets form the bases of a matroid and hence the matroid greedy algorithm gives rise to the desired algorithm.Partially supported by OTKA F014919, OTKA T17181 and OTKA T17580.     

AHP算法和三角模糊数在虚拟企业的盟员选择中的应用

虚拟企业的盟员选择是一个复杂的问题，为此本提出出一个比较新颖的算法。此算法是基于AHP算法和模糊数学理论的。它整合了企业管理的主观意愿和企业的客观情况，是一种比较全面的算法。最后以实例表明本算法能有效的支持伙伴选择。     

Conjugate-normal matrices with conjugate-normal submatrices

In studying the reduction of a complex n × n matrix A to its Hessenberg form by the Arnoldi algorithm, T. Huckle discovered that an irreducible Hessenberg normal matrix with a normal leading principal m × m submatrix, where 1 < m < n, actually is tridiagonal. We prove a similar assertion for the conjugate-normal matrices, which play the same role in the theory of unitary congruences as the conventional normal matrices in the theory of unitary similarities. This fact is stated as a purely matrix-theoretic theorem, without any reference to Arnoldi-like algorithms. Bibliography: 2 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 346, 2007, pp. 21–25.