找到一切非负整系数不可约多项式的一种新方法与算法

本文利用一种独特的映射方法将非负整系数多项式转化为正整数。运用该方法及数论理论，借助于计算机程序，可以找到任意多个非负整系数不可约多项式，并且可以对这些不可约多项式进行排序，这样，为扩频通信与信道密码利用不可约多项式提供了一种实用的算法，通过上机编程操作，结果说明本文提供的映射方法和寻找不可约多项式的方法十分实用，有效。     

找到不可约多项式的研究与FoxPro程序实现

在扩频通信与传统的密码体制中广泛使用的伪随机序列,大部分是利用不可约多项式通过反馈位移寄存器和其他非线性逻辑来产生的。同时,多项式理论,特别是不可约多项式的性质对分析各种伪随机序列有着特殊的作用。 (1)找到非负整系数不可约多项式的原理 建立非负整系数多项式与正整数的符号对应和运算对应:设α_0,α_1,α_2,α_3,…,α_n是非负整数,2,3,5,7,…,p_n是n+1个相邻的素数。用正整数2~(α_0)3~(α_1)5~(α_2)(?)p_n~(α_n)表示非负整系数多项式α_0+α_1x+α_2x~2+…+α_nx~n。记作:{α_0+α_1x+α_2x~2+…+α_nx~n}←→2~(α_0)3~(α_1)5~(α_2)(?)p_n~(α_n)。     

采用牛顿插值的多项式因式分解算法的设计与实现

基于Kronecker所提供的一元多项式因式分解的构造算法、一元整系数多项式在整数环上因式分解理论,利用牛顿向前差分插值算法代替拉格朗日插值算法,把有理域上一元高次多项式因式分解化为在整数环上的因式分解,得到了整数环上的一元多项式因式分解的构造性算法,给出了具体实现过程。     

不可约M-矩阵最小特征值的新算法

我们利用M-矩阵与非负矩阵的关系,给出了求不可约M-矩阵最小特征值的新算法, 该算法具有计算量小,易在计算机上实现的特点,且可以达到实际需要的精度,并给出了收敛性证明．数值实验表明该算法具有可行性和有效性．     

GF（2）上一类多项式因式分解及算法实现

循环码在信道编码中起着非常重要的作用，它构造简单，易于实现，可通过x^n-1的既约多项式构造出来，介绍了将GF（2）上，n^x-1型多项式分解为既约多项式的方法，并给出了具体的实现方法，实验表明此算法实现简单，有很高的实用价值。     

Bernstein多项式的快速复合算法

在计算机辅助几何设计中,Bernstein多项式的复合是一个重要的研究课题。目前,实现复合的方法主要有Blossoming算法和优化的Blossoming算法。这类方法虽然是数值稳定的,但是计算量很大,存储空间和程序复杂性方面也要求较高,文中基于多项式插值和符号运算,提出了一种新的复合算法。理论分析表明,新算法不但保持了数值稳定性,而且在计算量,存储空间和程序复杂性方面明显优于已有算法。     

基于Chebyshev多项式的椭圆曲线密码系统算法

通过结合Chebyshev多项式与椭圆曲线, 构造基于Chebyshev多项式的椭圆曲线密码系统算法。利用有限域上Chebyshev良好的半群特性和椭圆曲线上的性质, 实现了在椭圆曲线上的加密算法。该算法具有混沌密码和椭圆曲线密码算法的优点。通过对该算法的分析, 认为算法简单、安全性高、方案可行。     

基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

GF(2m)上的快速模约减算法

针对GF(2m)上的模约减运算问题,在基于固定三(或五)项式(FTOP)算法的基础上提出一种改进的快速算法。该算法采用动态计算分组字序号和偏移量的方法,克服FTOP只适用于特定约减多项式的不足。实验结果表明,当约减多项式项数小于123(m<719)时,该算法速度比一次一位的算法有较大提高,最大为89%,平均为30%左右,当约减多项式为任意三(或五)项式时,能达到与FTOP相同的速度。     

一种新的大整数乘法算法

为解决超出计算机系统基本整数类型表达能力的整数(大整数)算术运算问题,以基础算法--大整数乘法为研究对象,根据大整数的表示形式与多项式表示形式上的相似性,结合大整数乘法进位与取模的特点,给出了一种关于大整数乘法的多项式算法.其方法与别的方法最大的不同是,虽然是求两个大整数乘法,但整个算法没有使用乘法,只是用加法运算而已...     

一种带数据整数规划的新型并行自平衡PSO算法

为有效解决标准粒子群(PSO)算法在进化后期缺乏多样性且精度不高的问题,利用多核系统及实际高校地理数据,给出一种高校数据的整数规划方法及并行自平衡PSO算法模型来并行求解高校路网问题,同时体现算法性能。将自平衡机制采用多核系统并行处理方式生成相互独立的子群体,每个子群体间并行求解,最终生成主群体最优路径即高校路网。在Visual Studio2005.NET环境下用C++编程实现仿真。实验结果表明,此算法从求解精度及计算时间两个重要方面综合改善了算法性能。     

A New Algorithm for Finding Trees with Many Leaves

We present an algorithm that finds out-trees and out-branchings with at least k leaves in directed graphs. These problems are known as Directed Maximum Leaf Out-Tree and Directed Maximum Leaf Out-Branching, respectively, and—in the case of undirected graphs—as Maximum Leaf Spanning Tree. The run time of our algorithm is O(4 ^k nm) on directed graphs and O(poly(n)+4 ^k k ²) on undirected graphs. This improves over the previously fastest algorithms for these problems with run times of 2 ^O(klog k) poly(n) and O(poly(n)+6.75 ^k poly(k)) respectively.     

求不相交QoS路由的一种整数线性规划方法

提出求解不相交QoS路由问题的一种整数线性规划方法.首先,利用一个0-1变量集合来表示不相交路由和路由的QoS需求;然后,通过拉格朗日乘子将集合中的复杂约束引入所导出的整数线性规划问题的目标函数中.因为约束系数矩阵是全幺模矩阵,所以这类整数线性规划问题能用单纯形法容易地求解,从而可在求解线性规划问题的迭代过程中求出不相交QoS路由.数值实验结果表明了所提出方法的有效性.     

求大素数的一个新算法

讨论了一些关于素数最重要的结果及其性质,同时给出一个新算法,它能快速产生大素数。     

一种求关键路径的新算法

文章提出了一种求关键路径的新算法,该算法数据结构形式简单,求解方便且易于实现,并且算法能求出所有关键路径。用C语言设计了相应的程序验证了此算法。     

一种新的Kth最短路径搜索算法

借助于“背离”路径的概念,论文在2nd最短路径搜索算法的基础上提出了一种新的Kth最短路径搜索算法,并将其应用至实际环境中。通过K-1次2nd最短路径搜索算法的迭代,该算法可以求出网络中任意两个给定节点之间的Kth最短路径,2nd最短路径搜索算法在计算上具有简单性,因而也同样具有简洁、快速的特点。     

Reflection Coefficients of Polynomials and Stable Polytopes

The geometry of stable discrete polynomials using their coefficients and reflection coefficients is investigated. Two linear Schur invariant transformations with a free parameter in the polynomial coefficient space are introduced. The first transformation ${cal R}^{n}times{cal R}rightarrow{cal R}^{n}$ maps an arbitrary stable polytope into another stable polytope. The second transformation ${cal R}^{n}times{cal R}rightarrow{cal R}^{n+1}$ maps a stable tilted $n$-dimensional hyperrectangle defined by the discrete Kharitonov theorem into a stable $(n+1)$- dimensional polytope.      

A New Approximation Algorithm for Finding Heavy Planar Subgraphs

We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G . This problem has applications in circuit layout, facility layout, and graph drawing. No previous algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH had a performance ratio exceeding 1/3 , which is obtained by any algorithm that produces a maximum weight spanning tree in G . Based on the Berman—Ramaiyer Steiner tree algorithm, the new algorithm has performance ratio at least 1/3+1/72 and at most 5/12 . We also show that if G is complete and its edge weights satisfy the triangle inequality, then the performance ratio is at least 3/8 . Furthermore, we derive the first nontrivial performance ratio (7/12 instead of 1/2 ) for the NP-hard SC MAXIMUM WEIGHT OUTERPLANAR SUBGRAPH problem.     

所有最短路径的求解算法

本文提出了一种求所有最短路径的算法,能高效地求出一个顶点到其它各顶点的所有最短路径。此外,我们用C语言设计的相应程序验证了此算法。