Подход к оценке репрезентативности случайно сгенерированных дискретных структур на примере недетерминированных конечных автоматов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Рогова, Ольга Александровна

  • Рогова, Ольга Александровна
  • кандидат физико-математических науккандидат физико-математических наук
  • 2012, Тольятти
  • Специальность ВАК РФ05.13.18
  • Количество страниц 114
Рогова, Ольга Александровна. Подход к оценке репрезентативности случайно сгенерированных дискретных структур на примере недетерминированных конечных автоматов: дис. кандидат физико-математических наук: 05.13.18 - Математическое моделирование, численные методы и комплексы программ. Тольятти. 2012. 114 с.

Оглавление диссертации кандидат физико-математических наук Рогова, Ольга Александровна

1. Введение.

2. Методы получения входных данных.

3. Конечные автоматы и операции над ними.

4. Алгоритмы построения базисного конечного автомата и универсального конечного автомата.

5. Алгоритмы случайной генерации недетерминированных конечных автоматов.

6. Статистические критерии для оценки репрезентативности.

7. Характеристики недетерминированных конечных автоматов.

8. Модель случайной генерации структур для различных предметных областей.

9. Применение рассмотренного подхода к репрезентативности в различных предметных областях.

10. Описание вычислительных экспериментов и полученные результаты.

11. Применение теории репрезентативности к вариантам алгоритмов принятия решений.

Рекомендованный список диссертаций по специальности «Математическое моделирование, численные методы и комплексы программ», 05.13.18 шифр ВАК

Введение диссертации (часть автореферата) на тему «Подход к оценке репрезентативности случайно сгенерированных дискретных структур на примере недетерминированных конечных автоматов»

Актуальность темы

Тематика настоящей работы (исследование репрезентативности случайно сгенерированных входных данных, применяемое для различных задач дискретной оптимизации) в настоящее время считается специалистами практически неисследованной. Это в первую очередь касается отсутствия общей теории, которую фактически приходится создавать заново для каждой рассматриваемой предметной области [52]. Данная работа не претендует на создание такой общей теории - однако может рассматриваться как начало работ в данном направлении; она фактически формулирует необходимый подход для целого класса задач, связанных с исследованием репрезентативности случайно сгенерированных дискретных структур. В представляемой работе этот подход рассматривается на примере недетерминированных конечных автоматов (ниже - НКА).

В реальных задачах требуется рассматривать конечные автоматы с достаточно большим количеством состояний. Сразу отметим только некоторые из возможных областей применения НКА: они используются, например, в лексических анализаторах - для компиляции языков программирования и для реализации человеко-машинного интерфейса; при тестировании программного обеспечения на основе моделей проверяемой системы [67]; при проектировании интегральных микросхем [62]; при редактировании текста и сравнении образов [26]; при автоматном программировании [51].

Для проверки различных алгоритмов необходимы входные данные. Но во многих задачах невозможно хранение набора (наборов) входных данных - например, из-за ограничений памяти системы. Поэтому становится актуальным исследование методов получения входных данных для решения различных задач. Одним из таких методов является метод случайной генерации данных.

Ввиду того, что в конкретных задачах используются НКА с большим числом состояний, в программах, предназначенных для имитационного моделирования, необходимо генерировать НКА также с большим числом состояний. Основной целью комплекса работ, проводимых в данном направлении, является применение к сгенерированным дискретным структурам (в частности - к НКА) конкретных характеристик - для их сравнения с соответствующими характеристиками реальных объектов.

Цель работы

Целью работы является описание подхода к оценке репрезентативности случайно сгенерированных дискретных математических структур - на основе алгоритмов генерации недетерминированных конечных автоматов, а также описание применения полученных моделей для создания приемлемых (репрезентативных) алгоритмов случайной генерации НКА для выбранной предметной области - с применением обучающихся алгоритмов.

Основные задачи исследования:

1) описание оригинальных модификаций алгоритмов ван Зейл случайной генерации недетерминированных конечных автоматов и их реализация;

2) для нескольких выбранных предметных областей применения недетерминированных конечных автоматов - описание конкретных характеристик НКА;

3) проверка репрезентативности генерируемых структур - согласно предлагаемой автором методике;

4) на основе применения к генерируемым структурам конкретных характеристик данной предметной области - разработка и реализация метода случайной генерации недетерминированного конечного автомата, более приемлемого (репрезентативного) для выбранной предметной области;

5) формулировка подхода для исследования репрезентативности входных данных в других областях;

6) применение разработанного подхода случайной генерации недетерминированных конечных автоматов в задачах статистического исследования свойств конкретных НКА;

7) применение современных инструментальных средств разработки программного обеспечения, в том числе средств объектно-ориентированного программирования.

Объект исследования

Объектом исследования являются недетерминированные конечные автоматы Рабина-Скотта (Медведева) и обучающиеся алгоритмы.

Предмет исследования

Предметом исследования являются алгоритмы работы с недетерминированными конечными автоматами.

Методы исследования

В работе использованы:

• математическое моделирование;

• математические методы разработки алгоритмов;

• элементы математической статистики;

• методы системного анализа;

• системное и объектно-ориентированное программирование.

Результаты исследования

Результатами диссертационного исследования являются новые вычислительные методы и алгоритмы работы с недетерминированными конечными автоматами, а также полученные новые закономерности, характеризующие изучаемые объекты.

Научная новизна

Описан подход к оценке репрезентативности для класса задач, связанных с исследованием недетерминированных конечных автоматов. Предложенный подход заключается в выделении характеристик для рассматриваемой предметной области; при этом недетерминированные конечные автоматы можно считать одной из таких областей. Также в работе рассмотрено возможное применение описанного подхода к репрезентативности входных данных и в других предметных областях.

Практическая значимость исследования

Полученные результаты могут быть применены в различных задачах, связанных с исследованием свойств недетерминированных конечных автоматов. Описанный подход к оценке репрезентативности входных данных может быть применён и в других предметных областях, в других задачах дискретной оптимизации.

Достоверность результатов

Достоверность и обоснованность научных положений подтверждается соответствием результатов теоретических исследований экспериментальным тестам и расчётам математического моделирования. Результаты исследований обсуждались на российских и международных конференциях и семинарах.

Основные положения, выносимые на защиту

1) Разработка оригинальных методов случайной генерации недетерминированных конечных автоматов на основе подходов ван Зейл и Па-рантоэна.

2) Применение статистических критериев (характеристик) для проверки случайности сгенерированной последовательности чисел с целью исследования репрезентативности недетерминированных конечных автоматов.

3) Описание полученных структур (сгенерированных недетерминированных конечных автоматов) с помощью сформулированных характеристик и получение численных характеристик, отражающих репрезентативность в данной конкретной предметной области.

4) Разработка методов изменения алгоритмов генерации недетерминированных конечных автоматов при неудовлетворительных результатах, полученных при вычислении оценки репрезентативности в конкретной предметной области.

5) Применение описанного подхода к репрезентативности входных данных в других областях (моделирование задачи оптимального управления) и формулировка подхода к оценке репрезентативности для произвольных сгенерированных дискретных структур.

6) Применение описанного подхода к некоторым задачам статистического исследования свойств недетерминированных конечных автоматов.

Апробация результатов исследования

Основные научные и практические результаты исследований по теме диссертации докладывались на:

• Всероссийской конференции «Проведение научных исследований в области обработки, хранения, передачи и защиты информации» (г. Ульяновск, 2009);

• IX Международной научно-технической конференции, посвящённой 70-летию Пензенского государственного педагогического университета им. В.Г.Белинского «Проблемы информатики в образовании, управлении, экономике и технике» (г. Пенза, 2009);

• VI Всероссийской научно-практической конференции-конкурсе «Технологии Microsoft в теории и практике программирования» (г. Томск, 2009);

• конференции в рамках академической программы «Летняя школа Intel» (г. Нижний Новгород, 2010);

• V Международной научной конференции «Математика. Образование. Культура» (г. Тольятти, 2011);

• Международная научно-практическая конференция «Молодежь и наука: модернизация и инновационное развитие страны» (г. Пенза, 2011);

• научном семинаре кафедры мехатроники в автоматизированных производствах Самарского государственного университета путей сообщения, январь 2012;

• научном семинаре кафедры математического анализа Ульяновского государственного педагогического университета, январь 2012;

• научных семинарах кафедры прикладной математика и информатики Тольяттинского государственного университета, 2007-2012.

Публикации

Основные результаты диссертации опубликованы в 10 работах, 2 из них входит в список изданий, рекомендованных ВАК.

Личный вклад автора

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

Структура и объём диссертации

Общий объём диссертации - 114 страниц. Диссертация состоит из введения, 10 глав, заключения, списка используемой литературы из 95 наименований и 2 приложений.

Похожие диссертационные работы по специальности «Математическое моделирование, численные методы и комплексы программ», 05.13.18 шифр ВАК

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Рогова, Ольга Александровна

Основные результаты заключаются в следующем:

• Разработаны методы случайной генерации недетерминированных конечных автоматов, являющиеся модификациями алгоритмов ван Зейл и Парантоэна.

• Описан метод исследования репрезентативности сгенерированных дискретных структур на основе применения статистических критериев к формируемым характеристикам.

• Данный метод применён к недетерминированным конечных автоматам - для чего описаны конкретные численные характеристики для этой предметной области.

• Разработаны методы изменения алгоритмов генерации недетерминированных конечных автоматов при неудовлетворительных результатах, полученных при вычислении оценки репрезентативности в конкретной предметной области применения НКА.

• Описана возможность применения этого подхода к исследованию репрезентативности входных данных в других областях и дана формулировка подхода к оценке репрезентативности для произвольных сгенерированных дискретных структур.

• Описанный подход применён к некоторым задачам статистического исследования свойств недетерминированных конечных автоматов.

• Разработанная теория репрезентативности применена к алгоритмизации некоторых задач принятия решений для разработки эвристических алгоритмов минимизационных проблем НКА.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Рогова, Ольга Александровна, 2012 год

1. Алексеева А., Мельников Б. Итерации конечных и бесконечных языков и недетерминированные конечные автоматы. - Вектор науки Тольяттинского государственного университета. - Тольятти, 2011. -№3 (17).-С. 30-33.

2. Алёхина М. Синтез асимптотически оптимальных по надежности схем. Пенза: изд-во ПТУ, 2006. - 150с.

3. Андерсон Т. Введение в многомерный статистический анализ. М.: Физматлит, 1963. - 500 стр.

4. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии, инструменты. М.- СПб - Киев: Вильяме, 2003. - 768 с.

5. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. - Т. 1. - 612 с.

6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 535 с.

7. Балинова В. Статистика в вопросах и ответах: Учеб. пособие. М.: ТК Велби, изд-во Проспект, 2004. - 344 с.

8. Батищев Д., Исаев С. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов. //Межвузовский сборник научных трудов «Высокие технологии в технике, медицине и образовании». Воронеж: ВГТУ, 1997.

9. Брауэр В. Введение в теорию конечных автоматов. М.: Радио и связь, 1987. - 392 с.

10. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985.-410 с.

11. Вирт Н. Паскаль. Руководство для пользователя и описание языка. -М.: Финансы и статистика, 1982.

12. Вылиток А. О построении графа магазинного автомата. Вестник Московского университета, сер. 15. - 1996. - №3. - стр. 68-73.

13. Гилл А. Линейные последовательностные машины. Анализ, синтез и применение. М.: Наука, 1974. - 287 с.

14. Грогоно П. Программирование на языке Паскаль. М.: Мир, 1982

15. Гумаюнов В. Принцип «турнирного» самообучения для генетических алгоритмов (дипломная работа). Ульяновский гос. университет, ф-т Инф. и телекомм, технологий, 2003.

16. Гурин Р.Ф., Романенко С.А. Язык программирования Рефал Плюс. -Переславль: Университет города Переславля, 2006. 13 с.

17. Девятов А. Варианты применения минимизации ДНФ в прикладных оптимизационных задачах (дипломная работа). Тольятти: ТГУ, 2009. - 56с.

18. Журавлев Ю. Алгоритмы упрощения дизъюнктивных нормальных форм конечного индекса. Доклад академии наук СССР, 1961. - Т. 139. -№6. - С.1329-1331.

19. Журавлев Ю. Локальные алгоритмы вычисления информации. -Кибернетика. 1965. -№1. - С. 12-19.

20. Журавлев Ю. Оценка сложности локальных алгоритмов для некоторых экстремальных задач на конечных множествах. Доклад академии наук СССР. - 1964. - Т. 158. -№ 5. - С. 1018-1021.

21. Канер С. Тестирование программного обеспечения. М.: ДиаСофт, 2000.

22. Кендалл М., Стьюарт А. Статистические выводы и связи. Наука, 1973.-466 стр.

23. Кендалл М., Стьюарт А. Теория распределений, 2-е издание. -Наука, 1966. Т. 1 - 588 стр.

24. Кнут Д. Искусство программирования, т.2. Получисленные алгоритмы. М.: Вильяме, 2003. - 832 с.

25. Кобзарь А. Прикладная математическая статистика. Для инженеров и научных работников. -М.: Физматлит, 2006. 816 с.

26. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. МЦНМО, 2004. - 956 с.

27. Крамер Г. Математические методы статистики. М.: Мир, 1975. -648 с.

28. Лаптев В. С++. Объектно-ориентированное программирование. Изд-во Питер, 2008.

29. Ларман К. Применение UML 2.0 и шаблонов проектирования = Applying UML and Patterns : An Introduction to Object-Oriented Analysis and Design and Iterative Development, 3-е изд. M.: Вильяме, 2006. -736 c.

30. Левитин А. Алгоритмы: введение в разработку и анализ, 4-е издание. М.: Вильяме, 2006. - 212-215 с.

31. Лернер А. Начала кибернетики. М.: Наука, 1967.

32. Липаев В. В. Тестирование программ. М.: Радио и связь, 1986.

33. Майерс Г. Искусство тестирования программ. М.: Финансы и статистика, 1982.

34. Мельников Б. Мультиэвристический подход к задачам дискретной оптимизации. // Кибернетика и системный анализ (НАН Украины). -2006. -№ 3. С. 32-42.

35. Мельников Б. Недетерминированные конечные автоматы. Тольятти: Изд-во ТГУ, 2009. - 160 с.

36. Мельников Б. Некоторые следствия условия эквивалентности однозначных скобочных грамматик. Вестник Моск. Ун-та, сер. Вычисл. матем. и киб-ка. - 1991. -№ 3. - С. 51-53.

37. Мельников Б. Об одной классификации последовательностных контекстно-свободных языков и грамматик. Вестник Моск. ун-та, сер. Вычисл. матем. и киб-ка. - 1993. - № 3. - С. 64-69.

38. Мельников Б. Подклассы класса контекстно-свободных языков. -М.: Изд-во МГУ, 1995. 159 с.

39. Мельников Б. Эвристики в программировании недетерминированных игр. Программирование (Известия РАН). - 2001. - №5. - с.63-80.

40. Мельников Б., Зубова М. Построение автомата СОМ на основе базисного автомата. Вектор науки Тольяттинского государственного университета. - 2010. - №4. - 30-32.

41. Мельников Б., Мельникова А. Автомат «Ватерлоо» с точки зрения базисного автомата Известия вузов. Математика, 2012.

42. Мельников Б., Пивнева С., Рогова О. Ещё раз о репрезентативности случайно сгенерированных недетерминированных конечных автоматов. // Некоторые вопросы математического моделирования дискретных систем: Сб. науч. тр. Тольятти: ТГУ, 2011. - С. 175-183.

43. Милькова Е. Подход к репрезентативности входных данных для случайной генерации дизъюнктивных нормальных форм (дипломная работа). Тольятти: ТГУ, 2011. - 56 с.

44. Оллонгрен А. Определение языков программирования интерпретирующими автоматами М.: Мир, 1977. - 287 с.

45. Пивнева С. Математическое моделирование оптимального управления образовательной средой. // Татищевские чтения: Актуальные проблемы науки и практики. Материалы международной научной конференции Тольятти. - 2004.

46. Пивнева С. Принятие решений в гуманитарных областях подходы к репрезентативности входных данных и сравнению эффективности алгоритмов. // Информационные технологии моделирования и управления - Воронеж: Научная книга. - 2008. - №8(51). -888с.

47. Пивнева С., Рогова О. Алгоритм определения репрезентативности НКА. // Интернет-журнал «Электроника и информационные технологии», 2009. http://db.inforeg.ru

48. Пивнева С., Рогова О. Метод случайной генерации недетерминированных конечных автоматов и проверка репрезентативности сгенерированных структур // Вестник ВГУ, серия «Системный анализ и информационные технологии». Воронеж, 2010. - №2. - С. 5-8.

49. Поликарпова Н., Шалыто А. Автоматное программирование. -СПб.: Питер, 2009. 176 с.

50. Разборов A. Theoretical Computer Science: взгляд математика. // Компьютерра. № 2. - 2001.

51. Рогова О. Исследование репрезентативности случайно сгенерированных входных данных // Молодежь и наука: модернизация и инновационное развитие страны: Сб. трудов международной научно-практической конф. Пенза: Изд-во ПТУ, 2011. 2 ч. - С. 435 - 437.

52. Рогова О. Об одном подходе к репрезентативности обучающегося алгоритма // Проблемы информатики в образовании, управлении, экономике и технике: Сб. статей IX Международной научно-технической конф. Пенза: Приволжский Дом знаний, 2009. С. 103 - 106.

53. Рогова О. Подход к репрезентативность входных данных // Проведение научных исследований в области обработки, хранения, передачи и защиты информации: Сб. научных трудов Всероссийской конф. Ульяновск: УлГТУ, 2009. Т. 2. - С. 31 - 38.

54. Рогова О. Репрезентативность входных данных // Вектор науки То-льяттинского государственного университета. Тольятти, 2010. -№3 (13).-С. 19-21.

55. Самарский А., Михайлов А. Математическое моделирование. Идеи. Методы. Примеры. -М.: Физматлит, 2001.

56. Сапоженко А. Геометрическая структура почти всех булевых функций. -Проблемы кибернетики. 1975. -№30. - С. 227-261.

57. Сапоженко А. Дизъюнктивные нормальные формы. М.: Изд-во МГУ, 1975.-С. 1-89

58. Сапоженко А. Локальные алгоритмы. Некоторые вопросы сложности алгоритмов. - Изд-во факультета ВМиК МГУ, 2001. - С.6-11.

59. Соловьев В., Климович А. Логическое проектирование цифровых систем на основе программируемых логических интегральных схем. Изд-во «Горячая линия - Телеком», 2007. - 636 с.

60. Станевичене Л. О некоторых определениях класса КС-языков. -Программирование (РАН). 1999. - №5. - стр. 15-25.

61. Туккель Н., Шалыто А. Программирование с явным выделением состояний. Мир ПК. - 2001. - №9. - С. 132-138.

62. Хопкрофт Дж. Алгоритм для минимизации конечного автомата. -Кибернетический сборник, новая серия, вып. 11. М.: Мир, 1974.1. С. 177-184.

63. Binder R. Testing Object-Oriented Systems: Models, Patterns, and Tools. -Addison-Wesley, 1999.

64. Bridson M., Gilman R. Formal language theory and the geometry of 3-manifolds. Commentarii Mathematici Helvetici. 1996. - №71. - P. 525-555.

65. Brzozowski J. Open problems about regular languages. Ronald V. Book, editor, Formal language theory—Perspectives and open problems. - N. Y.: Academic Press, 1980. - P. 23^17.

66. Champarnaud J., Hansel G., Paranthoen Т., Ziadi D. Random generation models for NFA's. Journal of Automata, Languages and Combinatorics. - 2004. - №9. - P. 203-216.

67. Chomsky N., Miller G. Finite state languages, Inform, and Control. M.: Мир, 1962.-233-255 с.

68. Eggen L. Transition graphs and the star-height of regular events. The Michigan Mathematical Journal. - 1963. - P. 385-397.

69. Garrido-Alenda A., Forcada M. Comparing nondeterministic and qua-sideterministic finite-state transducers built from morphological dictionaries. Procesamiento del Lenguaje Natural. - 2002. - №29. - P. 73-80.

70. Gross M., Perrin D. Electronic Dictionaries and Automata in Computational Linguistics. Lecture Notes in Computer Science 377. - SpringerVerlag, Berlin. - 1989.

71. Gurevich Y., Veanes M., Wallace C. Can Abstract State Machines Be Useful in Language Theory? Theoretical Computer Science. - 2007. 376 p.

72. Hashiguchi K. Algorithms for determining relative star height and star height. Inform. Comput., 1988 - №78. - P. 124-169.

73. Holland J. Adaptation in Natural and Artificial Systems. // Ann Arbor: The University of Michigan Press, 1975.

74. Hopcroft J., Ullman J. Formal languages and their relation to automata. -Addison-Wesley, Reading, Mass, 1969.-212-215 c.

75. Johnson W., Porter J., Ackley S., Ross D. Automatic generation of efficient lexical processors using finite state techniques. Comm. ACM 11. - 1968. -№12. -P. 805-813.

76. Kent Dybvig R. The Scheme Programming Language, Fourth Edition. Mi l Press, 2009.

77. Levin L. Randomness and Nondeterminism. J. Symb. Logic. - 1993. -№58(3). -P. 1102-1103.

78. Little J., Murty K., Sweeney D., Karel C. An algorithm for the traveling salesman problem. // Operations Research. 1963. - Vol.11 - P. 972989.

79. Lombardy S., Sakarovitch J. The Universal Automaton. // Logic and Automata, Texts in Logic and Games, Amsterdam Univ. Press. 2008. -Vol.2.-P. 457-504.

80. Lucchesi C., Kowaltowski T. Applications of Finite Atomata Representing Large Vocabularies. // Relatorio Tecniko DCC. 1992. - №1.

81. McCulloch W., Pitts W. A logical calculus of the ideas immanent in nervous activity. // Bulletin of Mathematical Biophysics. 1943. - №5. -P. 115-133.

82. Melnikov B. On an expansion of nondeterministic finite automata. // J. of Applied Mathematics and Computing, Springer Berlin/Heidelberg. -2007.-Vol.24-№1-2-P. 155-165.

83. Melnikov B. Some more on the finite automata. // The Korean Journal of Computational and Applied Mathematics. 1998. -№3. - P. 495-506.

84. Melnikov B. Melnikova A. A new algorithm of constructing the basis finite automaton. // Informatika (Lithuanian Acad. Sci. Ed.). 2002. -Vol.13-№3-P. 299-310.

85. Melnikov B., Melnikova A. Some properties of the basis finite automaton. // J. of Applied Math, and Computing (The Korean J. of Computational and Applied Math.). -2002. -Vol.9. -№1. -P. 131-150.

86. Naur P. The design of the GIER ALGOL compiler Part II. // BIT Numerical Mathematics 3. September 1963. - P. 145-166.

87. Rabin M., Scott D. Finite automata and their decision problems. // IBM J. Research and Development. 1959. - №3. - P. 114-125.

88. The international SAT Competitions web page: сайт. URL:http://www.satcompetition.org/

89. Thomas W. Automata on Infinite Objects. // Handbook of Theoret. Com-put. Sci., Vol. B, Elsevier Sci. Publ. 1990. - P. 133-191.

90. Van Zijl L., Oliver F., Harper J.-P. The MERLin Environment applied to *-NFAs. // Proceedings of the CIAA. July, 2000.

91. Wolter K. Introduction to Variance Estimation. // Springer Science Business Media LLC, 2006. 447 p.

92. Wood D. Grammar and L Forms: an Introduction. Berlin: Springer, 1980.-328 p.

Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.