Читать книгу Mathematics of Harmony as a New Interdisciplinary Direction and “Golden” Paradigm of Modern Science - Alexey Stakhov - Страница 26

The essence of the method of the recurrent relations in connection with synthesizing of the optimal (n, k, 0)-algorithms is as follows. We do the so-called inductive hypothesis. Suppose that for some n and k, there exists the optimal (n, k, 0)-algorithm that implements on the segment AB the (n, k)-exactness equal to F(n, k). In other words, our inductive hypothesis consists in the fact that the optimal (n, k, 0)-algorithm divides the segment AB into F(n, k) equal intervals of the unit length Δ = 1, that is,

Now, let the first step of the optimal (n, k, 0)-algorithm on the segment AB be in the enclosing of the k indicatory elements on the segment AB, as shown in Fig. 1.8.

Fig. 1.8. The first step of the optimal (n, k, 0)-algorithm.

After the first step, by using the indications of k IE, we get the (k + 1)th situations:

In this case, all the segments in Fig. 1.8 are connected by the following relationship:

Let’s consider the situation For this situation, before taking the next step, we have (n – 1) steps because one step has already been used, and k IE, which, according to the restriction S = 0, can be enclosed to some points of the new uncertainty interval CjCj+₁, which contains point X. But then each of the situations (1.15), that arose after the first step, is not distinguished from the initial situation in Fig. 1.8. Only the number of steps for the realization of the measurement algorithm, which operates on the new segment CjCj+i, decreased to (n – 1), and then, in this situation, for searching the coordinate of point X, we can use the new uncertainty interval CjCj+i the optimal (n – 1, k, 0)-algorithm, which, according to the inductive hypothesis (1.14), divides the segment C_jC_j+1 on F(n – 1, k) equal intervals of the unit length Δ = 1, that is,

The above reasoning is valid for all the (k + 1) situations (1.15), that is, for some of the segments (1.15), the relation (1.17) is fulfilled. By using now the relation (1.16), connecting the initial segment AB with (k+1) segments (1.15), as well as expressions (1.14) and (1.17), we obtain the following recurrent formula for the (n, k)-exactness of the optimal (n, k, 0)-algorithm:

Now, we will try to solve the recurrent relation (1.18), that is, to obtain the expression for the efficiency function F(n, k)in the explicit form. For this, we use for the function F(n – 1, k)in the formula (1.18) the same recurrent formula (1.18), that is, we represent the recurrent formula (1.18) in the form:

Continuing this process, that is, sequentially decomposing in (1.19) all the expressions for F(n – 2, k), F(n – 3, k), …, F(2, k) by the recurrent formula (1.18), we get the following expression for (1.18):

In the expression (1.20), we have the member F(1, k), whose value is unknown to us. According to our definitions, the member F(1, k) is the (1, k)-exactness of the optimal (1, k, 0)-algorithm, that is, the measurement algorithm, which is realized in the first step and uses k IE. It is clear that in this case the optimal strategy consists in dividing the last uncertainty interval into (k +1) equal parts by using k IE; the (1, k)-exactness of this algorithm is equal to

Substituting the expression (1.21) into (1.20), we obtain the expression for the efficiency function of the optimal (n, k, 0)-algorithm in the explicit form:

It is easy to understand that the strategy of the optimal (n, k, 0)-algorithm at each step is very simple: it is necessary to divide the uncertainty interval by using k IE into (k +1) equal parts at each step.