1
УДК 004.4'24+519.6
Автоматизация анализа вычислительной
и емкостной сложности алгоритмов
на множествах и графах
© Г.С. Иванова
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
Предложен подход, позволяющий автоматически получить оценки вычислитель-
ной, временной и емкостной сложности структурных алгоритмов решения задач
структурного анализа и синтеза, описанных в операциях над графами и/или
множествами. Алгоритм реализует метод D-карт.
Алгоритм оценки вычислительной и временной сложности предполагает рекурсив-
ное распознавание базовых и производных структурных конструкций алгоритма с
применением их инвариантов, расчет интегральных характеристик этих кон-
струкций и свертку распознанных конструкций с назначением им соответст-
вующих оценок. Оценка емкостной сложности алгоритма выполняется с исполь-
зованием моделей задействованных структур данных.
Ключевые слова
:
задачи структурного синтеза, структурный алгоритм, вычис-
лительная сложность, емкостная сложность, автоматизация оценки.
Введение.
Алгоритмы решения комбинаторных задач структур-
ного анализа и синтеза часто имеют экспоненциальную оценку вы-
числительной сложности, и при больших размерностях входов их
выполнение может потребовать нереализуемо больших затрат вре-
менных и емкостных ресурсов вычислительной системы. Поэтому в
процессе разработки алгоритма необходимо проводить анализ его
вычислительной и емкостной сложности.
Исследованию свойств алгоритмов решения задач рассмат-
риваемого класса уделяется большое внимание, наиболее известными
в этой области являются работы [1, 2]. При этом анализ вычислитель-
ной и емкостной сложности алгоритмов их разработчики проводят
вручную.
В настоящее время в литературе встречается единственное
упоминание о системе, выполняющей автоматизированный анализ
алгоритмов на графах, в которой для оценки вычислительной слож-
ности использован вероятностный подход [3]. Он имеет ряд
недостатков. Во-первых, оценка осуществляется по программе на
алгоритмическом языке и, соответственно, жестко к нему привязана.
Во-вторых, класс алгоритмов, для которых выполняется оценка,
ограничен заданным в системе набором расчетных функций, что
существенно сужает область применения системы. И, наконец,
в-третьих, система выдает только асимптотическую оценку, в то
