Engineering Journal: Science and InnovationELECTRONIC SCIENCE AND ENGINEERING PUBLICATION
Certificate of Registration Media number Эл #ФС77-53688 of 17 April 2013. ISSN 2308-6033. DOI 10.18698/2308-6033
  • Русский
  • Английский
Article

The optimizing transformations formulation of algorithms on graphs and sets

Published: 19.11.2013

Authors: Ovchinnikov V.A., Ivanova G.S.

Published in issue: #11(23)/2013

DOI: 10.18698/2308-6033-2013-11-1056

Category: Information technology

In this work we research of ways of computational complexity reducing of combinatorial optimization algorithms on graphs and sets. In this article the concept of "optimizing transformations of algorithms" is defined. Expediency of their formulation for automatic transformation of algorithms is motivated. The analysis methods to reduce the computational complexity results of characterizing the possibility of formalization are given. The realization stages of the computational complexity reducing of the algorithm method are specified, the structure of optimizing transformations and modification rules of the algorithm are defined. The examples of context-free and context-dependent optimizing transformations formalization in the form of syntactic description of replaceable and substitute fragments and transformation rules are made. The sources and methods of data obtaining to optimizing transformations performance are given, the complexity of their implementation is characterized.