常见随机数发生器的缺陷及组合随机数发生器的理论与实践

随机数是蒙特卡罗 Monte- Carlo方法的基础 .本文首先指出线性同余法和移位寄存器 (亦称 Tausworthe)序列等常见随机数发生器的一些缺陷 ;在此基础上介绍可产生具有优良品质随机数的组合发生器。本文既介绍理论结果 ,用以证明组合发生器确实可以优于单个发生器 ;也具体构造了几个可供实际使用的组合随机数发生器。严格而全面的统计检验表明 ,它们可以产生具有优良品质的随机数     

基于泊松对相关的伪随机数发生器的统计测试方法

测试伪随机数发生器(pseudo random number generator,PRNG)的性能是一个非常重要的问题,通常以能否通过检验均匀性和独立性的统计测试方法来衡量.1998年Rudnick和Sarnak提出了[0,1)上实数序列的泊松对相关(Poissonian pair correlations,PPC)的概念,独立且均匀分布的实数序列满足泊松对相关.该文基于泊松对相关的概念提出了一种测试(0,1)中伪随机数序列的一级统计测试方法,给出了收敛判别标准的选取方法,并对常见的PRNG(线性同余发生器、Mersenne Twister、Matlab.rand函数以及基于无理数π重叠产生的PRNG等)进行了测试,同时与卡方检验、序列检验、游程检验以及自相关检验进行比较.结果表明该测试方法不仅简单灵活、可操作性和可移植性较强,能有效地同时检验伪随机数序列的均匀性和独立性.     

伪随机数串叠加的渐近理论

用单一方式产生的伪随机数串,其随机性常不够理想。讨论当将大量这种串按同余的意义叠加时,其结果的渐近性态,得出了能收敛到真正的随机性的充要条件。     

矩阵有理标准形的性质研究及其应用

研究了矩阵的有理标准形理论,给出了友矩阵的主要性质和判断其相似对角化的条件,证明了线性定常系统的能控性,研究了伪随机数的生成过程和周期性,并对其在自动控制和计算机科学领域的应用做了一定的解读,最后用实例验证系统的有效性.     

组合的分组测试算法的近似控制标准

对于给定的一个集合,分组测试问题是通过一系列的测试去确定这个集合的一个子集. 在文中, 作者首先运用动态规划的理论与方法, 建立了一个近似控制标准, 目的是对分组测试算法的构建过程进行有效控制, 使所构建的算法达到最优. 其次, 应用该近似控制标准研究了在n个硬币集合中确定一个伪硬币的最小平均测试数的问题. 文中所涉及的近似控制问题, 给出了在一个给定集合中去确定这个集合的一个子集的最优分组测试算法, 该最优分组测试算法是在平均测试步骤最少意义下的最优分组测试算法.     

S-PLUS与Visual C++随机数发生器性质的比较

本文通过对统计软件S-PLUS和Visual C++6.0自带的随机数发生器产生的一定数量的随机数进行参数检验、均匀性检验、独立性检验以及周期检验后, 发现S-PLUS产生的随机数列均匀性、独立性以及周期明显地优于VC++.     

集合$\tau$-标准部分的闭性

In this paper,the closeness of the τ-standard part of a set is discussed.Some related propositions of the τ-neighborhood system of a set are given.And then some related conclusions of the τ-monad of a set and the τ-standard part of a set are presented.And based on it,the necessary and sufficient conditions of the enlarged model and the saturated model are showed.Finally,some sufficient conditions that the τ-standard part of a set is closed are proved in the enlarged model and the saturated model.     

交叉概率对改进遗传算法运算速度影响的测试与分析

在现有文献基础上,通过理论分析,提出了交叉概率应取1.通过四个测试函数的测试结果,表明交叉概率越大,运算速度越快,平均运行代数越少,验证了通过理论分析提出的交叉概率应取1的科学性和可行性.同时克服了交叉概率难以确定以及确定交叉概率时缺少理论依据的不足.     

网络效应下的架构标准创新及其社会福利分析

通过对网络效应下的架构标准创新进行研究,本文发现,在位厂商通过采取开放架构标准,推动市场标准快速形成,在进入厂商新产品创新成功率不高,或新产品效率提高不是很大的情况下,迅速统一的市场标准提高了社会福利;然而,在进入厂商新产品创新成功率较高,或新产品效率提高较大的情况下,迅速统一的市场标准降低了社会福利.也就是说,开放架...     

一种改进的粒子群优化算法及其算法测试

粒子群算法原理简单、参数少、易于实现,但有时容易陷入局部最优解,收敛速度慢.本文在粒子群算法理论研究的基础上,对算法的初始值选取、惯性权重取值、算法结构进行了改进:首先采用线性惯性递减权重调整,平衡全局搜索和局部搜索的能力;然后通过logistic映射将混沌状态引入到优化变量中,增强搜索空间的遍历性;最后引入遗传算法中的选择、交叉、变异保持了种群的多样性,使其具有不易陷入局部最优的能力.采用六种典型的测试函数,对惯性权重和算法进行了测试和对比分析.结果表明,算法在收敛速度和精度上都有所提高.     

软件统计测试的比较和改进

针对软件统计测试中随机测试和分域测试的优劣问题，章对这两种测试方法进行了全面的比较，从理论上证明了分域测试优于随机测试。并根据软件验收的实际情况，提出了一种改进的软件测试方法，该方法有较好的测试效率。     

Testing algebraic geometric codes

Property testing was initially studied from various motivations in 1990’s. A code C  GF (r)n is locally testable if there is a randomized algorithm which can distinguish with high possibility the codewords from a vector essentially far from the code by only accessing a very small (typically constant) number of the vector’s coordinates. The problem of testing codes was firstly studied by Blum, Luby and Rubinfeld and closely related to probabilistically checkable proofs (PCPs). How to characterize locally te...     

改进的基于ECDLP的无证书部分盲签名机制

对邵国金等人(四川大学学报(工程科学版),2012年第1期)提出的基于椭圆曲线离散对数难题(ECDLP)的无双线性对运算的部分盲签名方案进行安全性分析,发现方案不能抵抗公钥替换攻击.为此,提出了一个改进方案.在随机谕言模型下证明了改进方案对自适应选择消息和身份攻击是存在性不可伪造性的.将所提方案与部分现有的无证书部分盲签名方案的计算性能进行了比较,结果显示改进方案具有较高的运算效率.     

线性同余人字映射组合产生均匀随机数

研究了线性同余法与人字映射组合随机数发生器 :xn=Axn-1(mod M) ,wn=2 xn,　 xn≤ 0 .5 M,wn=2 (M-xn) +1 ,　 xn>0 .5 M,yn=wn/ M.该组合发生器比相应的线性同余法在空间结构上有明显改善 ,并通过统计检验     

Local maxima of a random trigonometric polynomial

In this paper we obtain a formula for the expected number of maxima of a normal process (t) which occur below a levelu. The main condition assumed in the derivation is that (t) and its first and second derivative have, with probability one, continuous one-dimensional distributions. The expected number of such maxima of a trigonometric polynomial with random coefficients follow from this result. It is shown that, wich probability one, all the maxima of this type of polynomial occur below a levelu if , and a sizeable number of maxima exist below zero level.     

Testing for the Mean of Random Curves: A Penalization Approach

Let X ₁,...,X _n be an i.i.d. sample of random curves, viewed as Hilbert space valued random elements, with mean curve m. An asymptotic test of m = m ₀ vs m ≠ m ₀ is proposed, when m ₀ is a fixed known function. The test statistics converges under very mild assumptions and relies on the pseudo-inversion of the covariance operator (leading to a non standard inverse problem). The power against local alternatives is investigated. In final form November 2004     

Metrical Theorems on Prime Values of the Integer Parts of Real Sequences

Let a_n be an increasing sequence of positive reals with a_n as n . Necessary and sufficient conditions are obtained foreach of the sequences to take on infinitely many prime values for almost all > rß.For example, the sequence a_n is infinitely often prime for almostall > 0 if and only if there is a subsequence of the a_n,say b_n, with b_{n + 1} > b_n + 1 and with the series divergent. Asymptotic formulae areobtained when the sequences considered are lacunary. An earlierresult of the author reduces the problem to estimating the measureof overlaps of certain sets, and sieve methods are used to obtainthe correct order upper bounds. 1991 Mathematics Subject Classification:primary 11N05; secondary 11K99, 11N36.     

On percolation and ‐hardness

The edge‐percolation and vertex‐percolation random graph models start with an arbitrary graph G, and randomly delete edges or vertices of G with some fixed probability. We study the computational complexity of problems whose inputs are obtained by applying percolation to worst‐case instances. Specifically, we show that a number of classical ‐hard problems on graphs remain essentially as hard on percolated instances as they are in the worst‐case (assuming ). We also prove hardness results for other ‐hard problems such as Constraint Satisfaction Problems and Subset‐Sum, with suitable definitions of random deletions. Along the way, we establish that for any given graph G the independence number and the chromatic number are robust to percolation in the following sense. Given a graph G, let be the graph obtained by randomly deleting edges of G with some probability . We show that if is small, then remains small with probability at least 0.99. Similarly, we show that if is large, then remains large with probability at least 0.99. We believe these results are of independent interest.     

Fast algorithms for determining the linear complexities of sequences over GF(p~m) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p-1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(pm)(any positive integer m) with the period 3n (n and pm - 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-lmamura algorithm, we can determine the linear complexity of any sequence over GF(pm) with the period 3n (n and pm - 1 are coprime) more efficiently.     

基于标准区间灰数的发展带离散DDGM预测模型

由于区间灰数运算体系尚不完善,灰数间的代数运算将导致结果灰度增加,难以有效构建基于"区间灰数"的灰色发展带预测模型.对此,通过将区间灰数进行标准化处理,分解成基于实数形式的"白部"和"灰部"两个部分;然后分别对"白部"和"灰部"建立发展带预测模型,再推导并还原得到区间灰数的发展带预测模型;最后,将模型用于摆动幅度大且整体趋势增长的区间灰数在未来时刻的预测,预测效果验证了所提出模型的有效性.