DS-THEORY AS A PROTOTYPE OF THE THEORY OF APPLIED ALGORITHMS

 

DS-THEORY AS A PROTOTYPE OF THE THEORY OF APPLIED ALGORITHMS

V. G. Kolesnyk

The notion of the decomposition scheme as a core for DS-theory is proposed and described here. The notions of clump-property and algorithmic dependence are also described. Decomposition scheme is proposed to be used taking into account its algorithmic nature as the basis for building universal (canonical) algorithm. The questions of the canonical algorithm transformation into the specific application-oriented algorithms are discussed. The operations over the decomposition schemes which are itself operations over algorithms are described.

Introduction

The notion of the decomposition scheme as a core for DS-theory is proposed and described here. The

notions of clump-property and algorithmic dependence are also described. Decomposition scheme is proposed to be used taking into account its algorithmic nature as the basis for building universal (canonical) algorithm. The questions of the canonical algorithm transformation into the specific application-oriented algorithms are discussed. The operations over the decomposition schemes which are itself operations over algorithms are described.

The description of the theoretical model, called the decomposition schemes (DS), is proposed in the article. The decomposition scheme is an integral part of the theory of decomposition schemes (algorithmic theory of decomposition schemes – DSA-theory). DSA-theory is considered as a theory or as a prototype of the theory for the design of applied algorithms. The software engineering [1, 2] needs a similar theory.

The use of the method for structured programming based on correspondences between the data structure and program structure - JSP [3], Logical Construction of Programs [4] and R-technology [5] - preceded the creation of a theoretical model and a DSA theory. At some point, a number of researchers independently of each other drew attention to the fact that the structure of the data being processed can determine the structure of the program. The class of such programs is quite large. Many programmers of practitioners who developed programs for processing linear files and hierarchical databases saw a similar dependence. The main disadvantage of the method was that there was no clear and detailed way to determine the data structure.

As a result of the search, the author found that it is the decomposition scheme that determines the data structure and indirectly determines the structure of the program. Thus, the main ideas of the DSA-theory appeared as a result of attempts to develop a programming method based on the data structure with a view to extending its scope [6] and with a view to deeper substantiation of the method itself [7]. The decomposition scheme in the methodical plan answered questions of designing algorithms for data processing in the 70s and 80s. But the potential of DS as a means of designing algorithms is much broader and therefore it is the basis of the DSA-theory described below.

The purposes of the creation and development of DSA-theory are as follows:

- reduction of the complexity of algorithms due to a system of more capacious concepts;

- reducing the complexity of algorithms by creating graphical tools for designing algorithms;

- creation of algorithms generation principles.

Understanding the importance of capacious concepts for software engineering is in the scientific community [8]. The implementation of this approach – the use of capacious concepts – was the creation of algorithmic languages, macros, the mechanism of subroutines. The capacity of the macro or operator of the algorithmic language is greater than the capacity of the computer instruction or the mnemonic code. Nevertheless, almost simultaneously with the invention of the first algorithmic languages, the understanding that the expressive possibilities of these languages are very limited [9] has come.

Specialized tools – report generators and simulation languages – were created later. They also used concepts more capacious than an algorithmic language operator or a macro. But in the future development of programming technology in this direction did not happen. The concepts of DSA-theory possessing a large capacity are: collective property (C-property), algorithmic dependence (A-dependence), decomposition scheme and synthesis path (PS).

The basic paradigm of DSA-theory

The fundamental key idea of the DSA-theory (project paradigm) is: "New knowledge is produced in the computer". This paradigm is accepted in theory as an axiom, as an initial position and contrasted with another paradigm: "Information processing takes place in the computer". The basic idea develops as follows: "Knowledge has its own internal structure and its formation mechanism - the decomposition procedure." And further: "The algorithm and program in the computer are a reflection of the decomposition scheme."

The decomposition procedure is known and intuitive to almost any researcher, as this is one of the thinking tools of research. In addition, the decomposition scheme is something that is very similar to the structural analysis [10]. But in the DSA-theory the accents are established on the procedure of knowledge formation, and not on the mechanism of decomponent constructions and their management. The decomposition procedure is the implementation of the project paradigm.

The expected effectiveness and productiveness of the DSA-theory is that it develops and studies the principles of designing algorithms. The algorithm is designed long before programming and even without programming. DSA-theory is aimed at eliminating the personal subjective factor from the design process of algorithms and programs.

Object Properties

Analysis and research in DSA-theory are based on the idea of "object" (Note: The concept of "object" is used in general scientific and philosophical meaning and has nothing to do with the concept of "object" in object-oriented design and programming). Objects can be real objects existing in the reality surrounding the person - natural and artificial. Natural: the geographical portion of the Earth's surface, the mineral, the human body, etc. Artificial: a product of engineering or light industry, etc. As an object, something static, relatively unchanged and observable, for example, a table, a house or a car, can be considered. As an object can be considered and something that does not have a visible form, for example, a verbal contract between business entities. As an object can be considered a different kind of processes. For example, the process of digestion or the process of observing the experiment.

Selecting a few objects from the surrounding reality, they can be viewed as a system. Within the system, each object in relation to any other object manifests its properties. Object properties exist independently of other objects. Actually, a property is a manifestation of the internal structure of an object.

Properties of objects are manifested for a person when objects enter into any relations with him (table height = 75 cm was manifested in comparison with another table, with the height of a person, with a measuring ruler). These relationships can be real or conceivable when it relates and compares these objects in their minds.

The properties of the object or its parts are represented by a formula or a qualification sentence: "The subject is a predicate". The qualification sentence can be of three types.

The first type is the simplest. It reflects the specific meaning of one property or one characteristic of a particular object. Example: The object is a detail. The object's property is the weight. The qualification sentence has the form: "1214 - 15 kg". Here is the "1214" part number, and "15 kg" is the weight of the part. This type of qualification is called an elementary property (El-property).

The second kind of qualification sentence reflects the specific values of several properties of one particular object (or one part). Example: The object is a detail. Object properties - weight, material, number of operations, total processing cost. The qualification sentence has the form: "1214 - 15 kg, steel 40, 8, 35". Here is the "1214" part number, "15 kg." - the weight of the part, "steel 40" is the material, "8" is the number of operations for making the part, "35" is the number of hours for manufacturing the part. This type of qualification sentence is called an aggregated property (A-property).

The third type of qualification sentence is due to the situation when the list of properties of its components is considered as the property of the object. Such a list is a collective property (C-property).

Example. The characteristics (C-property) of the enterprise of reinforced concrete products can be a catalog of manufactured products:

• floor slab;

• ring of the well;

• flight of stairs;

• staircase, etc.

Another characteristic (C-property) of the same enterprise, along with integral indicators expressed by one number - such as quarterly sales volume or quarterly profit, can be a list of realized products with indication of sales volumes. The qualification sentence in this case is: The volume of sales in the first quarter is:

• overlay plate - 120 pieces;

• ring of the well - 70 pcs .;

• a flight of stairs - 250 pcs .;

• ceiling slab - 230 pieces. Etc

Here, the C-property of the object is the quarterly volume of sales. The object number is the first (quarter). The C-property of the object is a list of products manufactured in the first quarter.

The C-property of an object can simply be a list of names or component numbers.

The C-property, the Al-property, and the A-property have a generic notion, the P-property, which embraces them. In the DSA-theory, along with the properties of the object, data about the object are also considered. In the DSA-theory, along with the properties of the object, data of the object (data that characterize the object) are also considered. A data of an object (P-data) or a value that characterizes an object is the property of an object for which a readable or perceived by a person or (and) by technical means sign is determined. Like the concepts of the C-property, the El-property and the A-property, there are concepts: the collective data (C-data), the aggregated data (A-data) and the elementary data (El-data). P-properties and P-data are correlated both with the object and with the parts of the object. The A-data may include the El-data, A-data and C-data. The C-data may contain A-data.

A certain number of parts (component) can be obtained as a result of the object decomposition procedure. If for each part a numerical value of the same property is defined, for example, the weight of the part, then the collective of all these values is considered as a property of one type (or data of one type). Data types and property types are named. To display all types of P-data (and also types of P-properties) obtained as a result of decomposition, a tree-like graph is used.

In Fig. 1 shows a comparison of the notation for an image of P-data types in comparison with the method of notation of data structures adopted in JSP [2]. This comparison is legitimate, since the same phenomena are compared.

Algorithmic dependence

Another key concept of DSA-theory is the algorithmic dependence (A-dependence) between the properties of the object.

The difference between the A dependence and the functional dependence is that, in addition to formulas and mathematical signs, text descriptions and various tabular constructions can be used to describe the algorithmic dependence. Algorithmic dependence can be completely formalized only by means of algorithmic language tools.

There are two categories of algorithmic dependencies.

The first category - the analytic dependence (A^a-dependence) reflects the dependencies between the El-properties and (or) A-properties of the object (or the same part of the object).

The second category - the synthetic dependence reflects the dependence (A^s-dependence) between the P-properties of the object and the P-properties of the parts that make up the object. It can also be a relationship between the P-properties of a part of an object and the P-properties of parts that directly make up a given part of the object. The second category includes two types of A^s-dependencies.

The first kind is the situation in which the argument is the El-property of the object, and the function is the El-property of the object parts or in another notation:

R = α (Q),

where Q is the El-property of the object, R is the El-property of the component of the object, and α is the designation of the A^s-dependence. If the C-property P consists of the El-properties of R (P = (È R)), then the following is possible:

P = α (Q).

The second kind is a situation in which the argument is the P-properties of the parts of the object, and the function is the P-properties of the object or in another notation:

W = γ (V),

where W is the El-property of the object, V is the C-property of the part of the object, and γ is the name of the A^s-dependence. If the C-property Z consists of the El-properties V (Z = (È V)), then the following is possible:

W = γ (Z).

A representative of this kind of A^s-dependence can be the calculation of the sum of values, the search for the minimum or maximum element, or any calculation in which all the elements of a certain collection are processed.

Realization of A-dependencies

To illustrate how the A-dependencies are algorithmically implemented, and for the image of an algorithm that can be built on the basis of the decomposition scheme, a hypothetical computing device is used, consisting of input and output tapes, a processor, and a tape containing the description of A-dependencies.

Note: The computing device is similar to the algorithmic system "Turing machine". The difference lies in the fact that the cells of the input and output tapes place the El-data, instead of the control device, the term "processor" is used, and the algorithm is determined by the contents of the processor tape, and not by the internal states of the control device.

The given (known) properties of the object, represented as El-data, are placed on the input tape.

The desired properties of the object, represented as the EL data obtained as a result of the calculation, are placed on the output tape. One El-data is placed in one cell of the tape (note: it is assumed that the dimensions of the El-data are the same as the cell sizes, although this is not the case in the practice of electronic data processing), and the A-data and the C-data occupy groups of cells. The reading head has access to the input tape. For one reading operation, the reading head can read the contents of only one cell.

Description of A-dependencies, according to which the required properties are determined, are placed on the tape of the processor. The description of one A-dependence is placed in one cell. Input data and corresponding descriptions of A-dependencies are placed on the corresponding tapes synchronously.

The computing device realizes data processing (calculation of P-properties) in accordance with those A-dependencies that exist between P-properties. The device operates as follows. Both tapes move from right to left. At any one time, only one cell is available for reading and one cell for recording.

Similarly, the A-dependency description is available for reading by the processor's read head. A situation is possible in which several A-dependencies will be realized when processing one El-data.

For the next El-data this group of A-dependencies will be repeated again. Graphically this group is placed in a rectangle. Rectangle is the area of the processor.

Beginning the processing of the next El-data, the reading head within the processor zone will regularly return to the first of the descriptions of the A-dependencies.

The analytic A^a-dependence is algorithmically realized as follows (Fig. 2, a). The processor, in accordance with the description of the A-dependence β, processes the El-data (D_i), which is available on the input tape. The result of the El-data C_i processing is written to the cell on the output tape. The processing is completed when the El-data is exhausted on the input tape.

 

The synthetic dependence of the first kind is algorithmically realized as follows (Fig. 2, b). The processor, in accordance with the description of the A-dependence α, processes the El-data R, which is available on the input tape. The result of processing C-data Q is recorded in a group of cells on the output tape. The input tape and the tape of the processor do not move, the output tape is shifted as the cells are filled with the El-data Q_i. The completion of processing is determined by the nature of the synthetic dependence.

The synthetic dependence of the second kind is algorithmically realized as follows (Fig. 2, c). The processor, in accordance with the description of the A-dependence γ, processes the C-data V, which is available on the input tape. The result of processing El-data W is written to the cell on the output tape.

The output tape and the tape of the processor do not move, the input tape is shifted as the cells are read with the El-data V_i. The completion of processing is determined by the nature of the synthetic dependence and the size of the C-data V.

Decomposition Procedure

In the most general form, the cognitive process is a movement from phenomenon to essence, a movement from the contemplation of the form of the object to the understanding of its content. This movement is a movement from explicit, more accessible properties of the object to its essential properties. Such a movement is characterized by the fact that this is a movement from the more easily defined characteristics of the object to the more difficult to determine its characteristics.

If there is a relationship between a pair of characteristics or properties of an object, one of which reflects the form and the other is the content of the object, then using it and the value of the first one you can determine the value of the second. If such a relationship is unknown, then the object is treated as a system or as something composite, and the following is true:

a) the object is divided into parts;

b) for each part, a pair of characteristics (form and content) and the relationship between them are determined;

c) the concrete characteristics of the formal characteristics determine the content characteristics of the parts of the first level of decomposition;

d) on the basis of the obtained information on parts, the value of the content characteristic of the object is synthesized.

Thus, the decomposition procedure is performed. For this mechanism of knowledge formation, it is not essential how the decomposition schemes (division scheme) of an object and the scheme for synthesizing information (properties, data) are constructed, it is also not important how the dependence between characteristics is searched. It is important that as a result of the search, the dependence can be found or not. If the dependency is not found, then a deeper level decomposition is performed to find it, and all the other items, b, c, d, are also executed. The shallower (deeper) division of the parts of the object will continue until two conditions are met at the next level:

a) the dependence between the properties of smaller parts is found;

b) using this relationship, the properties of these smaller parts are found.

Then, using these properties, the properties of the parts that are composed of the smaller (parts of the previous level) will be found. The synthesis procedure, in the process of moving from the properties of the included parts to the properties including, will be completed when the desired characteristic (the sought property) of the original object is determined.

Decomposition can be stopped if it turns out to be hopelessness of its continuation. This means that there is no way for further deeper division of parts or after another division of the non-productive relationship between the characteristics of the parts obtained or there is no procedure for synthesizing characteristics for the inclusive level. The decomposition is valuable, if after its completion the data about the object itself is generated - the data is synthesized.

There are particular schemes and complete decomposition schemes. A particular decomposition scheme (a decomposition scheme of one level) shows how to divide an object into directly components of its components. A particular decomposition scheme should determine how each component is allocated. A particular scheme can be used to divide both the object and its part. The complete decomposition scheme is the result of the decomposition of the object after the application of all the schemes required in the process of division. In the process of forming a complete scheme, particular schemes were applied to the object, and, possibly, to its parts.

The same particular decomposition scheme can be used many times - for objects of different types. That is, there can be universal decomposition procedures.

All parts resulting from the application of a particular decomposition scheme can be grouped. The characteristic, according to which the parts are included in the groups, are determined by the researcher. A group of parts that have the same characteristic is called the type of part. In the decomposition scheme, each part belongs to certain type. At each level of decomposition, one's own set of types is generated. The set includes at least one type. In the DSA-theory, as a result of partial or complete decomposition, a set of types is considered. As a result of the real decompositions of various objects, a different number of parts belonging to a particular type may appear. Depending on the object or (and) the decomposition scheme, an arbitrary number of parts of one type (instances of a type) can be obtained, at least one part, or one part is mandatory, or no part, etc. As a result of object decomposition, an arbitrary number parts, types of parts and levels.

Graphically, the result of the decomposition can be represented by a tree. In general, the decomposition scheme is shown in Fig. 3. On this tree, each node corresponds to one type of part. A tree can contain an arbitrary number of levels, nodes, edges. Each type of part can have an arbitrary number of P-properties and A-dependencies between P-properties. A-dependencies only relate to the types of parts (with nodes of the tree). First of all, the tree displays a hierarchy of the types of parts of the object, but can also display property types, A-dependencies, and particular decomposition schemes. The complete decomposition scheme shows the possibility of dividing the types of parts by certain particular schemes, but does not display the detailed order of division of parts and calculation in accordance with A-dependencies.

From the point of view of the tree shown in Fig. 3, decomposition is the movement from the root node to the leaves - from top to bottom. Synthesis of data, the definition of new information about the object can be partially or completely material - weighing, determining the number of defective components or replacing the broken part. Synthesis of data is the movement from the leaves to the root node - from the bottom up.

The description of the decomposition scheme contains the tree of the complete decomposition scheme (DPS), where for each node K_i the tuple of the node description KR_i = (T_i, A^a_i, A^s_i, DM_i) must be defined, which includes:

• T_i - a list of property types.

• A^a_i - analytical dependencies.

• A^s_i - synthetic dependencies.

• DM_i is a partial decomposition scheme.

K_i is the node identifier, where the index reflects the node number when traversing the tree from top to bottom from left to right.

The symbolic description of the decomposition scheme has the form:

DPS={K₀[KR₀] (K₁[KR₁] (…), K_r[KR_r] (…),…,K_z[KR_z] (…))}.

Leaf tuples do not contain partial decomposition schemes and synthetic dependencies.

The decomposition scheme and the canonical algorithm

The decomposition scheme in its pure form is not an algorithm. The decomposition scheme shows only the fundamental possibility of how decomposition can be performed, but does not describe in detail the order of its execution. In order for the decomposition procedure to become an algorithm, it is necessary to determine the order of access to the P-data and the order of their processing (the order of realization of A-dependencies).

As an example, the decomposition scheme is shown in Fig. 4, a. As a result of the decomposition, N parts are obtained. The decomposition tree contains two nodes that have the C-properties: U and W. U = È EN, W = È FN. In Fig. 4, b shows the same decomposition scheme with its inherent A-dependences (Note: In Fig. 4 and in some of the following figures the A-dependencies are correlated with the nearest nodes located above). The A-dependencies U = α (C) and G = γ (W) correlate with the node K₁. And with the node K₂ the A-dependence of F = β (E) is correlated.

The implementation of this scheme consists of three steps.

1. The A-dependence U = α (C) is the synthetic dependence of the first kind. To implement this dependence, it is necessary to use the algorithm shown in Fig. 2, b. The result of this algorithm is the El-data U = È E_i, where i varies from 1 to N.

2. The A-dependence F = β (E) is an analytical dependence. To implement this dependence, it is necessary to use the algorithm shown in Fig. 2, a. The result of this algorithm is the El-data W = È F_i, where i varies from 1 to N. Each El-data of E_i is the initial one for calculating the El-data F_i.

3. The A-dependence G = γ (W) is a synthetic dependence of the second kind. To implement this dependence, it is necessary to use the algorithm shown in Fig. 2, c. The result of this algorithm is the El-data G. To calculate G, every El-data F_i was used.

During these three steps, it is necessary return the input tapes twice to their original position. Finally, three passes are required to implement the decomposition scheme and to synthesize new values of the required properties. Calculations of these three passes can be combined and implemented using the algorithm shown in Fig. 5. In the algorithm with each advancement of the tape per cell, three operations are performed:

• the El-data E_i is calculated and written to cell i;

• the El-data F_i is calculated and is written to cell i;

• the C-data G is calculated.

Following the formation of the instance of E_N, the F_N instance is formed and the formation of the El-data G is completed.

This computational procedure is called the implementation algorithm for DS. The latter demonstrates the algorithmic nature of DS in the traditional sense for programming. The implementation algorithm for DS is also called the canonical algorithm.

The list of all A-dependencies, compiled in the process of traversing the decomposition tree from top to bottom and from left to right, is called a synthesis path for the properties of an object or simply a synthesis path. Under the conditions of the previous example, the synthesis path is a list of the names of the A-dependencies: U = α (C); F = β (E); G = γ (W) or α> β> γ. With this definition, the following assertion holds: "The canonical algorithm realizes the PS".

 

Real decomposition schemes have an arbitrary number of levels of decomposition, as a rule, more than two. With each node, an arbitrary number of A-dependencies correlates. From A-dependencies of different levels, chains of three different types can be composed. The chains of the first kind consist of synthetic dependencies of the first kind. They describe the procedure for decomposing an object or its parts and the procedure for calculating the properties of the included components based on the properties of the parts of the object that include them. The chains of the second kind consist of synthetic dependencies of the second kind. They describe the procedure for synthesizing the properties of parts of an object or the object itself based on the properties of the included components. Chains of the third kind include A-dependencies between the El-properties of one node of the DS tree. From the chains of these three types, both from the fragments and the PS is constructed a decomposition scheme of arbitrary complexity.

The fact that DS have many levels of decomposition (Fig. 6, a) suggests that the C-data may contain data of a different type as a component (Fig. 6, b). Nesting of groups of C-data can be arbitrary. The processing of nested groups of C-data in the canonical algorithm generates repetitions of computations, which are also nested into each other. Embedded repetitions of calculations are depicted in traditional lowercase programming languages ​​using nested loops (Fig. 6, c, d). The fact that the repetitions (and therefore the cycles) can be nested is also represented by a tree (Fig. 6, d). The so-called tree cycles.

It is the tree of cycles - the main framework of most applied real algorithms. It is the tree of cycles that is an essential factor in the complexity of algorithms. A two-dimensional tree-like graph with dozens of nodes can easily be placed on a sheet of A4 paper or on a display screen. And the program corresponding to this graph, even if you take the functionality out of it, will take several times more space. The conceptual capacity of a tree of cycles and PS, as attributes of DSA-theory, is the advantage of this theory. Decomposition schemes can also generate alternatives that are reflected in the canonical algorithm. The existence of alternatives is due to the fact that the DS can contain parts of different types that are components of the same part of the object that includes them. The canonical algorithm is defined both theoretically and practically, but it differs from the algorithms existing in real software. This is due to the fact that real algorithms implement many factors associated with a particular computing environment, with data placement and access to data. The canonical algorithm is in no way connected with any particular computer and with any particular computing environment.

Algorithmically relevant factors

From DS on paper or in consciousness to a specific application program a number of additional works should be done. These works must adapt the canonical algorithm to the real conditions of data processing.

The reasons for this are the following:

• The algorithmic model can be complex because the input tapes can be more than one. Also, there can be more than one output tape; (Note: An input tape is a prototype or ideal image of any machine-readable medium with sequential access. An input tape is also a prototype of a stream of any kind of transactions, messages or input signals.)

• The size of real C-data, as a rule, does not coincide with the sizes of cells on input and on output tapes. Because of this, it is necessary to include blocks in the algorithm that format the C-data;

• The model for sequential access to C-data is the simplest. In the practice of electronic data processing, there are more sophisticated methods of accessing data;

• C-data can come not from tape, but in ONLINE mode from different sensors or in dialogue mode;

• C-data can be output not only to the tape, but to the monitor, to various control devices;

• The C-data for placement can be encoded, packed, etc.

In addition to these reasons, there are others. Each of the above causes a group of factors that affect the canonical algorithm. These factors are called algorithmically relevant factors. To implement them, algorithmic constructions are added to the canonical algorithm. Because of this, the algorithm becomes more complex and becomes more difficult to understand. The canonical algorithm can turn into a real program only after all the groups of factors caused by a particular computing environment have been taken into account and implemented. Each group of factors involves its own set of algorithmic constructions or its algorithmic layer, which is superimposed on the canonical algorithm. These are the so-called adaptive layers.

Both the decomposition scheme and the canonical algorithm together are an invariant, unchanging kernel of the application program in terms of the conditions for implementing this program in various computing environments. The decomposition scheme and the canonical algorithm remain unchanged irrespective of:

• in which language the program is implemented,

• uunder which operating system is the program running,

• which DBMS is running which accesses the data.

The decomposition scheme and the canonical algorithm generate in the analysis and design those difficulties that are called Brooks [11] essential. The programming of the adaptation layers gives rise to the difficulties of the non-hereditary [11] or the accidents in the software.

In some cases, the decomposition scheme can be represented only by a tree, the nodes of which are loaded with the names of C-data. This graph can be called a «data structure». (Note: The term «data structure» is not an attribute of the DSA-theory.) If the C-data is placed on the same input tape and on one output, and the order of their placement on the tapes is known, then this information is enough to restore the cycle tree of the program that will process this data. That is, with certain reservations it is possible to assert the following: "Using the data structure it is possible to construct the structure of the program". This idea is the conceptual basis of the method of designing programs by data structure [3 - 7]. The idea and essence of this method is a particular case or a partial result of the DSA-theory.

Any canonical algorithm can be implemented as an application program, but not every real application program is an implementation of the canonical algorithm. If any real application program is freed from all the adaptation layers, then it may turn out that the program implements only a part of the canonical algorithm, or only some of its components. Another situation is also possible. After releasing the canonical algorithm from the adaptation layers, it may turn out that the canonical algorithm is a combination of several simpler canonical algorithms.

Operations on algorithms

In the DSA-theory, various manipulations or operations with decomposition schemes are investigated, which under certain conditions are the calculus of algorithms. Below is a short description of some of these operations on schemes.

1. Addition of DS (Fig. 7).

This operation means that in the process of researching (designing) the object there is a need to do a deeper decomposition. A possible reason is that as a result of the decomposition, a higher accuracy of calculations will be achieved.

As a result of this operation, one PS fragment was replaced with another, as a result of which the PS became longer:

The PS was: f₁ ­› g₁ ­› h₁ ­› f₂ ­› g₂ ­› h₂.

The PS became: f₁ ­› g₁ ­› h₁ ­› f₂ ­› l₁ ­› m₁ ­› n₁ ­› h₂.

In the decomposition tree, more nodes and more levels appeared.

2. Truncate the DS (Fig. 8).

This operation means that in the existing decomposition scheme at node 3 between P-properties, an acceptable analytic dependence g₆ is found, which allows to make the calculation in another way, and there is no need to do a deeper decomposition.

As a result of this operation, one PS fragment was replaced with another, as a result of which the PS became shorter:

The PS was: f₁ ­› g₁ ­› h₁ ­› f₂ ­› f₅ ­› g₅ ­› h₅ ­› h₂ ­› f₃ ­› g₃ ­› h₃.

The PS became: f₁ ­› g₁ ­› h₁ ­› f₂ ­› g₆ ­› h₂ ­› f₃ ­› g₃ ­› h₃.

3. Synthesis of DS (Fig. 9).

This operation means that during the calculation of the PS in the first tree, it became necessary to perform one more calculation procedure simultaneously. In this operation, the following condition must be met: the decomposition results (the number of parts) according to schemes f₂ and l₁ must be the same.

The operation has two options:

a) the analytic dependencies of g₁ and m₁ are somehow related. Then a superposition of these dependences g₂ α (m₁) or m₁ β (g₂) will appear in the PS.

The PS was: f₁ ­› f₂ ­› g₂ ­› h₂ ­› h₁.

The PS becomes: f₁ ­› f₂ ­› g₂ α (m₁){or m₁ β (g₂)} ­› (h₂, n₁) ­› h₁.

b) the analytic dependencies of g₁ and m₁ are not related to one another. Then in the PS they will simply be listed side by side in an arbitrary order.

The initial PS was: f₁ ­› f₂ ­› g₂ ­› h₂ ­› h₁.

The additional PS is: l₁ ­› m₁ ­› n₁.

PS as a result of the synthesis became: f₁ ­› f₂ ­› ( g₂, m₁ ) ­› ( h₂, n₁ ) ­› h₁.

Generating algorithms

DSA-theory creates prerequisites for the generation of algorithms (not machine code). The initial data for generation is the decomposition scheme, the corresponding canonical algorithm, as well as tuples of the node description and tuples of descriptions of algorithmically relevant factors. Each of the tuples corresponds to the node of the DS tree. The generated algorithm can be used as input data for generating machine code.

The direction of research in terms of DSA-theory

Currently, there are several areas for further development of the DSA-theory. The first is to study the typology of decomposition schemes and their components. The second is a study of algorithmically relevant factors and an analysis of their influence on the canonical algorithm. The third is designing algorithms generation procedures. In each of the directions, progress can be planned, predictable and foreseeable. The planned nature of the research is real, in spite of the fact that the aggregate of all real algorithms and programs existing at the present time in all application areas may seem unimaginable. This is explained as follows.

From the point of view of the DSA-theory, a lot of algorithms mean a lot of decomposition schemes represented by a tree. Each circuit has an arbitrary number of edges and nodes. Algorithmically relevant factors affect the algorithms of one node and (or) adjacent to it - the predecessor or child. Algorithmically relevant factors are limited. Their influence on the nodes is almost the same, regardless of where the node is in the scheme. Also the number of node types is limited. That is, only tree nodes and their modifications are examined and analyzed. And the number of nodes, their types and their modifications is much smaller, in comparison with the number of trees made up of these nodes. That is, the DSA-theory allows to study instead of an unlimited number of really and potentially existing set of algorithms a limited number of algorithmic objects much simpler than real applied algorithms. DSA-theory also allows you to design these designs and manipulate them not intuitively, but logically justified, even routinely.

Conclusions

The decomposition scheme and its attributes are described in the article. The definitions of the concepts of the qualification sentence, collective property, algorithmic dependence and synthesis path are given. The algorithmic nature of the scheme is shown. The decomposition scheme is considered as the basic concept of DSA-theory. DSA-theory is considered as a prototype of the theory of algorithms for modern software. The concept of the canonical algorithm as one of the theoretical models of the DSA-theory is proposed. Operations on decomposition schemes are described. The ability to use tree-like two-dimensional graphs in the design of algorithms instead of the textual record of modern programming languages ​​is shown. The existence of a difference between the canonical algorithm and real applied algorithms is described briefly.

 

1.      Ivar Jacobson and Bertrand Meyer. Methods Need Theory. Dr. Dobb's Journal, 6 August 2009.

2.      Victor R. Basili. The role of experimentation in software engineering: past, current, and future. Proceedings of the Eighteenth International Conference on Software Engineering (ICSE), Berlin, Germany, March 1996.

3.      Jackson, M.A. Principles of Program Design. New York: Academic Press, 1975.

4.      Warnier J. –D. Logical Construction of Programs. Leiden: H.E. Stenfert Kroese B.V., 1975.

5.      Velbitsky I.V. “Technology of programming.” Tekhnika, Kiev, 1984. (In Russian).

6.      Kolesnyk V.G. Joint processing of files and hierarchical databases in conditions of application of the JSP method. - Donetsk: IEP of the Academy of Sciences of the Ukrainian SSR, 1988. – 16 p. (In Russian).

7.      Kolesnyk V.G. The conceptual basis of the programming method based on the data structure (knowledge). - Kramatorsk, 1986. – 22 p. Deposited in UKRNIINTI 6.06.88, № 1409. (In Russian).

8.      Edmund M. Clarke, Jeannette M. Wing, Et Al. Formal Methods: State of the Art and Future Directions // ACM Computing Surveys. – 1996.– V. 28, N 28.– P. 626– 643.

9.      Бэкус Дж. Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. М.: Mir, 1993. – p. 84– 158.

10.   Marca D., McGowan К. Structured Analysis and Design Technique (SADT), MethaTechnologia. –.М., 1993. – 240 p. (In Russian).

11.   Brooks Frederick P., No Silver Bullet: Essence and Accidents of Software Engineering // Computer. – 1987. – V. 20., N. 4.– P. 10– 19.