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

• Автор: Рогова, Ольга Александровна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Тольятти
• Количество страниц: 114 с. : ил.

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

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

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

4. Алгоритмы построения базисного конечного автомата и универсального конечного автомата
В данной главе вводится понятие базисного конечного автомата [88] и универсального автомата Конвея [82]; оба этих формализма задают специальные инварианты НКА. Описывается авторская реализация алгоритма построения базисного автомата и автомата Конвея.
Пусть задан регулярный язык L; этот язык определяется недетерминированным конечным автоматом К = ( О, X, ô, S, F ). Для автомата К построены канонический автомат L = (QK, X, 8Ю {ут}, FK) и зеркальный к каноническому LR= (Qp, X, 8Р, {sp}, Fp). Определим автомат
BA(L) = (T,Z ,§T,ST,FT)
(базисный конечный автомат для заданного регулярного языка) следующим образом.
• Г - множество пар Т = (А,Х), таких что А е Р , X е R, причём AUX. При этом мы будем писать А = а(Т) и X = fi(T), где PçzQK и RqQp , для каждой пары состояний р е Р и г е R выполнено условие р#г;
• функцию §т определим следующим образом. Для всех 7), Т'2 G Т и a g Yu полагаем Т2е ÔATva) тогда и только тогда, когда:
ôMTAa)={a{TÙ) и = {№)};
• считаем, что Т е Si тогда и только тогда, когда а(Т) = ;
• аналогично, Т е /7,,. тогда и только тогда, когда р(Т) - $R.
Ниже приведён алгоритм построения базисного автомата для автомата К = ( Q, X, 8, S, F):
1) строим канонический автомат L для К;