复系数多项式完全判别系统及其自动生成

通过建立多项式的完全判别系统，彻底解决了复系数多项式根的完全分类问题；而且，把所得算法用Ｍａｐｌｅ编成一个通用程序，使多项式的完全判别系统及其完全根分类由计算机自动生成，绝不需要人工的干预；另外，还利用自动生成多项式根分类的结果，给出判定一元、二元多项式正定（正半定）性的具体方法及其自动实现。     

多项式的完全判别系统

符号（文字）系数多项式的１个完全判别系统是由这些系数构成的１组显式表达式，这些表达式足够判定该项式的实根和虚根的数目及相应的重数，这样１个关于多项式根的分类的显式判准，对于五次及五次以上多项式迄今无人给出，这方面有效工具的缺乏，严重地妨碍了Ｔａｒｓｋｉ的判定算法及近期的一些机器证明方法的计算机实现，为了弥补这一缺陷，提出了对任意次数的多项式建立完全判别系统的１个通用算法，这一结果在各个不同的领域会     

基于置换图的便笺存储器分配

在当今的嵌入式系统中,广泛地将片上存储器组织为软件管理的便笺存储器(SPM).Li等研究发现,对于很多嵌入式应用,其相干图中的数组生存期满足包含性.他们证明了满足生存期包含性的数组相干图为超完美图,并提出了一个基于超完美图的SPM分配算法.他们的算法在面向嵌入式应用的SPM分配上获得了当前最好的性能.本文进一步证明满足生存期包含性的数组相干图为置换图.置换图是超完美图的一个子类.在现有技术的情况下,置换图在判定及区间着色方面比超完美图有优势,如存在线性时间的识别算法,存在线性时间的最优区间着色算法.基于此理论结果,我们将Li等的算法在保留原算法逻辑的基础上,改进为基于置换图.实验表明,改进后的算法在很多不满足生存期包含性的相干图上仍能取得最优SPM分配,获得比基于超完美图的分配算法更好的分配结果.     

广义预测控制系统闭环特性研究

利用内模控制结构下对对象至ＧＰＣ闭环特征多项式的系数映射关系，讨论了ＧＰＣ最优控制的可解性问题，研究了其闭环特性与设计参数之间的关系，给出了通过适当选择设计参数使ＧＰＣ闭环系统表现为ｄｅａｄｂｅａｔ控制的定量，进而还得出阴关闭环系统降阶的新结果，从而大大扩展了已有的结论，并提供了一种基于系数空间映射研究ＧＰＣ系统的新思路。     

Petri网的动态不变性

定义了Ｐｅｔｒｉ网的动态不变性概念，分别从行为和状态两方面刻划了系统合成过程中不变性特征。讨论了行为不变性与状态不变性之间的关系，获得判定不变性的代数判据，由此为系统合成的一致性检验提供了依据。     

Banach空间中时变广义分布参数系统的可解性

广义分布参数系统是比分布参数系统更常见的一类系统,二者有着本质的区别,如广义分布参数系统受到干扰时会引起脉冲行为等．广义分布参数系统的可解性问题是广义分布参数系统研究的重要问题之一．本文主要研究Banach空间中时变广义分布参数系统的可解性问题．首先,讨论Banach空间中由有界线性算子所引导的广义发展算子及其性质,定义了广义发展算子的生成元．证明了广义发展算子的存在性;然后,应用广义发展算子研究时变广义分布参数系统的可解性问题,证明了强解的存在性和唯一性,并应用广义发展算子给出了时变广义分布参数系统强解的构造性表达式．所得结果对于研究时变广义分布参数系统的稳定性问题、能控性问题及最优控制问题等都有重要的理论及应用价值．     

命题规则知识库更新的一种代数方法

知识库更新的一个重要主题就是寻找高效的实现方法,为此人们做了很多工作,但还没有很好地解决,代数方法具有良好的性质和实现方法,文中给出了基于规则知识库更新的代数方法．首先讨论了如何把知识库更新和协调性检查转化为代数问题．知识库中的规则用Petri网来表示,事实用Petri网的标识表示,这样把知识库更新和协调性检查转化为Petri网的可达性问题．在做了这个转化以后,协调性检查就变成了可达性问题,可达性的判断可以用代数的方法解决,同样,矛盾性检查也可以用代数方法实现,在此基础上,给出了基于规则命题知识库的更新方法,以及扩充逻辑程序知识库的更新方法,和相关的工作进行比较,所提出的方法更实用,效率更高。     

零维三角型系统带重数的实解隔离

现有的隔离零维多项式系统实解的算法都不计算解的重数.文中用一种自然的方式定义了零维三角型多项式系统解的重数并证明了该定义与经典的局部(相交)重数的定义等价.使用该定义,给出了一个完备有效的算法计算零维三角型多项式系统的实解隔离及实解重数.文中的算法基于代数数系数多项式的无平方因子分解和区间算术.文中还给出了一些算例.     

多变量Hash函数的构造理论与方法

文中基于多变量非线性多项式方程组的难解性问题,并结合HAIFA迭代框架,提出了一种新的Hash算法,它与目前广泛使用的Hash算法相比具有下列优点:安全性基于一个公认的数学难题;输出Hash值长度可变;设计自动化,用户可根据实际需求构造满足其特定要求的Hash函数.同时还详细讨论了新算法的安全性、效率和性能,通过理论分析,选取适当参数的新算法,在其难解性问题的假设前提下,可达到理想Hash函数的安全性强度;实验结果表明,新算法在效率和性能方面与其他Hash函数具有可比性.此外,由于新算法具有良好的随机性,还可将其作为一种伪随机数生成器.     

自动发现不等式型定理的一个完备算法

利用多项式的判别式序列、WR算法、吴消元法及部分的柱形代数分解算法,给出了能自动发现不等式的一个实用算法. 该算法无须事先对结果做任何形式的猜测,而能全自动地发现新不等式. 该算法对一大类不等式型定理是完备的,而且可用于几何约束问题的实解分类. 在Maple下,据之编写的程序DISCOVERER已发现了许多不同背景的不等式型定理.     

基于流形鸽群优化的智能合约重入性漏洞检测方法研究

重入性漏洞在智能合约中普遍存在,可能造成巨大的经济损失.现有的基于符号执行的静态分析工具通过预设的规则判断漏洞是否存在,然而预设规则不全面可能会导致重入性漏洞的误报.为了避免误报,本研究尝试从软件测试用例生成的动态分析角度解决这一难题.本文将该应用场景抽象为存在重入性循环路径的路径覆盖测试用例自动生成问题,通过生成并执行覆盖重入性循环路径的测试用例来检测重入性漏洞.以鸽群算法为代表的群体智能算法是求解测试用例生成这类黑盒优化问题的常用方法.鸽群算法在整个决策空间内围绕种群最优解邻域搜索,然而,问题的最优解可能并不在该邻域内,导致路径覆盖率较低.为了提升鸽群算法的路径覆盖率,本文将利用流形启发式算子改进鸽群算法,使其分配更多的算力搜索与优化目标相关的子空间,从而提升鸽群算法求解效率,覆盖重入性循环路径.实验结果显示,改进后的流形鸽群算法能够更加高效地生成覆盖重入性循环路径的测试用例,检测出被测合约的重入性漏洞.与Oyente, Securify和Smartcheck这三个智能合约测试工具相比,本文提出的方法能够有效避免重入性漏洞的误报,在实验的8个被测试智能合约中重入性漏洞识别准确率分别...     

构造广义Sturm序列的递归算法

广义Ｓｔｕｒｍ序列被用于判断一个多项式方程ｆ（ｘ）在多项式ｈ（ｘ）〉０条件下的实根数。为了构造这样的序列，原先的方法基本上就是辗转相除法。对于带符号系数的多项式，大量的实例表明其效率甚低，无法处理较复杂的问题，代之以一个新的递归算法，成功地避免了由辗转相除引起的高复杂度的计算。     

缩减MAX SAT问题中变元个数的多项式时间算法

针对ＭＡＸ ＳＡＴ问题，提出一个缩减变元个数的多项式时间算法，若Ｔ是ＭＡＸ ＳＡＴ问题的任何一个实例，该处法将其转化为另一个实例Ｐ，具Ｐ中的变元个数小于Ｔ中的子句个数，在采用其他算法求出Ｐ的最优解后，可用Ｐ的最优解构造Ｔ的最优解。此算法可作为一个有效的预处理处理。     

自动发现不等式型定理的一个完备算法

利用多项式的判别式序列、WR算法、吴消元法及部分的柱形代数分解算法,给出了能自动发现不等式的一个实用算法.该算法无须事先对结果做任何形式的猜测,而能全自动地发现新不等式.该算法对一大类不等式型定理是完备的,而且可用于几何约束问题的实解分类.在Maple下,据之编写的程序DISCOVERER已发现了许多不同背景的不等式型定理.     

扩展的语义分析的WAP协议缺陷测试

首先介绍了一种基于语义分析的缺陷测试技术.该测试方法利用语义测试及软件错误注入来进行测试.它比传统测试的成本要小,同时能达到很好的效果.但该方法只能检测协议实现级别的漏洞,而不能检测协议设计中可能存在的缺陷.本文结合了Petri网在协议测试方面的优点提出了一种扩展的语义分析的协议缺陷测试方法.它能通过对协议Petri网模型的分析来捕获协议层面的缺陷,而为此所需的额外开销是很小的.这弥补了原缺陷测试在协议层面的不足.之后对该方法各个阶段进行了介绍.对WAP-WSP协议的进行了缺陷测试,并对结果进行了分析,证明其可行性.     

序列递推关系与一类代数几何码的有效译码——Ⅰ.一种新的序列递推关系

在序列上引进了一种新的递推关系 ,它是线性递推关系的推广 .建立了这种递推关系的极小多项式集的概念 .给出了这种递推关系的一些重要性质 ,如一致预言定理等 .在此基础上 ,推广了线性递推关系的Berlekamp Massey算法 ,给出了计算这种递推关系的极小多项式集的算法 ,并讨论了它的复杂度 .     

具有等式约束的滑动多项式建模方法

滑动多项式是广泛应用的动态系统建模方法,如何有效利用先验信息(也称为附加信息或约束信息)是改善多项式模型性能的有效途径.鉴于可转变成等式约束条件的附加信息的广泛应用,提出了带等式约束项的滑动多项式的两阶段建模方法.在理论分析的基础上,以空间目标跟踪为例,进行了算法的数值验证.该方法只需在原无约束模型的迭代格式上增加一个修正步骤,实现简单,且具有良好的可观测性、收敛性、估计精度和计算效率.文中的模型并未针对特定系统,稍加调整,可直接应用于一般非线性系统的状态建模.此外,这里的性能分析方法对其他建模方法的性能预测也同样具有参考价值.     

基于RTP/RTCP协议的音视频同步算法研究

视频和音频是流媒体传输的主要数据,各个媒体流在时间上彼此关联,互相约束.针对多媒体业务传输中出现的音视频不同步问题,提出一种将RTP时间戳映射到RTCP绝对时间NTP轴的方法,建立音视频之间的同步点和同步检测判决准则.通过仿真实验,该算法能够实现音视频的基本同步.     

二次分配问题的骨架分析与算法设计

骨架分析是近年来NP-难解问题研究的热点，对于衡量问题的相变、难度及算法设计具有重要意义．骨架的理论分析及在算法设计方面的应用还处于起步阶段，从QAP问题入手，对QAP骨架进行了理论分析，证明寻找QAP问题的骨架属于NP．难解问题，不存在多项式时间的算法可以保证得到QAP问题的骨架，为局部最优解交叉来获得近似骨架提供了合理性解释，在此基础上，利用偏移实例构造方法，提出了基于偏移实例的近似骨架算法．其基本思想是：首先为QAP实例构造偏移实例，其最优解恰是原QAP实例的一个全局最优解；然后利用现有算法求得新实例的多个局部最优解，通过对局部最优解求交得到近似骨架；将近似骨架固定以得到规模更小的搜索空间，最后在新空间上求解，拓广了骨架理论研究的范围，所提出的算法为NP-难解问题的通用算法设计提供了一种新思路。     

F[x]格基约化算法和多条序列综合

利用F[x]-格基约化算法给出了域F上长度为N 的 m条序列的最短线性移位寄存器(即极小多项式)的综合算法. 此算法的计算复杂度为O(N ²)次F中乘运算, 同时给出了一个极小多项式惟一的充要判别条件, 且在极小多项式不惟一时, 给出所有的极小多项式的一般形式和当F为有限域时极小多项式的个数.