Автоматизация анализа вычислительной и емкостной сложности алгоритмов на множествах и графах

задачи структурного синтеза структурный алгоритм вычислительная сложность емкостная сложность автоматизация оценки

Использование радиуса устойчивости оптимизационных задач для скрытия и проверки корректности информации, Решение стационарных двумерных задач естественной конвекции в замкнутых полостях методом R-функций, ...

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

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт