Optimizing Transformations of Algorithms using Properties of Sets, Predicates, and Operations over Them

Many combinatorial optimization problems of structural synthesis relate to the class of NP-complete problems, the time required to solve them depends exponentially on the problem input size. A majority ofproblems to design structures of complex systems have a large dimensionality of input: millions and more components. In connection with this, even for polynomial algorithms, the problem to save their computation time for expense of reducing their computational complexity is urgent. This work is aimed at the investigation of the proposed methods for reducing the computational complexity of algorithms for graphs and sets including the estimation of efficiency of these transformations. The notion of optimizing transformations of algorithms is defined. The urgency of their application is substantiated. The methods for reducing the computational complexity of algorithms using the properties ofsets, predicates, and operations over them are classified. Each ofeight transformations is considered in detail and its efficiency is estimated.

References

[1] Ovchinnikov V.A. Algoritmizatsiya kombinatorno-optimizatsionnykh zadach pri proektirovanii EVM i system [Construction of algorithms for combinatorial optimization problems in computer and system design]. Moscow, MGTU im. N.E. Baumana Publ., 2001. 288 p.

[2] Sudoplatov S.V., Ovchinnikova E.V. Elementy diskretnoy matematiki [Elements of discrete mathematics]. Moscow, INFRA-M Publ., 2002. 280 p.

[3] Aho A.V., Hopcroft J.E., Ullman J.D. The design and analysis of computer algorithms. Addison-Wesley, 1974. (Russ. ed.: Akho A.V., Khopkroft D.E., Ul’man D.D. Postroenie i analiz vychislitel’nykh algoritmov. Moscow, Mir Publ., 1979. 535 p.).

[4] Aho A.V., Hopcroft J.E., Ullman J.D. Data structures and algorithms. Addison-Wesley, 1983. (Russ. ed.: Akho A.V., Khopkroft D.E., Ul’man D.D. Struktury dannykh i algoritmy. Moscow, Vil’yams Publ., 2001. 384 p.).

[5] Cormen T.H., Leiserson C.E., Rivest R.L. Introduction to algorithms. MIT Press, 1990,1296 p. (Russ. ed.: Kormen T., Leyzerson Ch., Riverst R. Algoritmy: postroenie i analiz. Moscow. MTsNMO Publ., 2000. 960 p.).