Agent Versus Decomposition of an Algorithm - A Perspective on Agent Systems - page 8

where U —is a non-empty set
F —is the function F

: ₒ

U .
The function F is a partial function which means that the domain of the function
F is a subset of the set U .
The components of the set U are called the states of algorithm Al g . The realization
of algorithm Al g for the particular initial state u 0

U

u 0 ∈ U (is denoted by Exec ( Al g, ) )

will be a finite or an infinite sequence [41]:

u 0 u 0 u 1 u i u i + 1 u k

Exec ( Al g, ) = ( , ,..., , ,..., ) (2.2)

such that

u i + 1 u i u k = F ( ), − final state (2.3)

The above sequence, being the realization of the algorithm Al g , is finite if the
final state u k exists and it proceeds when the state u k does not belong to the
domain of the function F (but it belongs to the range of function F ). So the final
states of the algorithm Al g are those elements of the set U which belong to the
domain of the function F . Further, we will take into account only these algo-
rithms whose realization constitute the finite sequences (Formula 2.2 ) mentioned
above.
Let us accept that the algorithm is used as a solution to a certain problem. With
the use of the above denotations a given problem is represented by u 0 , however,
the solution to a problem is represented by u k and the sequence Exec

u 0

(

Al g,

) =

u 0 u 1 u i u i + 1 u k

( , ,..., , ,..., ) is the schema or the method of solving a given

problem.
In practical applications, when we form an algorithm which is too complicated,
it is interesting to decompose it into a few simpler algorithms. The algorithm Al g
will be referred to as a complex algorithm, and the algorithms it was decomposed
(distributed) to—component algorithms Al g 1 ,...,

Al g n .
For this reason, it is necessary to define the decomposition process of a certain
algorithm. We may say that a certain algorithm Al g was decomposed into component
algorithms Al g 1 , Al g n , when by using component algorithms we receive

the same result as with the use of a complex algorithm Al g . What is more, we expect
component algorithms Al g 1 ,

Al g 2 ,...,

Al g n to be independent to such an extent that
they could be created (designed, programmed) separately and in parallel—at the same
time (which should accelerate the process of complex algorithms). It is possible in
certain cases.
Along with further considerations we will often limit ourselves to two component
algorithms Al g a , Al g b (sometimes referred to as Al g 1 , Al g 2 ), which does not limit
the generality of the above considerations. The problem of decomposition may
be considered from different perspectives. Here, we will limit ourselves to two
approaches: decomposition inspired by the division of the set of states into a few
subsets (e.g. two), and decomposition inspired by the concept of the Cartesian
product [180].

Al g 2 ,...,