The optimizing transformations formulation of algorithms on graphs and sets
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.