А. С. Епифанов Институт проблем точной механики и управления ран, Саратов, Россия




Скачать 107.36 Kb.
НазваниеА. С. Епифанов Институт проблем точной механики и управления ран, Саратов, Россия
Дата27.11.2012
Размер107.36 Kb.
ТипДокументы

Доопределение частично заданных законов функционирования дискретных детерминированных систем



А. С. Епифанов


Институт проблем точной механики и управления РАН, Саратов, Россия


Введение.

Задачи управления, технического диагностирования, синтеза поведения систем и т.п. в случае сложных систем не обеспечены полной и точной информацией для их решения. Теория экспериментов по распознаванию поведения автоматов (см., например, [3,4]) нашла эффективное применение в техническом диагностировании отдельных элементов, узлов, агрегатов и других технических объектов, допускающих задание явно представленными дискретными математическими структурами: таблицами, матрицами, графами, логическими уравнениями и т.п. В этих случаях модели объектов диагностирования задаются, как правило, явно и точно, средства диагностирования определены полностью, а решаемые вопросы сводятся к проверке работоспособности и локализации неисправности по местоположению или функциям. Принципиально отличается техническое диагностирование сложных систем. Неустранимая для сложных систем неполнота исходной и фактически получаемой контрольным и диагностическим экспериментами информации делает задачи доопределения информации актуальными.

В работе исследуется доопределение частично заданных законов функционирования автоматов из классов (n, m, l) – автоматов, где n – число состояний автомата, m и l - числа входных и выходных сигналов автомата для классов (4,2,2)-автоматов, (8,2,2)-автоматов, (16,2,2)-автоматов и классов автоматов, законы функционирования которых представлены частично заданными последовательностями вторых координат точек геометрических образов (см.[8]).

Выбор для исследования классов (4,2,2)-автоматов, (8,2,2)-автоматов определяется тем, что они являются автоматными моделями в исходном базисе технических элементов для синтеза систем. Синтез систем из базовых элементов позволяет строить такие системы, законы функционирования которых, во-первых, существенно более сложные, чем законы функционирования отдельных элементов, а, во-вторых, определены с меньшей полнотой. Для того, чтобы учесть эту ситуацию исследовано доопределение законов функционирования автоматов по частично заданным последовательностям вторых координат точек геометрических образов автоматов без учета ограничения на число состояний автоматов (см.[7-8]).

В.М.Глушков в работе [2] отмечает: «При дискретном подходе также имеют дело с переменными векторными полями. Однако, в отличие от предыдущего случая, компоненты векторов, а также пространственные и временные координаты принимают дискретные ряды значений. Наиболее употребительным является случай, когда число значений, принимаемых компонентами векторов и пространственными координатами, конечно (поле задано в конечном числе точек). Что же касается временной координаты, то ее область значений при дискретном подходе отождествляют обычно с множеством целых чисел (положительных, отрицательных и нуля). Нулевой момент времени считается при этом начальным, а остальные моменты времени получают названия в соответствии с их номерами: первый, второй, минус первый, минус второй и т.д. При этом чаще всего ограничиваются рассмотрением конечных временных промежутков, начиная либо с нулевого, либо с первого момента времени.» Это непосредственно согласуется с представлением законов функционирования дискретных детерминированных автоматов с конечными и счетно-бесконечными множествами состояний автоматными диаграммами (диаграммами Мура), в которых точкам пространства соответствуют состояния в векторной форме, связи точек определяются функцией переходов δ , а наблюдаемые признаки функционирования (результат функционирования) представляется функцией выходов λ для автоматов типа Мили и функцией отметок состояний μ для автоматов типа Мура. Выбор и применение метода интерполяции по смыслу соответствуют принятию и реализации гипотезы о том, что метод интерполяции, применяемый к числовому графику, представляющему частично заданный геометрический образ, достаточно точно восстанавливает точки геометрического образа, т.е. достаточно точно доопределяет частично заданные законы функционирования автомата. Следовательно, обоснованность результатов, полученных с использованием выбранного метода интерполяции, сведена к обоснованию правильности гипотезы.


Геометрические образы законов функционирования автоматов.

Наблюдаемое функционирование (наблюдаемое поведение) автомата A = (S, X, Y, ) где S – множество состояний, X – множество входных сигналов, Y – множество выходных сигналов, а  SXS – функция переходов и : SXY – функция выходов , может быть систематизировано в двух вариантах автоматных отображений: и . Множества пар s и s' рассматриваются как точки и преобразуются в графики (см.[5]). Для этого на множестве всех последовательностей X* (на множестве всех слов в алфавите ) определяется линейный порядок 1. В соответствии с этим порядком получаем линейно упорядоченные множества пар (s,1) и ('s,1). Дополняя эти множества линейными порядками 0 на Y* и 2 на Y , получаем графики: (s,1,0) и ('s,12). Построенные графики размещаются в системах координат с осью абсцисс (X*,1) и осями ординат соответственно (Y*,0) и (Y,2). Линейные порядки 0 и 2 выбираются на основе учитываемых свойств выходных сигналов, а линейный порядок 1 определяется условиями и ограничениями, предполагаемыми для взаиморасположения на оси абсцисс последовательностей входных сигналов. Основной вариант линейного порядка 1 определяется следующими правилами (см.[5]):

Правило 1. На множестве Х вводится некоторый линейный порядок 1 () .

Правило 2. Порядок 1 на Х распространяется до линейного порядка на множестве Х*:

- для любых слов р,р2 Х* неодинаковой длины (p1p2) p1<p2 ;

- для любых слов р1,р2Х*, для которых p1=p2 и p1p2 их отношение по порядку 1 повторяет отношение ближайших слева несовпадающих букв в словах р1 и р2 .

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


Метод анализа эффективности применения классических методов интерполяции для доопределения законов функционирования автоматов.

В данной работе исследованы и разработаны методы выбора гипотезы (выбора конкретного метода интерполяции) для конкретных классов автоматов (класс (4,2,2)-автоматов, класс (8,2,2)-автоматов, класс (16,2,2)-автоматов) на примере выбора более точного метода интерполяции из двух методов интерполяции: Ньютона и Лагранжа.

Эти методы включают следующие этапы:

1 Этап. Определяется и конкретно строится класс автоматов U , в котором частично заданные автоматы методом интерполяции их частичных геометрических образов доопределяются до полных геометрических образов. Выбирается для исследования набор методов интерполяции (в данной работе набор состоит из методов Ньютона и Лагранжа).

2 Этап. Для интерполяции определяются узлы интерполяции (в работе для исследования рассматриваются 2 варианта выбора узлов интерполяции: использование в качестве узлов интерполяции вершин геометрических образов автономных подавтоматов и использование в качестве узлов интерполяции тех вершин геометрических образов законов функционирования автоматов, которые расположены на прямых, параллельных оси абсцисс).

3 Этап. Выбирается длина d геометрического образа, по частичному заданию которого интерполируется геометрический образ законов функционирования автомата.

4 Этап. К выбранным на этапе 2 узлам интерполяции применяются методы интерполяции Ньютона и Лагранжа.

5 Этап. Результаты интерполяции представляются следующими числовыми показателями:

- для каждого инициального автомата и каждого метода интерполяции определяется число правильно восстановленных вершин геометрического образа законов функционирования автомата;

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

6 Этап. Выбирается функция для оценки эффективности методов интерполяции, т.е. для определения в исследуемом наборе методов интерполяции наиболее эффективного метода. В данной работе используется функция , по значениям которой сравнивается по эффективности методы интерполяции Ньютона и Лагранжа.


Определение областей эффективной интерполяции методами Ньютона и Лагранжа частично заданных автономными подавтоматами автоматов класса (4,2,2) – автоматов.

В классе (4,2,2)-автоматов исследован весь класс с разделением его на 12 подклассов: , , где для конкретного значения длины d рассматриваемых начальных отрезков геометрических образов автоматов, соответственно, подклассы автоматов, для которых число правильно восстановленных точек методом Ньютона строго больше числа (строго меньше числа, равно числу) правильно восстановленных точек методом Лагранжа.

Каждый (n, m, l)-автомат включает точно m автономных подавтоматов с n состояниями и l выходными сигналами. Геометрические образы автономных подавтоматов заданного автомата являются сечениями его геометрического образа. В данной части работы содержатся результаты анализа эффективности доопределения частично заданных законов функционирования автоматов из класса (4,2,2)-автоматов, представленных в форме частично заданных геометрических образов, классическими методами интерполяции Ньютона и Лагранжа. Для рассматриваемых в данной статье классов автоматов число входных сигналов равно двум. Каждый частично заданный геометрический образ автомата предполагается заданным двумя сечениями, которые представляют собой геометрические образы автономных подавтоматов.

Исследованные инициальные автоматы вида =(S, X, Y, δ, λ, ), где S, X и Y- множества состояний, входных и выходных сигналов, δ и λ – функции переходов и выходов вида , , а - начальное состояние, представлены классами автоматов: классами (n, m, l) – автоматов, где n = |S|, m = |X|, l = |Y| , и классами (n, m, l)d  начальных отрезков геометрических образов длины d, определяющих автоматы из класса (nml) – автоматов. В работе проведен сравнительный анализ точности интерполяции методами Ньютона и Лагранжа, а также модифицированными методами Ньютона и Лагранжа. Модификация методов интерполяции состоит в том, что узлами интерполяции являются точки геометрических образов автономных подавтоматов вида A1=(S, {0}, Y, , , s0) и A2=(S, {1}, Y, , , s0). Для сравнения эффективности интерполяции методами Ньютона и Лагранжа используется функция со следующим условием , где () – число автоматов, для которых методом Ньютона (методом Лагранжа) восстановлено больше точек, чем методом Лагранжа (чем методом Ньютона), а - число автоматов, для которых совпадает число правильно восстановленных точек методом Ньютона и методом Лагранжа. Используются следующие свойства функции F:

1. функция F принимает значения из отрезка [0,1] ;

2. функция F принимает значение 0 , если методы интерполирования Ньютона и Лагранжа имеют одинаковую точность;

3. функция F принимает значение отличное от 0 только в том случае, когда интерполяция одним из методов более точная;

4. функция F принимает значение 1 , когда только один из методов правильно восстанавливает некоторые точки графика.

В теоремах 1 - 4 отражены результаты анализа эффективности применения методов интерполяции Ньютона и Лагранжа по отношению к частично заданным геометрическими образами автономных подавтоматов автоматам класса (4,2,2)-автоматов при различных значениях длины начального отрезка геометрического образа.

Теорема 1. Пусть узлами интерполяции для частично заданного геометрического образа длины d каждого автомата A=(S, {0,1}, Y, δ, λ, s0) из класса инициальных (4,2,2)-автоматов являются точки геометрических образов автономных подавтоматов A0=(S, {0}, Y, δ0 , λ0, s0) и A1=(S, {1}, Y, δ1 , λ1, s0) автомата A . Тогда для методов интерполяции Ньютона и Лагранжа при d=30 в классе инициальных (4,2,2) – автоматов выполняется отношение > и функция F принимает значение (метод интерполяции Ньютона с оценкой 0,65 точнее метода Лагранжа).

Теорема 2. Пусть узлами интерполяции для частично заданного геометрического образа длины d каждого автомата A=(S, {0,1}, Y, δ, λ, s0) из класса инициальных (4,2,2)-автоматов являются точки геометрических образов автономных подавтоматов  A0=(S, {0}, Y, δ0 , λ0, s0) и A1=(S, {1}, Y, δ1 , λ1, s0) автомата A . Тогда для методов интерполяции Ньютона и Лагранжа, при d=62, в классе инициальных (4,2,2) – автоматов выполняется отношение > и функция F принимает значение (метод интерполяции Ньютона с оценкой 0,44 точнее метода Лагранжа).

Теорема 3. Пусть узлами интерполяции для частично заданного геометрического образа длины d каждого автомата A=(S, {0,1}, Y, δ, λ, s0) из класса инициальных (4,2,2)-автоматов являются точки геометрических образов автономных подавтоматов A0=(S, {0}, Y, δ0 , λ0, s0) и A1=(S, {1}, Y, δ1 , λ1, s0) автомата A . Тогда для методов интерполяции Ньютона и Лагранжа при d=126 в классе инициальных (4,2,2) – автоматов выполняется отношение  > и функция F принимает значение (метод интерполяции Ньютона с оценкой 0,14 точнее метода Лагранжа).

Теорема 4. Пусть узлами интерполяции для частично заданного геометрического образа длины d каждого автомата A=(S, {0,1}, Y, δ, λ, s0) из класса инициальных (4,2,2)-автоматов являются точки геометрических образов автономных подавтоматов A0=(S, {0}, Y, δ0 , λ0, s0) и A1=(S, {1}, Y, δ1 , λ1, s0) автомата A . Тогда для методов интерполяции Ньютона и Лагранжа при d=254 в классе инициальных (4,2,2) – автоматов выполняется отношение > и функция F принимает значение (метод интерполяции Ньютона с оценкой 0,14 точнее метода Лагранжа).

Из теорем 1 - 4 следует, что при небольших длинах частично заданных геометрических образов законов функционирования автоматов из класса (4,2,2)-автоматов, следует использовать метод интерполяции Ньютона, а при длинах геометрических образов от 126 до 254 интерполяция методами Ньютона и Лагранжа выравнивается по точности.


СПИСОК ЛИТЕРАТУРЫ


1. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. 435 с.

2. Глушков В.М. Абстрактная теория автоматов // Успехи мат. наук.- 1961, 16. Вып.5 (101). С.3-62.

3. Гилл А. Введение в теорию конечных автоматов. М.: Наука.1966.

4. Мур Э. Умозрительные эксперименты с последовательными машинами / Автоматы. Сб. статей под ред. К. Шеннона и Д. Маккарти, ИИЛ, М., 1956, с.179-213.

5. Твердохлебов В.А. Геометрические образы законов функционирования автоматов.– Саратов: Изд-во «Научная книга», 2008. – 183 с. ISBN 978-5-9758-0924-7

6. Твердохлебов В.А. Методы интерполяции в техническом диагностировании. / Ж-л «Проблемы управления». М. №2 2007. С.28-34.

7. Безопасность критических инфраструктур: математические и инженерные методы анализа и обеспечения. Под.ред. В.С.Харченко. Харьков. Изд-во Национальный аэрокосмический университет им. Н.Е.Жуковского. ("ХАИ").2011г. 672с.

Похожие:

А. С. Епифанов Институт проблем точной механики и управления ран, Саратов, Россия iconКризисные явления, возможности и пути их преодоления в социально-экономических системах регионов России
Биробиджан. Институт комплексного анализа региональных проблем дво ран. Амурский государственный университет. Тихоокеанский институт...
А. С. Епифанов Институт проблем точной механики и управления ран, Саратов, Россия iconУчебное пособие Санкт-Петербургский Гос институт точной механики и оптики (техн ун-т)
Санкт-Петербургский Гос институт точной механики и оптики (техн ун-т), Кафедра вычислительной техники
А. С. Епифанов Институт проблем точной механики и управления ран, Саратов, Россия iconО. В. Батурина Институт проблем управления ран, Москва, Россия
В методе не осуществляется варьирование относительно улучшаемого управления с параметрической оптимизацией, в отличие, например,...
А. С. Епифанов Институт проблем точной механики и управления ран, Саратов, Россия iconА. Г. Александров Институт проблем управления им. В. А. Трапезникова ран россия, 117997, Москва, Профсоюзная ул., 65
Идентификатор динамических процессов идп-1 на базе сигнального процессора adsp-21990
А. С. Епифанов Институт проблем точной механики и управления ран, Саратов, Россия iconА. Г. Александров Институт проблем управления им. В. А. Трапезникова ран россия, 117997, Москва, Профсоюзная, 65
Ключевые слова: программное обеспечение, идентификация, адаптивное управление, частотный подход
А. С. Епифанов Институт проблем точной механики и управления ран, Саратов, Россия iconПрограмма россия, Абзаково 17-23 августа 2011 года Четвертая Международная конференция «Системный анализ и информационные технологии»
Учреждение Российской академии наук Институт проблем управления им. В. А. Трапезникова ран
А. С. Епифанов Институт проблем точной механики и управления ран, Саратов, Россия iconKhristianovich institute of theoretical and applied mechanics
Институт теоретической и прикладной механики им. С. А. Христиановича со ран, Новосибирск, Россия
А. С. Епифанов Институт проблем точной механики и управления ран, Саратов, Россия iconУважаемые коллеги!
Организаторы: Институт проблем управления (ипу) им. В. А. Трапезникова ран, Университет новых информационных технологий управления...
А. С. Епифанов Институт проблем точной механики и управления ран, Саратов, Россия iconПленарные доклады
Чантурия В. А. (Россия, г. Москва, Институт проблем комплексного освоения недр ран (уран ипкон ран)) современные процессы переработки...
А. С. Епифанов Институт проблем точной механики и управления ран, Саратов, Россия iconА. А. Шалыто (1), Н. И. Туккель (2)
Санкт-Петербургский государственный институт точной механики и оптики (технический университет)
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница