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