共查询到20条相似文献,搜索用时 15 毫秒
1.
The main problem of interval computations is as follows:given sets of possible valuesX i for variablesx i, and an algorithmf:R n → R, to.estimate the rangef(X 1, ..,X n ) of the possible values off(x 1, ...,x n ). In many real-life, situations setsX i are not intervals. To handle such problems, it is desirable to add set data type and operations with sets to a programming language. it is well known that the entire mathematics can be formulated in terms of sets. So, if we already have a set as a data type, why have anything else. The main reason, is that expression in terms of sets is often clumsy. To avoid this clumsiness, it has been suggested to use not only sets, but alsobags (multisets), in which an element can have multiple occurrences. Bags are used in many areas of Computer Science, and recently, several languages have appeared that use the bag as a basic data type. In this paper, we explain the main ideas behind bag languages, and we also show: · that bag languages are naturally parallelizable, thus leading to a parallelization of the coresponding generalized interval computations; · and that bag languages can be also helpfully applied to traditional interval computations (where setsX i are intervals). 相似文献
2.
One of the main problems of interval computations is, given a functionf(x 1, ...,x n ) andn intervals x1, ..., x n , to compute the range y=f(x1, ..., x n ). This problem is feasible for linear functionsf, but for generic polynomials, it is known to be computationally intractable. Because of that, traditional interval techniques usually compute theenclosure of y, i.e., an interval that contains y. The closer this enclosure to y, the better. It is desirable to describe cases in which we can compute theoptimal enclosure, i.e., the range itself. In this paper, we describe a feasible algorithm for computing the optimal enclosure forfractionally linear functionsf. Applications of this result tointelligent control are described. 相似文献
3.
In the present paper a new method is given for the numerical treatment of the initial problemsy (n)=f(x,y,y′, ...,y (n?1),y (i) (x o )=y o (i) , i=0, 1, ...,n?1. This method is an one-step process of order four. For a class of linear differential equations the exact solution is obtained. Moreover some numerical results are presented. 相似文献
4.
In many real-life situations, we want to reconstruct the dependencyy=f(x 1,…, xn) from the known experimental resultsx i (k) , y(k). In other words, we want tointerpolate the functionf from its known valuesy (k)=f(x 1 (k) ,…, x n (k) ) in finitely many points $\bar x^{(k)} = (x_1^{(k)} , \ldots ,x_n^{(k)} )$ , 1≤k≤N There are many functions that go through given points. How to choose one of them? The main goal of findingf is to be able to predicty based onx i. If we getx i from measurements, then usually, we only getintervals that containx i. As a result of applyingf, we get an interval y of possible values ofy. It is reasonable to choosef for which the resulting interval is the narrowest possible. In this paper, we formulate this choice problem in mathematical terms, solve the corresponding problem for several simple cases, and describe the application of these solutions to intelligent control. 相似文献
5.
Tamm U. 《Information and Computation》1995,116(2)
The communication complexity of a function f denotes the number of bits that two processors have to exchange in order to compute f(x, y), when each processor knows one of the variables x and y, respectively. In this paper the deterministic communication complexity of sum-type functions, such as the Hamming distance and the Lee distance, is examined. Here f: X × X → G, where X is a finite set and G is an Abelian group, and the sum-type function fn:Xn × Xn → G is defined by fn((x1, ..., xn), (y1, ..., yn)) = Σni=1f(xi, yi) Since the functions examined are also translation-invariant, their function matrices are simultaneously diagonalizable and the corresponding eigenvalues can be calculated. This allows to apply a rank lower bound for the communication complexity. The best results are obtained for G =
/2
. For prime numbers |X| in this case the communication complexity of all non-trivial sum-type functions is determined exactly. Exact results are also obtained for the parity of the Hamming distance and the parity of the Lee distance. For the Hamming distance and the Lee distance exact results are only obtained for special parameters n and |X|. 相似文献
6.
We consider functions f(x
1, ..., x
n
, z
1, ..., z
m
) of k-valued logic, where x
1, ..., x
n
are ordinary k-valued variables and z
1, ..., z
m
are improper k-valued variables indicating external factors. An algorithm is presented for designing a circuit of k-valued functional elements, which realizes a k-valued indicator z, z {z
1, ..., z
m
}. 相似文献
7.
Dipl.-Ing. Dr. techn. R. Hafner 《Computing》1972,10(4):335-351
When objects are scattered at random in the plane or in space, some of them overlap to form clumps. It is the object of the present paper to study the asymptotic distribution of the number of clumps of given size and topological structure generated within the following model: Ifx 1, ...,x n are points in ? n andU=-U?? n is a symmetric set, then the pointsx i andx j are said tooverlap or rather to form aU-coincidence, ifx i ?x j ∈U. Adjoining tox 1, ...,x n andU, the graphG(x 1, ...,x n ;U)?({1, ..., n}, {[i, j]:1≤ix i ?x j ∈U}), the so calledcoincidence-graph, we ask for the number of connected components of this graph isomorphic to a given graphH and call this numberL9x 1, ...x n ;U, H). In the paper, the asymptotic distribution ofL(...) under various assumptions about the distribution of the pointsx 1, ...,x n and the size ofU is studied. Depending on these assumptions, we prove that the asymptotic distribution ofL(...) is either Poisson or normal. 相似文献
8.
In many real-life applications, physical considerations lead to the necessity to consider the smoothest of all signals that is consistent with the measurement results. Usually, the corresponding optimization problem is solved in statistical context. In this paper, we propose a quadratic-time algorithm for smoothing aninterval function. This algorithm, givenn+1 intervals x0, ..., x n with 0 ∈ x0 and 0 ∈ x n , returns the vectorx 0, ...,x n for whichx 0=x 0=0,x i ∈ x i , and Σ(x i+1?x i )2 → min. 相似文献
9.
Amos Beimel Sebastian Ben Daniel Eyal Kushilevitz Enav Weinreb 《Computational Complexity》2014,23(1):1-42
We consider several questions inspired by the direct-sum problem in (two-party) communication complexity. In all questions, there are k fixed Boolean functions f 1,…,f k and each of Alice and Bob has k inputs, x 1,…,x k and y 1,…,y k , respectively. In the eliminate problem, Alice and Bob should output a vector σ1,…,σ k such that f i (x i , y i ) ≠ σ i for at least one i (i.e., their goal is to eliminate one of the 2 k output vectors); in the choose problem, Alice and Bob should return (i, f i (x i , y i )), for some i (i.e., they choose one instance to solve), and in the agree problem they should return f i (x i , y i ), for some i (i.e., if all the k Boolean values agree then this must be the output). The question, in each of the three cases, is whether one can do better than solving one (say, the first) instance. We study these three problems and prove various positive and negative results. In particular, we prove that the randomized communication complexity of eliminate, of k instances of the same function f, is characterized by the randomized communication complexity of solving one instance of f. 相似文献
10.
The problem of locating local maxima and minima of a function from approximate measurement results is vital for many physical applications: inspectral analysis, chemical species are identified by locating local maxima of the spectra; inradioastronomy, sources of celestial radio emission, and their subcomponents, are identified by locating local maxima of the measured brightness of the radio sky;elementary particles are identified by locating local maxima of the experimental curves. Since measurements are never absolutely precise, as a result of the measurements, we have aclass of possible functions. If we measuref(x i ) with interval uncertainty, this class consists of all functionsf for whichf(x i ) ε [y i ??, y i +?], wherey i are the results of measuringf(x i ), andε is the measurement accuracy. For this class, in [2], a linear-time algorithm was described. In real life, a measuring instrument can sometimes malfunction, leading to the so-calledoutliers, i.e., measurementsy i that can be way offf(x i ) (and thus do not restrict the actual valuesf(x i ) at all). In this paper, we describerobust algorithms, i.e., algorithms that find the number of local extrema in the presence of possible outliers. These algorithms solve an important practical problem, but they are not based on any new mathematical results: they simply use algorithms from [2] and [3]. 相似文献
11.
《Information and Software Technology》2002,44(2):123-132
An important application of the dynamic program slicing technique is program debugging. In applications such as interactive debugging, the dynamic slicing algorithm needs to be efficient. In this context, we propose a new dynamic program slicing technique that is more efficient than the related algorithms reported in the literature. We use the program dependence graph as an intermediate program representation, and modify it by introducing the concepts of stable and unstable edges. Our algorithm is based on marking and unmarking the unstable edges as and when the dependences arise and cease during run-time. We call this algorithm edge-marking algorithm. After an execution of a node x, an unstable edge (x, y) is marked if the node x uses the value of the variable defined at node y. A marked unstable edge (x, y) is unmarked after an execution of a node z if the nodes y and z define the same variable var, and the value of var computed at the node y does not affect the present value of var defined at the node z. We show that our algorithm is more time and space efficient than the existing ones. The worst case space complexity of our algorithm is O(n2), where n is the number of statements in the program. We also briefly discuss an implementation of our algorithm. 相似文献
12.
I. M. Sobol 《Mathematical Models and Computer Simulations》2011,3(4):419-423
A mathematical model f(x) given in the unit n-dimensional cube, where x = (x 1, ..., x n ), is considered. How can one estimate the global sensitivity of f(x) with respect to x i ? If f(x) ∈ L 2, global sensitivity indices help answer this question. Being less reliable, derivative-based sensitivity criteria are sometimes easier-to-compute. In this work, a new derivative-based global sensitivity criterion is compared to the respective global sensitivity index. These estimates are proven to coincide in the particular case when f(x) linearly depends on x i . However, Monte Carlo approximations to the derivative-based criterion converge faster. Thus, the global derivative-based sensitivity criterion can prove useful when f(x) depends on x i almost linearly. It can be also used to find nonessential variables x i . 相似文献
13.
The FORTRAN code calculates, plots and labels approximate contour linesz(x, y)=c for data that are given as a rectangular arrayz ik =z(x i ,y k ). 相似文献
14.
Adam Strzeboński 《Journal of Symbolic Computation》2011,46(11):1284-1290
We present a generalization of the Cylindrical Algebraic Decomposition (CAD) algorithm to systems of equations and inequalities in functions of the form p(x,f1(x),…,fm(x),y1,…,yn), where p∈Q[x,t1,…,tm,y1,…,yn] and f1(x),…,fm(x) are real univariate functions such that there exists a real root isolation algorithm for functions from the algebra Q[x,f1(x),…,fm(x)]. In particular, the algorithm applies when f1(x),…,fm(x) are real exp-log functions or tame elementary functions. 相似文献
15.
In the present paper a new exponentially fitted one-step method is given for the numerical treatment of the initial value problemy (n)=f(x, y, y′, ..., y (n?1)),y (j) (x 0)=y 0 (j) j=0, 1, ...n?1. The method is given by a local linearisation off(x, y, y′, ..., y (n?1)). Using new functions the solution of a special linear differential equation of then-th order with constant coefficients is transformed in such a way so that it no longer contains numerical singularities. The efficiency of the method is demonstrated by several numerical stiff-examples. 相似文献
16.
One of the main objectives of interval computations is, given the functionf(x 1, ...,x n ), andn intervals $\bar x_1 ,...,\bar x_n$ , to compute the range $\bar y = f(\bar x_1 ,...,\bar x_n )$ . Traditional methods of interval arithmetic compute anenclosure $Y \supseteq \bar y$ for the desired interval $\bar y$ , an enclosure that is often an overestimation. It is desirable to know how close this enclosure is to the desired range interval. For that purpose, we develop a new interval formalism that produces not only the enclosure, but also theinner estimate for the desired range $\bar y$ , i.e., an interval y such that $y \subseteq \bar y$ . The formulas for this new method turn out to be similar to the formulas of Kaucher arithmetic. Thus, we get a new justification for Kaucher arithmetic. 相似文献
17.
In many problems in science and engineering ranging from astrophysics to geosciences to financial analysis, we know that a physical quantity y depends on the physical quantity x, i.e., y = f(x) for some function f(x), and we want to check whether this dependence is monotonic. Specifically, finitely many measurements of xi and y = f(x) have been made, and we want to check whether the results of these measurements are consistent with the monotonicity of f(x). An efficient parallelizable algorithm is known for solving this problem when the values xi are known precisely, while the values yi are known with interval uncertainty. In this paper, we extend this algorithm to a more general (and more realistic) situation when both xi and yi are known with interval uncertainty. 相似文献
18.
João B. Oliveira 《Reliable Computing》1996,2(3):299-320
This paper presents algorithms evaluating sharper bounds for interval functionsF(X) :IR n →IR. We revisit two methods that use partial derivatives of the function, and develop four other inclusion methods using the set of slopesS f (x, z) off atx εX with respect to somez εIR n . All methods can be implemented using tools that automatically evaluate gradient and slope vectors by using a forward strategy, so the complex management of reverse accumulation methods is avoided. The sharpest methods compute each component of gradients and slopes separately, by substituting each interval variable at a time. Backward methods bring no great advantage in the sharpest algorithms, since object-oriented forward implementations are easy and immediate. Fischer's acceleration scheme [2] was also tested with interval variables. This method allows the direct evaluation of the productf′(x) * (x?z) as a single real number (instead of working with two vectors) and we used it to computeF′(X) * (X?z) for an interval vectorX. We are led to decide against such acceleration when interval variables are involved. 相似文献
19.
Assume that n is a positive integer with n?2. It is proved that between any two different vertices x and y of Qn there exists a path Pl(x,y) of length l for any l with h(x,y)?l?n2−1 and 2|(l−h(x,y)). We expect such path Pl(x,y) can be further extended by including the vertices not in Pl(x,y) into a hamiltonian path from x to a fixed vertex z or a hamiltonian cycle. In this paper, we prove that for any two vertices x and z from different partite set of n-dimensional hypercube Qn, for any vertex y∈V(Qn)−{x,z}, and for any integer l with h(x,y)?l?n2−1−h(y,z) and 2|(l−h(x,y)), there exists a hamiltonian path R(x,y,z;l) from x to z such that dR(x,y,z;l)(x,y)=l. Moreover, for any two distinct vertices x and y of Qn and for any integer l with h(x,y)?l?2n−1 and 2|(l−h(x,y)), there exists a hamiltonian cycle S(x,y;l) such that dS(x,y;l)(x,y)=l. 相似文献
20.
A mathematical basis is given for comparing the relative merits of various techniques used to reduce the order of large linear and non-linear dynamics problems during their numerical integration. In such techniques as Guyan-Irons, path derivatives, selected eigenvectors, Ritz vectors, etc., the nth order initial value problem of for t > 0, y(0) given] is typically reduced to the mth order (m ? n) problem of for t > 0, z(0) given] by the transformation where P changes from technique to technique. This paper gives an explicit approximate expression for the reduction error ei in terms of P and the Jacobian of f. It is shown that: (a) reduction techniques are more accurate when the time rate of change of the response y is relatively small; (b) the change in response between two successive stations contributes to the errors at future stations after the change in response is transformed by a filtering matrix H, defined in terms of P; (c) the error committed at a station propagates to future stations by a mixing and scaling matrix G, defined in terms of P, Jacobian of f, and time increment h. The paper discusses the conditions under which the reduction errors may be minimized and gives guidelines for selecting the reduction basis vector, i.e. the columns of P. 相似文献