Модели и методы анализа, интерполяции и распознавания автоматов

СОДЕРЖАНИЕ
ВВЕДЕНИЕ........................................... 4
ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ, ИСПОЛЬЗУЕМЫЕ
МОДЕЛИ И МЕТОДЫ................................... 13
1.1. Геометрические образы законов функционировав!!*! дискретных детерминированных динамических систем.......................... ^3
1.2. Классические методы интерполяции как средство доопределения законов функционирования дискретных детерминированных динамических систем............................................ 25
1.3. Спектр динамических параметров рекуррентного определения числовых последовательностей................................... 32
ГЛАВА 2. ДООПРЕДЕЛЕНИЕ ЧАСТИЧНО ЗАДАННЫХ ЗАКОНОВ
ФУНКЦИОНИРОВАНИЯ АВТОМАТОВ НА ОСНОВЕ КЛАССИЧЕСКИХ МЕТОДОВ ИНТЕРПОЛЯЦИИ.............................. 36
2.1. Анализ эффективности применения классических методов интерполяции для доопределения законов функционировании автоматов в классе (4,2,2)-автоматов........................... 36
2.2. Анализ эффективности в классе (8,2,2)-автоматов методов интерполяции Ныотона и Лагранжа но узлам интерполяции, определенным автономными подавтоматами......................... 57
2.3. Анализ эффективности методов интерполяции Ныотона и Лагранжа по узлам интерполяции, расположенным на прямых, параллельных оси абсцисс....................................... 63
ГЛАВА 3. РАСПОЗНАВАНИЕ АВТОМАТОВ............................... 70
3.1. Распознавание автоматов по их геометрическим образам...... 7р
3.2. Метод распознавания автоматов, заданных последовательностями вторых координат точек геометрических образов автоматов........ 82
2
ГЛАВА 4. ОЦЕНКА СЛОЖНОСТИ И КЛАССИФИКАЦИЯ ПО СЛОЖНОСТИ ЗАКОНОВ ФУНКЦИОНИРОВАНИЯ АВТОМАТОВ... 87
4.1. Оценка сложности законов функционирования автоматов, заданных последовательностями, на основе использования спектра динамических параметров........................................ 87
4.2. Оценка сложности и классификация но сложности геометрических образов автоматов из класса (4,2,2)-автоматов.................. 99
4.3. Оценка сложности законов функционирования автоматов, заданных геометрическими кривыми, на основе использовании
спектра динамических параметров............................... 104
4.4. Метод оценки сложности конечных детерминированных автоматов но числу состояний в минимальной форме с использованием
дискретных Шу-функций......................................... 113
СПИСОК ЛИТЕРАТУРЫ............................................. 126
Приложение 1.................................................. 134
3
ВВЕДЕНИЕ
В классе дискретных детерминированных динамических систем конечные детерминированные автоматы образуют простейший, но достаточно исследованный подкласс. Развитые методы анализа, синтеза, распознавания и т.п. конечных детерминированных автоматов эффективно применяются в решении прикладных задач для реальных систем, автоматные модели которых явно задаются таблицами, матрицами, графами, логическими уравнениями и др. После введения Мак-Каллоком и Питтсом (1943г.) основных положений, па которых строится понятие автомата, теория автоматов получила развитие в работах Дж.Неймана, С.Клини, М.Л.Минского, Дж.Маккарти, М.Арбиба, В.М.Глушкова, А.А.Летичевского, Ю.В.Капитоновой, В.Б.Кудрявцева, С.В.Алешина, А.С.Подколзина, М.И.Кратко, Н.Е.Кобринского, Б.А.Трахтенброта, Я.М.Бардзиня, В.Г.Лазарева, Е.И.Пийля, В.И.Варшавского, С.И.Баранова, М.А.Спивака, М.А.Айзермана и др. Результаты исследований, представленные в работах указанных авторов, составляют фундаментальную основу символьной теории автоматов, т.е. теории, в которой автоматы, как правило, не связаны с классическими числовыми структурами, что ограничивает применение в теории автоматов методов классической математики.
В связи с развитием областей приложения теории автоматов оказалось, что для реальных систем большой размерности задание автоматных моделей таблицами, матрицами, графами, логическими уравнениями практически не эффективно. Одним из путей расширения области приложения теории автоматов явились исследования В.А.Твердохлебова, в которых, начиная с 1995 г., рассматривается представление законов функционирования автоматов, заданных дискретными символьными функциями переходов и выходов, непрерывными (геометрическими кривыми линиями) и дискретными (последовательностями) структурами. Для этого автоматное
4
отображение полагается множеством точек с числовыми координатами и законы функционирования представляются ломаными линиями, вершины которых расположены на аналитически заданных кривых. Этот подход к заданию автоматов, а также некоторые методы анализа, синтеза и распознавания автоматов по их геометрическим образам используются и развиваются в дальнейшем.
В данной работе рассматриваются задачи из общей проблемы распознавания конечных детерминированных автоматов по свойствам и признакам их функционирования, включая интерполяцию частично заданных законов функционирования автоматов и оценку сложности законов функционирования автоматов.
В диссертации поставлены и решены следующие задачи.
Задача 1. Исследовать возможность методов интерполяции Мыотона, Лагранжа, Гаусса, Бесселя, Стирлинга и др. для законов функционирования автоматов, частично заданных геометрическими образами.
Разработать методы интерполяции частично заданных законов функционирования автоматов с новым выбором узлов интерполяции: узлов, определяемых автономными подавтоматами, и узлов, определяемых горизонтальными сечениями геометрических образов.
Задача 2. Разработать методы распознавания автоматов в семействах автоматов, заданных последовательностями вторых координат точек геометрических образов и геомегрическими кривыми линиями, на которых размещены точки автоматных отображений.
Задача 3. Получить оценки сложности законов функционирования автоматов (и их реализаций) с использованием спектра рекуррентных описаний в случаях, когда законы функционирования заданы геометрическими образами, представленными:
- последовательностями вторых координат точек геометрических образов автоматов;
- последовательностями точек на аналитически заданных кривых, интерпретируемых как вершины геометрических образов;
5
- классом (4,2,2)-автоматов и его подклассами, определенными по свойствам Поста;
- конфигурациями стандартных областей, определяющих расположение геометрических образов.
Принципиальную важность задач интерполяции для математики показали выдающиеся математики, именами которых названы методы интерполяции: Ныотои, Лагранж, Гаусс, Стирлинг, Бессель и др.
Актуальность интерполяции при распознавании автоматов связана с тем, что математические модели сложных систем не могут быть полными и точными и, как правило, в этих моделях определены только фрагменты процесса функционирования, а при решении задач управления сложными системами, задач технического диагностирования и др. требуется хотя бы грубая информация о процессах функционирования системы в целом.
Один из основных классов задач математической кибернетики составляют задачи распознавания поведения (наблюдаемого функционирования) искусственных и естественных систем. При этом распознаются системы по поведению или по функционированию (технические системы), распознаются свойства систем, состояний систем и т.д. Задачи из этого класса задач решали А.Тыоринг (тест Тыоринга), Э.Мур и А.Гилл (распознавание автоматов и состояний автоматов), С.В.Яблонский (логические способы контроля) и др. Решение задач управления необходимо использует решение задач распознавания состояния и положения объекта управления. Все эти задачи для случая дискретных детерминированных систем формулируется как задачи распознавания автомата в заданном семействе автоматов или задачи распознавания свойств и состояний автомата.
Фундаментальные понятия сложности — класс Р-проблем, разрешимых за полиномиальное время детерминированными машинами Тыоринга, и класс ЫР-проблем, разрешимых за полиномиальное время
недетерминированными машинами Тыоринга, связаны с автоматами
6
(машинами Тыоринга). На ряду с общим «алгоритмическим» пониманием сложности в теории автоматов исследовались частные варианты показателей сложности: число состояний автомата, длины входных и выходных
последовательностей, число компонент связности в структуре автомата, сложность структуры структурного автомата и др.
Проблема оценки сложности автоматов исследовалась многими авторами сразу же после введения автоматных моделей. Дж. (Don Нейман задачам оценки сложности автоматов посвятил ряд разделов своей работы «Теория самовоспроизводящихся автоматов»:
Роль высокой и очень высокой сложности (включая роль сложности и необходимость соответствующего теоретического обоснования и др);
Переоценка проблем сложных автоматов - проблемы иерархии и эволюции.
Получили распространение оценки сложности структурных автоматов по числу составляющих их элементов. Такие оценки существенно изменяются при изменениях элементной базы и метода синтеза. В диссертации оценка сложности автоматов рассматривалась на основе показателей, характеризующих (наблюдаемое) поведение абстрактного автомата, т.е. на основе показателей, зависящих только от законов функционирования. Эти показатели разработаны и систематизированы в спектр показателей в работе [811. Спектр применяется к последовательностям и имеет иерархическую структуру показателей, где показатели каждого следующего уровня содержат новые данные о структуре последовательности: наименьший порядок рекуррентной формы, определяющей последовательность; число смей рекуррентных форм фиксированного порядка, при определении последовательности; длины подпоследовательностей, определяемых рекуррентными формами фиксированных порядков и т.д. В диссертации такой спектр показателей используется только как средство для оценки сложности законов
7
функционирования автоматов в целом и для оценки конкретных процессов фу н кцион и рова11 ия.
В первой главе приводятся понятия конечного детерминированного автомата, геометрического образа законов функционирования автомата, эквивалентное представление геометрического образа автомата последовательностью вторых координат его точек. Приводится структура спектра показателей рекуррентного описания последовательностей для оценки сложности структуры последовательностей, что в дальнейшем используется для оценки сложности законов функционирования автоматов.
В главе 2 содержатся два разработанных метода интерполяции частично определенных геометрических образов законов функционирования автоматов. В методе 1 используются узлы интерполяции, выделенные первыми проекциями вершин геометрического образа на основе известных конкретных вариантов функционирования автоматов. В методе 2 используются узлы интерполяции, вторые координаты которых получены сечениями геометрических образов прямыми линиями, параллельными оси абсцисс. Глава 2 также содержит результаты оценки точности интерполяции методами Ньютона и Лагранжа частично заданных законов функционирования автоматов, представляющих класс (4,2,2)-автоматов и его подклассы, класс линейных (8,2,2)-автоматов. Кроме этого рассмотрена интерполяция частично заданных законов функционирования автоматов, которые определены последовательностями вторых координат точек геометрических образов.
Оценка точности интерполяции проведена для начальных отрезков длины до 1 млн. знаков в приближенных представлениях величин п , е,
<Р= ] + ^ (т.н. золотое сечение), -J2 у \!г, ln(2), 1п(10), C(3) = Z“T> константа
2 х=1 аг
« /_|Я\ 111
Каталана С = У——Ц-, константа Эйлера / = lim(l + - + - + + — 1п(/?))) и др.
,,=о(2н + 1) "-**> 2 3 п
В главе 3 разработаны методы и алгоритмы распознавания автоматов. В первом методе предполагается, что вершины геометрических образов
8
законов функционирования расположены на аналитически заданных геометрических кривых, что позволяет определять решение задач распознавания автоматов на основе решения уравнений и неравенств для аналитически заданных кривых. Во втором методе автоматы распознаются по последовательностям вторых координат точек их геометрических образов.
Проводится распознавание законов функционирования автоматов, заданных последовательностями (которые полагаются последовательностями вторых координат точек геометрических образов), на основе декомпозиции исходных (числовых) последовательностей в набор характеристических последовательностей и их последующего анализа.
В главе 4 на основе спектра динамических параметров П (см.[81]) осуществляется исследование свойств фундаментальных математических величин, заданных приближенно в виде последовательностей, и законов функционирования дискретных детерминированных динамических систем в форме геометрических образов. Ввиду того, что геометрический образ взаимно-однозначно определяется последовательностью вторых координат его точек, в главе свойства законов функционирования исследуются на основе анализа свойств числовых последовательностей. Рассматривается множество последовательностей длины от 80 до 10 млн. знаков, представленных в банке [92], определяющих приближения фундаментальных
математических величин тг , е, - 1 (т.н. золотое сечение), Л, 1/2,
«о 1 а> (
1п(2), 1п( 10), £(3) = У—г-, константа Каталана ——г, константа Эйлера
х-\х п,о(2л +1)
у = Нш(1 + - + — + - 1п(л))) и др. Для классификации и оценки сложности
"->о> 2 3 п
последовательностей используется спектр динамических параметров, характеризующих сложность правил порождения последовательности. Для каждой последовательности строятся спектр и на основе совпадения по показателям построенных спектров множество разбивается на классы эквивалентных последовательностей. Например, с точки зрения
9
используемого спектра динамических характеристик, наибольшую сложность среди указанных выше последовательностей па начальном отрезке
длины 50 знаков имеют число е и константа Каталана С = У——=Ц-. При
£о(2п + \)2 к
увеличении длины анализируемых начальных отрезков до 200 знаков сложнейшими оказались последовательности, задающие приближения чисел
у/2 и 1п( 10), при длине 1000 знаков - наибольшую сложность имеют е , Уг и
00 1
С(3) = 1~, на начальном отрезке 2000 знаков наибольшую сложность имеет
х=\ X
последовательность, задающая приближение 1п(2), в то время как тс , е, <р (т.н. золотое сечение), -Л, ^2 , 1л(10), 4"(3), константа Каталана и константа Эйлера имеют одинаковую сложность при данной длине. С увеличением длины начальных отрезков последовательностей до 5000 знаков оказывается, что последовательности к , е, (р (т.н. золотое сечение), у/2, \/2, 1п(2), СО), константа Каталана и константа Эйлера имеют одинаковую сложность, а 1п( 10) оказывается самой сложной.
Проведенный в главе 4 анализ последовательностей вторых координат точек геометрических образов всех членов класса (4,2,2)-автоматов, т.е. автоматов, имеющих 4 состояния, 2 входных и 2 выходных сигнала, выявил следующие свойства. Класс (4,2,2)-автоматов, состоящий из 1677721 б элементов, разбит на 4 подкласса по числу состояний у автомата после минимизации. В построенных подклассах для последовательностей вторых координат точек геометрических образов автоматов на основе использования спектра динамических параметров £2 вы числены следующие
характеристики: к[ - минимальное значение сложности в подклассе
автоматов, имеющих / состояний после минимизации, к\ - максимальное значение сложности в подклассе и к\ - среднее значение сложности, в подклассе. Отмечено, что к[ имеет одинаковое значение для всех / е {1,2,3,4},
10
автоматов, имеющих после минимизации 4 состояния (все 4 состояния у таких автоматов различимы), максимальное значение сложности с точки зрения используемого спектра в 15 раз больше, чем в подклассе автоматов, имеющих после минимизации 1 состояние (все 4 состояния у таких автоматов эквивалентны). Среднее значение сложности к\ почти в 8 раз меньше, чем к*.
Также в главе 4 приведены результаты но оценке сложности и классификации по сложности законов функционирования автоматов, заданных геометрическими кривыми, извлеченными из банка 20,30-кривых и фракталов, представленного в сети Интернет по адресу [93]. Для анализа выбраны 50 наиболее известных и распространенных геометрических
кривых на плоскости: спираль Фибоначчи, лемниската Бернулли
логарифмическая спираль (Abscisse curviligne et équation intrinsèque 2 :
fonctionnelle : minimal ), кардиоида (Paramétrisation complexe :
((x2 + y2)2 =a2(x2- y2)), баллистическая кривая
эвольвента
круга (Paramétrisation complexe
о
s = p.'/ltL- )? спираль Архимеда (Absvcisse curvilgne:
le
спираль
о
(Abscisse curviligne : ds = Va2+2b(at-2b)02 + b204d0 ), брахистохрона (Équation
2 = -|(1+2с,1+с2'1)), улитка Паскаля ((x2 + y2-eax)2 =a2(x2+y2))> циссоида
t2 2
(x(x2 + y2) = ay2), кривая Корно (Paramétrisation complexe : z=aje'u du), кривая
о
11
1 (х-д)*
Гаусса (у = = -е 2а1 ), КОрНОИДа ((х2+у2)3+а2(Зх4-6х2у2-5у4) + 8а4у2-4а6=0) И
(ту]2л
др. Проведенное исследование свойств 2Э-кривых включило:
- построение по кривым законов функционирования автоматов;
- построение спектров для последовательностей вторых координат точек геометрических образов построенных автоматов;
- разбиение множества геометрических образов на классы эквивалентности на основе совпадения показателей на уровнях £20 - £23 спектра £2.
По показателям нулевого уровня Д) используемого спектра £2 эквивалентными по сложности оказались автоматы, законы функционирования которых задают: 1.спираль Фибоначчи; 2. двулистник -
2 2 2 2
геометрическая кривая, определенная уравнением (х + у ) = (ах + оу)х , где а=1, Ь=0.5; 3.кривая Сакре. Класс эквивалентности на четвертом уровне £23 спектра £2 составляют автоматы, заданные окружностью и аезроидой.
12