积分方程的ε复杂性

本文考虑积分方程的ε复杂性问题问题的ε复杂性是在误差不超过ε的前提下解决问题所需的最小成本.对某些具各向异性核与自由项的第二类Fredbolm方程,求得了ε复杂性的精确阶.同时,找到了解决该问题具最小成本的算法。     

核属于H函数类的多维Fredholm积分方程类近似解的计算复杂性

给出了在 Lp,2 p<∞ ,范意义下 ,核下自由项均属于 H函数类的多维 Fredholm积分方程类近似解的ε-计算复杂性估计 .     

基于适应性信息向量的复杂性

计算复杂性,作为近几十年发展起来的新学科,无论从实践的还是从理论的观点出发,都已经成为当今计算机科学和数学的主要研究领域之一。 科学和工程中的大量问题都具有这样的特点:相关于解的信息是部分的,不精确的而且是有代价的,对这些问题,我们只能给出近似解。另外,由于数字计算机只能在有限数集上     

多元积分方程自适应解法的最优化

In this paper it was considered that problem of optimization of adaptive direct algorithm of approximate solution of integral equations. For the Fredholm integral equations of second kind with kernels belonging to Besov classes there is determined the exact order of the error of an optimal adaptive direct algorithm and a algorithm for realizing it is indicated.     

一类分式规划问题的ε-近似算法

本文针对一类复杂的分式规划问题,提出一种全局最优ε-近似解算法,并从理论上证明该算法的收敛性和计算复杂性,数值结果表明本文算法有效可行.     

数值积分的计算复杂性

本文研究Smale仅开了个头的关于数值积分的计算复杂性.就具有k—1次代数精度的一般求积泛函,求得了其复化求积公式在空间(?)的平均误差.本文所用的运算方法,对于其它的线性逼近也许都是有用的.     

一类广义分式规划问题的ε-近似算法

本文针对一类广义分式规划问题提出一种求其全局最优解的ε-近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值结果表明算法是有效可行的.     

非线性Galerkin算法的收敛性和复杂性

本文给出了数值求解非线性发展方程的全离散非线性Ｇａｌｅｒｋｉｎ算法,即将空间离散时的谱非线性Ｇａｌｅｒｋｉｎ算法和时间离散的Ｅｕｌｅｒ差分格式相结合,得到了显式和隐式两种全离散数值格式,相应地也考虑了显式和隐式的Ｇａｌｅｒｋｉｎ全离散格式,并分别分析了上述四种全离散格式的收敛性和复杂性,经过比较得出结论;在某些约束条件下,非线性Ｇａｌｅｒｋｉｎ算法和Ｇａｌｅｒｋｉｎ算法具有相同阶的收敛速度,然而前     

布尔函数的判定树复杂性及问题

设f（x₁,x₂,…,x_n）是一个布尔函数。如果计算f（x₁,x₂,…,x_n）的每个判定树算法在最坏情况下都要检查所有n个变量才能求得f的值,则称f是诡秘函数。1988年,A.C.C.Yao提出一个问题:如果一个单调非平凡的布尔函数f（x₁,x₂,…,x_n）在循环群C_m×C_n的直积的可迁作用下不变,则f是诡秘的吗?对这个问题的肯定回答支持著名的Rivest-Vuillemin猜想.本文将部分地解答这一问题.     

网络计划图的工序关系及其复杂性研究

本文研究了将原始的施工工序关系表转换为规范网络计划图的活动关系的算法.在理论上讨论了网络图中活动与紧前活动的关系以及与节点的关系,研究了网络图中添加虚活动的规律,进一步提出了生成网络计划图的按先行工序类生成算法的补充研究.     

一类带机器准备时间的排序复杂性及算法

1引言文[2-4]中考虑了如下定义的一个排序模型：m台同型机器加工n个工件，每个工件在零时刻到达，第i个工件需加工时间pi,而各机器有各自的准备时间Tj≥0,怎样安排工件加工顺序，使机器总完工时间（makespan）尽可能早．这是一个强NP-完全问题．本文考虑增加这样一个约束，即每     

带点弧约束的最短路问题：复杂性和算法

本文首先提出了带点弧约束的最短路问题,证明了该问题属于ＮＰ－Ｃ,然后给出了一个伪多项式时间算法．最后给出了最小成本最短路问题的一个时间复杂性为Ｏ（ｎ２）的算法．     

带多重选择的最短路问题:复杂性和算法

本文提出了带出重选择的是短路问题,建立了该问题的数学模型,利用背包问题的一个变形问题－带限制选择的背包问题,证明了该问题是ＮＰ－Ｃ的,最后利用动态规则给出了一个伪多项式算法,其时间复杂性Ｏ（Ｃｈｍｎ）,其中ｈ是最大的选择重数。     

基于信息量度量的企业管理复杂性评价方法——神东煤炭公司管理复杂性评价

应用物理学、数学、力学、信息论、统计学和管理学等理论方法 ,提出了管理力、管理功和管理复杂度的基本概念、定义、基本原理和研究范围 ;并基于管理熵理论的基本原理 ,建立了企业管理系统复杂性评价的新尺度和评价方法 ;构造了尺度的矢量空间、数学模型及量化模型 ;对神东煤炭集团公司的企业组织管理系统复杂性进行了实例分析与评价 .     

次最小树及其相关问题-算法设计和复杂性分析

支撑树问题已经有很长的研究历史了,见[1].在许多工程问题中,需要产生一个网络G的所有支撑树,见[2,3,4].当G为赋权图时,每棵支撑树T有长度L（T）.在产生G的所有支撑树时,许多工程问题希望按照L（T）的非降顺序产生,见[5,6].在按照L（T）的非降顺序产生的支撑树中,有许多支撑树长度是相同的,而支撑树的数目又非常大（可以高达nn-2个）,因此算法的计算量非常大.本文希望能够按照L（T）的严格上升顺序产生所有的支撑树,从而避免大量的重复计算.     

算子方程近似解直接方法的优化和信息复杂性研究进展

算子方程近似解直接方法的优化和信息复杂性是80年代发展起来的连续复杂性理论的两个主要方面,是计算机科学和数学的交叉研究领域．本文拟就这两个方面的研究进展做一简要介绍．     

几乎满的ε-等距算子的等距逼近问题

我们从减弱文Vestfrid[1]中定理3中空间一致凸条件和加强ε-等距算子条件着手去研究Banach空间中几乎满的ε-等距算子的等距逼近问题．另外，我们结合完备的β-范（0〈β〈1）空间的性质得到一些相关结论．     

具有(F,α,ε)-G凸的分式半无限规划问题的ε-最优性

首次引入了（F,α,ε）-G凸函数,（F,α,ε）-G拟凸函数和（F,α,ε）-G伪凸函数等概念,对已有的凸函数进行了推广,研究了涉及这类函数的一类分式半无限规划的ε-最优性条件,得到了一些有意义的结果．这些结果不仅是现有某些结果的推广,而且为诸如资源分配,投资组合等问题的研究提供了依据,也为理论上研究分式规划提供了参考．     

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

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