Личный кабинет
Подробное описание документа
Овчинников В. А.
Оптимизирующие преобразования алгоритмов, использующие свойства множеств, предикатов и операций над ними / Овчинников В. А., Иванова Г. С. // Вестник МГТУ им. Н. Э. Баумана. Сер. Приборостроение. - 2013. - № 4. -
Скачать документ
Многие комбинаторно-оптимизационные задачи структурного синтеза относятся к классу NP-полных, время решения которых экспоненциально зависит от размера входа задачи. Большинство задач проектирования структур сложных систем имеют большую размерность входа - миллионы и более компонентов. В связи с этим даже для полиномиальных алгоритмов актуальной является проблема сокращения времени работы за счет снижения их вычислительной сложности. Цель работы - исследование предлагаемых способов снижения вычислительной сложности алгоритмов на графах и множествах, в том числе оценка эффективности этих преобразований. В статье определено понятие "оптимизирующие преобразования алгоритмов". Обоснована актуальность их применения. Выполнена классификация способов снижения вычислительной сложности алгоритмов, использующих свойства множеств, предикатов и операций над ними. Рассмотрено подробно каждое из восьми преобразований и приведена оценка их эффективности.
Статья опубликована в следующих изданиях
№ 4. - 2013.
