一种在欧氏空间设计多项式时间近似方案的新技术

提出了一种在欧氏平面上设计多项式时间近似方案的新技术．应用该技术设计多项式近似方案分为两步：(1)对欧氏平面进行随机分割；(2)对随机分割的结果利用动态规划技术计算近似最优解．近年来Arora利用该技术获得了TSP，Steiner树，K-median三个著名NP-hard问题的多项式近似方案．经验表明，该技术适用于欧氏平面上对“距离和”优化的NP-hard问题，并可十分容易地推广到多维欧氏空间．     

具有正比权值完工时间与交货期偏差加权和最小化单机随机调度

完工时间与交货期偏差加权和最小化单机调度(简记TWD)问题是Just—In—Time生产环境下典型的调度模型，是NP—hard问题．然而工件权值与加工时间成正比时，LPT(Largest Processing Time)调度最优．本考虑了随机TWD问题，其中工件的加工时间和交货期都服从指数分布，证明了LEPT(Largest Expected Processing Time)调度的最优性，并进一步将结论推广到机器随机故障的情形．     

仿射多项式矩阵的鲁棒D稳定性分析

研究仿射多项式矩阵的鲁棒D稳定性问题，该多项式矩阵仿射地依赖于独立摄动的不确定参数．提出了检验仿射多项式矩阵的鲁棒性D稳定的充分条件，研究的D域为复平面的左半平面上广义二阶线性矩阵不等式(LMI)域．采用线性矩阵不等式和多凸性处理方法，证明了该问题等价于线性矩阵不等式的可解性问题．最后，通过数值实例说明该方法的有效性。     

特定材料构建支撑树问题的近似算法研究

结合最小支撑树问题和装箱问题,该文研究了一类新的组合优化问题:给定权重图G=(V,E;w, c)和一种长度为L的特定材料,要在图G中寻找一颗支撑树,并用给定的材料来构建支撑树的边,支撑树的总构建费用包括材料费用和构建费用两部分,目标是使得总构建费用达到最小。该问题是NP—难的,不存在多项式时间算法,除非P=NP。该文对所提问题设计了一个2—近似算法,并分析了算法的复杂性,证明了算法的近似度。     

关于平面构形的特征多项式的研究

对三维欧氏空间中平面构形的特征多项式进行了研究。用代数与几何的方法，以特征多项式为不变量，把平面个数不多于5的构形进行了分类，同时计算了空间中一些图形有规律的非中心平面构形的特征多项式。     

带有拒绝工件和机器维修区间的单机排序问题 (运筹学与控制论)

考虑带有拒绝工件和机器维修区间的单机排序问题。目标是最小化被加工工件的总完工时间与被拒绝工件的总惩罚(被拒绝加工的工件需要支付拒绝惩罚)的和。这个问题是一般意义下NP-难的,因此需要快速寻找满足指定精确度要求的近似解。为了能在较少的运行时间内得到该问题的较好的近似解,利用削减状态空间方法得到了一个全多项式时间近似方案(FPTAS)。该FPTAS是一个具有强多项式运行时间的较优近似方案,其时间复杂性为O(n2/ε2),其中n为输入工件的个数,ε>0为任意小的实数。     

一种新的等价于多项式离散对数的公钥密码体制研究

有限域上的离散对数问题是公钥密码设计的重要研究内容之一.文中通过对有限域上不可约多项式性质的进一步研究,得出不可约多项式与其诱导出的友矩阵周期的相关定理,并利用有限域同构的性质构造了一种新的类ELGamal公钥密码体制.经论证,该方案的安全性等价于求解有限域上多项式离散对数问题的难解性.同时,分析了方案的加解密算法的性能,并进行了优化.新公钥体制下的密文膨胀率近似为1,在加密大批量数据时有较高的效率.     

网络生命周期和延迟负载均衡算法的设计

在半汇聚数据收集网络中,越靠近Sink的节点数据转发量越大越容易过早死亡而造成网络分割。如何均衡能耗和数据延迟达到较优的数据收集是NP完全问题。基此将问题公式化为构造一棵路径树问题,并设计了一个近似最优的算法MMLAT。 MMLAT算法可以在多项式时间内完成。实验结果表明,MMLAT与现有的算法相比,能够较好的均衡网络生命周期和数据延迟。     

网格环境下资源调度问题的统一建模与分析

结合工作流的思想,提出了一种网格资源调度的统一模型,统一了对异构资源的描述,使网格资源不仅包括技术资源如计算资源、存储资源、网络资源,也包括人力资源、代理资源等;统一了从存储结点获取数据和从前驱任务获取数据的不同的数据获取方式.阐述了多任务的资源调度问题的形式化定义、复杂性和可近似性难度分析,证明了该问题是NP完全的且是强NP完全的,不存在任何常数近似比的多项式时间近似算法.     

一类背包问题的可解性

本文的主要结果是,对K背包问题给出了时间、空间复杂性为O(nM~k)的拟多项式算法;证明了若P≠NP,则该问题不存在完全多项式时间ε近似算法;对动态背包问题给出了时间复杂性为O(nM~k)的拟多项式算法。     

一个基于状态树的(t, n)秘密共享方案

在简述已有(t,n)秘密共享方案的基础上,提出了一个直观、简洁有效的基于状态树的(t, n)秘密共享方案,包括设计考虑、算法描述、算法实例,并对该方案进行了分析。分析表明,该方案秘密分割算法具有多项式复杂度,秘密重建算法具有线性复杂度,满足门限机密性和门限可用性。     

光码分复用/波分复用多跳网的地址码转换方案及误码率性能

采用码分复用(OCDM)与波分复用(WDM)相结合的技术可以构成多跳网，其关键技术是波长和地址码的转换，但转换中存在着电子瓶颈．提出了一个全光的地址码转换方案，该方案依赖于光硬限幅器技术，适用于时域编码的OCDM系统．分析了影响该方案工作性能的各项因素，并利用Gaussian近似，得到了码字转换差错率的边界与光硬限幅器的阈值之间的关系，以及该光码字转换方案对网络端到端误码率性能的影响．     

平面三次曲线等距线近似求解算法：——神经网络算法

本文根据神经网络函数学习模型，提出了平面三次多项式曲线一种近似等距线算法。该算法计算简单，近似精度高，且近似等距线也为三次多项式曲线，有利于计算机存贮管理，可为数控机床加工三次曲线提供刀具中心运动轨迹的计算工具。     

方向随机效果模型及其协方差结构

定义了方向随机效果模型(DREM)．这个模型是由随机效果Rasch模型发展而来．当连接函数是多项式或指数函数时，给出了DREM的协方差结构．当连接函数为一般形式时，给出了DREM的近似协方差结构．这些协方差结构和近似协方差结构与线性随机效果模型的协方差结构有相似的形式。     

一种基于一致性分片FCM的图像分割算法

针对传统FCM(fuzzy c-means)算法抗噪性差的问题,提出了一种基于一致性分片的模糊c均值聚类算法.为避免额外的空间邻域约束项带来的控制变量设置问题,该算法直接将FCM应用于图像片空间.为减弱空间邻域对图像边缘的模糊,采用基于置信区间的局部多项式交叉近似技术(local polynomial approximation and intersection of confidenec intervals,LPA-ICI)构造自适应形状一致性分片.在脑磁共振图像上的实验表明,与传统的FCM算法相比,该算法具有更高的分割精度和运行效率.     

三角多项式拟合曲线基本方法的改进

前言。在工程规划、设计与管理中，常用到一些由实际资料绘制的曲线，由于没有函数表达式，应用起来很不方便．当曲线具有周期性质(通常近似于三角函数曲线)时，自然考虑到采用三角多项式来近似拟合．本文探讨了三角多项式拟合曲线基本方法存在的不足，提出了一个有效的改进方法，并从理论上证明了该方法的正确性．     

NPC问题及某些近似算法(续)

§5.近似算法的概念及其例子由于人们普遍认为NPC类里的问题不大可能有多项式的算法,因此人们试图寻找NP—完全问题的多项式近似算法。这是当前对NP—完全问题的一个重要研究方向。本节我们仅讨论一些组合最优化问题,故下面的一些概念都是对组合最优化问题提出来的。给定一个组合最优化问题D,用opl(I)表示D中例子I的最优值,如果存在一个常数k同一个多项式算法A,使得对任意I∈D,有 R_A(I)≤k则称A为解问题D的多项式近似算法,其中     

多项式时间复杂度的可计算实数域

近来,联系于著名的P与NP问题,开展了对构造分析(递归分析或可计算分析)的计算复杂性研究(见文献[1]、[2])。本文在Aberth的程序设计系统的计算模型里给出了两个可计算实数子类:多项式时间复杂度确定型可计算实数类PR与多项式时间复杂度非确定型可计算实数类NPR,证明了它们都是实数域与Rice可计算实数域的真子域。我们在该程序设计系统中引入了Oracle(神喻)集变元、Oracle函数变元以及随机变元,使用了Oracle指令与随机指令,从而建立了相对化的多项式时间复杂度可计     

一类双约束最短路问题的近似算法

带时间和边数约束的双约束最短路问题是NP-完备的。它的一种拟多项式精确算法可以利用动态规划方法给出，在此基础上采用rounding和scaling的处理技术得到了一种全多项式时间近似方案（FPAS）。     

四杆机构九精确点轨迹综合的延拓法

平面四杆机构连杆上某点精确通过预定九个点位的轨迹综合问题是长期以来难以精确求解的课题，至今，多以近似求解法求解．本文将以求解多项式方程组的延拓法求解基于标准型方程而导出的高次多项式方程组，详细介绍了延拓法及其计算机算法，该方法的特点是能可靠地得到方程给的全部数学解系，但计算量大，本文最后给出了九精确点轨迹综合实例及其计算结果，经计算机动画模拟演示，说明计算结果是正确的．