Формализация оптимизирующих преобразований алгоритмов на графах и множествах
3
ности в виде оптимизирующего преобразования требует выполнения
следующих этапов:
• выявление заменяемого и синтез заменяющего фрагментов;
• доказательство эквивалентности преобразования;
• формирование условий, при выполнении которых эта замена
допустима и эффективна.
Исходный и преобразованный алгоритмы
эквивалентны
, если на
всех допустимых наборах входных данных задачи дают одинаковые
результаты. Эквивалентность заменяемого и заменяющего фрагмен-
тов доказывается при конструировании последнего.
Оптимизирующие преобразования [2] разделяют на
контекстно
свободные
и
контекстно зависимые
. Преобразование является кон-
текстно свободным, если не существует условий на допустимые свя-
зи преобразуемого фрагмента с остальными компонентами алгорит-
ма, при выполнении которых вносимые изменения сохраняют его
эквивалентность.
Другими словами, преобразование контекстно свободно, если за-
меняющий фрагмент конструируется только из объектов заменяемо-
го фрагмента (логических переменных и их значений, элементов
множеств, самих множеств и графов). Эквивалентность заменяемого
и заменяющего фрагментов контекстно свободного преобразования
обеспечивает эквивалентность трансформированного алгоритма ис-
ходному. В противном случае преобразование будет контекстно за-
висимым.
Условие на требуемые свойства объектов алгоритма и/или связи
заменяемого фрагмента с остальной частью алгоритма, при выполне-
нии которых эта замена возможна, назовем
условием допустимости
.
Отношение или логическое выражение, устанавливающее факт
снижения вычислительной сложности алгоритма при замещении за-
меняемого фрагмента заменяющим, назовем
условием целесообраз-
ности
. Эффективность оптимизирующего преобразования является
функцией отношений и характеристик конкретных объектов алго-
ритма, свойств и количества операций над ними. Таким образом,
условие целесообразности является объектно и параметрически зави-
симым.
Значительное количество оптимизирующих преобразований свя-
зано с использованием дополнительных множеств, что увеличивает
емкостную сложность алгоритма. В рамках данной работы не будем
учитывать ограничение на емкостную сложность преобразованного
алгоритма.
Очевидно, что формула (описание) контекстно зависимого пре-
образования должна включать заменяемый и заменяющий фрагменты
и условия допустимости и целесообразности.
