古人笔记中的抽屉原则

抽屉原则又名鸽笼原理或狄利克雷原理,在数论、集合论和组合数学中有很多应用,共最简单的表述形式是:若把多于n个的物体放到n个抽屉里,则至少有一个抽屉里有两个或两个以上的物体。 十九世纪以来,这一原则首先被用来建立有理数     

有理g-轮换阵之性质及g-轮换阵求逆的计算复杂性

本文利用本原多项式在有理数域上的不可约性及n次本原根的性质。证明了若(g,n)=1,则n阶有理g-轮换阵为可对角化矩阵。进一步利用快速富里叶变换(FFT)给出了g-轮换阵之求逆算法。算法的主要运算为FFT的计算,因此时间复杂性为O(n log n)。其中(g,n)表示整数,g,n,的最大公约数。     

函数单调性的应用

单调性是函数的一个基本性质 ,该性质有广泛的应用 ,主要用于如下几个方面 :1　比较两个数的大小例 1　比较log2 (x + 1)与log2 ( 2x + 3)的大小 .简析　从题设的两个对数 ,便联想起y =log2 u在 ( 0 ,+∞ )上是单调函数 ,因此只要比较两个真数的大小 ,原题就可获解 .解　由 x + 1>0 ,2x + 3>0 ,解得x >- 1.当x >- 1时 ,有 0 - 1,且x≠ 0 ,n∈N ,n≥ 2 ,求证 :( 1+x) n>1+nx .简析　欲证 ( 1+x) n >1+nx ,需…     

有理数乘群的两类子群及其相互关系

本文对任意的素数p 及自然数n,构造出有理数乘群G= (Q,·)的两类子群Gp,n和Gp,0,G关于它们的商群分别为Zn 和Z,它们之间有许多很好的关系,特别是其中的同构关系.这些对我们进一步认识有理数域及近世代数的入门教学有一定的参考价值.     

3一致 C-超图的最小边数

混合超图是含有两类超边的超图,一类称为C-超边,一类称为D-超边,它们的区别主要体现在染色要求上．混合超图的染色,要求每一C-超边至少有两个点染相同的颜色,而每一D-超边至少有两个点染不同的颜色．所用的最大颜色数称为对应混合超图的上色数,所用的最小颜色数称为对应混合超图的下色数．上、下色数与边数有密切关系．作者在文献[2]中证明了具有最小上色数的3一致C-超图边数的一个下界为‘n(n-2)/3’,其中n为对应混合超图的顶点数．该文证明当n=2k 1时,该下界是可以达到的．     

具有时间与位置相关的两类平行机排序问题

研究带有维修时间限制的时间和位置效应平行机排序问题,涉及同型机和非同类机两种机器类型.工件的实际加工时间同时受到位置效应和时间效应影响,且机器具有维修限制.目标函数由机器负载,总完工时间与总等待时间组成.非同类机情形下,通过将排序问题转化为指派问题,给出多项式时间算法,其算法的时间复杂度为O(n~(k+2))/((k-1)!).同型机情形下通过转化目标函数,使用匹配算法得出排序问题的多项式时间解,其时间复杂度为O((2n+m+n log n)n~(k-1))/((k-1)!).     

圈上的多重懒惰随机游走

本文考虑了n个定点的圈上的多重懒惰随机游走.利用偶和方法证明了其最大相遇时的期望的阶数为h_(max)×log n,其中h_(max)为圈上的一简单随机游走的最大击中时.     

极小化最大完工时间的单机分批加工问题

本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b相似文献   

对称λ-Cantor集自相似子集的压缩系数的对数可比性

Mattila在1998年提出了这样一个问题:能不能找出三分Cantor集的全部自相似子集?本文主要讨论对称λ-Cantor集自相似子集的压缩系数的对数可比性.证明如果自相似子集的压缩系数ρ满足ρ23-λ-1时,logρ(logλ-1)-1为有理数.     

随机场下重对数律的渐近性

设{X,Xk,k∈Zd+}是d维随机场独立同分布零均值的随机变量,β》-1/2,EX2=σ2,如果E[X2(log+|X|)α+d-1(log+log+|X|)β]《∞,则Sn=Σκ≤nXk,α》-1,β》-1/2,EX2=σ, ε(↓)σlim(2(α+d))[ε2-2(α+d)σ2(σ+d)σ2]β+1/2Σn(logㄧnㄧ)α(log logㄧnㄧ)β-ㄧnㄧP(ㄧSnㄧ≥εΓㄧnㄧlog log ㄧnㄧ)=2βσ-(d-1)!(2-(α+d))∏Γ(β+1/2), 其中Γ(·)为Gamma函数.由此回答了Gut和Spataru[4]在d=1时所提出的问题.     

搜索两个不同坏硬币的最优化方法

设n个外观相同的硬币的集合X中含有两个坏硬币，这两个坏硬币的重量彼此不同，但都比好硬币重，而假定好硬币有相同的重量．以g2（n）表示用天平从X中找出两个坏硬币的最少测试次数．本文证明了对任意的n成立［log3（n2）］≤g2（n）≤［log3（n2）］＋1．且对无穷多个n，文中所给的测试过程是最优的．     

平行机中关于关于同类机近似算法的研究

我们考虑平行机排序问题中的这样一类:机器两台,类型一样,但效率不同.其中n个工件在第一台机器上的加工时间分别为p1,p2,…,Pn,在第二台机器上的加工时间分别为αρ1,αρ2,…,αρn,其中0<α≤1.每台机器上的工件总数不受限制.n个工件的权分别为w1,w2,…,wn,我们的目标是如何在这两台机器上安排这n个工件以及如何确定每台机器上工件加工的先后顺序,使得这n个工件的完工时间的总权和 达到最小.该问题记为 .对于这个问题,我们给出一个1.1755近似算法.     

订单带多类工件时的最大迟后问题

本文考虑多工类工件的单机排序问题,每一客户提供一由若干工件组成的订单,总共n个工件又分成k个类,当机器从加工某类中的工件转向加工不同于它的第i类工件时需一调整时间S_i,每一订单有一给定的应交工时间,所考虑目标函数是使订单的最大迟后最小,相应这一排序问题的三种模式,文中分别给出了一多项式算法,分枝定界算法和动态规划解法。     

标准多重二部图中点不交的重4圈

若多重二部图中不同划分的任意一对点之间至多包含两条边,则称其为标准多重二部图.令D是一个标准多重二部图,使得|V_1|=|V_2|=n≥2,其中n是正整数.我们证明了若D的最小度至少是3/2n,则D一定包含■个点不交的4圈,并且当n为奇数时,上述■个4圈中的前n-3/2中的每条边都是重边,剩余的一个4圈中至少有3条边是重边;当n为偶数时,前n-4/2个4圈的每条边都是重边:剩余的两个4圈中每个至少有3条边是重边,除非有一个例外.     

一类实二次域类数的可除性

<正> 我们来证明 定理 设D=4q~(2n)+1是无平方因子正整数,其中n与q均为正整数,且q≥2,那么我们有: 1)n除尽实二次域Q(D~(1/2))的类数h(D),这里Q表有理数域;     

一类特殊Beatty序列中的素因子问题

研究了数论函数Ω和ω取值于一类特殊的非齐次Beatty序列[αn+β](n=1,2,…)的问题.特别地,证明了渐近公式∑ω([αn+β)=N log log N+O(N(log log N) )以及∑(一1)Ω(αn+β)=O( n/(log N 1/2)),其中α,β∈R,n∈Z+,α>0是型为1的无理数,Ω(k)和ω(k)表示整数k(≠0)的素因子个数(Ω记重数,ω不计重数).     

订单带多工类工件时的极小迟后范围问题

本文考虑下述由多工类工件组成的订单的单机排序问题：每一个客户提供一个由若干工件组成的订单,总共n个工件又分成k个类．当机器从加工某类中的工件转向加工不同于它的第i类工件时,需一调整时间si．每一订单有一给定的应交工时间,订单的完工时间定义为该定单所含全部工件完工时的时间．我们希望适当排列这n个工件,使得订单的迟后范围最小．相应这一排序问题,文中依不同的背景给出了以下二种模式：同类工件一起连续加工,工件的完工时间为其所属类中全部工件完工时的时间,用GT,Ba来表示；同类工件一起连续加工,工件的完工时间为其本身的完工时间,用GT,Ja来表示．对于这两种模式的排序同题,我们均证明了其NP-hard性并给出了对应的分枝定界算法．     

β-变换的常返率问题

设([0,1),T_β)是β-变换动力系统.对x∈[0,1),记τ_n~β(x)为x首次返回到包含x的n阶柱集的时间.本文研究集合{x ∈ [0, 1) : lim inf n→∞(log τ_n~β(x))/log n= α, lim sup n→∞(log τ_n~β(x))/logn= γ}的Hausdorff维数,其中0αγ+∞,并证明了当α1时,这个集合的Hausdorff维数是0;当α1时,这个集合的Hausdorff维数就是1.随后,本文还考虑了首次返回到球的维数谱,得到了类似的0-1律.     

探究一道高考题的幕后知识

湖北卷（理）22题：已知不等式1/2＋1/3＋…＋1/n〉1/2[log2 n],其中n为大于2的整数，[log2 n]表示不超过log2 n的最大整数，设数列｜an｜的各项为正，且满足：a1=b（b〉0）,an≤nan-1/n＋an-1,n=2,3,4…，     

一个单台机器排序问题的下界

本文考虑下述n个工件在一台机器上加工的排序问题。其中d_i,C_i,w_i和h_i分别为工件i的应交工时间、完工时间、延误权因子和成本权因子。工件i所需的加工时间为p_i,所有工件在时间t=0时同时到达机器旁,机器不允许空转,工件被加工时不允许中断。本文用一O(n)快速方法给出(P)的一个下界。对问题(P),当取O≤u_i≤w_i,i=1,2,…,n时,