共查询到20条相似文献,搜索用时 171 毫秒
1.
We previously proved that almost all words of length n over a finite alphabet A with m letters contain as factors all words of length k( n) over A as n→∞, provided limsup n→∞ k( n)/log n<1/log m. In this note it is shown that if this condition holds, then the number of occurrences of any word of length k(n) as a factor into almost all words of length n is at least s(n), where limn→∞ log s(n)/log n=0. In particular, this number of occurrences is bounded below by C log n as n→∞, for any absolute constant C>0. 相似文献
2.
In this paper a recursive method is developed to obtain the steady state probability distribution of the number in system at arbitrary and departure time epochs of a single server state-dependent arrival rate queue λ( n)/G/1/ K in which the arrival process is Markovian with arrival rates λ( n) which depend on the number of customers n in the system and general service time distribution. It is assumed that there exists an integer K such that λ( n) > 0 for all 0 n < K and λ( n) = 0 for all n K. Numerical results have been presented for many queueing models by suitably defining the function λ( n). These include machine interference model, queues with balking, queues with finite waiting space and machine interference model with finite waiting space. These models have wide application in computer/communication networks. 相似文献
3.
We present particle simulations of natural convection of a symmetrical, nonlinear, three-dimensional cavity flow problem. Qualitative studies are made in an enclosure with localized heating. The assumption is that particles interact locally by means of a compensating Lennard-Jones type force F, whose magnitude is given by − G/ rp + H/ rq. In this formula, the parameters G, H, p, q depend upon the nature of the interacting particles and r is the distance between two particles. We also consider the system to be under the influence of gravity. Assuming that there are n particles, the equations relating position, velocity and acceleration at time tk = kΔt, K = 0, 1, 2, …, are solved simultaneously using the “leap-frog” formulas. The basic formulas relating force and acceleration are Newton's dynamical equations Fi,k = miai,k, I = 1, 2, 3, …, n, where mi is the mass of the ith particle. Extensive and varied computations on a CRAY X - MP/24 are described and discussed, and comparisons are made with the results of others. 相似文献
4.
The nonlinear projection methods are minimization procedures for solving systems of nonlinear equations. They permit reevaluation of nk, 1 ≤ nk ≤ n, components of the approximate solution vector at each iteration step where n is the dimension of the system. At iteration step k, the reduction in the norm of the residue vector depends upon the nk components which are reevaluated. These nk components are obtained by solving a linear system. We present two algorithms for determining the components to be modified at each iteration of the nonlinear projection method and compare the use of these algorithms to Newton's method. The computational examples demonstrate that Newton's method, which reevaluates all components of the approximate solution vector at each iteration, can be accelerated by using the projection techniques. 相似文献
5.
In this paper, we obtain some new sufficient conditions for the existence of nontrivial m-periodic solutions of the following nonlinear difference equation by using the critical point method, where f: Z × R → R is continuous in the second variable, m ≥ 2 is a given positive integer, pn+m = pn for any n Z and f( t + m, z) = f( t, z) for any ( t, z) Z × R, (−1) δ = −1 and δ > 0. 相似文献
6.
This paper develops optimal algorithms to multiply an n × n symmetric tridiagonal matrix by: (i) an arbitrary n × m matrix using 2 nm − m multiplications; (ii) a symmetric tridiagonal matrix using 6 n − 7 multiplications; and (iii) a tridiagonal matrix using 7 n −8 multiplications. Efficient algorithms are also developed to multiply a tridiagonal matrix by an arbitrary matrix, and to multiply two tridiagonal matrices. 相似文献
7.
A new tridiagonal Toeplitz linear system (TTLS) solver is proposed. The solver first decomposes an n-dimensional strictly diagonally dominant TTLS equation into a number of m-dimensional subsystems employing a modified Gaussian elimination method. An analytic solution of a continued fraction is obtained to derive the solver. The solver based on the modified Gaussian elimination method fully exploits parallelism. Computation and communication complexities of the proposed algorithm are all shown to be O( n/ m). 相似文献
8.
This paper presents an efficient algorithm for enumerating all minimal a- b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = ( V, E), Our algorithm requires O( n3Rab) time, which improves the known result of O( n4Rab) time for solving this problem, where ¦ V¦= n and Rab is the number of minimal a- b separators. The algorithm can be generalized for enumerating all minimal A- B separators that separate non-adjacent vertex sets A, B < V, and it requires O( n2( n − nA − nb) RAB) time in this case, where na = ¦ A¦, nB = ¦ B¦ and rAB is the number of all minimal A− B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O( n3R+Σ + n4RΣ), which improves the known result of O( n6RΣ) time, where Rσ is the number of all minimal separators of G and RΣR+Σ = ∑ 1i, v j) ER vivj (n( n − 1)/2 − m) RΣ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O(( n/ log n) Rab) time and the second one runs in time O(( n/ log n) R+Σ+ n log nRΣ) on a CREW PRAM with O( n3) processors. 相似文献
9.
We consider the problem of scheduling n identical jobs with unequal ready times on m parallel uniform machines to minimize the maximum lateness. This paper develops a branch-and-bound procedure that optimally solves the problem and introduces six simple single-pass heuristic procedures that approximate the optimal solution. The branch-and-bound procedure uses the heuristics to establish an initial upper bound. On sample problems, the branch-and-bound procedure in most instances was able to find an optimal solution within 100,000 iterations with n≤80 and m≤3. For larger values of m, the heuristics provided approximate solutions close to the optimal values. 相似文献
10.
For a least-squares problem of m degree polynomial regression with n measured values ( n ≥ m + 1), the traditional methods need O( n2m) arithmetic operations. We prove that the arithmetic complexity of this problem does not exceed O( nlog 22m). 相似文献
11.
In recent years, the conversion of residue numbers to a binary integer has been intensively studied. The Chinese Remainder Theorem (CRT) is a solution to this conversion problem of a number to the Residue Number System with a general moduli set. This paper presents a new division-free conversion approach for the conversion of residue numbers to a binary integer. The algorithm differs from others employing a great number of division instructions by using shift instructions instead. These simple instructions keep the power consumption lower. This algorithm can also be implemented with a lookup table or upon a vector machine. Both make the conversion process efficient. This division-free algorithm employs the concept of Montgomery multiplication algorithm. There are two variations of Montgomery algorithm proposed, which are algorithms MMA and IMA. The algorithm MMA is to transform the input number into the output presentation of Montgomery algorithm. Algorithm IMA is therefore inverse the computation of Montgomery algorithm to obtain the multiplicand. These two algorithms are in the complexity of O( n), where n is log 2 qi. qi is a modulus. The proposed algorithm for converting the residues to a binary integer therefore runs on O( n × log m) times on O( m) processors. There are O(log m) iterations of O( n) complexity. Compared with the traditional conversion algorithm, the advantages of this proposed algorithm are not only in employing simpler operations but also in performing fewer iterations. 相似文献
12.
The inflation GI of a graph G with n( G) vertices and m( G) edges is obtained from G by replacing every vertex of degree d of G by a clique Kd. A set S of vertices in a graph G is a paired dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired domination number γ p( G) is the minimum cardinality of a paired dominating set of G. In this paper, we show that if a graph G has a minimum degree δ( G)2, then n( G)γ p( GI)4 m( G)/[δ( G)+1], and the equality γ p( GI) = n( G) holds if and only if G has a perfect matching. In addition, we present a linear time algorithm to compute a minimum paired-dominating set for an inflation tree. 相似文献
13.
This paper presents an optimal bound on the Shannon function L( n, m,) that gives the worstcase circuit-size complexity to approximate, within an approximation degree at least , partial boolean functions having n inputs and domain size m. That is . Our bound applies to any partial boolean function and any approximation degree, and thus completes the study of boolean function approximation introduced by Pippenger (1977). Our results give an upper bound for the hardness function h(ƒ), introduced by Nisan and Wigderson (1994), which denotes the minimum value l for which there exists a circuit of size at most l that approximates a boolean function ƒ with degree at least 1/l. Indeed, if H(n) denotes the maximum hardness value achieved by boolean functions with n inputs, we prove that for almost every nH(n)2n/3 + n2 + O(1). The exponent n/3 in the above inequality implies that no family of boolean functions exists which has ‘full’ hardness. This fact establishes connections with Allender and Strauss' (1994) work that explores the structure of BPP. Finally, we show that for almost every n and for almost every boolean function ƒ of n inputs we have h(ƒ)2n/3−2 log n. The contribution in the proof of the upper bound for L(n, m, ) can be viewed as a set of technical results that globally show how boolean linear operators are ‘well’ distributed on the class of 4-regular domains. This property is then applied to approximate partial boolean functions on general domains using a suitable composition of boolean linear operators. 相似文献
14.
This paper presents a new practical bit-vector algorithm for solving the well-known Longest Common Subsequence (LCS) problem. Given two strings of length m and n, nm, we present an algorithm which determines the length p of an LCS in O( nm/ w) time and O( m/ w) space, where w is the number of bits in a machine word. This algorithm can be thought of as column-wise “parallelization” of the classical dynamic programming approach. Our algorithm is very efficient in practice, where computing the length of an LCS of two strings can be done in linear time and constant (additional/working) space by assuming that mw. 相似文献
15.
We show an Ω( m) lower bound on the number of queries required to test whether a Boolean function depends on at most m out of its n variables. This improves a previously known lower bound for testing this property. Our proof is simple and uses only elementary techniques. 相似文献
16.
In this paper the problem of pole assignment using constant gain output feedback is studied for MIMO system with system order n > m + l − 1, where m and l are the number of inputs and outputs, respectively. A new procedure is presented to design a constant gain output feedback matrix which assigns ( m + l − 2) poles exactly to the desired locations and shifts all the unassigned poles to suitable locations using root locus techniques. 相似文献
17.
Two parallel algorithms for finding minimum spanning forest (MSF) of a weighted undirected graph on hypercube computers, consisting of a fixed number of processors, are presented. One algorithm is suited for sparse graphs, the other for dense graphs. Our design strategy is based on successive elimination of non-MSF edges. The input graph is partitioned equally among different processors, which then repeatedly eliminate non-MSF edges and merge results to gradually construct the desired MSF of the entire graph. Low communication overhead is achieved by restricting the message-flow to between the neighboring processors in the hypercube topology. The correctness of our approach is due to a theorem which states that with total-ordered edges, if an edge of an arbitrary subgraph does not belong to its MSF, then it does not belong to the MSF of the entire graph. For a graph of n vertices and m edges, our first algorithm finds an MSF in O( m log m)/ p) time using p processors for p ≤ ( mlog m)/ n(1+log( m/ n)). The second algorithm, efficient for dense graphs, requires O( n2/ p) time for p≤ n/log n. 相似文献
18.
In this paper we consider the unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an O( n( n/ m+1) m) time dynamic programming algorithm and an O( mkk+1P2k−1) time dynamic programming algorithm, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the processing times of all families. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme for the problem. 相似文献
19.
Probability-one homotopy methods are a class of methods for solving nonlinear systems of equations that are globally convergent from an arbitrary starting point. The essence of all such algorithms is the construction of an appropriate homotopy map ρ a(λ, x) and subsequent tracking of some smooth curve γ in the zero set of the homotopy map. Tracking a homotopy curve involves finding the unit tangent vector at different points along the zero curve, which amounts to calculating the kernel of the n × ( n + 1) Jacobian matrix Dρ a(λ, x). While computing the tangent vector is just one part of the curve tracking algorithm, it can require a significant percentage of the total tracking time. This note presents computational results showing the performance of several different parallel orthogonal factorization/triangular system solving algorithms for the tangent vector computation on a hypercube. 相似文献
20.
We define the 0—1 Integer Programming Problem in a finite field or finite ring with identity as: given an m × n matrix A and an n × 1 vector b with entries in the ring R, find or determine the non-existence of a 0—1 vector x such that Ax = b. We give an easily implemented enumerative algorithm for solving this problem, along with conditions that spurious solutions occur with probability as small as desired. Finally, we show that the problem is NP-complete if R is the ring of integers modulo r for r ≥ 3. This result suggests that it will be difficult to improve on our algorithm. 相似文献
|