Information Technology Reference
In-Depth Information
2.3 Decomposition Inspired by the Division of a Set
The algorithm
Al
g
=
(
is defined by two sets: the set of states U, and the set
defining the transition between the states, which is the function
F
; in other words the
set of pairs (according to the theory of the set of the definition of the function).
The decomposition of the algorithm
Al
g
=
(
U
,
F
)
is a decomposition of the set of
states
U
into the divided subsets (for instance two subsets
U
1
,
U
,
F
)
U
2
) and decomposition
of the function
F
(considered as the set of pairs) into two functions
F
1
,
F
2
:
U
=
U
1
∪
U
2
,
U
1
∩
U
2
=∅
(2.4)
satisfying the following conditions:
F
=
F
1
∪
F
2
,
F
1
∩
F
2
=∅
and
F
1
:
U
1
ₒ
U
1
,
F
2
:
U
2
ₒ
U
2
,
(2.5)
which in applications may be difficult or even impossible to realize.
The most frequent and possible decomposition in practice is the following:
F
1
:
U
1
ₒ
U
,
F
2
:
U
2
ₒ
U
,
(2.6)
where the sets of values of these functions is the set
U
.
Let us consider the problemdenoted by
u
0
to be solvedwith the use of decomposed
algorithms. Then, we can accept that the algorithm
Al
g
=
(
U
,
F
)
is decomposed into
u
l
+
1
1
u
2
}
,
two component algorithms
Al
g
1
=
(
.
The completion of the set
U
1
with the element
u
2
and the set
U
2
with the
element
u
l
+
1
allows the realization of operation of calling a subprogram from the
main program (
call
), and the return from the subprogram to the main program
(
return
).
For a given problem with the initial value
u
0
U
1
∪{
F
1
)
and
Al
g
2
=
(
U
2
∪{
}
,
F
2
)
∈
U
we may consider the following
realization of a decomposed algorithm (Fig.
2.1
):
u
1
)
=
(
u
1
,
u
1
,...,
u
l
1
,
u
2
),
Exec
(
Al
g
1
,
u
l
+
1
1
u
2
)
=
(
u
2
,
u
2
,...,
u
2
,
Exec
(
Al
g
2
,
),
(2.7)
u
l
+
1
1
u
l
+
1
1
u
1
)
Exec
(
Al
g
1
,
)
=
(
,...,
u
l
+
1
1
u
2
=
u
l
1
),
u
2
),
F
1
(
=
F
2
(
where the problem (
u
0
) is denoted by
u
1
, and the result by
u
k
.
Fig. 2.1
Schema of the
decomposition of an
algorithm through the
division of the set
U
Alg
1
u
0
F
1
F
1
F
1
…
…
u
1
1
u
1
l
u
1
l+1
u
1
k
F
1
F
2
F
2
…
u
2
0
u
2
m
Alg
2
