ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ
ТЕХНИКА
УДК 004.421 + 519.6
ОПТИМИЗИРУЮЩИЕ ПРЕОБРАЗОВАНИЯ АЛГОРИТМОВ,
ИСПОЛЬЗУЮЩИЕ СВОЙСТВА МНОЖЕСТВ, ПРЕДИКАТОВ
И ОПЕРАЦИЙ НАД НИМИ
В.А. Овчинников
,
Г.С. Иванова
МГТУ им. Н.Э. Баумана, Москва, Российская Федерация
e-mail:
Многие комбинаторно-оптимизационные задачи структурного синтеза отно-
сятся к классу NP-полных, время решения которых экспоненциально зависит
от размера входа задачи. Большинство задач проектирования структур слож-
ных систем имеют большую размерность входа — миллионы и более компо-
нентов. Всвязи с этим даже для полиномиальных алгоритмов актуальной
является проблема сокращения времени работы за счет снижения их вычи-
слительной сложности. Цель работы — исследование предлагаемых способов
снижения вычислительной сложности алгоритмов на графах и множествах,
в том числе оценка эффективности этих преобразований. Встатье опре-
делено понятие “оптимизирующие преобразования алгоритмов”. Обоснована
актуальность их применения. Выполнена классификация способов снижения
вычислительной сложности алгоритмов, использующих свойства множеств,
предикатов и операций над ними. Рассмотрено подробно каждое из восьми
преобразований и приведена оценка их эффективности.
Ключевые слова
:
алгоритм, вычислительная сложность, оптимизирующие пре-
образования, эффективность, множества, предикаты, операции.
OPTIMIZING TRANSFORMATIONS OF ALGORITHMS
USING PROPERTIES OF SETS, PREDICATES, AND OPERATIONS
OVER THEM
V.A. Ovchinnikov
,
G.S. Ivanova
Bauman Moscow State Technical University, Moscow, Russian Federation
e-mail:
;
Many combinatorial optimization problems of structural synthesis relate to the class
of NP-complete problems, the time required to solve them depends exponentially on
the problem input size. A majority of problems to design structures of complex systems
have a large dimensionality of input: millions and more components. In connection
with this, even for polynomial algorithms, the problem to save their computation
time for expense of reducing their computational complexity is urgent. This work is
aimed at the investigation of the proposed methods for reducing the computational
complexity of algorithms for graphs and sets including the estimation of efficiency
of these transformations. The notion of optimizing transformations of algorithms is
defined. The urgency of their application is substantiated. The methods for reducing
the computational complexity of algorithms using the properties of sets, predicates,
and operations over them are classified. Each of eight transformations is considered
in detail and its efficiency is estimated.
Keywords
:
algorithm, computational complexity, optimizing transformations,
efficiency, sets, predicates. operations.
ISSN 0236-3933. ВестникМГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 4 53
