算法复杂性

摘要： 基于深度神经网络的非监督学习方法通过联合优化特征表示和聚类指派,大大提升了聚类任务的性能。但大量的参数降低了运行速度,另外,深度模型提取的特征的区分能力也影响聚类性能。为此,提出一种新的聚类算法(asymmetric fully-connected layers convolutional auto-encoder,AFCAE),其中卷积编码器结合非对称全连接进行无监督的特征提取,然后K-means算法对所得特征执行聚类。网络采用3×3和2×2的小卷积核,大大减少了参数个数,降低了算法复杂性。在MNIST上AFCAE获得0.960的聚类精度,比联合训练的DEC(deep embedding clustering)方法(0.840)提高了12个百分点。在6个图像数据集上实验结果表明AFCAE网络有优异的特征表示能力,能出色完成下游的聚类任务。

摘要： 机器学习是多学科融合的一门学科,涉及数学优化、算法复杂性理论、博弈论等多门学科,受到了国内外学者的广泛关注。2021年4月16-18日,由天津理工大学理学院、南开大学组合数学中心、中国运筹学会数学规划分会、天津市工业与应用数学学会共同举办了第四届机器学习与优化会议,近120名优化工作者参加了此次学术会议。前面三届会议均在北京举办。

摘要： Petri网是形式化验证领域最重要的模型之一,具有重要的理论和应用价值.从验证算法分析的角度,Petri网可以被等价地抽象为向量加法系统.在对向量加法模型的研究中,人们又发展了一些重要的扩展模型.对近些年来国内外学者在向量加法系统验证领域取得的成果进行了系统总结.首先给出了向量加法系统及几个关键验证问题的形式化定义,并重点总结了一般向量加法系统模型上可达性问题的最新研究进展和关键技术;接着总结了当限定模型的维度为固定值时相关研究进展,重点给出了2维情况的核心定理;随后介绍了几个重要扩展模型,并总结了这些模型上验证问题研究的最新进展.在每一部分,都对未来研究方向及可能面临的挑战进行了展望.%Petri nets is a fundamental model in the area of formal verification.It is popular in both theoretical study and application.For the analysis of algorithmic properties of Petri nets,they are often equivalently viewed as vector addition systems.This survey gives a comprehensive review of the recent achievements in this area.First,formal definitions of the vector addition systems and their key verification problems are provided with emphasis on the discussion about reachability problem,including the latest results and the main proof techniques.Then the development on the case where the dimension is a constant number rather than a variable is summarized along with some key theorems which are fundamental to the current complexity results.Furthermore,as some important variants of vector addition systems have been proposed in recent years,a brief introduction is given to the motivation and definitions of some of the most representative ones,and the latest results on verification relating to these models.In addition,possible future work are highlighted at the end of each section.

摘要： 布尔可满足性问题(SAT)是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=-NP.学者们大都研究了子句长度不超过k的SAT问题(k-SAT),从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O((2-2/k)n),当k=3时,最好算法时间复杂度为O(1.308n).而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题(3-RSSAT),证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O(1.890n)判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O(1.890n)精确算法,该算法与子句长度无关.

摘要： 本文研究一种带有学习和恶化效应,并且机器具有可用性限制的单机排序问题.在这种模型中,工件的加工时间与所排位置及开始加工时间有关,以及机器在加工过程中,由于发生故障或进行维护与保养等原因产生的可用性限制.本文讨论的目标函数为极小化总完工时间的单机问题,对于机器在任意时间段维修的情况,分别给出了动态规划算法,分析了算法复杂性.%This paper investigates a single machine scheduling problem with learning and worsening effects and machine availability constraints. In this model, the machining time of the workpiece is related to the position and starting time of machining, as well as the usability limitations of the machine during processing due to failure or maintenance and maintenance. The objective function discussed in this paper is a single machine problem which minimizes the total completion time. For the maintenance of the machine at any time, the dynamic programming algorithm is given and the complexity of the algorithm is analyzed.

摘要： 分支降阶是目前广泛用于求解组合优化领域中难题的技术之一，该技术的核心思想是将原问题分支成若干个子问题，并递归求解这些子问题。加权分治技术是算法设计和时间复杂度分析中的一种新技术。设计一个基于分支降阶的递归算法求解最大团问题。运用常规技术对该算法进行时间复杂度分析，得出其时间复杂度为O(1.380n p(n))，其中 p(n)表示问题规模数n的多项式函数。运用加权分治技术对原算法进行时间复杂度分析，将该算法的时间复杂度由原来的O(1.380n p(n))降为O(1.325n p(n))。研究结果表明运用加权分治技术能够得到较为精确的时间复杂度。%Branch and reduce is a widely used approach for solving combinatorial optimization problems. The main idea of the approach is to solve the problem by decomposing it into two or more subproblems, and the subproblems are recur-sively solved. The measure and conquer approach is a new technique for algorithm design and complexity analysis. This paper designs an algorithm to solve the maximum clique problem. This paper uses traditional analysis technology to ana-lyze the worst-case running time of the algorithm and gets O(1.380n p(n)) running time, where p(n) is the polynomial function of node number n of the problem. This paper employs the measure and conquer approach to improve the time-complexity of the algorithm from O(1.380n p(n)) to O(1.325n p(n)) without modifying the algorithm. The results of this paper show that measure and conquer approach has tremendous impact on the worst-case running time of the algorithm.

摘要： After weeding out the dirty data that affecting the performance of single hidden layer feedforward network,traditional extreme learning machine has the need to train the entire networks.However,this will increase a lot of extra training time.In light of this issue,the paper proposes an online negative incremental algorithm based on traditional extreme learning machine algorithm:after the “dirty training sample”being eliminated,there has no need to train the whole networks once again,but only need to accomplish the network update by updating output weights matrix on the basis of original.The complexity analysis of the algorithm and the result of simulation experiment show that the proposed algorithm has higher execution speed.%在剔除影响单隐层前馈神经网络性能的“脏数据”后，传统的极限学习机算法需要重新训练整个网络，这会增加很多额外的训练时间。针对这一问题，在传统的极限学习机算法的基础上，提出一种在线负增量学习算法：剔除“脏训练样本”后，不需要再重新训练整个网络，而只需在原有的基础上，通过更新外权矩阵来完成网络更新。算法复杂性分析和仿真实验的结果表明所提出的算法具有更高的执行速度。

摘要： 加权分治技术是算法设计和分析中的一种新技术,该技术通过对处理对象设置不同的权值来更加精确的描述分支子问题规模的大小,其目的是得到最坏情况下时间复杂性更好的精确算法.加权最小顶点覆盖问题是一典型的NP难题,基于分支降阶技术为其设计一个快速递归算法;同时使用加权分治技术对算法加以分析,得到一个时间复杂性为O(1.3482np(n)的精确算法,其中p(n)为问题中结点个数n的多项式函数,对比分析表明该时间复杂性低于采用传统方法得到的时间复杂性.

摘要： 基于梯度的神经网络训练算法收敛速度慢且易陷入局部最优,并且算法收敛依赖网络参数的初始值。现有基于PSO算法的训练算法虽然可以提高算法收敛速度,但是由于微粒群尺寸随着神经网络规模的扩大而增大,从而导致算法复杂性急剧增加,并且存在过早收敛问题。为此,本文提出了一种改进的神经网络PSO训练算法,该算法仅用到两个微粒子,且可以证明算法以概率1收敛到全局最优。仿真实例表明,本文提出的算法不仅收敛速度快、收敛精度高,并且算法收敛不依赖于网络参数的初始值。

摘要： 景象匹配技术是巡航导弹实现精确末制导的关键,而景象匹配算法是这一技术的软件核心.本文介绍了景象匹配算法,分析了实际应用中影响匹配性能的因素,对两种经典的匹配算法,MAD(平均绝对差)算法与NPROD(归一化积相关)算法,理论分析了算法的复杂性,对噪声因素影响下的适应性进行了仿真试验,对算法的时间复杂性进行了定量比较,精确测量得出了正确匹配概率与加噪级数和信噪比之间的关系,得出了结论.

摘要： 景象匹配技术是巡航导弹实现精确末制导的关键,而景象匹配算法是这一技术的软件核心.本文介绍了景象匹配算法,分析了实际应用中影响匹配性能的因素,对两种经典的匹配算法,MAD(平均绝对差)算法与NPROD(归一化积相关)算法,理论分析了算法的复杂性,对噪声因素影响下的适应性进行了仿真试验,对算法的时间复杂性进行了定量比较,精确测量得出了正确匹配概率与加噪级数和信噪比之间的关系,得出了结论.

摘要： 景象匹配技术是巡航导弹实现精确末制导的关键,而景象匹配算法是这一技术的软件核心.本文介绍了景象匹配算法,分析了实际应用中影响匹配性能的因素,对两种经典的匹配算法,MAD(平均绝对差)算法与NPROD(归一化积相关)算法,理论分析了算法的复杂性,对噪声因素影响下的适应性进行了仿真试验,对算法的时间复杂性进行了定量比较,精确测量得出了正确匹配概率与加噪级数和信噪比之间的关系,得出了结论.

摘要： 景象匹配技术是巡航导弹实现精确末制导的关键,而景象匹配算法是这一技术的软件核心.本文介绍了景象匹配算法,分析了实际应用中影响匹配性能的因素,对两种经典的匹配算法,MAD(平均绝对差)算法与NPROD(归一化积相关)算法,理论分析了算法的复杂性,对噪声因素影响下的适应性进行了仿真试验,对算法的时间复杂性进行了定量比较,精确测量得出了正确匹配概率与加噪级数和信噪比之间的关系,得出了结论.

摘要： 景象匹配技术是巡航导弹实现精确末制导的关键,而景象匹配算法是这一技术的软件核心.本文介绍了景象匹配算法,分析了实际应用中影响匹配性能的因素,对两种经典的匹配算法,MAD(平均绝对差)算法与NPROD(归一化积相关)算法,理论分析了算法的复杂性,对噪声因素影响下的适应性进行了仿真试验,对算法的时间复杂性进行了定量比较,精确测量得出了正确匹配概率与加噪级数和信噪比之间的关系,得出了结论.

摘要： 景象匹配技术是巡航导弹实现精确末制导的关键,而景象匹配算法是这一技术的软件核心.本文介绍了景象匹配算法,分析了实际应用中影响匹配性能的因素,对两种经典的匹配算法,MAD(平均绝对差)算法与NPROD(归一化积相关)算法,理论分析了算法的复杂性,对噪声因素影响下的适应性进行了仿真试验,对算法的时间复杂性进行了定量比较,精确测量得出了正确匹配概率与加噪级数和信噪比之间的关系,得出了结论.

摘要： 图象形态学是建立在集合论基础上的图象处理方法,最基本的形态运算为膨胀和腐蚀,由此可以得到一些非线性的图象过滤器.但由于膨胀和腐蚀均与结构元素的定义密切相关,因此绝大多数算法依赖于对结构元素的分解,往往具有多项式复杂性.本文在对平面点集上的度量空间进行一般研究后,引入了基于离散度量的膨胀与腐蚀新定义及新算法,该算法对不同大小的结构元素,算法的复杂性为常数,并从理论上证明了新定义与原定义的吻合性.

摘要： 图象形态学是建立在集合论基础上的图象处理方法,最基本的形态运算为膨胀和腐蚀,由此可以得到一些非线性的图象过滤器.但由于膨胀和腐蚀均与结构元素的定义密切相关,因此绝大多数算法依赖于对结构元素的分解,往往具有多项式复杂性.本文在对平面点集上的度量空间进行一般研究后,引入了基于离散度量的膨胀与腐蚀新定义及新算法,该算法对不同大小的结构元素,算法的复杂性为常数,并从理论上证明了新定义与原定义的吻合性.

摘要： 图象形态学是建立在集合论基础上的图象处理方法,最基本的形态运算为膨胀和腐蚀,由此可以得到一些非线性的图象过滤器.但由于膨胀和腐蚀均与结构元素的定义密切相关,因此绝大多数算法依赖于对结构元素的分解,往往具有多项式复杂性.本文在对平面点集上的度量空间进行一般研究后,引入了基于离散度量的膨胀与腐蚀新定义及新算法,该算法对不同大小的结构元素,算法的复杂性为常数,并从理论上证明了新定义与原定义的吻合性.

摘要： 本发明公开一种基于格子复杂性算法的无线动态麻醉深度检测方法。该发明方法是基于以下麻醉深度监测装置，该装置包括采集模块、无线传输模块、数据处理模块、中央处理模块、显示模块；采集模块采集脑电信号对该模拟脑电信号进行放大，并将该将其转换为数字脑电信号。无线传输模块通过WiFi无线网络，将采集模块输出的数字脑电信号数据上传到数据处理模块进行预处理；预处理后的数据输入中央处理模块进行分析处理，分别计算格子复杂度、边缘频率、爆发抑制比，并利用决策树算法拟合得到麻醉深度指数并显示。由于使用了无线传输模块和格子复杂性算法，使得该发明方法省去传统检测装置的导线所带来的不便，且算法简单，实时性强。

摘要： 本发明的目的是增强变型快速卷积算法，以便增加这种算法的灵活性。在本发明的一个典型实施例中，引入了一个折叠单元，在接收机的IDFT前进行预处理。折叠单元在频率域内将外部的频率分量添加内部的频率分量上，形成一个较小的频率分量组。在另一个实施例中，引入了一个解折叠单元，在发射机的DFT后进行后处理。解折叠单元通过将一些经变换的原分量添加在原分量组外面来扩展频率分量组的设置。折叠和解折叠处理通过减少每秒钟必须为算法的信道专用部分执行的操作，增加了变型快速卷积算法的灵活性。而且，由于减少了每个信道的操作，单个芯片就可以处理较多的信道。

摘要： 本发明涉及一种复杂产品复杂性动力学优化方法。该方法包括如下步骤：(1)建立复杂产品的复杂性模型，提取该复杂性模型中的约束方程并组成约束方程组CN(P)＝0，其中P为复杂模型中约束参数集合；(2)复杂产品功能变更后，求取约束方程组CN(P)＝0中约束参数稳态值集合P

摘要： 本文中提供了扩增的同种异体的脂肪组织来源的基质干细胞，其用于治疗克罗恩病的复杂性肛周瘘。

摘要： 本发明公开一种基于格子复杂性算法的无线动态麻醉深度检测方法。该发明方法是基于以下麻醉深度监测装置，该装置包括采集模块、无线传输模块、数据处理模块、中央处理模块、显示模块；采集模块采集脑电信号对该模拟脑电信号进行放大，并将该将其转换为数字脑电信号。无线传输模块通过WiFi无线网络，将采集模块输出的数字脑电信号数据上传到数据处理模块进行预处理；预处理后的数据输入中央处理模块进行分析处理，分别计算格子复杂度、边缘频率、爆发抑制比，并利用决策树算法拟合得到麻醉深度指数并显示。由于使用了无线传输模块和格子复杂性算法，使得该发明方法省去传统检测装置的导线所带来的不便，且算法简单，实时性强。

摘要： 本发明的目的是增强变型快速卷积算法,以便增加这种算法的灵活性。在本发明的一个典型实施例中,引入了一个折叠单元,在接收机的IDFT前进行预处理。折叠单元在频率域内将外部的频率分量添加内部的频率分量上,形成一个较小的频率分量组。在另一个实施例中,引入了一个解折叠单元,在发射机的DFT后进行后处理。解折叠单元通过将一些经变换的原分量添加在原分量组外面来扩展频率分量组的设置。折叠和解折叠处理通过减少每秒钟必须为算法的信道专用部分执行的操作,增加了变型快速卷积算法的灵活性。而且,由于减少了每个信道的操作,单个芯片就可以处理较多的信道。

摘要： 本发明涉及一种复杂产品复杂性动力学优化方法。该方法包括如下步骤：(1)建立复杂产品的复杂性模型，提取该复杂性模型中的约束方程并组成约束方程组CN(P)＝0，其中P为复杂模型中约束参数集合；(2)复杂产品功能变更后，求取约束方程组CN(P)＝0中约束参数稳态值集合P

摘要： 本发明涉及的复杂地形条件下地震波传播复杂性定量分析方法，按以下步骤进行：导入复杂地形数据，复杂地形数据为地震测线上检波点的含高程空间坐标；利用复杂地形的含高程空间坐标信息，计算复杂地形的地形倾角非均质谱；利用傅里叶有限差分方法的角谱函数g(θ)与复杂地形的地形倾角非均质谱q(θ)，计算复杂地形条件下的地震波传播效率；利用复杂地形条件下的地震波传播效率，来计算复杂地形条件下地震波传播复杂性系数；通过本方案，实现了对复杂地形所引起的地震波传播复杂性的定量评估，定量评价不同复杂地形对地震波传播的影响和复杂地形接收到的地震资料的品质，实现较为准确地预测复杂地形的地震勘探的效果，避免地震勘探的盲目性。

摘要： 本文中提供了扩增的同种异体的脂肪组织来源的基质干细胞，其用于治疗克罗恩病的复杂性肛周瘘。

摘要： 本发明涉及用于在治疗复杂性区域性疼痛综合征(CRPS)或与CRPS相关的疼痛的方法中使用的奈立膦酸，其中奈立膦酸以一个或更多个单独的单位剂量被静脉内地施用，每个单位剂量施用持续至少4小时。本发明还涉及用于在根据患者中CRPS的持续时间治疗CRPS的方法中使用的奈立膦酸，涉及根据患者的肾功能的特定给药，并且涉及用于在本发明方法中施用奈立膦酸的试剂盒。