DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 2

V.G. Kolesnyk


This is the next essay from the cycle describing the theory of decomposition schemes as the theory of applied algorithms. A decomposition scheme is being considered as a prototype of an applied algorithm. The aim of the essay is to consider the turning of a decomposition scheme into an algorithm in the case when the processed input P-data are placed in various media. R-data kinds of division are described and factors of their fragments and components placing are considered. For all the variants of R-data division the changes into the canonic algorithm which are necessary for their union are described. From the standpoint of the complexity changes in algorithm vary from primitives in several imperative operators to algorithmic constructions with loops and control constructs. For making the algorithmic constructions there is the mechanism of synthesis offered – bound to the levels of algorithm tree. For purposes of the comparative analysis the schemes of decomposition and applied algorithm there was offered the notion of NAC-conditionality as more fitting that the graph isomorphism. It is shown that description of the variants and factors of R-data division is declarative. This work endorses the idea that the theory of decomposition schemes allows to research the algorithms systematically. The aim of the research is to develop the mechanism of synthesis of the applied algorithms. The descriptions of the decomposition schemes are used as raw data for generating.


algorithm; design; data; fragment; structure; node; level; area; section; merger; synthesis


Alferova Z.A. The theory of algorithms. Moscow: Statistics, 1973. – 164 p.


  • There are currently no refbacks.