字典序地生成有序根树的一个算法

§1.引言由于树的生成在计算机科学中有着重要应用,近年来许多文章研究了树的生成,其中大多数文章是讨论2分树及 k 分树的生成.研究一般有序根树的文章尚少.文献[1]给出了有序根树的一个序列表示法,并描述了一个生成有序根树的算法.文献[2]及[3]讨论了生成2分树及 k 分树的算法.本文用0,1序列表示有序根树,并给出了一个字典序地生成具有 n 个顶点的所有有序根树的算法.本文的表示法及算法与文献[1]中所提方法不同.本算法亦可用来生成具有 n 个叶子的所有2分树.它比[2]中的算法更简单.本文中未加说明的术语皆见[1].     

字典序地生成叶子数限制的有序根树的算法

本文利用一个正整数序列来表示一棵叶子数限制的有序根树,给出了一个序列为某叶子数限制的有序根树的表示序列的充要条件,从而给出了字典序地生成所有叶子数限制的有序根树的算法.§1.叶子数限制的有序根树的序列表示法设T表示有序根树,用|T|表示T的边树.若v是T的顶点,v不是根且次数为1,则称v是T的叶子.     

非奇函数是M序列反馈函数的一个充要条件

本文第1段系将文献[2]中所引进的M序列反馈函数用标号表示的概念推广为非奇反馈函数的标号表示法.文献[3]在第 2章里给出了非奇函数是M序列反馈函数的一些必要条件,而在本文第2段则根据文献[2]中的剪接法与有关结论给出了非奇函数是M序列反馈函数的一个充分与必要条件.     

强有序输入消解原理

本文是在文献[1]的基础上提出一种直接判误法,并给出了相应的算法。然后又提出强有序输入消解原理,证明这个新原理对Horn集也是完备的。同时揭示了它与文献[1]中讨论的正单项有序消解策略的内在关系。最后给出了相应的算法和例子。     

一类用迭代方法生成的分片线性谱序列

本文引入了空间L2[0,1]的一种具有指数形式的正交基,其中对应的指数序列称为谱序列.文章得出了一系列理论上的刻画,但主要贡献在于给出迭代解法以生成多节点分片线性谱序列,并且对分片常数谱序列进行了研究.另外,本文还给出在离散情形计算分解系数的快速算法,并估计了算法复杂度.     

奇数阶亚循环p-群分类的一个证明

一个有限p群p称为亚循环的,如果P有一个循环的正规子群A,使得PA是循环的.1973年King在文[2]中对亚循环p群进行了分类;在文[4,5]中M.F.NewmanandMingYaoXu发现了这些群的新的表示,给出了新的分类方法,这种方法是由p群生成算法(见文[3])得到的.本文的目的是给这些结果的另一种证明,与p群生成算法是不相关的.     

DNA序列比对数目的算法研究

生物序列比对是生物信息学中非常重要的内容.文[1]中作者用差分方程理论给出了求两DNA序列间比对数目的一个计算公式,然而解法较为繁琐.本文将借助于组合数学中母函数这一计数工具给出另一简单、优美的算法,并在此基础上剔除非生物比对,得到进一步的计算公式,这一结果缩小了需要考查的比对范围.     

序列的一种无组合系数的根表示

本文在讨论了组合数C_x~k等在GF(q)上的多元多项式表示的基础上,给出了序列的一种避免组合系数的根表示法,并利用它对两个有重根的反馈多项式生成序列之积的线性复杂性进行了讨论.     

r-循环阵的逆阵或广义逆阵

在应用数学和其他学科(如数理统计、固态物理等)中,都将遇到求循环阵的逆阵或广义逆阵的问题.如何求非奇异循环阵的逆阵?文[1]提出了一种算法而无证明,文[2]则给出了这种算法的一个证明,文[3]又提出一种新算法,但上述两种算法的计算量大,实际使用时是很繁的.针对这一情况,文[4]除了对[1]中提出的方法重新给了一个初等证明外,还导出了一些特殊循环阵的逆阵公式.关于求奇异循环阵的广义逆阵的问题,则除了[3]中给出了某类特殊的奇异循环阵的 Moor-Penrose 逆阵外,还未见到有文章论述求奇异循环阵的广义逆阵的一般方法.本文给出了 r-循环阵的逆阵或一个反射 g 逆阵的公式和具体算法.特别,这个公式可用来求通常的循环阵及反循环阵的逆阵和 Moor-Penrose 逆阵.文[3]、[4]中的各个公式可用本文的统一方法推广到 r-循环阵的情形.     

指定根的最小树形图的一个算法

文[1]给出了求有向图的最小树形图的算法,[2]中给出了求有指定根的最小树形图的算法.本文采用了[1]和[2]中的收缩回路的方法,给出了求有指定根的最小树形图的一个算法.设有向图G=(X,U),其中X={x_1,x_2,…,x_n}是顶点的集合,     

求解均衡问题的内部束方法

结合logarithmic二次函数和Lemar6chal和Wolfe(1975)提出的束方法,本文提出了一个求解非光滑均衡问题的束方法.一方面,我们算法推广了Nguyen等在文[1]中的束方法,并且保证了算法生成的序列在集合的内部.另一方面,将内部束方法应用到求解均衡问题.     

方程带两参数的高阶椭圆型方程一般边值问题的奇摄动

本文研究方程带两参数的高阶椭圆型方程一般边值问题解的渐近式的构造.用两参数表示法给出渐近解的表达式和有关的余项估计.拓广了文[1]和[7]的结果.     

一族非线性约束条件下的摄动梯度投影法

对问题(P),堵丁柱改变了以往的做法,利用对约束切空间的摄动技巧,给出了一个收敛的梯度投影方法.本文推广了[1]中方法,给出了一个更一般的收敛算法,它无需[1]中对约束函数的凸性假设,也不须多次求投影梯度.本文中算法的收敛性证明是建立在[3]中引理10.2.6的简单推广得到的引理3的基础上的.本文引理3减弱了引理10.2.6中的条件3,因而更具实用性.可以简化许多算法的收敛性证明.     

一种基于后验概率判决的one-by-one快速相关攻击算法(英文)

本文描述了一种基于后验概率判决的 one by one快速相关攻击算法.本文试图通过概率的观点来看待和分析快速相关攻击问题.该算法的优点有以下三点.首先,和文献[5]相比 one by one算法减少了对存储空间的需求.其次,提出了攻击失败概率的概念,并利用中心极限定理给出了它和密钥流序列长度的关系.最后,和文献[4]相比,该算法只需要更少的密钥流序列就可以达到几乎相同的攻击效果.     

产生 M 序列的一个递推算法

§1.引言M 序列又称 de Bruijn 序列,是一类具有最长周期的非线性移位寄存器序列。本文研究产生 M 序列的算法。早在70年代万哲先等对构造 M 序列的方法已有系统的研究。此后有一系列的文章研究 M 序列的构造问题。最近 Fredricksen 对这方面的工作给出了一个很好的综述。产生 M 序列的一个常用方法是先由一个较简单的移位寄存器产生许多短圈,再用并圈法将这些短圈合并起来构成 M 序列。如在[1,6]中就已给出过一些将 n 级纯轮换移位寄存器(简记为 PCK_n)和 n 级补轮换移位寄存器(简记为 CCR_n)产生的圈合并为 M 序列的方法。与[1—7]不同,Fredricksen 给出一个将 PCR_n 产生的圈合并为 M 序列的递推算法。最近 Etzion 和 Lempe 在 Fredricksen 算法的基础     

关于凝聚局部环的正则性

本文证明了极大理想m是有限生成的交换凝聚局部环（R,M）是正则的充分必要条件是m可以由一个正则R-序列生成,推广了文献[1]中相应的结论并给出了一个由正则凝聚局部环构造大量的非正则凝聚局部环的方法．     

无单调性集值变分不等式的一种投影算法

本文给出了求解无单调性集值变分不等式的一个新的投影算法,该算法所产生的迭代序列在Minty变分不等式解集非空且映射满足一定的连续性条件下收敛到解.对比文献[10]中的算法,本文中的算法使用了不同的线性搜索和半空间,在计算本文所引的两个数值例子时,该算法比文献[10]中的算法所需迭代步更少.     

一种求解混合约束优化问题的半可行序列线性方程组滤子算法的局部收敛性

作者在[10]中提出了一种半可行序列线性规划滤子方法.它将QP-free方法推广至混合约束优化问题上,并且保持对不等式约束的可行性,对等式约束部分用滤子方法处理,从而避免了罚参数的选取.该算法只需求解四个具有相同系数矩阵的线性方程组以得到搜索方向.在一定程度上克服了序列二次规划方法的缺点.[10]中仅给出了全局收敛性.本文主要给出了该算法的局部超线性收敛性证明以及数值结果.     

凸集样条函数的一种光顺样条迭代算法

关于凸集上的样条函数,我们在[1]中已作总结。P.J.Laurent一再强调这问题的研究目标基本是给出一种有效的算法。 本文给出凸集样条函数的一种新算法,每次迭代只需要求一个光顺样条函数,程序简单,计算方便,效果不错。     

一类新的伪单调变分不等式的自适应次梯度外梯度投影算法

Gibali[J.Nonlinear Anal.Optim.,2015,6(1):41-51]提出了一种解伪单调非Lipschitz连续变分不等式的自适应次梯度外梯度投影算法.其下一迭代点是通过向一个特定的半空间投影来实施.本文通过构造新的下降方向得到了一类新的自适应次梯度外梯度投影算法,并借助于何炳生和廖立志[J.Optim.Theory Appl.,2002,112(1):111-128]中的技巧优化了这些算法的步长.证明了这些算法所生成序列的全局收敛性.数值实验结果表明这类次梯度外梯度投影算法比已有算法受初始点的选取、变分不等式的维数及停止标准的精度的影响更小.而且,从迭代次数及运算所花的时间来看,新的算法均优于Gibali提出的算法.