共查询到20条相似文献,搜索用时 78 毫秒
1.
The foundation of information society is computer interconnection network, and the key of information exchange is communication algorithm. Finding interconnection networks with simple routing algorithm and high fault-tolerant performance is the premise of realizing various communication algorithms and protocols. Nowadays, people can build complex interconnection networks by using very large scale integration (VLSI) technology. Locally exchanged twisted cubes, denoted by ( s + t + 1)-dimensional LeTQs,t, which combines the merits of the exchanged hypercube and the locally twisted cube. It has been proved that the LeTQs,t has many excellent properties for interconnection networks, such as fewer edges, lower overhead and smaller diameter. Embeddability is an important indicator to measure the performance of interconnection networks. We mainly study the fault tolerant Hamiltonian properties of a faulty locally exchanged twisted cube, LeTQs,t − ( fv + fe), with faulty vertices fv and faulty edges fe. Firstly, we prove that an LeTQs,t can tolerate up to s−1 faulty vertices and edges when embedding a Hamiltonian cycle, for s≥2, t≥3, and s≤t. Furthermore, we also prove another result that there is a Hamiltonian path between any two distinct fault-free vertices in a faulty LeTQs,twith up to ( s − 2) faulty vertices and edges. That is, we show that LeTQs,t is ( s−1)-Hamiltonian and ( s−2)- Hamiltonian-connected. The results are proved to be optimal in this paper with at most ( s − 1)-fault-tolerant Hamiltonicity and ( s − 2) fault-tolerant Hamiltonian connectivity of LeTQs,t. 相似文献
2.
This paper presents a sum-of-product neural network (SOPNN) structure. The SOPNN can learn to implement static mapping that multilayer neural networks and radial basis function networks normally perform. The output of the neural network has the sum-of-product form ∑ Npi=1∏ Nvj=1 fij ( xj), where xj's are inputs, Nv is the number of inputs, fij( ) is a function generated through network training, and Np is the number of product terms. The function fij( xj) can be expressed as ∑ kwijkBjk( xj), where Bjk( ) is a single-variable basis function and Wijk's are weight values. Linear memory arrays can be used to store the weights. If Bjk( ) is a Gaussian function, the new neural network degenerates to a Gaussian function network. This paper focuses on the use of overlapped rectangular pulses as the basis functions. With such basis functions, WijkBjk( xj) will equal either zero or Wijk, and the computation of fij( xj) becomes a simple addition of some retrieved Wijk's. The structure can be viewed as a basis function network with a flexible form for the basis functions. Learning can start with a small set of submodules and have new submodules added when it becomes necessary. The new neural network structure demonstrates excellent learning convergence characteristics and requires small memory space. It has merits over multilayer neural networks, radial basis function networks and CMAC in function approximation and mapping in high-dimensional input space. The technique has been tested for function approximation, prediction of a time series, learning control, and classification. 相似文献
3.
并行计算机系统功能的实现很大程度上依赖于系统互连网络的性能。为了精确度量以 k元 n方体为底层拓扑结构的并行计算机系统的容错能力,研究了点故障模型下 k元 n方体中 k元( n-1)方体子网络的可靠性。当 k ≥ 3且为奇数时,分别在固定划分模式和灵活划分模式下对 k元 n方体中不同数目的 k元( n-1)方体子网络保持无故障状态的平均失效时间进行了分析,并得出了这一子网络可靠性评估参数的计算公式。结果表明,当基于 k为奇数的 k元 n方体构建的并行计算机系统指派子网络执行用户任务时,在点故障模型下灵活划分模式相比固定划分模式有着更好的容错能力。 相似文献
4.
We derive asymptotic approximations for the sequence f( n) defined recursively by f( n)=min 1j<n { f( j)+ f( n− j)}+ g( n), when the asymptotic behavior of g( n) is known. Our tools are general enough and applicable to another sequence F( n)=max 1j<n { F( j)+ F( n− j)+min{ g( j), g( n− j)}}, also frequently encountered in divide-and-conquer problems. Applications of our results to algorithms, group testing, dichotomous search, etc. are discussed. 相似文献
5.
Some recent results claimed the existence of a class of algorithms for certain NP-complete problems, with running time O( n1g k 2 n/2) and storage requirements O( k 2 n/k), for 2 kn. In this note we show that those results do not hold, implying that an algorithm with time O( n 2 n/2) and space O(2 n/4) is still the best-known solution for such class of NP-complete problems. 相似文献
6.
In this paper, we shall give a combinatorial proof of the following equation: , where m and n are positive integers, m ≤ n, and k1, k2, …, kn-1 are nonnegative integers. 相似文献
7.
Consdier I( z) = ∫ ba w( t) f( t, z) d t, f( t, z) = (1 + t/z) −1. It is known that generalized Gaussian quadrature of I( z) leads to approximations which occupy the ( n, n + r − 1) positions of the Padé matrix table for I( z). Here r is a positive integer or zero. In a previous paper the author developed a series representation for the error in Gaussian quadrature. This approach is now used to study the error in the Padé approximations noted. Three important examples are treated. Two of the examples are generalized to the case where f( t, z) = (1 + t/z) −v. 相似文献
8.
为了度量发生故障时 k元 n方体对其可匹配性的保持能力,通过剖析条件故障下使得 k元 n方体中不存在完美匹配或几乎完美匹配所需故障集的构造,研究了条件故障下使得 k元 n方体不可匹配所需的最小故障数。当 k ≥ 4为偶数且 n ≥ 2时,得出了 k元 n方体这一容错性参数的精确值并对其所有相应的最小故障集进行了刻画;当 k ≥ 3为奇数且 n ≥ 2时,给出了该 k元 n方体容错性参数的一个可达下界和一个可达上界。结果表明,选取 k为奇数的 k元 n方体作为底层互连网络拓扑设计的并行计算机系统在条件故障下对其可匹配性有良好的保持能力;进一步地,该系统在故障数不超过2 n时仍是可匹配的,要使该系统不可匹配至多需要4 n-3个故障元。 相似文献
9.
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. 相似文献
10.
We consider the basic problem of searching for an unknown m-bit number by asking the minimum possible number of yes–no questions, when up to a finite number e of the answers may be erroneous. In case the ( i+1)th question is adaptively asked after receiving the answer to the ith question, the problem was posed by Ulam and Rényi and is strictly related to Berlekamp's theory of error correcting communication with noiseless feedback. Conversely, in the fully non-adaptive model when all questions are asked before knowing any answer, the problem amounts to finding a shortest e-error correcting code. Let qe( m) be the smallest integer q satisfying Berlekamp’ s bound
. Then at least qe( m) questions are necessary, in the adaptive, as well as in the non-adaptive model. In the fully adaptive case, optimal searching strategies using exactly qe( m) questions always exist up to finitely many exceptional m's. At the opposite non-adaptive case, searching strategies with exactly qe( m) questions—or equivalently, e-error correcting codes with 2 m codewords of length qe( m)—are rather the exception, already for e=2, and are generally not known to exist for e>2. In this paper, for each e>1 and all sufficiently large m, we exhibit searching strategies that use a first batch of m non-adaptive questions and then, only depending on the answers to these m questions, a second batch of qe( m)− m non-adaptive questions. These strategies are automatically optimal. Since even in the fully adaptive case, qe( m)−1 questions do not suffice to find the unknown number, and qe( m) questions generally do not suffice in the non-adaptive case, the results of our paper provide e fault tolerant searching strategies with minimum adaptiveness and minimum number of tests. 相似文献
11.
This paper considers the problem of simultaneous H∞ control of a finite collection of linear time-invariant systems via a nonlinear digital output feedback controller. The main result is given in terms of the existence of suitable solutions to Riccati algebraic equations and a dynamic programming equation. Our main result shows that if the simultaneous H∞ control problem for k linear time-invariant plants of orders n1, n2,…, nk can be solved, then this problem can be solved via a nonlinear time-invariant controller of order nn1+ n2++ nk. 相似文献
12.
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. 相似文献
13.
针对泡型网络边连通度和限制边连通度小、容错能力弱的弊端,采用在泡型网络中增加通信线路的方法构建了高可靠性的增广泡型网络。通过构造最小边割的方法,证实了 n维增广泡型网络中去除任意不多于 n-1条边时,该增广泡型网络的任意两个节点之间依旧连通;通过构造最小限制边割的方法,证实了在不产生孤立节点的条件下, n维增广泡型网络中去除任意不多于2 n-3条边时,该增广泡型网络的任意两个节点之间依旧连通。依据上述结果,通过实例证明增广泡型网络的容错能力优于泡型网络。 相似文献
14.
Whether or not there is a difference of the power among alternating Turing machines with a bounded number of alternations is one of the most important problems in the field of computer science. This paper presents the following result: Let R( n) be a space and reversal constructible function. Then, for any k 1, we obtain that the class of languages accepted by off-line 1-tape rσ k machines running in reversal O( R( n)) is equal to the class of languages accepted by off-line 1-tape σ 1 machines running in reversal O( R( n)). An off-line 1-tape σ k machine M is called an off-line 1-tape rσ k machine if M always limits the non-blank part of the work-tape to at most O( R( n) log n) when making an alternation between universal and existential states during the computation. 相似文献
15.
We call a function f in n variables an order-configuration function if for any x1,…, xn such that xi1 … xin we have f( x1,…, xn) = xt, where t is determined by the n-tuple ( i1,…, in) corresponding to that ordering. Equivalently, it is a function built as a minimum of maxima, or a maximum of minima. Well-known examples are the minimum, the maximum, the median, and more generally rank functions, or the composition of rank functions. Such types of functions are often used in nonlinear processing of digital signals or images (for example in the median or separable median filter, min-max filters, rank filters, etc.). In this paper we study the mathematical properties of order-configuration functions and of a wider class of functions that we call order-subconfiguration functions. We give several characterization theorems for them. We show through various examples how our concepts can be used in the design of digital signal filters or image transformations based on order-configuration functions. 相似文献
16.
We propose a mathematical model for fault-tolerant routing based on acyclic orientations, or acorns, of the underlying network G=( V, E). The acorn routing model applies routing tables that store the set of parent pointers associated with each out-neighborhood defined by the acorn. Unlike the standard single-parent sink-tree model, which is vulnerable to faults, the acorn model affords a full representation of the entire network and is able to dynamically route around faults. This fault tolerance is achieved when using the acorn model as a multi-tree generator for gathering data at a destination node, as well as an independent tree generator for global point-to-point communication. A fundamental fault-tolerant measure of the model is the capacity of an acorn, i.e., the largest integer k such that each vertex outside the neighborhood N( v) of the destination v has at least k parent pointers. A capacity- k acorn A to destination v is k-vertex fault-tolerant to v. More strongly, we show A supports a k independent sink-tree generator, i.e., the parent pointers of each vertex w V− N( v) can be partitioned into k nonempty classes labeled 1,2,…, k such that any set of sink trees T1, T2,…, Tk are pairwise independent, where tree Ti is a sink tree generated by parent pointers labeled i together with the parent pointers into v. We present an linear time optimization algorithm for finding an acorn A of maximum capacity in graphs, based upon a minimax theorem. We also present efficient algorithms that label the parent pointers of capacity- k acorn A, yielding a k-independent sink tree generating scheme. 相似文献
17.
针对以超立方体网络为蓝本的多处理机系统的可靠性和容错能力的精准度量问题,结合多处理机系统遭受计算机病毒攻击时常常发生结构性故障的特点,研究了n维超立方体网络的结构连通性和子结构连通性评价问题。首先,使用构造n维超立方体网络的3路结构割的方法得到其3路结构连通度的一个上界;然后,使用构造 n维超立方体网络的3路子结构集的等价变换或约简变换的方法,得到其3路结构子连通度的一个下界;最后,利用任意网络的3路结构连通度不小于3路子结构连通度的性质,证实了超立方体网络的3路结构连通度和子结构连通度均为该超立方体网络维数的一半。这一结果表明,在3路结构故障模型下,破坏敌方以超立方体网络为底层拓扑的多处理系统至少需要攻击该系统中维数一半的3路结构或子结构。 相似文献
18.
An eNCE graph grammar is k-separated ( k1) if the distance between any two nonterminal nodes in any of its sentential forms is at least k. Let SEP k denote the class of graph languages generated by k-separated grammars. Then, SEP 1 (SEP 2) is the class of eNCE (boundary eNCE) graph languages, and so SEP 2SEP 1. Recently, Engelfriet (1991) showed that SEP 3SEP 2 and conjectured that, in fact, SEP k+1SEP k for each k 1. We prove this conjecture affirmatively. 相似文献
19.
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. 相似文献
20.
The distribution of black leaf nodes at each level of a linear quadtree is of significant interest in the context of estimation of time and space complexities of linear quadtree based algorithms. The maximum number of black nodes of a given level that can be fitted in a square grid of size 2 n × 2 n can readily be estimated from the ratio of areas. We show that the actual value of the maximum number of nodes of a level is much less than the maximum obtained from the ratio of the areas. This is due to the fact that the number of nodes possible at a level k, 0≤ k≤ n − 1, should consider the sum of areas occupied by the actual number of nodes present at levels k + 1, k + 2, …, n − 1. 相似文献
|