| Аннотацiя: | Многие комбинаторно-оптимизационные задачи структурного синтеза относятся к классу NP-полных, время решения которых экспоненциально зависит от размера входа задачи. Большинство задач проектирования структур сложных систем имеют большую размерность входа - миллионы и более компонентов. В связи с этим даже для полиномиальных алгоритмов актуальной является проблема сокращения времени работы за счет снижения их вычислительной сложности. Цель работы - исследование предлагаемых способов снижения вычислительной сложности алгоритмов на графах и множествах, в том числе оценка эффективности этих преобразований. В статье определено понятие "оптимизирующие преобразования алгоритмов". Обоснована актуальность их применения. Выполнена классификация способов снижения вычислительной сложности алгоритмов, использующих свойства множеств, предикатов и операций над ними. Рассмотрено подробно каждое из восьми преобразований и приведена оценка их эффективности. |