凸规划的一个内点算法

对于含线性约束的凸规划问题，本文给出了一个内点算法，并且证明了算法经过Ｏ（ｎ￣（０．５）｜ｌｎε｜）步迭代后，原始一对偶间隙必小于ε，整个算法的复杂度为Ｏ（ｎ￣（３．５）｜ｌｎε｜）．特别的，如果目标函数为凸二次函数或者线性函数，则得到相应的多项式算法，其算法复杂度为Ｏ（ｎ￣（３．５）Ｌ），其中Ｌ为相应问题的输入长度．ε取做２￣（－Ｌ）．     

无向图中严格第三短路问题的多项式时间算法

给定一个无向图G=（V,E;w;s,t）,其中s,t是2个固定顶点,w：E→R^＋是边的长度函数．最短路是指所有路中长度最小者,次短路是指长度比最短路严格大的所有路中的最小者,严格第三短路是指长度比次短路严格大的所有路中的最小者．对正权重无向图中严格第三短路问题给出一个O（n^4）多项式时间算法．     

二阶导数的五点数值微分公式及外推算法

本文通过对四次Lagrange插值多项式求二次导数推导出二阶导数的五点数值微分公式,中心点处截断误差为O（h^4）,其他点处为O（h^3）．利用Richardson外推原理得到该公式各个点的外推算法,K次外推后,中间节点的数值精度提高到O（h^2（k＋2）,其他节点的精度提高到O（h^k＋3）．     

凸二次规划基于新的核函数的大步校正原始-对偶内点算法

本文对凸二次规划提出了一种基于新的核函数的大步校正原始-对偶内点算法．这种核函数构造新的障碍函数不仅可以定义新的搜索方向，而且可以控制内迭代的过程，使得对凸二次规划提出的大步校正原始-对偶内点算法的多项式复杂性阶改善到O（√n（logn）2log（n／ε）），优于基于经典对数障碍函数的相应算法的复杂性阶．     

一类工件带有优先约束的分批排序问题

本文对工件带有“扩充链”优先约束的分批排序问题进行了研究,其目标函数为最大完工时间．优先约束为：在一个扩充链上包含有n个工件,另外有m个孤立点工件（即工件之间无任何优先约束）．讨论了时问题的最优算法,把这一问题多项式转化成了组合优化中求解非二部图赋权匹配问题,并相应地给出了一个运算次数为的多项式算法．     

线性分式规划的多项式时间算法

线性规划（ＬＰ）各种形式的多项式时间算法的研究和成果已相当成熟，但对线性分式规划（ＬＦＰ）的研究甚少．在理论上，ＬＦＰ可转换为ＬＰ，但ＬＰ的多项式时间算法求得的多半为近似解，且ＬＦＰ转换为ＬＰ是通过一个非线性分式映射实现的．因此研究和分析ＬＰ的各种多项式时间算法对ＬＦＰ的稳定性具有理论和实际意义．本文首先系统地分析了从ＬＦＰ到ＬＰ的转换及各种性质．然后，将ＬＰ的一些多项式时间算法推广到ＬＦＰ，最后证明它们仍可在多项式时间内求得满足精度的近似解．     

求解一类整数规划问题最优解的算法

本文给出了求解一类整数规划问题所有最优解的两个算法．一个算法较为简单，其时间复杂性为O（n）,另一个算法求解较为快速，其时间复杂性为O（log n）.     

一类线性规划问题的强多项式算法

对一类线性规划问题提出了一个强多项式算法．此算法可进行双向搜索．可行解集、目标函数的两个目标值以及相应的最优解，全部可行基与最优基可以一步求得，无需迭代．算法的复杂性为Ｏ（ｎ３＋ｎ２＋ｎ），其中ｎ为线性规划问题变量的个数     

多元整系数多项式因式分解（Ⅰ）——多项式复杂度算法

将ｔ（ｔ是不小于２的整数）元整系数多项式看成系数为ｔ－２元整系数多项式的二元多项式．利用已有的多项式时间复杂度的分解一元整系数多项式的算法，得到了一个分解多元整系数多项式时间复杂度的算法．     

多元整系数多项式因式分解（Ⅱ）——关于时间复杂度算法的讨论

多元整系数多项式因式分解（Ⅱ）——关于时间复杂度算法的讨论余新国黄文奇赖楚生（计算机科学与工程系）摘要给出了多项式时间复杂度算法的证明．并进一步分析得到了整个算法的一个多项式时间复杂度的上界．这是多元整系数多项式的因式分解算法的多项式时间复杂度的上界...     

K-vertex-connectivity minimum augmentation for undirected unweighted graphs

For an undirected unweighted graph G0＝(V0,E0) and a positive integer K, the K-vertex-connectivity minimum augmentation problem (K-VCMAP) is to find a minimum set of edges Emin such that the graph H0＝(V0,E0∪Emin) is K-vertex-connected. Results in the literature have given polynomial time algorithms for K-VCMAP in several special cases such as where k≤3, or G0 is a tree. However, it still remains open whether or not there exist polynomial time algorithms for K-VCMAP for any graph G0 and any integer K. In this paper, we settle the problem by describing an efficient algorithm (KUCA) with time-complexity of O(K|V(G0)|5) for the K-VCMAP for any G0 and any positive integer K.     

B.D.Acharya和S.M.Hegde关于算术图一个猜想的证明

B．D．Acharya和S．M．Hcgdc猜想[1]：(1)、如果圈C4t 1是(k,d)的算术图，那么必有k=2td 2r，其中r是某个非负整数；(2)如果圈C4t 3是(k，d)算术图，则k=(2t 1)d 2r，其中r是某个非负整数。本文对以上猜想给出了肯定性证明。     

数论函数方程kφ(Y)=φ2(Y)+S(Y 8)的解

该文讨论了包含φ(n)、φ_e(n)与S(n)3个数论函数的方程kφ(Y)=φ₂(Y)+S(Y ⁸)的可解性.利用这3个数论函数的性质,得到了该方程只在k=1、2、4、5、9、11时有正整数解,并给出了其具体的正整数解,其中函数φ(n)是Euler函数,函数φ_e(n)是广义Euler函数,函数S(n)是Smarandache函数.     

微分方程超越整函数解的增长

本文中我们讨论了下面的非线性代数微分方程P(z,f,f',…,f^(n))=O的整函数解的增长，其中n≥1是整数，p(z1,z2,…,zn 2)是一个多项式．紧接着我们将证明，如果p满足某些条件，则上述方程的超越整函数解具有无穷级。     

用数列的不同项的和表示数

对于用正整数的子列的不同项的和表示正整数的问题,给出了一个充分必要条件.对于用调和数列的子列表示正有理数的问题,研究了一些特殊情况.特别对于分母是等差数列的情况,给出完整的解答.对于一般情况,给出了一个必要条件.     

关于一种高阶算术几何级数的求和问题

本文对形如的高阶算术几何级数研究了显式求和公式的构造问题，并给出了公式系列的速归生成法则。作为例子，对一类多项式系数的三角和计算提供了求和公式。     

整系数多项式不可约的一个判别法

本文将整系数多项式置于模p之下,然后在域p里添加其多项式的一个零点θ扩张为域p(θ)——calois域,由多项式所有零点在p(θ)域上的分布规律得出其不可约的一个判别法。     

Arithmetic computation using self-assembly of DNA tiles: subtraction and division

Recently,experiments have demonstrated that simple binary arithmetic and logical operations can be computed by the process of selfassembly of DNA tiles.In this paper,we show how the tile assembly process can be used for subtraction and division.In order to achieve this aim,four systems,including the comparator system,the duplicator system,the subtraction system,and the division system,are proposed to compute the difference and quotient of two input numbers using the tile assembly model.This work indicates that these systems can be carried out in polynomial time with optimal O(1)distinct tile types in parallel and at very low cost.Furthermore,we provide a scheme to factor the product of two prime numbers,and it is a breakthrough in basic biological operations using a molecular computer by self-assembly.     

多项式0-1整规划的两个连续化途径

本文给出一种整系数多项式０－１整规划的两个连续化途径,能将含等式和不等式约束的０－１多项式规划转化成无约束多项式规划问题     

关于Dickson多项式的不动点问题

设,p>3是素数,证明了,当p(?)±1(mod5)或p(?)±1(mod7),且p(?)±1(mod8)或p≡11(mod30),等等,均存在有限域F_p上的d次置换多项式g_d(x,1),使其恰有5个不动点0,±1,±2,并由此提出一个猜想.此结果在运用置换多项式g_d(x,1)构造RSA公开密钥码体制的研究中,有重要意义.