Оптимизирующие преобразования алгоритмов, использующие свойства множеств, предикатов и операций над ними

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

Литература

[1] Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 288 c.

[2] Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: учебник. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. 280 с.

[3] Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Построение и анализ вычислительных алгоритмов: пер. с англ. М.: Мир, 1979. 535 с.

[4] Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы: пер. с англ. М.: Вильямс, 2001. 384 с.

[5] Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 960 с.