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