Формализация оптимизирующих преобразований алгоритмов на графах и множествах
УДК 004.4'4+519.6
Формализация оптимизирующих преобразований
алгоритмов на графах и множествах
© В.А. Овчинников, Г.С. Иванова
МГТУ им. <...> Н.Э. Баумана, Москва, 105005, Россия
Объектом исследования настоящей работы являются способы снижения вычислительной сложности комбинаторно-оптимизационных алгоритмов на графах и
множествах. <...> Обоснована целесообразность их формализации для автоматической
трансформации описания алгоритмов. <...> Приведены результаты анализа способов
снижения вычислительной сложности, характеризующие возможность их формализации. <...> Указаны этапы реализации способа снижения вычислительной сложности алгоритма, определена структура оптимизирующего преобразования и
последовательность действий над алгоритмом, необходимых для его автоматической трансформации. <...> Выполнена формализация ряда контекстно свободных и
контекстно зависимых оптимизирующих преобразований в виде синтаксического
описания заменяемого и заменяющего фрагментов и правила трансформации. <...> Указаны источники и способы получения данных для выполнения оптимизирующих
преобразований, охарактеризована сложность их реализации. <...> Под оптимизирующими преобразованиями будем понимать реализацию способов снижения вычислительной сложности
алгоритмов, заключающуюся в формировании правил их модификации. <...> Формализация оптимизирующих преобразований необходима
для автоматической трансформации описания алгоритма. <...> Оптимизационный эффект применения способа снижения вычислительной сложности к алгоритму достигается удалением лишних вычислений посредством замены части алгоритма (заменяемый фрагмент) на
более эффективную (заменяющий фрагмент), т. е. имеющую меньшую
вычислительную сложность. <...> Эта трансформация должна сохранять эквивалентность исходного и полученного алгоритмов. <...> Возможность трансформации может зависеть от удовлетворения
контекстных <...>