Creation and development of a general theory of applied algorithms
_____Problem. In mechanical engineering, designers and technologists usually consider drawings of new technical products at various councils. During the work of the council, drawings of the components of new products and the products themselves are hung on the walls of the room where the council meets. A two-dimensional image and uniform terminology allow specialists to delve into the essence of the design and mechanism within five to ten minutes. During the discussion, comments may be made regarding the design. Errors may also be noticed.
_____In programming, it is impossible to hang program texts on a board and on walls and for a group of specialists to quickly understand the essence of the program. This is because algorithmic languages are text-based – they are displayed in text. Programs are written in lines. As a result, program complexes reach tens of millions of lines. Until now, it has not been possible to compress program texts. Because of this, programming continues to suffer from old diseases: delivery deadlines are disrupted, money is overspent, and, most importantly, errors remain in program texts. Or at least testing requires large expenses. This is evidence that the software industry remains at a dead end in terms of labor productivity and program reliability. The software technology community has long been discussing the need to create a theory that could solve these problems [1]. Current work is aimed at solving these problems. The solution is to create visual tools for a radical, significant compression of program texts. For this purpose, a presentation of the general theory of applied algorithms is proposed [2].
_____Jackson's method. Some statements in the theory and the theory itself may seem paradoxical. Therefore, it is necessary to show that it is based on real practical discoveries, that the theory is not the fruit of speculative fantasies. In the sixties, a method of designing programs based on the data structure was discovered in Great Britain [3] - the Jackson method (JSP). The idea of the method is not complicated. It was also implemented in the Varnier-Or method, in R-technology, developed at the Institute of Cybernetics of the NAS of Ukraine. The idea of the method is that the program structure is built on the structure of the input data.
Not knowing about the existence of the method abroad, I rediscovered it. The advantage of my version of the method was based on a more compact graphics (Fig. 1.). Also, instead of the concept of iteration, which was in the JSP method, I introduced the concept of a collective data (C-data). Thanks to this concept and the refined graphics, the data structure diagram clearly defined the algorithm diagram and the structure of the COBOL program. Absolute isomorphism (Fig. 2). The complexity of applying the method in all cases was only in how to build the data structure.
_____Unlike other authors, I continued my search. In the search process, the data structure in the input files, the data structure in the output files, the data structure divided between the input and output files at the same time, the number of input files with more than one data structure, the joint processing of linear files and hierarchical databases, the combination (or synthesis) of data structures and data storage structures were considered. The solutions were constantly tested practically.
_____In the process of searching, a natural question arose: if the hierarchical data structure determines the hierarchical structure of the program, then what determines the data structure? At some point, it seemed that the answer had been found. The world around us is full of hierarchical structures: organizational, industrial, etc. But a dissonance arose. Not all hierarchical structures that exist in the surrounding reality are suitable for building a data structure. Some are simply not used, others need to be modified: add nodes or levels; or, conversely, simplify the real hierarchical scheme.
_____Decomposition scheme. There was a break in my scientific research. An attempt was made to practically implement the method in the form of an algorithmic language and a program generator. This attempt ended in failure. First, it was necessary to thoroughly think over the method - a theory was needed. After the break, I again took out the folder with notes and continued the search. And this time the correct answer was found. The hierarchical structure of the program is determined by the decomposition scheme, which is hierarchical. There is one of the universal methodologies with which a person explores the surrounding material world. An object is mentally or materially divided (disassembled) into components and its further study is based on the components. The components, in turn, can be divided (dismembered) into constituent components, etc. The result of the division - a hierarchical decomposition scheme can be depicted as a graph - a tree. In the process of decomposition, different parts (or components) are revealed. Not the components themselves, but their types are taken into account. Belonging to a type determines the similarity of algorithmic aspects of processing correlated data. The data structure discussed earlier is just one simplified representation of the decomposition scheme.
_____Thus, from this moment on, the object of research becomes the decomposition scheme. The construction of a decomposition scheme ceases to be programming, but provides programming. The construction of a decomposition scheme is essentially the construction of an algorithm. This is how the main concept of the theory was found.
Without exaggeration, it can be stated that each of the computer programs operating in the world is an implementation of either a decomposition scheme, or a fragment thereof, or a synthesis of two or more decomposition schemes.
_____Virtual component operations. The next result in the study was led by another observation. Processing of a given set is always implemented using a cycle. Any cycle in the program implements one or more general scientific concepts or procedures known as decomposition, deduction, composition, induction. Within the framework of this work, these procedures are called virtual component operations (VCO). They manipulate not material objects, but their virtual images. In the decomposition scheme, VCOs can occur in different quantities and in different combinations. In the graphical representation of the decomposition scheme, these procedures are correlated with edges (Fig. 3). Any number of VCOs can be correlated with an edge in any interaction - connection by concatenation or conditional constructions, or be synthesized. But at least one VCO must be correlated with an edge.
_____Algorithmic cell. A significant leap in the study of living nature occurred due to the formation of an understanding of the cell and the beginning of its study. Within the framework of this work, the concept of a cell, an algorithmic cell, is also proposed (Fig. 4.). Just as organic tissue is formed from organic cells, a complete decomposition scheme and, accordingly, a computer program algorithm are formed from the proposed algorithmic cells. In an algorithmic cell, the VKO correlates an object with its immediate components. The algorithmic cell is depicted as a graph in which two nodes are connected by an edge. The graph lists the VKOs involved next to the edge.
_____Methodologically, there are two approaches in the process of any cognition: decomposition (or isolation) and composition (or inclusion). Decomposition: the object is perceived as something complex and to determine its properties, the object is divided into components and its further study is carried out on the basis of the components. Inclusion: the object (initial) is considered as a component of some more complex encompassing object and the properties of the larger one are transferred to the initial object. Each approach is implemented by a corresponding algorithmic cell.
_____Each node can be associated with an analytical relationship between the properties of the corresponding object. This relationship can be represented by a mathematical formula, a text description, or an algorithm. The work uses the concept of algorithmic dependence, which includes all these types of description. Algorithmic dependence is implemented by the transformation operation (Tr).
_____It is necessary to distinguish between an algorithmic cell as a theoretical construct and as a practical one.
A practical cell may include:
• two or more VKOs of the same type;
• an arbitrary number of VKOs of different types;
• VKOs that can be synthesized,
• VKOs of some types, correlated with the theoretical cell in its description, may be absent.
Algorithmic cells are the building blocks from which partial and complete decomposition schemes are built.
_____Complete decomposition scheme. The final or complete decomposition scheme is depicted as a tree with the root at the top of the drawing (Fig. 5). A tree node from the perspective of the nearest parent node depicts a component of the object associated with the parent node. A tree node from the perspective of the nearest parent node depicts a complex object that includes the parent node as a component.
_____In the graphical representation, descriptions of properties represented by data can be connected (or not connected) to the nodes of the tree. One or more transformation operations can be associated with each type of part. The number of nodes, levels, edges emanating from one node in the tree is not limited.
_____When traversing a tree depicting a decomposition scheme, from top to bottom, from left to right, VKOs can be found near each edge, and Tr can be found near each node. The list of these VKOs and Trs in the order obtained when traversing the tree is the so-called synthesis contour of the object properties. In it, the output data of one operation is the input data for the operation of the next in the contour. It is the content of the algorithm and the essence of the work of the corresponding program in the computer. The first level of correctness of programs is the correctness of the synthesis contour.
_____Strategy for applying the general theory of applied algorithms. The software industry is dominated by a craft style of production. That is, the creation of algorithms - as design and programming (coding) - as production are performed simultaneously. Sometimes, along with design and production, research into algorithms or the designed system is also performed. This situation indicates that important and productive organizational resources, such as division of labor, unification, specialization and cooperation, are not fully utilized in the programming industry. Stages such as research, algorithm design and programming should be separated. The division of labor should take place as it is in industry: in mechanical engineering, aircraft engineering, instrument making, etc. In industry, the stages of research, design, technological preparation and production are separated and performed sequentially.
_____The division of labor in industry allows for the improvement of individual parts, assemblies, materials, and technology. Such work is carried out constantly, regardless of current production. This is actually specialization.
In industry, the speed of product manufacturing on the assembly line, at the final stage of production, is important. In the production of software products, the final stage is copying the program. This is not a bottleneck. In the production of software products, the division of labor is important due to unification and specialization - that is, the improvement of almost all fragments of the algorithm. Within the framework of this work, fragments of algorithms and programs are VKOs and algorithmic cells. The division of labor in industry increases the functionality and reliability of the final product. Similar results should be sought in the production of software products. And they are achievable.
_____Research directions. Possible directions of further research are the study of the attributes of the theory. The attributes of the theory are.
• Topology of various types of decomposition schemes.
• Filling of algorithmic cells as the main components of decomposition schemes.
• Mechanisms of decomposition scheme synthesis.
• Algorithmic aspects of VKO and transformation operations.
• Mechanisms of VKO synthesis and transformation operation synthesis.
And also.
• Improvement of graphical notation.
• Improvement of program generation - implementation of decomposition schemes into program texts.
• Research and construction of generalized models of application domains.
_____The above graphical representation of the complete decomposition scheme is the first approximation of the notation that the general theory of applied algorithms should provide. This will be a notation that is implemented by a symbiosis of graphics, mathematical formulas, text description and tables. The main, basic carrier of the probable notation is a tree-shaped graph.
_____Conclusion. From research within the framework of the theory, first of all, a concise and compact notation is expected, which will ensure the overview of algorithms and programs. At the same time, it is possible to study the system of assumptions, deductive inference and synthesis of algorithms, which will provide a significant increase in the reliability and speed of programs.
_____The compact notation in question will allow to radically change the organization of software development. The changes will consist in the introduction of the division of labor, unification, specialization and cooperation, which together constitute industrial production.
_____The importance of this work is that it opens up prospects and gives hope. The work shows that from algorithmic languages based on text (text-based), it is possible to move to a more compact recording of algorithms and programs. The work also shows the direction of research.
1. Steve Adolph, Philippe Kruchten. Generating A Useful Theory of Software Engineering, Conference: Software Engineering (GTSE), May 2013 DOI: 10.1109/GTSE.2013.6613870
2. Kolisnyk V.H., Bodyk O.P. A Novel Approach: Leveraging A General Theory Of Applied Algorithms For High-Level Language Design: Karlsruhe, February 28, 2025 DOI: 10.30890/2567-5273.2025-37-02-053
3. Jackson, M.A. Principles of Program Design. New York: Academic Press, 1975.
Report at the conference. Chernivtsi University November 13, 2025
Valery Kolesnyk
No comments:
Post a Comment