Information Technology Reference
In-Depth Information
Example 1
Let us consider the following example of an algorithm:
U
={
a
,
b
,
c
,
d
}
,
(2.25)
F
(
a
)
=
b
,
F
(
b
)
=
c
,
F
(
c
)
=
d
Let us apply decomposition, using the concept of the Cartesian product applied
to the set
U
:
X
1
={
,
}
,
X
2
={
,
}
0
1
0
1
(2.26)
=
X
1
×
={
(
,
), (
,
), (
,
), (
,
)
}
X
X
2
0
0
0
1
1
0
1
1
We may define the following correspondence between the elements of the set
U
and the set
X
:
a
corresponds with
(
0
,
0
),
b
corresponds with
(
0
,
1
),
(2.27)
c
corresponds with
(
1
,
0
),
d
corresponds with
(
1
,
1
)
The definition of the function
f
may be presented as follows:
f
((
0
,
0
))
=
(
0
,
1
),
f
((
0
,
1
))
=
(
1
,
0
),
f
((
1
,
0
))
=
(
1
,
1
)
(2.28)
The component algorithms
Al
g
1
and
Al
g
2
may be defined as follows—the
algorithm
Al
g
1
:
Al
g
1
=
(
X
,
f
1
)
f
1
(
0
,
1
)
=
(
1
,
0
)
(2.29)
and the algorithm
Al
g
2
:
Al
g
2
=
(
X
,
f
2
)
(2.30)
f
2
(
0
,
0
)
=
(
0
,
1
),
f
2
(
1
,
0
)
=
(
1
,
1
)
We note that for the algorithm
Al
g
2
:
∀
z
∈
X
1
:
f
2
(
z
,
0
)
=
(
z
,
1
)
(2.31)
(which allows to state that the algorithm
Al
g
2
is autonomous towards the algorithm
Al
g
1
).
However,
Al
g
1
is non-autonomous (interaction relationship) because it changes
the state
x
2
of the algorithm
Al
g
2
.
The function
f
1
or f2 is sometimes informally denoted by
f
2
=
(
•
,
0
)
=
(
•
,
1
)
,
where
denotes an optional value (in example 0 or 1).
However, if we change the functions and the component algorithms will be defined
as follows:
•
Al
g
1
=
(
X
,
f
1
)
f
1
(
0
,
0
)
=
(
0
,
1
),
f
1
(
1
,
0
)
=
(
1
,
1
)
(2.32)
Al
g
2
=
(
X
,
f
2
)
f
2
(
0
,
1
)
=
(
1
,
0
)
