共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
Judea Pearl 《Artificial Intelligence》1980,14(2):113-138
The model most frequently used for evaluating the behavior of game-searching methods consists of a uniform tree of height h and a branching degree d, where the terminal positions are assigned random, independent and identically distributed values. This paper highlights some curious properties of such trees when h is very large and examines their implications on the complexity of various game-searching methods.If the terminal positions are assigned a WIN-LOSS status with the probabilities P0 and 1 ? P0, respectively, then the root node is almost a sure MIN or a sure LOSS, depending on whether P0 is higher or lower than some fixed-point probability . When the terminal positions are assigned continuous real values, the minimax value of the root node converges rapidly to a unique predetermined value , which is the of the terminal distribution.Exploiting these properties we show that a game with WIN-LOSS terminals can be solved by examining, on the average, terminal positions if positions if and positions if , the former performance being optimal for all search algorithms. We further show that a game with continuous terminal values can be evaluated by examining an average of positions, and that this is a lower bound for all directional algorithms. Games with discrete terminal values can, in almost all cases, be evaluated by examining an average of terminal positions. This performance is optimal and is also achieved by the ALPHA-BETA procedure. 相似文献
3.
J.L. Brown 《Information Sciences》1977,12(2):93-103
A given deterministic signal x(.) is distorted by passing it through a linear time-invariant filter and also by subjecting it to the action of an instantaneous nonlinearity. The resulting time crosscorrelation of the two distorted versions of the original signal is expressed by the function , where x(.) is the given signal, k(.) is the nonnegative definite impulse response of the linear filter, and g(.) is the output-input characteristic of the zero-memory nonlinear device. The problem considered is that of determining conditions on the pair (x,g) such that R2(s) ? R2(0) for all s and any choice of nonnegative definite filter function k; the principal result is the formulation of a necessary and sufficient condition for R2 to have a global maximum at the origin. In particular, the peak value occurs at the origin if and only if is real and nonnegative for all ω ? 0, where Gx(.) and X(.) are the Fourier transforms of g[x(.)] and x(.), respectively. An equivalent condition is that the correlation function , previously studied by Richardson, be nonnegative definite.Several examples are given, and it is shown that, unlike the case for R1(.), monotonicity of g(.) is not a sufficient condition for R2(.) to have a global maximum at s = 0 independently of the choice of filter characteristic k. Certain extensions of these results are given for the case when x(.) is a Gaussian random input. 相似文献
4.
5.
《Theoretical computer science》2002,284(2):199-206
We discuss the uniform computational complexity of the derivatives of C∞-functions in the model of Ko and Friedman (Ko, Complexity Theory of Real Functions, Birkhäuser, Basel, 1991; Ko, Friedman, Theor. Comput. Sci. 20 (1982) 323–352). We construct a polynomial time computable real function g∈C∞[−1,1] such that the sequence is not bounded by any recursive function. On the other hand, we show that if f∈C∞[−1,1] is polynomial time computable and the sequence of the derivatives of f is uniformly polynomially bounded, i.e., |f(n)(x)| is bounded by 2p(n) for all x∈[−1,1] for some polynomial p, then the sequence is uniformly polynomial time computable. 相似文献
6.
Roger D. Nussbaum 《Systems & Control Letters》1983,3(5):243-246
A.S. Morse has raised the following question: Do there exist differentiable functions with the property that for every nonzero real number λ and every (x0, y0) ∈ 2 the solution (x(t),y(t)) of , , , is defined for all t ? 0 and satisfies and y(t) is bounded on [0,∞)? We prove that the answer is yes, and we give explicit real analytic functions f and g which work. However, we prove that if f and g are restricted to be rational functions, the answer is no. 相似文献
7.
Mituhiko Araki 《Systems & Control Letters》1985,6(1):1-5
It is proved that, for a given stable transfer matrix G(s), there exists a constant diagonal matrix W which makes WG(s) positive-real if Re gii(jω) ≥ 0 and I?? is an M-matrix where ? = (?jk) is defined by ?ii = 0 and . 相似文献
8.
We construct a sequence of monotone Boolean functions hn :{0, 1}n→{0, 1}n, such that the monotone complexity of hn is of order . This result includes the largest known lower bound of this kind. Previously there were an bound for the Boolean matrix product, an bound for Boolean sums and an bound by the author for the same functions hn. This new lower bound is proved by new methods which probably will turn out to be useful also for other problems. 相似文献
9.
Michael C. Loui 《Theoretical computer science》1981,15(3):311-320
Let L be a language recognized by a nondeterministic d-dimensional Turing machine with one worktape head of time complexity T(n). Then L can be recognized by a deterministic Turing machine of space complexity . The proof employs a generalization of crossing sequences. 相似文献
10.
Amir Schorr 《Information Processing Letters》1983,17(2):103-106
It is proven that any (uniform) family of physical parallel devices, recognizing a language C? with time-complixity TP(n), can be simulated by a (uniform) family of sequential devices with time-complexity (d is a constant, depending on the technology, but not greater than 13). 相似文献
11.
J.M.F. Chamayou 《Computer Physics Communications》1980,21(2):145-161
A method which consists in shifting different histograms of the same spectrum and then taking their average is presented in order to smooth the data and to increase the localization accuracy and separation of the peaks. The statistical properties of this method are investigated. The average of two histograms with shifted bin limits is studied. It is shown that for histograms with random bin limits, distributed according to ; where the standard deviation σ is very small compared to the difference of the means (μi+1 ? μi) for ll i the zero order approximation to the variance of this histogram is given by: , where and g is an unknown function fitted by the histogram. Formula (1) gives also the relation: , when H1 and H2 have stochastically independent bin limits.When the histogram H is considered as a spline function S of order one it is shown that for the minimization criterion with respect to the coefficient of the spline: , the following result holds: , where . If the number of shifted histograms tends to infinity, then , where , and h is a constant bin size. Then . Extensions to two-dimensional histograms and to higher order (empirical distributions) are presented. 相似文献
12.
In [5] the notion of an L form F defining a family d(F) of languages by means of X-interpretations has been introduced. Here X is one of a number of possible variations of the notion of interpretation originally used in [1] for grammar forms. In this paper it is shown that the questions whether for L forms F and F1 is decidable, if deterministic interpretations of PDOL systems are considered, where L(F) and L(F1) contain at most one word of length n for any n ? 0, and it is shown that same question is undecidable, if full or uniform interpretations are chosen. In contrast to this, no such results are known for grammar forms at this point. 相似文献
13.
This note supplements a result of Inoue and Takanami (1980) who showed that for any function L(m) such that (i) L(m)?log m, and (ii) , the class of sets of square tapes accepted by deterministic three-way L(m) tape-bounded two-dimensional Turing machines is incomparable with the class of sets of square tapes accepted by nondeterministic (resp. deterministic) two-dimensional finite automata. 相似文献
14.
15.
William P. Wardlaw 《Computers & Education》1978,2(3):247-257
Two examples are given in which the computer was used to supplement intuition in abstract algebra. In the first example, the computer was used to search Cayley tables of 4 element groupoids to find those which are 5-associative but not 4-associative. (n-associative means that the product of any n elements is independent of the way the factors are grouped by parentheses.) The computer generated examples suggested the existence of n element groupoids which are (2n?2+1)-associative but not (2n-2)-associative, for each integer n≧4.In the second example, the computer counted the numbers g2(m) of invertible 2×2 matrices with entries chosen from the ring Zmof integers, for m = 2, 3, 4,…, 18. The insight gained from these results led to a proof that there are invertible n×n matrices over Zm.Some applications to graduate and undergraduate instruction are indicated. 相似文献
16.
17.
18.
19.
Leszek Demkowicz Andrzej Karafiat Tadeusz Liszka 《Computer Methods in Applied Mechanics and Engineering》1984,42(3):343-355
The proof of convergence of the finite difference method with arbitrary irregular meshes for some class of elliptic problems is presented. By the use of the truncation error technique and stability analysis it was showed that , i.e., the solution uh converges linearly with the size of the star. Correctness of this theorem was also confirmed by numerical tests. 相似文献
20.
A. Nozaki 《Journal of Computer and System Sciences》1979,19(3):309-315
The number of required deques for sorting all sequences of n items in a parallel or series network of deques is considered. It is shown that the optimal number of required deques is for a parallel network, while it is O(log n) for a series network. These orders, and O(log n), also remain valid for the networks of restricted deques. 相似文献