混合基表示下的大数比较算法及其最优性

本文给出了大数在混合基表示下的比较算法,主要结论为:设X=b_(n 1)P_nP_(n-1)…P_1 … b_2p_1 b_1,其中{p_i}两两互素,则对于计算{b_i}的任何算法,计算b_(n 1)所花的时间大于计算b_1,b_2,… ,b_n所花时间的总和.从而利用计算b_1,b_2,…,b_n的最优算法进行两个大数的比较,本文提出的比较算法是最优的.     

THE DIRICHLET PROBLEM AND NEUMANN PROBLEM FOR NONLINEAR PARABOLIC SYSTEMS OF SECOND ORDER EQUATIONS WITH MEASURABLE COEFFICIENTS IN A HIGHER DIMENSIONAL DOMAIN

1 Formulation of Dirichlet Problem and Neumann Problem fOrParabolic SystemsLet O be a bounded domain in Rn and the boundary On E C2. Denote Q = g x I,I =0 < t 5 T, 0 < T < ool 0Q = Sl U S2 is the parabolic boundary where S1 = a x {t = 0} is thebottom and S2 = an x I is the lateral boundary. We consider the nonlinear parabolic systemof second order equationsFh(t, xl ut D.u, D:u) -- Hukt = 0 in Q, k = 1, 2,'',m. (l.l)Under certain conditions, system (1.1) can be reduced to the fOrmw…     

c个修理工同步多重休假的k/n(G)表决可修系统

本文首次将"多个修理工同步多重休假"规则引入到c个修理工的k/n(G)表决可修系统中,在假设部件的工作寿命、故障后的修理时间和修理工的休假时间 分别服从参数λ(>0)、μ(>0)和θ(>0)的负指数分布下,利用拟生灭过程 和矩阵几何解方法,讨论了在稳态下系统处于各状态的概率分布,以及一些刻画系统性能的可靠性指标 和排队指标,如系统的稳态可用度、稳态故障频度和故障部件的等待修理时间等,并且讨论了四种特殊情况: 1) c=1,θ→+∞; 2) c=1,k=1,θ→+∞; 3) c=1,k=n,θ→+∞; 4) c=1,k=n-1,θ→+∞.最后给出了在c=2,n=6,k=3,λ=1/10,μ=1/5,θ=1/2的数值计算例子.     

严格第k最小支撑树问题

提出了严格第 k最小树的概念 .利用定长支撑树问题的复杂性 ,证明了求支撑树的长度分布L( G)问题是 NP-C的 ,从而证明了严格第 k最小支撑树问题也是 NP-C的 .对于 k=2的情况 ,给出了一个多项式时间算法 ,其时间复杂性为 $O( | EX| n^2 )$ ,其中 EX是正交换的集合 ,n是顶点数.     

The Expansion of Dynamic Solving Process About a Class of Non-linear Programming Problems

For those mathematical programming problems which have special structures,we can alsoget very good result by applying the dynamic programming methods.1　 Special Structuresmin Z=∑3j=1cjx2j∑3j=1xj≥ bxj≥ 0 ,b >0 ,cj>0 ,　 j=1 ,2 ,3　　 Supposeλ1 ,λ2 ,andλ3are state variables,x1 ,x2 ,x3are decision variables,and statetransference equation as follows:λ1 =λ2 -x2 ,λ2 =λ3-x3,0≤x1 =λ1 ,0≤x2 ≤ λ2 ,0≤x3≤ λ3,λ3≥b.Then state transferenceequation isλS=λS 1 -x S 1 .The optimal value…     

局内军车调度的时间优化及其竞争策略

提出时间目标函数下的局内k－军车调度问题，应用复位策略给出该问题的几种竞争算法：给出了对应的局内k－服务器问题的竞争比的c时的该问题的竞争比为c 1 1/θ的竞争算法；分别给出了当k=n和k=n-1时该问题的竞争比为1和1＋1／θ的竞争算法。     

推广的$M^x$/G(M/G)/1(M/G)可修排队系统(Ⅱ)—— 一些可靠性指标

进一步研究推广的$M^x$/G(M/G)/1(M/G)可修排队系统,讨论了服务台如下的可靠性问题:1)在时刻t失效的概率,即不可用度;2)在“服务员忙期”内的失效次数;3)在(0,t]内的平均失效次数及其渐近展开;4)在“服务员忙期”内的失效时间;5)在(0,t]内的平均失效时间及其渐近展开,得到一系列结果,并给出了便于计算(0,t]内的平均失效次数和平均失效时间的近似式.     

逆一般中心选址问题的算法研究

主要讨论了逆一般中心选址问题的算法研究。对于实例是树且U为整数的情况,逆一般中心选址问题转化为逆中心选址问题。对于实例是一般简单图的情况,本文给出了一个逆一般中心选址问题转化为权重为1的S te iner树问题的拟多项式算法。并对于权w=1的S te iner树问题,本文也给出了一个近似界为43的近似算法。     

REDUCED FORM OF YANG-MILLS EQUATION OFSU(2) ON R~(3,1)

1.NotationsLetR3,1betheMinkowskifour-dimensionalspacewithcoordinatesx=(x')x',x',x').ThemetricdsZ=Zgijdx'dxjofR3'1isgivenbygll=gab=gb3=l,g'=--1,andgij~0fori/j.Letgi(2)betheLiealgebraofgroupSU(2).Theanti-Hermitianrepresentationsofabasisofgi(2)aretakenasfollows:inwhichi=n.Theconnectionisa1-forminwhichThereare12unknownfunctionsA,Thecurvaturetensorsaregivenbyinwhichoj=0/oxj,j=l,2,3,4.TheYang-MillsequationofSU(2)onR3)1is(see[1])TheYang-Millsequationconsistsof12equationsYMjk=0,j~1,2,3,4,k~…     

声纳浮标多普勒最接近法的一种新算法

在声纳浮标多普勒最接近点方法基础上,提出一种新算法.与原算法相比:(1)新算法推导出一个无误差的求解公式,而原算法是一个近似公式;(2)新算法在使用上较原方法更为方便,公式需要的输入在实际中更容易得到.比较了新算法和原算法的关系,原算法主要使用测量两个关于最接近点对称的多普勒频移及最接近点的频率变化导数;新方法在使用多普勒频移的同时还利用了测量点的时间信息.最后给出了仿真结果,表明新算法可以精确求解目标的运动参数.     

MapReduce系统中的两阶段混合流水作业调度算法

以极小化最大完工时间为目标,研究MapReduce系统中的两阶段混合流水作业调度问题.每个工件都包含两个任务集,即map任务集和reduce任务集.所有map任务必须在第一阶段的m1台平行机上加工,而reduce任务则必须在第二阶段的m2台平行机上加工.一个工件的reduce任务只有在该工件的所有map任务完成后才能开始加工.所有reduce任务不允许中断.对map任务不可中断情形,给出了一个最坏情况界为2-1/max{m1,m2}的近似算法.对map任务可任意分割情形,分别给出了基于Johnson规则和LPT规则的近似算法H(2,J)和H(2,L),并证明了这两个算法的最坏情况界分别为2-1/m2和2.通过数值实验发现,一般情况下H(2,J)性能要优于H2,L,但在reduce任务的总加工时间大于map任务且m2较大时则相反.最后,当map任务和reduce任务的总加工时间成比例关系时,给出了算法H(2,J)的参数最坏情况界.     

带不可用时间段的单机调度问题的启发式算法

研究了机器带有一个不可用时间段的部分可续型单机最大完工时间调度问题,提出了一种启发式算法,证明了其相对误差界,并举例说明该界是紧的,而且据此推出了该算法对相应不可续问题的相对误差界,此界低于该问题现有算法的界.将此算法与其它算法进行了多方面的比较,包括利用随机数据进行实验以评估其相对误差,结果表明此算法是一种非常高效的启发式算法.     

An on-line scheduling problem of parallel machines with common maintenance time

In this paper, the authors consider an on-line scheduling problem of m (m ≥ 3) identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance time interval is larger than the largest processing time of jobs, the authors prove that any on-line algorithm has not a constant competitive ratio. For the case that the length of maintenance time interval is less than or equal to the largest processing time of jobs, the authors prove a lower bound of 3 on the competitive ratio. The authors give an on-line algorithm with competitive ratio $4 - \tfrac{1} {m} $ . In particular, for the case of m = 3, the authors prove the competitive ratio of the on-line algorithm is $\tfrac{{10}} {3} $ .     

Asymptotic Normality of Maximum Quasi-Likelihood Estimators in Generalized Linear Models with Fixed Design*

In generalized linear models with fixed design, under the assumption λ↑_n→∞ and other regularity conditions, the asymptotic normality of maximum quasi-likelihood estimator ^↑βn, which is the root of the quasi-likelihood equation with natural link function ∑i=1^n Xi（yi -μ（Xi′β）） = 0, is obtained, where λ↑_n denotes the minimum eigenvalue of ∑i=1^nXiXi′, Xi are bounded p × q regressors, and yi are q × 1 responses.     

面向C-RAN的群稀疏线性预编码

云无线接入网络（cloud radio access network,C-RAN）是一种能够集中处理信号的网络架构。C-RAN能够通过算法动态选择无线电单元（remote radio head,RRH）来调整用户通信速率。而通信速率作为用户服务质量（quality of service,QoS）的关键部分,当参与服务的RRH越多时,用户的通信速率更大且体验更好,但同时所带来的能源损耗越大,因此本文研究通信速率和功率消耗二者之间的权衡关系。提出一种优化算法,将权衡问题建模成一个单目标优化模型,通过权衡系数来协调速率和RRH激活个数之间的矛盾。为了解决$\ell_0$-范数的非凸问题,本文使用重复加权$\ell_1$-范数去近似$\ell_0$-范数,同时使用加权最小均方误差（weighted minimum mean square error,WMMSE）的方法将通信速率从非凸问题转换成一个凸问题,最后使用改进的次梯度法对预编码矩阵进行更新。仿真结果证明该算法减少了时间复杂度,同时达到了与穷举法相近的性能。     

毫米波雷达多运动目标检测算法研究

在现代毫米波雷达多目标检测系统中,多分量线性调频信号时频分析产生的交叉项干扰和复杂的运动补偿等问题显得尤为突出。为了减小交叉项所带来的误差,提出了基于分数阶Fourier变换(fractional Fouriertransform,FRFT)的Choi-Williams-distribution(CWD)变换,即p0阶CWD变换,并与Hough变换结合起来形成了一种新的检测方法。该算法避免了复杂的运动补偿处理过程,降低了计算量。通过对一帧脉冲的初相位回波信号进行的仿真实验,在强背景噪声的情况下能清晰地分辨相距为0.5 m的两个点目标。仿真结果表明此方法可以精确探测成组飞行目标。     

一种改进鲁棒性的CAB盲波束形成算法

基于边界误差性能最优准则的鲁棒性方法是波束形成算法领域内的最新研究热点,将该鲁棒性方法与CAB(周期自适应波束形成)算法相结合,提出了一种新的改进鲁棒性的CAB盲波束形成算法。该算法与采用传统对角线加载技术的R-CAB盲波束形成算法相比,进一步提高了稳健性和输出信干噪比。计算机仿真验证了该算法的可行性和有效性。     

处理机具有不同开始加工时间的排序问题$Q,a_i‖C_{max}$

讨论任务的加工是不可中断、处理机是恒速机的排序问题$Q,a_i‖C_{max}$,证明了用ＬＰＴ算法求解该问题的误差界是２．     

推广的M~x/G(M/G)/1(M/G)可修排队系统(Ⅱ)—— 一些可靠性指标

进一步研究推广的MxG(MG)1(MG)可修排队系统,讨论了服务台如下的可靠性问题:1)在时刻t失效的概率,即不可用度;2)在“服务员忙期”内的失效次数;3)在(0,t]内的平均失效次数及其渐近展开;4)在“服务员忙期”内的失效时间;5)在(0,t]内的平均失效时间及其渐近展开,得到一系列结果,并给出了便于计算(0,t]内的平均失效次数和平均失效时间的近似式     

3维与4维q元线性码的重量谱

得到了不满足链条件的 [n,3;q]线性码 ( q =8,9)的差序列的充要条件 ;并应用改进的遗传算法搜索满足链条件的 [n,4 ;4 ]线性码的差序列 ,取得了较好的结果 .