Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Анализ структур данных для представления базовых моделей конечных автоматов

# 02, февраль 2015
DOI: 10.7463/0215.0756654
Файл статьи: SE-BMSTU...o168.pdf (1138.04Кб)
авторы: Гуренко В. В., Бычков Б. И.

УДК 004.043+519.713.1

Россия,  МГТУ им. Н.Э. Баумана

Проектирование сложных систем с использованием моделей конечных автоматов приводит к необходимости обоснованного выбора структур данных для их реализации.  Вопрос машинного представления автоматов и обоснования структур данных для них исследован недостаточно. Произвольное назначение структур данных для программной реализации моделей автоматов приводит к излишним затратам вычислительных ресурсов и снижает эффективность разработанных систем. В настоящей работе предложен подход к обоснованному выбору структур данных для представления базовых моделей конечных детерминированных автоматов и даны практические рекомендации на его основе.
Структуры данных статического и динамического типа выделены для трех основных способов задания автоматов Мили и Мура: таблицей переходов/выходов, матрицей соединений и графом переходов. К статическим структурам отнесены трехмерный массив, прямоугольная матрица и матрица списков. К динамическим – списковые структуры: двухуровневый и трехуровневый векторы Айлифа и многосвязный список. Названные структуры позволяют хранить всю требуемую информацию о компонентах модели конечного автомата – мощности характеристических множеств и данные о функциях переходов и выходов.
На основании алгоритмических особенностей задач, решаемых в теории автоматов, предложена система критериев для сравнительной оценки структур данных. Критерии ориентированы на емкостную и временную вычислительную сложность операций, выполняемых при решении таких задач, как эквивалентные преобразования автоматов, определение эквивалентности и изоморфизма автоматов, минимизация автомата.
С помощью системы критериев проведен сравнительный анализ структур данных как статического, так и динамического типа. Анализ позволил преимущественно выделить трехмерный массив, матрицу и двухуровневый вектор Айлифа – структуры, соответствующие способу задания автомата таблицей переходов/выходов. Для этих структур был проведен эксперимент по измерению времени выполнения над автоматами операций, входящих в систему критериев.
Анализ результатов эксперимента показал, что с увеличением размерности задач наиболее выгодно использовать динамическую структуру – двухуровневый вектор Айлифа. Статическим структурам в виде трехмерного массива и матрицы следует отдавать предпочтение для представления только тех автоматов,  компонентные множества которых обладают малой мощностью.
Результаты работы могут найти применение в процессе разработки программных систем с использованием аппарата теории автоматов при наложении условия минимизации затрат памяти и времени на обработку моделей конечных автоматов. В перспективе необходимо рассмотреть вопросы оптимизации структур данных, представляющих базовые модели конечных автоматов, и алгоритмов решения задач с их использованием. Также представляют интерес и другие модели, находящие практическое приложение, например, недетерминированные автоматы. Целесообразно исследовать аспекты машинной реализации таких моделей с точки зрения вычислительной сложности применяемых к ним алгоритмов.

Список литературы
  1. Гуренко В.В. Введение в теорию автоматов: электронное учебное пособие по дисциплинам «Теория автоматов», «Прикладная теория цифровых автоматов». М., МГТУ им. Н.Э. Баумана, 2013. Режим доступа: http://e-learning.bmstu.ru/moodle/mod/data/view.php?rid=206 (дата обращения 29.01.2015).
  2. Бобров М., Андрющенко Ю., Лаптева Н. Теория автоматов. 2005. Режим доступа: http://ofap.ulstu.ru/vt/Theory_of_automats/content.htm (дата обращения 29.01.2014).
  3. Ожиганов А.А. Теория автоматов: учеб. пособие. СПб.: НИУ ИТМО, 2013. 84 с.
  4. Лупал А.М. Теория автоматов: учеб. пособие. СПб.: СПбГУАП, 2000. 119 с.
  5. Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона + CD / пер. с англ. Ф.В. Ткачева. М .: ДМК Пресс , 2010. 272 с . [Wirth N. Algorithms and Data Structures. Oberon version: August 2004. Available at: http://www.inr.ac.ru/~info21/pdf/AD.pdf ].
  6. Райли Д. Абстракции и структуры данных: пер. с англ. М.: Мир, 1993. 752 с. [Riley D.D. Data Abstraction and Structures. Boyd & Fraser Pub. Co., 1987. 662 p.].
  7. Ахо А.В., Хопкрофт Д., Ульман Д.Д. Структуры данных и алгоритмы: пер. с англ. М.: Издательский дом Вильямс, 2001. 384 с. [ Aho A . V ., Hopcroft J . E ., Ullman J . D . Data Structures and Algorithms . Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983].
  8. Иванова   Г.С. Математические модели структур данных // Информационные технологии. 2006. № 9. С . 44-52.
  9. Guttag J. Abstract data types and the development of data structures // Communications of the ACM. 1977. Vol. 20, issue 6. P. 396-404. DOI: 10.1145/359605.359618
  10. Lattner C. Macroscopic Data Structure Analysis and Optimization. Ph.D. Thesis. Computer Science Dept., University of Illinois at Urbana-Champaign. 2005. 114 p. Available at: http://llvm.org/pubs/2005-05-04-LattnerPHDThesis-book.pdf, accessed 17.01.2015.
  11. Иванова Г.С. Способы представления структурных моделей // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2007. № 1. Режим доступа: http://technomag.bmstu.ru/doc/62742.html (дата обращения 17.01.2015).
  12. Овчинников В.А., Иванова Г.С., Ничушкина Т.Н. Выбор структур данных для представления графов при решении комбинаторно-оптимизационных задач // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2001. № 2 (43). C. 39-51.
  13. Пасечников К.А. Анализ проблемы синтеза оптимальных структур данных для алгоритмов решения комбинаторных задач на графах // Информатика и системы управления в ХХI веке: сб. трудов молодых ученых, аспирантов и студентов МГТУ им. Н.Э. Баумана. № 5. 2007. C. 118-124.
  14. Пасечников К.А. Синтез оптимальных структур данных для алгоритмов решения комбинаторных задач на графах: автореф. дис. ... канд. техн. наук. М., 2009. 16 с.
  15. Овчинников В.А. Графы в задачах анализа и синтеза структур сложных систем. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 423 с.
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)