斯泰勒三元系(STS)的着色理论

主要讨论斯泰勒三元系(Steiner Triple Systems,以下简称STS)的着色理论.文献中给出了顶点数为n的STS(n)的上色数的一个上界为[log_2(n+1)],并证明了当 n=2~k-1时该上界是可以达到的.该文作者在文章的最后提出的问题之一是当 n≠2~k-1时该上界是否也可以达到.本文改进了其上界为[log_2(n+1)],给出了一种由 STS(n)构造了STS(3n)的方法,并证明了当n=3(2~k-1)时,该上界也是可以达到的.     

一个瓶颈问题的多项式算法

在生产安排中会遇到这样问题:确定满足约束条件x_1+…+x_n=m的正整向量X=(x_1,…,x_n),使目标函数y=min{c_jx_i)达到最大。罗宗俊曾给出这个问题的一个拟多项式算法,大约需要n(m-n)次运算。本文给出一个多项式算法,仅需要n·log_2n次运算。     

4杆汉诺塔的最优移动次数

通常汉诺塔问题只带三根杆,当圆盘数为n时,最优移动次数为T3(n)=2n-1.对于带4杆的汉诺塔问题,最优移动次数满足关系T4(n)=2T4(m)+T3(n-m),其中m=arglmin{2T4(l)+T3(n-l)}依赖于n.对于正数整k,当k(k-1)/2+1≤n≤k(k+1)/2,n=k(k-1)/2+l时,T4(n)=(l+k-2)2k-1+1.特别,T4(sk)=2T4(sk-1)+T3(k),其中s0=0,sk=sk-1+k(k≥1).     

多处理器系统上的并行选择算法

对于共享存储的多处理器系统,给出一种易于实现的从任意给定的n个数据中既选取前m个最小者又选取前m个最大者的并行算法(m相似文献   

实序列斜圆卷积的实值变换计算法

实序列斜圆卷积是二维卷积多项式变换计算法中的核心计算。本文利用实值变换的快速性及斜圆卷积的特殊性,导出一种计算N(N=2~M)点实序列斜圆卷积的新算法。它完成该计算仅需N·(log_2N+1)次实乘、3N·(log_2N-(1/3))次实加,这分别仅约为FFT计算法所需的1/4、1/2。如将它与多项式变换法结合计算N×N(N=2~M)二维实圆卷积,则仅需N~2·log_2N次实乘、4N~2·log_2N次实加,这分别仅约为FFT计算法所需的1/8、1/3。     

尖点形式L函数的零点密度估计(Ⅱ)

设k为一正偶数,T是充分大的正数,s=σ+it,3≤Q=T,q为一正整数,χ是模q的特征,f(z)=∞∑n=1a(n)e2πinz为Γ=SL2(z)的权为k的全纯尖点形式.设Nf(σ0,T,χ)表示函数Lf(s,χ)=∞∑n=1χ(n)a(n)n-s在带形区域k/2+(l/(log(Q2T))≤σ0≤σ≤((k+1)/2),|t|≤T内的零点个数.当k/2+1/3≤σ0≤((k+1)/2)时,由Dirichlet多项式理论得出了∑q≤Q∑χmodqNf(σ0,T,χ)的一个上界.     

m台同类机上的分配博弈

研究n个工件在m台同类机上的资源分配问题.每个代理人管理一个工件并"自私"的选择一台机器加工,目标是极小化他的完工时间.该问题的性能与代理人的目标不同,是通过目标函数来衡量的,该问题的目标函数为全部工件的完工时间和.该文用POA(Price of Anarchy)来衡量一个纳什均衡(Nash Equilibrium)排序的目标函数值与一个最优排序的目标函数值的差异.证得当有一台速度比1大,其余速度均为1时,POA的上界为((4m-3)~(1/2)+1)/2,下界为3/4+(1/4)((m+1)/(m-1))~(1/2);当有一台机器速度小于1,其余速度均为1时,POA的上界为((4m-3)~(1/2)+1)/2,下界为1+(m(2m+1)~(1/2)-2m+1)/(m~2-4 m+2)((2m-1)~(1/2)+2m~2-m)).     

一类n阶本原图的广义Competition指数

根据图论、数论的相关知识,对本原图中每一点经过k长途径所到达点的集合进行分析,再结合广义Competition指数的定义,确定了一类n阶本原图的广义Competition指数.当m≤s+1且s+m为奇数时,km(D)=1+((s+m-1)/2)s,当m≤s且s+m为偶数时,km(D)=1+((s+m-1)/2)(s+1);当m≥s+2时,km(D)=1+s2.     

完全四部图K_(1,3,3,n)的交叉数

2008年,Ho证明完全三部图K_(1,m,n)的交叉数cr(K_(1,m,n))与完全二部图K_(m,n)的交叉数cr(K_(m,n))间的数量关系.对于完全四部图K_(1,3,3,n)的交叉数cr(K_(1,3,3,n)),证明cr(K_(1,3,3,n))≥1/2cr(K_(3,4,n+1))+cr(K_(3,4,n))-n-■n/2■-3),其中,■x■表示不超过x的最大整数;cr(K_(1,3,3,n))≤z(7,n)+5n+3■n/2■+3,其中,z(m,n)=■(m-1)/2■■m/2■■(n-1)/2■■n/2■.还证明cr(K_(3,4,n))≤z(7,n)+4n+2■n/2■+2.提出猜想:cr(K_(3,4,n))=z(7,n)+4n+2■n/2■+2.当上述猜想成立时,证明cr(K_(1,3,3,2N))=z(7,2 N)+13 N+3,并且cr(K_(1,3,3,2 N+1))≥z(7,2 N+1)+5(2 N+1)+3■(2N+1)/2■+2.从而,提出新的猜想:cr(K_(1,3,3,n))=z(7,n)+5n+3■n/2■+3.     

关于k次补数的一个恒等式

利用初等方法及解析方法研究了级数+∞1∑n-11/(na2(n))s的计算问题,证明了恒等式+∞∑n=11/naksk(n))sζ2(ks)/ζ(2ks)×∏p(1+1/1+pks)×…∏p(1+1/k-2+pks)其中ak(n)为n的k次补数,s为实部大于等于1的复数。     

在MIMD－CREW模型上确定凸多边形可碰撞区域的并行算法

设Ｐ和Ｑ是平面内任意两个互不相交的凸多边形，目前确定Ｐ与Ｑ的可碰撞区域的最佳串行算法时间复杂度为Ｏ（ｎ＋ｍ），其中ｎ和ｍ分别为凸多边形Ｐ和Ｑ的顶点个数．在该算法的基础上构造了一个易于并行化的求支撑点的串行算法，进而给出了在ＭＩＭＤ－ＣＲＥＷ模型上确定可碰撞区域的并行算法，其时间复杂度为Ｏ（（Ｓ＋ｌｏｇ＿２（ｎ＋ｍ））ｌｏｇ＿２（ｎ＋ｍ）／ｌｏｇ＿２Ｓ），其中Ｓ为处理机个数     

对Linux系统中的iptables过滤模块的改进

为了改善现有linux系统内核iptables模块在数据包过滤中线性匹配规则的效率。采用了散列表和动态平衡树来组织过滤表,提出了按照三层递进式的搜索规则,减少了原来的线性查找重复匹配的次数,改进了过滤效率,并确保原有功能不变。把A个IP地址、B个网络设备和C个协议规则的过滤表查找时间复杂度从O(A*B*C)降低到m*O(log2A)+n*O(B)+k*O(log2C),(m,n,k为系数因子)。通过适当增加数据结构,安排合理的搜索规则,在有限的系统开销内,可以提高数据包过滤的规则匹配效率。     

关于由Paley矩阵构造的码

从n阶Paley矩阵S出发,可以构造一个码C,它含有码字0＝（0,0,…,0）,1＝（1,1,…,1）以及矩阵（S＋I＋J）／2和（－S＋I＋J）的全部行向量,其中n是奇素数的方幂,I和J分别是单位矩阵和全1矩阵,证明了当n＝1（mode4）时,C是（n,2(n 1),(n-1)/2)码;而当n=3(mod4)时,C是（n,2(n 1),(n-3)/2)码。     

方格偶图Bm×n中的圈数

设Ｂ_(ｍ×ｎ)是具有ｍ×ｎ个顶点的方格偶图,ｇ（ｍ,ｎ）表示图Ｂ_(ｍ×ｎ)中不同圈的数目．证明了 ｇ（２, ｎ）＝ ｎ（ ｎ＋ １）／２, ｇ（３, ｎ）／２＝［（１＋√２）（ｎ＋２）＋（１－√２）（ｎ＋２）］／４－ ２（ ｎ－ １）－ ７／２,其中 ｎ＝２,３,４,…     

与基于变换存储结构的一种高效排序算法的商榷

作为计算机应用中一项复杂而重要的技术，排序一直是计算机领域内人们感兴趣的课题，寻找速度快、附加存储空间开销小的高效排序算法也一直是计算机工作者为之追求的目标．对变换存储结构的一种高效排序算法中所存在的几个问题进行商榷与讨论．并证明了建立／生成一棵含有n个数据元素的二又排序树，其时间复杂度最小为O（n log2n）．     

超球的内接单形的最大体积——献给柯召老师八十诞辰

本文用矩阵分块的技巧和Lagrange乘子法证明在R~n空间内半径为r的超球的内接单形体积V_n〔(n+1)~(n+1)/n~n〕~(1/2)r~n/n!,其中右边是内接正则单形的体积。     

求解两个与Smarandache函数有关的方程

对任意正整数n,著名的Smarandache函数S(n)定义为最小的正整数m,使得n│m!.对于任意给定的正整数n,伪Smarandache函数Z(n)定义为最小的正整数m,使得n│1+2+…m=m(m+1)/2.对任意正整数n,伪Smarandache无平方因子函数Zw(n)定义为最小的正整数m,满足n│mn,即Zw(n)=min{m∶m∈N,n│mn}.用初等方法研究了方程S(n)+Z(n)=n和Zw(Z(n))-Z(Zw(n))=0并给出了它们的全部解.     

循环小数的周期和数码和

如果素数p是102k-1u+1的一个因子,则说p在一k-类中,由此导出一个对素数的分类.设(b,10)=1且既约真分数a/b的循环节是q1q2…q2s,那么qi+qs+i=9当且仅当b的所有素因子都属于一k-类,这时a/b的数码和为9s.既约真分数a/3n+2的数码和为9(t-1)/2+r,这里t是a/3n+2的周期,r是a模9的最小非负剩余.如果1/p的周期等于p-1或(p-1)/2,那么p是一个素数.       

偏微分方程初始条件的核估计方法

对于一个适定的偏微分方程组广义初值问题,该文利用非参数回归分析中的核估计方法,对在不同时间和不同空间记录下的数据进行整合,估计出未知函数在初始曲面上的值.对于空间维数为n的问题,此估计受到n(n+1)/2个参数的控制,在一定的最优准则下,可以得到初始数据的最优估计.最后给出了一个海流浅水模式初始资料的估计实例,与大气或海洋数值预报中的其它常用同化方法相比,计算量相对较小.