Практическое решение NP-трудной задачи конфигурирования программного обеспечения

Авторы

Романова Т. Н.^*, Анисимов А. В.^**

Московский государственный технический университет им. Н.Э. Баумана, 2-я Бауманская ул., 5, стр. 1, Москва, 105005, Россия

*e-mail: rtn@bmstu.ru
**e-mail: alan_mephi@mail.ru

Аннотация

Представлена математическая постановка задачи структурного синтеза в области разработки программного обеспечения. Рассмотрены два варианта задачи, относящиеся к разным классам сложности, и способы их решения. Приведён сравнительный анализ эффективности методов применительно к рассматриваемым задачам.

Ключевые слова:

структурный синтез; теория множеств; оптимизация на графах; NP-трудность; приближённый метод; метод локальных улучшений; полный перебор; жадный алгоритм Радо—Эдмондса; комбинаторно-оптимизационная задача; асимптотическая оценка вычислительной сложности