Введение к работе
Актуальность темы
Тематика настоящей работы (исследование репрезентативности случайно сгенерированных входных данных, применяемое для различных задач дискретной оптимизации) в настоящее время считается специалистами практически неисследованной. Это в первую очередь касается отсутствия общей теории, которую фактически приходится создавать заново для каждой рассматриваемой предметной области . Данная работа не претендует на создание такой общей теории - однако может рассматриваться как начало работ в данном направлении; она фактически формулирует необходимый подход для целого класса задач, связанных с исследованием репрезентативности случайно сгенерированных дискретных структур. В представляемой работе этот подход рассматривается на примере недетерминированных конечных автоматов (ниже - НКА).
В реальных задачах требуется рассматривать конечные автоматы с достаточно большим количеством состояний. Сразу отметим только некоторые из возможных областей применения НКА: они используются, например, в лексических анализаторах - для компиляции языков программирования и для реализации человеко-машинного интерфейса; при тестировании программного обеспечения на основе моделей проверяемой системы ; при проектировании интегральных микросхем ; при редактировании текста и сравнении образов ; при автоматном программировании .
Для проверки различных алгоритмов необходимы входные данные. Но во многих задачах невозможно хранение набора (наборов) входных данных - например, из-за ограничений памяти системы. Поэтому становится актуальным исследование методов получения входных данных для решения различных задач. Одним из таких методов является метод случайной генерации данных.
Ввиду того, что в конкретных задачах используются НКА с большим числом состояний, в программах, предназначенных для имитационного моделирования, необходимо генерировать НКА также с большим числом состояний. Основной целью комплекса работ, проводимых в данном направлении, является применение к сгенерированным дискретным структурам (в частности - к НКА) конкретных характеристик - для их сравнения с соответствующими характеристиками реальных объектов.
Цель работы
Целью работы является описание подхода к оценке репрезентативности случайно сгенерированных дискретных математических структур - на основе алго-
1 Разборов A.. Theoretical Computer Science: взгляд математика. - Компьютерра. - 2001. - № 2. (Эту
статью, по-видимому, нужно рассматривать как обзорную научную, а не как научно-популярную. Сто
ит также отметить, что за прошедшие 11 лет подобная теория, по-видимому, не появилась.)
2 Binder R. Testing Object-Oriented Systems: Models, Patterns, and Tools. - Addison-Wesley, 1999.
Соловьев В., Климович А. Логическое проектирование цифровых систем на основе программируе
мых логических интегральных схем. - Изд-во «Горячая линия - Телеком», 2007. - 636 с.
4 Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - МЦНМО, 2004. - 956 с.
5 Поликарпова Н., Шалыто А. Автоматное программирование. - СПб.: Питер, 2009. - 176 с.
ритмов генерации недетерминированных конечных автоматов, а также описание применения полученных моделей для создания приемлемых (репрезентативных) алгоритмов случайной генерации НКА для выбранной предметной области - с применением обучающихся алгоритмов.
Основные задачи исследования:
1) описание оригинальных модификаций алгоритмов ван Зейл случайной генерации недетерминированных конечных автоматов и их реализация; для нескольких выбранных предметных областей применения недетерминированных конечных автоматов - описание конкретных характеристик НКА;
проверка репрезентативности генерируемых структур - согласно предлагаемой автором методике;
на основе применения к генерируемым структурам конкретных характеристик данной предметной области - разработка и реализация метода случайной генерации недетерминированного конечного автомата, более приемлемого (репрезентативного) для выбранной предметной области; формулировка подхода для исследования репрезентативности входных данных в других областях;
применение разработанного подхода случайной генерации недетерминированных конечных автоматов в задачах статистического исследования свойств конкретных НКА;
применение современных инструментальных средств разработки программного обеспечения, в том числе средств объектно-ориентированного программирования.
Объект исследования
Объектом исследования являются недетерминированные конечные автоматы Рабина-Скотта (Медведева) и обучающиеся алгоритмы.
Предмет исследования
Предметом исследования являются алгоритмы работы с недетерминированными конечными автоматами.
Методы исследования
В работе использованы:
математическое моделирование;
математические методы разработки алгоритмов;
элементы математической статистики;
методы системного анализа;
системное и объектно-ориентированное программирование.
Результаты исследования
Результатами диссертационного исследования являются новые вычислительные методы и алгоритмы работы с недетерминированными конечными автоматами, а также полученные новые закономерности, характеризующие изучаемые объекты.
Научная новизна
Описан подход к оценке репрезентативности для класса задач, связанных с исследованием недетерминированных конечных автоматов. Предложенный подход заключается в выделении характеристик для рассматриваемой предметной области; при этом недетерминированные конечные автоматы можно считать одной из таких областей. Также в работе рассмотрено возможное применение описанного подхода к репрезентативности входных данных и в других предметных областях.
Практическая значимость исследования
Полученные результаты могут быть применены в различных задачах, связанных с исследованием свойств недетерминированных конечных автоматов. Описанный подход к оценке репрезентативности входных данных может быть применён и в других предметных областях, в других задачах дискретной оптимизации.
Достоверность результатов
Достоверность и обоснованность научных положений подтверждается соответствием результатов теоретических исследований экспериментальным тестам и расчётам математического моделирования. Результаты исследований обсуждались на российских и международных конференциях и семинарах.
Основные положения, выносимые на защиту
Разработка оригинальных методов случайной генерации недетерминированных конечных автоматов на основе алгоритмов ван Зейл и Парантоэна.
Применение статистических критериев (характеристик) для проверки случайности сгенерированной последовательности чисел с целью исследования репрезентативности недетерминированных конечных автоматов.
Описание полученных структур (сгенерированных недетерминированных конечных автоматов) с помощью сформулированных характеристик и получение численных характеристик, отражающих репрезентативность в данной конкретной предметной области.
Разработка методов изменения алгоритмов генерации недетерминированных конечных автоматов при неудовлетворительных результатах, полученных при вычислении оценки репрезентативности в конкретной предметной области.
Применение описанного подхода к репрезентативности входных данных в других областях (моделирование задачи оптимального управления) и формулировка подхода к оценке репрезентативности для произвольных сгенерированных дискретных структур.
Применение описанного подхода к некоторым задачам статистического исследования свойств недетерминированных конечных автоматов.
Апробация результатов исследования
Основные научные и практические результаты исследований по теме диссертации докладывались на: Всероссийской конференции «Проведение научных исследований в облас-
ти обработки, хранения, передачи и защиты информации» (г. Ульяновск, 2009);
IX Международной научно-технической конференции, посвященной 70-летию Пензенского государственного педагогического университета им. В.Г.Белинского «Проблемы информатики в образовании, управлении, экономике и технике» (г. Пенза, 2009);
VI Всероссийской научно-практической конференции-конкурсе «Технологии Microsoft в теории и практике программирования» (г. Томск, 2009);
конференции в рамках академической программы «Летняя школа Intel» (г. Нижний Новгород, 2010);
V Международной научной конференции «Математика. Образование. Культура» (г. Тольятти, 2011);
Международная научно-практическая конференция «Молодежь и наука: модернизация и инновационное развитие страны» (г. Пенза, 2011);
научном семинаре кафедры мехатроники в автоматизированных производствах Самарского государственного университета путей сообщения, январь 2012;
научном семинаре кафедры математического анализа Ульяновского государственного педагогического университета, январь 2012;
научных семинарах кафедры прикладной математика и информатики Толь-яттинского государственного университета, 2007-2012.
Публикации
Основные результаты диссертации опубликованы в 10 работах, 2 из них входит в список изданий, рекомендованных ВАК.
Личный вклад автора
Постановка задач осуществлялась научным руководителем. Описываемые в диссертации математические модели вычислений, разработанные алгоритмы их решения, компьютерные реализации алгоритмов и исследование результатов работы программ выполнены автором самостоятельно либо в соавторстве.
Структура и объём диссертации
Общий объём диссертации - 114 страниц. Диссертация состоит из введения, 10 глав, заключения, списка используемой литературы из 95 наименований и 2 приложений.
