Введение к работе
Актуальность темы. Теория автоматов как один из разделов математической кибернетики нашла применение в технике (синтез технических систем, техническое диагностирование), в информатике (построение компиляторов, тестирование программ), в медицине и др. Формирование и развитие теория автоматов получила, например, в работах Дж.Неймана [12], В.М.Глушкова [6-7], В.Б.Кудрявцева и др. [10], М.И.Кратко [9], М.А.Айзермана [1] и др. Фундаментальным направлением в теории автоматов явилась теория экспериментов с автоматами (работы Э.Мура[11], А.Гилла [5]). Основа для использования моделей и методов дискретной математики в теории автоматов изложена, например, в работах С.В.Яблонского [14] и сборнике [8]. Исследования по теории автоматов проводились в Саратовско-Донецкой Школе, возглавлявшейся А.М.Богомоловым ([2-4]), в которую входили Д.В.Сперанский, В.Н.Салий, Ю.А.Скобцов, В.Г.Скобелев, А.А.Сытник, И.С.Грунский, В.А.Твердохлебов и др.
Анализ распространения основных положений, моделей и методов теории автоматов на область сложных систем при использовании традиционных средств задания автоматов (таблицами, матрицами, графами, логическими уравнениями, формулами языка регулярных выражений) показал, что требуется добавить новые средства, согласующиеся с возросшей размерностью автоматных моделей и неполнотой их представления, а также для устранения барьера между дискретными символьными и числовыми математическими структурами. Представления числовыми математическими структурами законов функционирования автоматов позволяет, во - первых, в ряде случаев преодолевать барьер размерности данных в моделях, а, во-вторых, принципиально расширить формальный аппарат теории автоматов на основе включения в него развитых числовых структур и методов геометрии. В 1995-1996гг. В.А. Твердохлебовым [13] был предложен новый подход к заданию законов функционирования конечных детерминированных автоматов - задание геометрическими образами, при котором автоматное отображение представляется в формах символьного и числового графиков. Это позволяет использовать для задания законов функционирования автоматов геометрические кривые, с расположенными на них точками автоматных
отображений, и произвольные последовательности, интерпретируемые как последовательности вторых координат точек геометрических образов. Задание автоматных отображений числовыми графиками позволило расширить класс автоматов, для которых эффективно решаются задачи распознавания автоматов, применять классические методы интерполяции и разрабатывать новые методы интерполяции для частично заданных автоматных отображений, оценивать сложность законов функционирования автоматов. Разработка методов распознавания, интерполяция и оценка сложности законов функционирования автоматов (при задании этих законов геометрическими образами) являются актуальными. Задачи распознавания, интерполяции и оценки сложности законов функционирования автоматов взаимосвязаны, так как сложные автоматы имеют частично заданные законы функционирования и их распознавание связано с предварительными оценкой сложности и интерполяцией.
Основные результаты диссертации получены с участием автора при выполнении исследований по планам НИР Института проблем точной механики и управления РАН: "Разработка методов и моделей для управления и технического диагностирования мехатронных систем (2007г., № гос. регистрации - 0120.0 502444)", " Разработка основных положений моделей и методов описания законов функционирования сложных технических систем в форме причинно-следственных комплексов взаимодействий разнородных процессов (2008-2010г.г., № гос. регистрации - 0120. 0 803005)" и по грантам РФФИ " Разработка моделей и методов для технического диагностирования больших систем с использованием автоматных моделей и интерполяции по числовым геометрическим образам законов функционирования объекта диагностирования (2007-2008г.г., №07-07-00088а)" и "Разработка методов технического диагностирования сложных систем с учётом интервалов времени, на которых законы функционирования систем не определены или невозможно применение средств диагностирования (2008-2009г.г., №08-08-00534)" .
Цели работы. Разработка методов распознавания, интерполяции и оценки сложности законов функционирования автоматов, заданных геометрическими образами. В настоящей диссертации поставлены и решены следующие задачи:
Задача 1. Исследовать возможность методов интерполяции Ньютона, Лагранжа, Гаусса, Бесселя, Стирлинга и др. для законов функционирования
автоматов, частично заданных геометрическими образами.
Разработать методы интерполяции частично заданных законов функционирования автоматов с новым выбором узлов интерполяции: узлов, определяемых автономными подавтоматами, и узлов, определяемых горизонтальными сечениями геометрических образов.
Задача 2. Разработать методы распознавания автоматов в семействах автоматов, заданных последовательностями вторых координат точек геометрических образов и геометрическими кривыми линиями, на которых размещены точки автоматных отображений.
Задача 3. Получить оценки сложности законов функционирования автоматов (и их реализаций) с использованием спектра рекуррентных описаний в случаях, когда законы функционирования заданы геометрическими образами, представленными:
последовательностями вторых координат точек геометрических образов автоматов;
последовательностями точек на аналитически заданных кривых, интерпретируемых как вершины геометрических образов;
- классом (4,2,2)-автоматов и его подклассами, определенными по
свойствам Поста.
Методы исследования. В работе используются методы теории автоматов, модели и методы дискретной математики, методы интерполяции, методы рекуррентного определения последовательностей, методы геометрии.
Научная новизна. Основные результаты диссертации являются новыми и впервые получены автором:
Разработаны методы интерполяции для частично заданных законов функционирования автоматов, представленных геометрическими образами и использующие: узлы интерполяции, вторые координаты которых получены сечениями геометрических образов прямыми линиями, параллельными оси абсцисс; узлы интерполяции, выделенные первыми элементами некоторых вершин геометрических образов.
Получены оценки для сравнения по точности интерполяции методами Ньютона, Лагранжа и др. для частично заданных законов функционирования автоматов, последовательности вторых координат вершин геометрических образов которых определены числовыми последовательностями из массива The
On-Line Encyclopedia of Integer Sequences (OEIS(CIIIA)). Получены оценки для автоматов с частично заданными геометрическими образами, представляющими класс (4,2,2)-автоматов и его подклассы и класс линейных (8,2,2)-автоматов.
3. Разработаны метод и алгоритм распознавания таких автоматов, законы функционирования которых заданы геометрическими образами, расположенными на аналитически заданных геометрических кривых: у=е^х"55\
, х , „„ f* + lY Гх-2.8^2
y = l + cos(—+ 1.75), у
1.0
эу = | —5— I идр'
V 6 j
4. Разработаны алгоритмы оценки сложности с использованием показателей спектра рекуррентных описаний геометрических образов для автоматов:
вершины геометрических образов которых расположены на аналитически заданных геометрических кривых, содержащихся в банке ENCYCLOPEDIE DES FORMES MATHEMATIQUES REMARQUABLES (Франция);
по последовательностям вторых координат вершин геометрических образов (включая оценку последовательностей длины 1 млн.знаков из массива OEIS(CIIIA));
для законов функционирования автоматов из класса (4,2,2)-автоматов и его подклассов.
Теоретическая и практическая значимость. Разработанные в диссертации модели, методы и алгоритмы позволяют: доопределять частично заданные законы функционирования автоматов до полностью определенных законов функционирования; решать задачи распознавания автоматов, законы функционирования которых частично или полностью заданы геометрическими образами; оценивать сложность законов функционирования автоматов и конкретных реализаций законов функционирования.
Апробация работы: Основные результаты работы докладывались и обсуждались на 2-ой школе-семинаре молодых ученых «Управление большими системами», (г.Воронеж, 9-12 июля 2007г.), Международной научной конференции "Гарантоспособные системы, сервисы и технологии DESSERT -2007" (г.Кировоград, Украина, 24-27 апреля 2007г.), Международной научной конференции «Автоматизация проектирования дискретных систем» (г.Минск, Белоруссия, Объединенный Институт проблем информатики НАН Беларуси, 14
-15 ноября 2007г.), Международной научной конференции "Гарантоспособные системы, сервисы и технологии DESSERT-2008" (г.Кировоград, Украина , 23-26 апреля 2008г.), Международной научной конференции "Информационные технологии и системы ИТиС'08" (г.Геленджик, 29 сентября - 3 октября 2008г.), 5-ой школе-семинаре молодых ученых «Управление большими системами» (г.Липецк, 21-24 октября 2008г.), Второй (1-3 октября 2008г) и Третьей (5-7 октября 2009г.) Международных научных конференциях "Управление развитием крупномасштабных систем" (г.Москва, Институт проблем управления РАН) , Международной научной конференции «Математические методы в технике и технологиях ММТТ-22» (г.Псков, 25 - 30 мая 2008г.), Международной научной конференции "Гарантоспособные системы, сервисы и технологии DESSERT-2009" (г.Кировоград, Украина , 22-25 апреля 2009г.), Международной научной конференции «Дискретные модели в теории управляющих систем» (г.Москва, МГУ им.М.В.Ломоносова, факультет ВМК, 6—9 апреля, 2009г.), на 7-ой молодежной научной школе по дискретной математике и ее приложениям (г.Москва, Институт прикладной математики им.М.В.Келдыша РАН, 18-23 мая 2009г.), 6-ой школе-семинаре молодых ученых «Управление большими системами» (г.Ижевск, Удмуртский государственный университет, 31 августа - 5 сентября 2009г.), Международной научной конференции «Мехатроника, автоматизация, управление (МАУ-2009)» (п.Дивноморское, 28 сентября - 3 октября 2009г.), на 10-ом Международном семинаре «Дискретная математика и ее приложения», (г.Москва, МГУ, механико-математический факультет, 1-5 февраля 2010г.), Международной научной конференции "Гарантоспособные системы, сервисы и технологии DESSERT-2010" (г.Кировоград, Украина , 11-15 мая 2010г.), на Седьмой Международной научно-практической конференции "Теоретические и прикладные аспекты построения программных систем" (Украина, г.Киев, Киевский Национальный Университет им.Т.Шевченко, факультет кибернетики, 4-8 октября 2010).
Публикации. Основные результаты диссертации опубликованы в 20 печатных работах [А1-А20] (включая монографию [A3]), список которых приведен в конце автореферата. Статьи [Al, А2] опубликованы в изданиях, содержащихся в Перечне ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, списка литературы и приложения. Общий объем диссертации 142 страницы, включая 16 рисунков, список литературы и приложение. Библиография содержит 93 наименования.
