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

На правах рукописи

Рогова Ольга Александровна

ПОДХОД К ОЦЕНКЕ РЕПРЕЗЕНТАТИВНОСТИ СЛУЧАЙНО СГЕНЕРИРОВАННЫХ ДИСКРЕТНЫХ СТРУКТУР НА ПРИМЕРЕ НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ

05.13.18 - математическое моделирование, численные методы и комплексы программ

5 " р ?п-;7

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Тольятти - 2012

005018532

Работа выполнена в ФГБОУ ВПО «Тольятгинский государственный университет»

Научный руководитель: доктор физико-математических наук,

профессор Мельников Борис Феликсович

Официальные оппоненты: доктор технических наук,

профессор Кацюба Олег Алексеевич

кандидат физико-математических наук, доцент Михеева Елизавета Алексеевна

Ведущая организация: Ульяновский государственный

педагогический университет им. И.Н.Ульянова

Защита диссертации состоится «13» апреля 2012 года в 15:00 часов на заседании диссертационного совета Д212.264.03 при Тольяттинском государственном университете по адресу: 445667, Тольятти, ул. Белорусская, 14. С диссертацией можно ознакомиться в библиотеке Тольятгинского государственного университета, с авторефератом - на сайте диссертационного совета http://edu.tltsu.ru/sites/site.php7s::: 1496.

Отзывы по данной работе в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 445667, Тольятти, ул. Белорусская, 14, ТГУ, диссертационный совет Д 212.264.03.

Автореферат разослан «13» марта 2012 года

Учёный секретарь

диссертационного совета Д 212.264.03

к.п.н., доцент

Пивнева С.В.

1. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Цель работы

Целью работы является описание подхода к оценке репрезентативности случайно сгенерированных дискретных математических структур — на основе алго-

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

статью, по-видимому, нужно рассматривать как обзорную научную, а не как научно-популярную. Стб-ит также отметить, что за прошедшие 11 лет подобная теория, по-видимому, не появилась.) 1 Binder R. Testing Object-Oriented Systems: Models, Patterns, and Tools. - Addison-Wesley, 1999.

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

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

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

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

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

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 приложений.

2. КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

Конечные автоматы с большим количеством состояний применяются в компьютерной лингвистике (словари, т.н. «спел-чекеры», морфологические анализаторы, переводчики и др.). Конечные автоматы с большим количеством стартовых состояний используются в разработке тезаурусов: при этом каждое начальное состояние принадлежит к одной из грамматических категорий слов (существительные, прилагательные и другие). По некоторым оценкам, автоматы для английского тезауруса, допускающие 9500 слов, имеют около 9000 вершин и 18000 переходов6. Недетерминированные конечные автоматы с большим числом состояний используются для представления морфологических словарей, содержащих словарное значение и морфологическую информацию приложений для обработки естественных языков, таких, как морфологический анализатор системы машинного перевода7.

Конечные автоматы с большим количеством состояний применяются и для Ы1-анализа8. При этом для моделирования процесса решения некоторых подзадач ЬЯ-анализа возможно применение таких недетерминированных конечных автоматов, которые сгенерированы предложенным в работе методом.

Во второй главе рассматриваются возможные методы получения входных данных для решения различных задач. При этом во многих задачах мы не можем хранить набор (наборы) входных данных. Например, при тестировании программного обеспечения наиболее трудоёмкими и детализирующими являются методы детерминированного тестирования. При детерминированном тестировании контролируется каждая комбинация исходных эталонных данных и соответствующая ей комбинация эталонных результатов. Разумеется, в сложных программах невозможно перебрать все комбинации исходных данных и проконтролировать результаты функционирования программы на каждой из них. В таких случаях применяется стохастическое тестирование, при котором исходные тестовые данные задаются множеством случайных величин с соответствующими распределениями, и при этом для сравнения полученных результатов также

6 Lucchesi С., Kowaltowski Т. Applications of Finite Atomata Representing Large Vocabularies. - Relatorio Täcniko DCC. -1992. - No. 1.

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

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

используются распределения случайных величин. В результате при стохастическом тестировании возможно более широкое варьирование исходных данных -хотя отдельные ошибки могут быть не обнаружены, если они мало искажают средние статистические значения или распределения9.

Ещё одним подходом к генерации входных данных можно считать турнирное самообучение - процесс изменения свойств системы самой системой, позволяющий ей достигнуть наилучшего или, по крайней мере, приемлемого функционирования в постоянных или изменяющихся условиях1 .

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

Метод случайной генерации, рассматриваемый в работе, можно считать альтернативой этим методам получения входных данных для решения задач.

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

После этого приводится понятие репрезентативности, а также другие определения, связанные с этим понятием. Понятие «репрезентативность» в статистике - это основное требование к выборочной совокупности, заключающееся в соответствии её характеристик аналогичным характеристикам генеральной совокупности - из которой с соблюдением определённых правил и отобрана выборочная13. Однако если воспользоваться более широким, но редко употребляемым понятием репрезентативности как «возможность воспроизвести представление о целом по его части» - то это понятие становится более сложным, т.к. описывает процесс, а не объект (выборку). Репрезентативность - величина из-

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

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

Гумаюнов В. Принцип «турнирного» самообучения для генетических алгоритмов. Квалификационная дипломная работа. Ульяновский гос. университет, ф-т Инф. и телекомм, технологий, 2003. Melnikov В., Radionov A., Gumayunov V. Some special heuristics for discrete optimization problems. - The 8th Int. Conf. on Enterprise of Information Systems (ICEIS-2006), Pathos (Cyprus). - P. 91-95.

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

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

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

меряемая, которая может быть определена «ошибкой репрезентативности», т.е. разностью между специально выбираемыми характеристиками выборочной и генеральной совокупностей. Однако фактическая (действительная) величина указанной разности остаётся неизвестной - вследствие чего мерой репрезентативности обычно служит определяемая по правилам математической статистики её вероятная величина (или среднее квадратичное её возможных значений).

Часто в различных работах утверждается, что в возникающих на практике задачах входные данные, являющиеся представлениями дискретных структур, поступают в соответствии с некоторым вероятностным распределением - и поэтому сложность большинства алгоритмов работы с этими структурами «в худшем случае» в таких ситуациях неадекватна. В настоящее время многими учёными ведется работа в направлении построения теории, отдельно описывающей алгоритмы для предположительно правильного распределения в каждом конкретном случае, которые достаточно адекватно описывали бы многие практические ситуации. Наибольший процесс был достигнут в работах американских математиков Л.Левина и Ю.Гуревича14. В данной работе подход к репрезентативности был сделан в этом же смысле. При этом важно отметить, что в рамках предлагаемого автором диссертации подхода (на примере недетерминированных конечных автоматов) можно не просто выяснить, насколько адекватно сгенерированные НКА представляют реальные объекты (т.е. насколько они репрезентативны), - но и улучшить их репрезентативность.

В четвёртой главе вводится понятие базисного конечного автомата15 и универсального автомата Конвея16; оба этих формализма задают специальные инварианты НКА. Описывается авторская реализация алгоритма построения базисного автомата и автомата Конвея.

Пятая глава посвящена алгоритмам случайной генерации недетерминированных конечных автоматов. Приводится наиболее популярный алгоритм Па-рантоэна (и его модификацию ван Зейл)17. Опишем основные шаги этого алгоритма для случайной генерации недетерминированного автомата:

• задан алфавит ...,/«} и набор состояний <2 = {1и},

• произведены равновероятные битовые потоки размера тп2; они описывают функцию перехода д; возникновение бита отличного от нуля в положении (1 -1 )п + (1 — \)п + ] обозначает существование перехода от состояния г в состояние}, помеченного 1,

14 Levin L. Randomness and Nondeterminism. http://www.cs.bu.edu/fac/lnd/expoicm94.htm. Gurevich Y., Veanes M., Wallace C. Can Abstract State Machines Be Useful in Language Theory? -Theoretical Computer Science., 2007. - 376 p.

" 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, No.l. - P. 131-150.

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

17 Champarnaud J., Hansel G., Paranthoen T., Ziadi D. Random generation models for NFA's. - Journal of Automata, Languages and Combinatorics. - 2004. - No.9. - 203-216.

Van Zijl L., Raitt L., Random Generation of Unary DFAs. - South African Computer Journal. - 2008. - Vol 41.-57-63.

• есть единственное начальное состояние (вершина 1),

• набор финальных состояний случайно выбран, каждое состояние имеет равный шанс на то, чтобы быть финальным: вероятность рл = II п.

С помощью этого метода с равновероятными битовыми потоками можно успешно сравнивать различные представления регулярных языков. Но структуры, сгенерированные данным методом, часто не соответствуют требованиям выбранной предметной области. Например, в автоматах, сгенерированных методом ван Зейл, сравнительно мало циклов; также обычно не устраивает получаемая разрежённость автомата. Поэтому автором был разработан другой алгоритм генерации недетерминированного конечного автомата, результатом работы которого являются автоматы, более соответствующие рассматриваемым характеристикам и подходящие для решения задач выбранной предметной области. Для сравнения сгенерированных структур далее будут приведены результаты счета для автоматов, полученных методом ван Зейл и авторским методом.

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

• Задан алфавит набор состояний ¡2= {1,...,п).

• Произведены равновероятные битовые потоки размера тп2; они описывают функцию перехода 6; возникновение бита отличного от нуля в положении 2* ((I -\) * п2 -1) + у обозначает существование перехода от состояния / в состояние у, помеченного /.

• Строится трёхмерная таблица переходов. В ячейках таблицы записываются символы, которые можно прочитать при переходе из состояния д, в состояние qJ.

• Есть единственное начальное состояние (вершина 1).

• Набор финальных состояний выбран случайно - каждое состояние имеет равную вероятность того, чтобы быть финальным.

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

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

Полученные объекты адекватны тем потребностям, которые возникают в реальных задачах. Например, при описании грамматических структур контекстно-свободных языков с помощью конечных автоматов, а также контекстно-свободных языков «полностью» с помощью различных расширений НКА19. Как

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

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

было отмечено выше, в реальных задачах20 требуется достаточно большое количество состояний конечного автомата, поэтому необходимо генерировать НКА с применением конкретных характеристик. Сгенерированные по оригинальной методике недетерминированные конечные автоматы могут использоваться для решения задач в соответствующих предметных областях.

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

Для проверки репрезентативности сгенерированных структур нами применялись некоторые статистические критерии. Даже если критерии Т^'Тг'—'Тп подтверждают, что последовательность ведет себя случайным образом, то это не означает, что проверка с помощью критерия 7"„+1 будет успешной. Но каждая успешная проверка даёт всё большую и большую уверенность в случайности последовательности. Обычно к последовательности применяются около 6 статистических критериев21 - и если она удовлетворяет этим критериям, то последовательность считается случайной (по Д.Кнуту - «презумпция невиновности до доказательства вины»).

В работе приведены семь статистических критериев, выбранных из всех тестов Д.Кнута, по которым выносится суждение о случайности сгенерированной последовательности структур. В доступной автору литературе22 отсутствует какая-либо информация о том, что по некоторому из этих критериев можно выполнить более качественную или менее качественную проверку. Поэтому из 12 критериев автором, согласно рекомендациям Д.Кнута, были выбраны 7: критерий «хи-квадрат»; критерий равномерности; критерий серий; критерий интервалов; покер-критерий (критерий разбиений); критерий собирания купонов; критерий сериальной корреляции.

В седьмой главе приведены «естественные» характеристики недетерминированных конечных автоматов. К генерируемым НКА были применены рассматриваемые характеристики и получены результаты, показывающие улучшения путём их генерации модификацией метода ван Зейл.

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

20 См. многие работы из предыдущих сносок, а также, например, следующие работы:

McCulloch W., Pitts W. A logical calculus of the ideas immanent in nervous activity. - Bulletin of Mathematical Biophysics. — 1943. — No.5. — 115—133. (Уже в этой классической работе можно увидеть необходимость рассмотрения НКА - причём с большим числом состояний.)

Вирт Н. Паскаль. Руководство для пользователя и описание языка. - М.: Финансы и статистика, 1982. (Многие описанные грамматические струюуры могут быть реализованы с помощью НКА.) Поликарпова Н., Шалыто А. Автоматное программирование. - СПб.: Питер, 2009. Van Zijl L., Oliver F., Harper J.-P. The MERLin Environment applied to *-NFAs. - Proceedings of the CIAA.-July, 2000.

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

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

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

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

1-я характеристика. Разрежённость автомата - среднее число дуг, исходящих из вершины и входящих в вершину. Разработанный метод должен генерировать автоматы с уменьшенным средним числом дуг из вершины по сравнению с автоматами, сгенерированными методом ван Зейл.

2-я характеристика. Вложенность циклов - содержание других циклов в теле внутреннего цикла. Уровень вложенности циклов НКА, сгенерированных авторским методом, увеличивается.

3-я характеристика. Минимальная длина пути от стартовой вершины до финальной, делённая на количество вершин, должна быть меньше, чем в автоматах, полученных алгоритмом ван Зейл.

Эти характеристики были сформулированы после рассмотрения конкретной предметной области - описания некоторых грамматических структур контекстно-свободных языков с помощью конечных автоматов. Программная реализация разработанного метода случайной генерации недетерминированного конечного автомата и проведённые вычислительные эксперименты показали, что сгенерированные структуры удовлетворяют требуемым характеристикам. А именно (по сравнению со стандартным вариантом метода ван Зейл):

• описанный выше метод генерирует автоматы с уменьшенным средним числом дуг из вершины;

• уровень вложенности циклов увеличен;

• минимальная длина пути от стартовой вершины до финальной, делённая на количество вершин, уменьшилась.

К сгенерированным недетерминированным автоматам были построены эквивалентные базисные конечные автоматы. Для построенных базисных конечных автоматов дополнительно были рассмотрены следующие характеристики:

4-я характеристика. Число вершин получаемого эквивалентного базисного автомата

5-я характеристика. Число дуг эквивалентного базисного автомата.

6-я характеристика. Отношение количества блоков к количеству клеток таблицы базисного автомата.

Эти характеристики были сформулированы при исследовании описания регулярных языков с помощью базисных конечных автоматов. Автором описаны алгоритмы для этих характеристик и реализованы соответствующие компьютерные программы.

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

Случайная генерация комбинаторных структур позволяет не только проверять алгоритмы, основанные на этой структуре, но и исследовать поведение этих структур. Исследовав сгенерированные структуры, можно не просто выяснить, насколько они представляют реальные объекты, поведение которых мы моделируем, насколько они репрезентативны, - но и улучшить их репрезентативность. Для этого необходимо как-то модифицировать алгоритм генерации, соответственно, чем больше у алгоритма параметров которые можно изменить,

тем более адекватные структуры мы можем генерировать для различных предметных областей. Когда у нас появляется возможность выбора, мы можем строить наши структуры, как нам будет удобно, проверять характеристики, которые нам больше подходят. Можно сказать, что наша модель генерации сама определяет репрезентативность для конкретной предметной области. При этом мы можем модифицировать алгоритм генерации недетерминированных конечных автоматов - например, для этого можно изменять формулу для определения существования переходов между вершинами автомата. Например, для исследования репрезентативности в рассматриваемых в работе предметных областях автором при генерации структур вместо формулы (1-\)пг +(1 — \)п + ] для определения существования переходов из метода ван Зейл использовалась формула 2*((1-\)*пг+0-\) + ]).

В работе с помощью рассматриваемых характеристик было показано, что сгенерированные авторским методом структуру больше подходят для решения задач в выбранных предметных областях. Итак, после программирования соответствующих алгоритмов, проведения необходимых исследований и анализа результатов экспериментов было установлено, что все получаемые значения эквивалентного базисного автомата соответствует «реальным» - при использовании авторских версий алгоритмов генерации НКА.

Соответствующие предметные области рассматриваются в девятой главе. В ней описано возможное применение сгенерированных недетерминированных конечных автоматов для решения различных задач. Рассмотрим такие предметные области.

1) С помощью недетерминированных конечных автоматов можно рассматривать представление бесконечных итераций языков, а также определять специальное отношение эквивалентности для двух итерируемых языков23 (т.е. вычислять ответ на вопрос о выполнении этого отношения в конкретном случае - принятие слова автоматом означает положительный ответ на вопрос о выполнении этого отношения).

2) Конечные автоматы используются в автоматном программировании. При этом программа представляется как модель какого-либо конечного автомата, а полное выполнение её кода представляет собой цикл шагов автомата24. Здесь речь идёт не только и не столько об использовании конечных автоматов в программировании, сколько о методе создания программ в целом, поведение которых (программ) и описывается автоматами. При рассмотрении примеров графов переходов автоматов, использованных при написании программ (при автоматном программировании), были сформулированы следующие характеристики.

1-я характеристика: Количество состояний автоматов, описывающих поведение программы.

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

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

2-я характеристика: Количество петель (т.е. случаи, когда при переходе сохраняется текущее состояние автомата) в автоматах, описывающих поведение программы.

Для улучшения репрезентативности НКА в этой предметной области мы можем модифицировать алгоритм генерации, чтобы сгенерированные структуры удовлетворяли полученным характеристикам. Для этого при генерации структур вместо формулы (1-\)пг +(1-\)п + ] для определения существования переходов из метода ван Зейл использовалась формула 0,5* ((7-1)* и2 + ]).

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

3) Конечные автоматы применяются для Ы1-анализа. При этом ЬЯ-анализ осуществляется на основе Ы1-грамматик и имеет ряд преимуществ, например, по сравнению с ЬЬ-анализатором. 1Л-анализаторы могут быть построены практически для всех грамматических конструкций языков программирования25.

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

Подход к репрезентативности, рассматриваемый в работе, может быть применён не только в области конечных автоматов. Были проведены исследования в области моделирования оптимального управления и в области проверки и оценивания алгоритмов, работающих с некоторыми булевыми структурами (дизъюнктивными нормальными формами).

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

Рассмотрим задачу оптимального управления. Пусть время дискретно и разбито на такты: 0,1,2,...Т\ п - номер такта, Т - полное время управления. В каждом такте выбирается одно из двух управлений и] и иг- Объект управления характеризуется вероятностями р] и р2 получения значений ъ = 1 и г =0 при выборе соответствующих управлений:

р(г = 1/ и;)=р;; р(г = 1/и2)^р1;р(г = 0/ щ)= 1-р1;р(г = 0/иг)= 1-р2;

т

I „

п-0

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

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

Значения вероятностей р! и р2 неизвестны, для них задается априорное распределение, например, равномерное для значений 0< р1<1; 0< р2<1. Необходимо найти алгоритм, который максимизирует математическое ожидание I на отрезке Т.

В описанной задаче алгоритм для каждой пары возможных значений р! и Р2 заключается в выборе того управления и, для которого р(г = 1) максимально.27

1-я характеристика. Алгоритм А§ - 5-оптимальный, если он обеспечивает максимум I при неизвестном заранее Е

2-я характеристика. Алгоритм Ао- обучающийся, если I Ао| > Ц*-

3-я характеристика. Алгоритм А - оптимально обучающийся, если I> 1д~ для любого А.

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

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

В таблицах 1, 2 и 3 показаны результаты генерации недетерминированных конечных автоматов методом ван Зейл и модифицированным методом. Для сгенерированных структур вычислено среднее число дуг из вершины, уровень вложенности циклов, отношение длины пути к количеству вершин автомата.

Таблица 1. Разрежённость автомата.

Количество состояний НКА Среднее число дуг из вершины Количество состояний НКА Среднее число дуг из вершины

Метод ван Зейл Модифицированный метод Метод ван Зейл Модифицированный метод

2 0.99 0.12 12 5.91 3.61

3 1.17 0.99 13 6.47 3.93

4 1.87 1.18 14 6.72 3.98

5 2.58 1.46 15 6.89 4.03

6 2.99 1.78 16 7.65 4.48

7 3.55 2.21 17 8.11 4.71

8 3.81 2.46 18 8.92 4.91

9 3.91 3.09 19 9.19 5.02

10 5.09 3.31 20 10.22 5.14

11 5.18 3.46

27 Пивнева С. Информационная динамическая модель обучения. - Многопрофильное профессиональное образование. Сборник научно-методических работ. - Российская академия естественных наук. -Тольяттинский государственный университет. - Тольятти. - 2007.

Из приведенных результатов в таблице 1 видно, что автоматы, полученные новым методом, более разрежены.

Таблица 2. Вложенность циклов.

Количество состояний НКА Уровень вложенности циклов Количество состоянии НКА Уровень вложенности циклов

Метод ван Зейл Модифицированный метод Метод ван Зейл Модифицированный метод

2 0 0 12 9.06 3.08

3 0 0 13 9.09 4.12

4 1.56 0.92 14 10.56 5.19

5 3.15 1.01 15 11.31 5.04

б 3.58 0.95 16 12.21 4.99

7 4.12 2.09 17 12.98 5.22

5.17 1.92 18 13.28 6.15

9 6.19 2.03 19 14.08 5.97

10 8.11 | 3.04 20 14.98 6.01

11 8.15 і 2.96

Из таблицы 2 очевидно, что уровень вложенности циклов стал ниже.

Таблица 3. Отношение длины пути к общему числу вершин.

Количество состояний НКА Отношение длины пути к общему количеству вершин Количество состояний НКА Отношение длины пути к общему количеству вершин

Метод ван Зейл Модифицированный метод Метод ван Зейл Модифицированный метод

2 0.99 0.22 12 0.51 0.11

3 0.31 0.29 13 0.59 0.12

4 0.35 0.25 14 0.65 0.14

5 0.39 0.19 15 0.69 0.12

6 0.52 0.17 16 0.71 0.13

7 0.61 0.13 17 0.72 0.14

8 0.61 0.12 18 0.75 0.14

9 0.63 0.12 19 0.78 0.13

10 0.64 0.11 20 ! 0.81 0.12

И 0.65 0.12 і

В таблицах 4, 5 и 6 приведены характеристики эквивалентных базисных автоматов, полученных из структур, сгенерированных методом ван Зейл и модифицированным методом. Для полученных базисных конечных автоматов вы-

числено среднее количество состояний, среднее количество переходов, отношение количества блоков к количеству клеток эквивалентного базисного автомата.

Таблица 4. Количество состояний эквивалентного базисного автомата.

Количество состояний НКА Количество состояний эквивалентного БА Количество состояний НКА Количество состояний эквивалентного БА

Метод ван Зейл Модифицированный метод Метод ван Зейл Модифицированный метод

2 1.81 3.87 12 6.59 6.19

3 7.71 | 5.02 13 5.38 4.21

4 10.23 6.96 24 6.19 5.02

5 9.12 13.61 15 4.58 5.93

6 8.66 8.25 16 5.02 4.58

7 8.24 7.26 17 5.38 6.19

8 5.53 6.59 18 5.42 5.38

9 5.22 7.04 19 5.79 5.02

10 4.58 5.79 20 4.62 4.17

11 4.17 | 4.62

Таблица 5. Количество переходов эквивалентного базисного автомата.

Количество состояний НКА Количество переходов эквивалентного БА Количество состояний НКА Количество переходов эквивалентного БА

Метод ван Зейл Модифицированный метод Метод ван Зейл Модифицированный метод

2 2,41 5.94 12 13.19 12.38

3 14.41 9.43 13 10.77 8.42

4 22.08 14.14 14 12.38 10.04

5 19.73 29.54 15 9.15 12.06

6 17.92 16.91 16 10.04 9.15

7 16.09 15.61 17 10.77 12.69

8 11.56 14.20 18 10.85 10.77

9 10.95 15.09 19 11.58 10.04

10 9.15 11.58 20 9.23 8.34

11 ( 8.34 9.54

Таблица 6. Отношение количества блоков к количеству клеток таблицы эквивалентного базисного автомата.

Количество состояний НКА Отношение количества блоков к количеству клеток таблицы БА Количество состояний НКА Отношение количества блоков к количеству клеток таблицы БА

Метод ван Зейл Модифицированный метод Метод ван Зейл Модифицированный метод

2 0.31 0.26 12 0.20 0.22

3 0.19 0.22 13 0.25 0.29

4 0.18 0.23 14 0.22 0.26

5 0.22 0.19 15 0.27 0.24

6 0.25 0.24 16 0.26 0.27

7 0.25 0.23 17 0.25 0.23

8 0.27 0.26 18 0.25 0.25

9 0.28 0.25 19 0.23 0.26

10 0.27 0.23 20 0.27 0.29

11 і 0.29 0.29

В таблице 7 показаны характеристики структур, полученных в результате генерации методом ван Зейл и модифицированным методом для автоматного программирования. Для полученных недетерминированных конечных автоматов вычислено среднее количество петель.

Таблица 7. Количество петель в недетерминированном конечном автомате

Количество состояний НКА Количество петель в НКА Количество состояний НКА Количество петель в НКА

Метод ван Зейл Модифицированный метод Метод ван Зейл Модифицированный метод

2 1.90 0.88 12 12.79 15.61

3 2.40 3.58 13 11.92 17.33

4 4.21 4.52 14 12.38 21.94

5 4.11 8.73 15 16.49 20.70

6 6.01 7.52 16 15.19 20.94

7 6.02 7.21 17 18.23 28.73

8 8.48 10.79 18 17.52 24.42

9 8.22 9.30 19 19.93 25.48

10 8.09 12.03 20 | 18.43 27.47

11 9.91 16.15 і

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

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

1) Удалось экспериментально подтвердить гипотезу о том, что при нашем варианте случайной генерации НКА. достаточно часто получаются так называемые АЛЫегЬо-подобные языки; а именно, для языков, канонические автоматы автоматов которых содержат 12 состояний, такие автоматы составляют более 87%. Для такого автомата с помощью выбора собственного подмножества множества блоков и дальнейших эквивалентных преобразований строится автомат, не являющийся эквивалентным исходному. При этом саму вероятность появления таких автоматов можно было рассматривать как ещё одну характеристику - однако это является довольно сложной задачей. Поэтому мы фактически рассматриваем обратную задачу - статистически определяем, насколько часто при различных методах генерации дискретных структур (НКА) появляются Waterloo-пoдoбныe языки.

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

3) Получены рекомендации по предпочтительности применения конкретных эвристик при разработке соответствующих эвристических алгоритмов минимизации НКА.

4) Характеристики сгенерированных структур имеют большую связь с выбором разделяющего элемента при решении задачи методом ветвей и границ. Основную идею метода ветвей и границ можно сформулировать как сокращение перебора путём игнорирования поиска в отдельных частях пространства допустимых решений, если известно, что эти части заведомо не содержат оптимальных решений28. Одна из основных целей хорошей реализации метода ветвей и границ состоит в удачном выборе разделяющего элемента29. Если получено подходящее значение какой-либо характеристики сгенерированной структуры, эта характеристика может служить тем самым разделяющим элементом при решении соответствующей задачи.

28 Little }., Murty К., Sweeney D., Karel С. An algorithm for the traveling salesman problem. // Operations Research. - 1963. - Vol. 11 - P. 972-989.

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

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

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

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

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

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

4. ПУБЛИКАЦИИ АВТОРА

Публикации в изданиях, рекомендованных списком ВАК:

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

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

Публикации в рецензируемых научных журналах и изданиях:

3. Рогова O.A. Об одном подходе к репрезентативности недетерминированного конечного автомата // Технологии Microsoft в теории и практике программирования: Сб. трудов VI Всероссийской научно-практической конференции студентов, аспирантов, молодых учёных. Томск: Изд-во Томского политехнического университета, 2009. - С. 31-33.

4. Рогова O.A. Репрезентативность входных данных // Проведение научных исследований в области обработки, хранения, передачи и защиты инфор-

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

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

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

7. Мельников Б.Ф., Пивнева C.B., Рогова O.A. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов // «Стохастическая оптимизация в информатике». - Изд-во С.-Петербургского университета, 2010. - Т. 6.-С. 74-82.

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

9. Мельников Б.Ф., Рогова O.A. Базисные конечные автоматы в качестве критерия репрезентативности случайно сгенерированных недетерминированных автоматов. // «Математика. Образование. Культура» (к 75-летию В.М. Монахова): Сб. трудов V Международной научной конф. - Тольятти: 1ГУ, 2011.-Ч. 1-С. 12-15.

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

Подписано в печать 11.03.2012. Формат 60x84/16. Печать оперативная. Усл. п. л. 1,28. Тираж 140 экз. Заказ № 3-50-12.

Издательство Тольяттинского государственного университета 445667, г. Тольятти, ул. Белорусская, 14

61 12-1/767

Тольяттинский государственный университет

На правах рукописи

Рогова Ольга Александровна

ПОДХОД К ОЦЕНКЕ РЕПРЕЗЕНТАТИВНОСТИ СЛУЧАЙНО СГЕНЕРИРОВАННЫХ ДИСКРЕТНЫХ СТРУКТУР НА ПРИМЕРЕ НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ

Специальность 05.13.18 -«Математическое моделирование, численные методы и комплексы программ»

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель: д. ф.-м. н., профессор Мельников Б.Ф.

Тольятти - 2012

Оглавление

1. Введение.................................................................................................12

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

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

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

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

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

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

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

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

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

11. Применение теории репрезентативности к вариантам

алгоритмов принятия решений................................................................68

Заключение...................................................................................................71

Литература....................................................................................................72

Приложение 1................................................................................................81

Приложение 2................................................................................................82

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

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

2

точками * - распределения для статистического критерия «хи-квадрат», описанного в шестой главе. Приложение 2 содержит фрагменты программной реализации алгоритмов, рассмотренных в работе.

1. Введение

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

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

Случайная генерация служит одним из способов входных данных для решения задач в различных предметных областях. Успех решения задач часто зависит от входных данных, поэтому методы получения этих данных становятся важными. В работе рассматривается подход к получению репрезентативных данных на примере недетерминированных конечных автоматов и некоторых областей их применения.

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

систематического изучения регулярных языков и конечных автоматов можно считать тот факт, что в 1940-х годах Мак-Каллок и Питтс применяли машины с конечным числом состояний для моделирования нейронных сетей [84]. С тех пор конечные автоматы были широко изучены и применялись в различных областях науки.

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

Одним из самых ранних и значительных вкладов в теории конечных автоматов является теорема Клини. Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков [35]. Кроме того, этот класс сов