Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

Подход к оценке репрезентативности случайно сгенерированных дискретных структур на примере недетерминированных конечных автоматов

Диссертация: Подход к оценке репрезентативности случайно сгенерированных дискретных структур на примере недетерминированных конечных автоматов
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Тематика настоящей работы (исследование репрезентативности случайно сгенерированных входных данных, применяемое для различных задач дискретной оптимизации) в настоящее время считается специалистами практически неисследованной. Это в первую очередь касается отсутствия общей теории, которую фактически приходится создавать заново для каждой рассматриваемой предметной области. Данная работа… Читать ещё >

Содержание

  • 1. Введение
  • 2. Методы получения входных данных
  • 3. Конечные автоматы и операции над ними
  • 4. Алгоритмы построения базисного конечного автомата и универсального конечного автомата
  • 5. Алгоритмы случайной генерации недетерминированных конечных автоматов
  • 6. Статистические критерии для оценки репрезентативности
  • 7. Характеристики недетерминированных конечных автоматов
  • 8. Модель случайной генерации структур для различных предметных областей
  • 9. Применение рассмотренного подхода к репрезентативности в различных предметных областях
  • 10. Описание вычислительных экспериментов и полученные результаты
  • 11. Применение теории репрезентативности к вариантам алгоритмов принятия решений

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

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

.

Тематика настоящей работы (исследование репрезентативности случайно сгенерированных входных данных, применяемое для различных задач дискретной оптимизации) в настоящее время считается специалистами практически неисследованной. Это в первую очередь касается отсутствия общей теории, которую фактически приходится создавать заново для каждой рассматриваемой предметной области [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 приложений.

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

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

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

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

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

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

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

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

Заключение

.

Показать весь текст

Список литературы

  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. С., Рогова О. Алгоритм определения репрезентативности НКА. // Интернет-журнал «Электроника и информационные технологии», 2009. http://db.inforeg.ru
  47. С., Рогова О. Метод случайной генерации недетерминированных конечных автоматов и проверка репрезентативности сгенерированных структур // Вестник ВГУ, серия «Системный анализ и информационные технологии». Воронеж, 2010. — № 2. — С. 5−8.
  48. Н., Шалыто А. Автоматное программирование. -СПб.: Питер, 2009. 176 с.
  49. Разборов A. Theoretical Computer Science: взгляд математика. // Компьютерра. № 2. — 2001.
  50. О. Исследование репрезентативности случайно сгенерированных входных данных // Молодежь и наука: модернизация и инновационное развитие страны: Сб. трудов международной научно-практической конф. Пенза: Изд-во ПТУ, 2011. 2 ч. — С. 435 — 437.
  51. О. Об одном подходе к репрезентативности обучающегося алгоритма // Проблемы информатики в образовании, управлении, экономике и технике: Сб. статей IX Международной научно-технической конф. Пенза: Приволжский Дом знаний, 2009. С. 103 — 106.
  52. О. Подход к репрезентативность входных данных // Проведение научных исследований в области обработки, хранения, передачи и защиты информации: Сб. научных трудов Всероссийской конф. Ульяновск: УлГТУ, 2009. Т. 2. — С. 31 — 38.
  53. О. Репрезентативность входных данных // Вектор науки То-льяттинского государственного университета. Тольятти, 2010. -№ 3 (13).-С. 19−21.
  54. А., Михайлов А. Математическое моделирование. Идеи. Методы. Примеры. -М.: Физматлит, 2001.
  55. А. Геометрическая структура почти всех булевых функций. -Проблемы кибернетики. 1975. -№ 30. — С. 227−261.
  56. А. Дизъюнктивные нормальные формы. М.: Изд-во МГУ, 1975.-С. 1−89
  57. А. Локальные алгоритмы. Некоторые вопросы сложности алгоритмов. — Изд-во факультета ВМиК МГУ, 2001. — С.6−11.
  58. В., Климович А. Логическое проектирование цифровых систем на основе программируемых логических интегральных схем. Изд-во «Горячая линия — Телеком», 2007. — 636 с.
  59. Л. О некоторых определениях класса КС-языков. -Программирование (РАН). 1999. — № 5. — стр. 15−25.
  60. Н., Шалыто А. Программирование с явным выделением состояний. Мир ПК. — 2001. — № 9. — С. 132−138.
  61. Дж. Алгоритм для минимизации конечного автомата. -Кибернетический сборник, новая серия, вып. 11. М.: Мир, 1974.1. С. 177−184.
  62. Binder R. Testing Object-Oriented Systems: Models, Patterns, and Tools. -Addison-Wesley, 1999.
  63. Bridson M., Gilman R. Formal language theory and the geometry of 3-manifolds. Commentarii Mathematici Helvetici. 1996. — № 71. — P. 525−555.
  64. Brzozowski J. Open problems about regular languages. Ronald V. Book, editor, Formal language theory—Perspectives and open problems. — N. Y.: Academic Press, 1980. — P. 2317.
  65. Champarnaud J., Hansel G., Paranthoen Т., Ziadi D. Random generation models for NFA’s. Journal of Automata, Languages and Combinatorics. — 2004. — № 9. — P. 203−216.
  66. Chomsky N., Miller G. Finite state languages, Inform, and Control. M.: Мир, 1962.-233−255 с.
  67. Eggen L. Transition graphs and the star-height of regular events. The Michigan Mathematical Journal. — 1963. — P. 385−397.
  68. 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.
  69. Gross M., Perrin D. Electronic Dictionaries and Automata in Computational Linguistics. Lecture Notes in Computer Science 377. — SpringerVerlag, Berlin. — 1989.
  70. Gurevich Y., Veanes M., Wallace C. Can Abstract State Machines Be Useful in Language Theory? Theoretical Computer Science. — 2007. 376 p.
  71. Hashiguchi K. Algorithms for determining relative star height and star height. Inform. Comput., 1988 — № 78. — P. 124−169.
  72. Holland J. Adaptation in Natural and Artificial Systems. // Ann Arbor: The University of Michigan Press, 1975.
  73. Hopcroft J., Ullman J. Formal languages and their relation to automata. -Addison-Wesley, Reading, Mass, 1969.-212−215 c.
  74. 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.
  75. Kent Dybvig R. The Scheme Programming Language, Fourth Edition. Mi l Press, 2009.
  76. Levin L. Randomness and Nondeterminism. J. Symb. Logic. — 1993. -№ 58(3). -P. 1102−1103.
  77. Little J., Murty K., Sweeney D., Karel C. An algorithm for the traveling salesman problem. // Operations Research. 1963. — Vol.11 — P. 972 989.
  78. Lombardy S., Sakarovitch J. The Universal Automaton. // Logic and Automata, Texts in Logic and Games, Amsterdam Univ. Press. 2008. -Vol.2.-P. 457−504.
  79. Lucchesi C., Kowaltowski T. Applications of Finite Atomata Representing Large Vocabularies. // Relatorio Tecniko DCC. 1992. — № 1.
  80. McCulloch W., Pitts W. A logical calculus of the ideas immanent in nervous activity. // Bulletin of Mathematical Biophysics. 1943. — № 5. -P. 115−133.
  81. 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.
  82. Melnikov B. Some more on the finite automata. // The Korean Journal of Computational and Applied Mathematics. 1998. -№ 3. — P. 495−506.
  83. 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.
  84. 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.
  85. Naur P. The design of the GIER ALGOL compiler Part II. // BIT Numerical Mathematics 3. September 1963. — P. 145−166.
  86. Rabin M., Scott D. Finite automata and their decision problems. // IBM J. Research and Development. 1959. — № 3. — P. 114−125.
  87. The international SAT Competitions web page: сайт. URL: http://www.satcompetition.org/
  88. Thomas W. Automata on Infinite Objects. // Handbook of Theoret. Com-put. Sci., Vol. B, Elsevier Sci. Publ. 1990. — P. 133−191.
  89. Van Zijl L., Oliver F., Harper J.-P. The MERLin Environment applied to *-NFAs. // Proceedings of the CIAA. July, 2000.
  90. Wolter K. Introduction to Variance Estimation. // Springer Science Business Media LLC, 2006. 447 p.
  91. Wood D. Grammar and L Forms: an Introduction. Berlin: Springer, 1980.-328 p.
Заполнить форму текущей работой

На отлично!