Information Technology Reference
In-Depth Information
then neither the algorithm
Al
g
1
is autonomous towards the
Al
g
2
nor the algorithm
Al
g
2
is autonomous towards the
Al
g
1
. As we can see from the example, gaining autonomy
of one component algorithm towards another component algorithm depends on the
appropriate decomposition of the initial complex algorithm.
2.5 Decomposition with the Use of the Concept
of the Cartesian Product Applied to the Set
U
Let us consider decomposition of the algorithm
Al
g
(
Al
g
=
(
), applying the
Cartesian product to the set of states
U
. Such a decomposition method seems to
be useful in practical applications, nevertheless, it results in component algorithms
which may often be mutually dependent and therefore that is more difficult for
parallel (independent) forming. As was mentioned above, the set
X
was associated
with the set of states
U
, which was the Cartesian product
X
U
,
F
)
=
X
1
×
X
2
(in the
general case
X
X
m
, see Sect.
2.4
). The function
f
, according to
the set theory definition of the function notion, may be considered as a set of pairs
(Sect.
2.4.1
):
=
X
1
×
X
2
×···×
x
)
x
,
(
x
,
such that
f
(
x
)
=
=
(
x
1
,
x
2
)
∈
where
x
X
x
=
(
x
1
,
x
2
)
∈
X
X
2
As a result, we may divide the function
f
into two disjoint subsets (generally, a
few disjoint subsets), each of them represents a certain component function being
the result of decomposition (division) of the initial function
f
(Fig.
2.4
).
Such functions as
f
1
and
f
2
map the set
X
onto
X
X
=
X
1
×
(
f
1
:
X
ₒ
X
,
f
2
:
X
ₒ
X
), and
the function
f
is decomposed into two functions
f
1
and
f
2
such that
f
=
f
1
∪
f
2
,
f
1
∩
f
2
=∅
. Because of the fact that the function
F
in the algorithm
Al
g
=
(
U
,
F
)
is a
partial function, the functions
f
and
f
1
as well as
f
2
are also partial functions.
As a result, we receive two algorithms
Al
g
1
for
which
x
1
and
x
2
may be treated as variables gaining the values form the sets
X
1
and
X
2
that realize the evolution of the states of the algorithms
Al
g
1
and
Al
g
2
.
These two algorithms may be treated as the decomposition of the algorithm
Al
g
=
=
(
X
,
f
1
)
and
Al
g
2
=
(
X
,
f
2
)
(
U
,
F
)
(or corresponding to it algorithm
Al
g
=
(
X
,
f
)
) realized with the use of the
Cartesian product applied to the set
U
.
Of course, from the practical point of view, in order to let the algorithms
Al
g
1
and
Al
g
2
be created independently (designed, programmed) these algorithms should
be mutually autonomous. Their transition functions would have the following form:
f
1
:
X
2
.
In practice these functions have the form
f
1
:
X
1
ₒ
X
1
and
f
2
:
X
2
ₒ
X
ₒ
X
and
f
2
:
X
ₒ
X
for
X
=
X
1
×
X
2
, which makes the component algorithms
Al
g
1
=
(
X
,
f
1
)
and
Al
g
2
=
(
X
,
f
2
)
non-autonomous.
