Инженерный журнал: наука и инновацииЭЛЕКТРОННОЕ НАУЧНО-ТЕХНИЧЕСКОЕ ИЗДАНИЕ
свидетельство о регистрации СМИ Эл № ФС77-53688 от 17 апреля 2013 г. ISSN 2308-6033. DOI 10.18698/2308-6033
  • Русский
  • Английский
Статья

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

Опубликовано: 19.11.2013

Авторы: Иванова Г.С.

Опубликовано в выпуске: #11(23)/2013

DOI: 10.18698/2308-6033-2013-11-1043

Раздел: Информационные технологии

Предложен подход, позволяющий автоматически получить оценки вычислительной, временной и емкостной сложности структурных алгоритмов решения задач структурного анализа и синтеза, описанных в операциях над графами и/или множествами. Алгоритм реализует метод D-карт. Алгоритм оценки вычислительной и временной сложности предполагает рекурсивное распознавание базовых и производных структурных конструкций алгоритма с применением их инвариантов, расчет интегральных характеристик этих конструкций и свертку распознанных конструкций с назначением им соответствующих оценок. Оценка емкостной сложности алгоритма выполняется с использованием моделей задействованных структур данных.


Литература
[1] Кормен Т., Лейзерсон Ч., Риверст Р., Штайн К. Алгоритмы: построение и анализ. Москва, Вильямс, 2005, 1296 с.
[2] Кнут Д.Э. Искусство программирования. Москва, Наука, 2006, 437 с.
[3] Vitter J., Flajolet Ph. Average-Case Analyse of Algorithms and Data Structure. Handbook of Handbook of theoretical computer science: algorithms and complexity, 1991, vol. A, pp. 431-524
[4] Овчинников В.А., Иванова Г.С. Информационно-логическая модель алгоритма. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение, 2005, № 2(59), с. 109-121
[5] Иванова Г.С. Формальная постановка задачи структуризации алгоритмов. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение, 2005, № 3 (60), с. 64-73
[6] Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона. Москва, ДМК Пресс, 2010, 406 с.
[7] Иванова Г.С. Математические модели структур данных. Информационные технологии, 2006, № 9, с. 44-52
[8] Овчинников В.А. Операции над ультра- и гиперграфами для реализации процедур анализа и синтеза структур сложных систем. Ч. 1. Инженерное образование, 2009, № 10. URL: http://technomag.bmstu.ru/doc/132769.html
[9] Овчинников В.А. Операции над ультра- и гиперграфами для реализации процедур анализа и синтеза структур сложных систем. Ч. 2. Инженерное образование, 2009, № 11. URL: http://technomag.bmstu.ru/doc/133223.html
[10] Овчинников В.А. Операции над ультра- и гиперграфами для реализации процедур анализа и синтеза структур сложных систем. Ч. 3. Инженерное образование, 2009, № 12. URL: http://technomag.bmstu.ru/doc/134335.html