Разработка математических моделей адаптивных дискретных систем, заданных полиномами с рациональными коэффициентами и перестановками тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Сластихина Мария Дмитриевна

• Сластихина Мария Дмитриевна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Сластихина Мария Дмитриевна

Введение

Глава 1. Математические модели и методы исследования адаптивных

дискретных систем

1.1 Общая характеристика математических моделей адаптивных дискретных

систем

1.2 Основные задачи математического моделирования адаптивных

дискретных систем

1.3.Выводы

Глава 2. Математические модели и методы проектирования адаптивных

систем, заданных полиномами

2.1. Моделирование дискретных систем полиномами с рациональными

коэффициентами

2.2. Решение задачи синтеза для дискретных систем, заданных

полиномами

2.3. Решение задачи анализа для дискретных систем, заданных

полиномами

2.4.Выводы

Глава 3. Математические модели адаптивных дискретных систем без потери

информации

3.1. Моделирование дискретных систем без потери информации с помощью

перестановок

3.2. Анализ эффективности решений задачи синтеза адаптивных дискретных

систем, заданных перестановками

3.3. Выводы

Глава 4. Разработка комплекса программ для исследования адаптивности

программных систем

4.1. Шаблоны проектирования автоматных программ

4.2 Функции и структура комплекса программ SMG

4.3 Апробация комплекса программ SMG при разработке программной

системы отслеживания ошибок и исследовании ее адаптивности

2

4.4. Выводы

Заключение

Список использованных источников:

3

Введение

Современные требования к системам различного класса (программным,

техническим, экономическим и т.д.) ориентированы на обеспечение их

адаптивности к изменяющимся внешним условиям. Например, в работах

таких ученых, как Б. Ченг, С. Саджади, Ф. Маккинли, Э. Кастен, С. Рассел, П.

Норвиг [92-94], отмечается, что одним из самых критичных требований к

современным программным системам является адаптивность. При этом

адаптивность понимается не только как свойство аппаратного обеспечения,

но и как комплекс взаимодействия аппаратной части, программного

обеспечения и человеческих ресурсов.

В соответствии с международным стандартом ISO/IEC 9126-1:2001 и его

российском аналогом ГОСТ Р ИСО/МЭК 9126-93 «Информационная

технология. Оценка программной продукции. Характеристики качества и

руководства по их применению» адаптируемость (аdaptabi1ity) относится к

основным характеристикам качества программного продукта и понимается

как «атрибуты программного обеспечения, относящиеся к удобству его

адаптации к различным конкретным условиям эксплуатации, без применения

других действий или способов кроме тех, что предусмотрены для этого в

рассматриваемом программном обеспечении». Иными словами, адаптивный

программный продукт должен иметь возможности настройки для адаптации

к новым условиям работы: файлы конфигурации, окна настроек приложения,

выбор расположения файлов данных, выбор строки подключения к базе

данных, выбор расположения результирующих файлов и т.п.

В общем случае под адаптивными программными системами понимают

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

влиянием внешней среды. Несомненным достоинством адаптивной системы

является то, что она намного дольше может быть актуальной. Например,

программы, разработанные без учета адаптивности, быстрее устаревают или

перестают корректно работать. Таким образом, время жизни такого

4

программного обеспечения снижается, требуется или выпустить измененную

версию программы, или разработать новый, востребованный на рынке

продукт.

Существует несколько механизмов достижения адаптивности системы.

Например, в работах В. В. Карачуна, В. Н. Мельника, В. А. Павского,

К В. Павского, В. Г. Хорошевского [26,37,38] исследуются вопросы

моделирования адаптивных систем с использованием механизма структурной

(аппаратной) избыточности. Под структурной избыточностью понимают

внесение в систему дополнительных (резервных) модулей, каждый из

которых полностью дублирует поведение какого-либо модуля системы.

Данный вид избыточности наиболее часто используется в технических

системах для обеспечения ее отказоустойчивости. Внесение дополнительных

модулей приводит к увеличению размеров и стоимости системы.

Добиться адаптивности можно и другим способом – за счет

функциональной избыточности [40,59]. Под функциональной избыточностью

понимают наличие таких модулей системы (универсальных), которые могут

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

временного резерва. Для этого следует специальным образом воздействовать

на универсальный модуль и снимать его реакции только в определенные

моменты времени.

Очевидно, что не каждая система обладает необходимой

функциональной избыточностью. Более того, среди систем, обладающих

функциональной избыточностью, не каждая обладает необходимым

временным резервом для ее реализации.

В данной работе рассматриваются дискретные системы, адаптивность

которых достигается за счет функциональной избыточности. Под дискретной

системой понимается система, находящаяся в любой момент времени в

одном из конечного числа состояний и преходящая из состояния в состояние

под воздействием входных сигналов в определенные моменты времени.

Например, программные системы являются дискретными, причем под

5

состояниями системы можно понимать содержимое ячеек памяти в каждый

момент времени. К системам такого типа относят системы, моделью которых

является конечный автомат[60].

Для дискретных систем временной резерв измеряется в количестве

тактов, необходимых для обработки так называемой восстанавливающей

последовательности входных сигналов, обеспечивающей необходимую

реакцию системы. То есть для того, чтобы вызвать необходимую реакцию

системы, необходимо обработать последовательность сигналов вместо

одного [83].

При исследовании функциональной избыточности дискретной системы

выделяется два типа задач: задачу синтеза[54,58] и задачу анализа[50]. Задача

синтеза решается на этапе проектирования системы и состоит из двух

подзадач: построения модуля, универсального для заданного класса модулей,

и нахождения восстанавливающих последовательностей. Задача анализа

заключается в нахождении класса модулей, для которых заданный является

универсальным.

Заметим, что для некоторых классов систем можно построить несколько

универсальных модулей. Эти модули будут отличаться, в том числе,

восстанавливающими последовательностями. Будем определять

эффективность решения задачи синтеза адаптивной системы минимизацией

длины восстанавливающей последовательности.

Одним из самых распространенных способов моделирования

дискретных систем являются конечные детерминированные автоматы (КДА)

[16, 72]. Если система моделируется семейством конечных

детерминированных автоматов, то функциональная избыточность в этой

системе может быть описана моделью универсального автомата.

Универсальные автоматы исследуются в работах К.Шеннона, М.Минского,

Дж. фон Неймона[36, 75], предложивших различные модели универсального

автомата (машины, устройства). Однако в этих работах не исследуется

6

возможность использования универсального автомата как модели

адаптивной дискретной системы.

Использование универсальных автоматов для проектирования

функционально избыточных систем исследуется в работах А.А. Сытника,

Т.Э. Шульги, Н.С. Вагариной, Н.И. Посохиной, К.П. Вахлаевой [13, 41, 42,

52-62, 77-89]. При этом было доказано, что общего решения задач синтеза и

анализа универсальных автоматов не существует. Поэтому в настоящее

время исследуются классы автоматов, для которых можно предложить

частные решения.

Одним из классов, для которых существует решение задачи анализа,

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

коэффициентами. При этом доказано, что не каждый КДА может быть задан

указанным способом. Следовательно, требуется расширить класс автоматов,

для которых решаются задачи синтеза и анализа функционально избыточных

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

коэффициентами.

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

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

групповым понимают такой автомат, функция переходов которого

представляет собой множество перестановок определенной длины. Для

групповых автоматов существуют решения задачи синтеза, однако не для

всех из них найдены ограничения на длину восстанавливающей

последовательности. Таким образом, требуется найти ограничения на длину

восстанавливающих последовательностей и выбрать наиболее эффективное

решение задачи синтеза.

Введение диссертации (часть автореферата) на тему «Разработка математических моделей адаптивных дискретных систем, заданных полиномами с рациональными коэффициентами и перестановками»

Цель и задачи работы

Целью данной работы является развитие математических моделей

адаптивных дискретных систем, заданных полиномами с рациональными

коэффициентами, а также перестановками, и разработка методов синтеза и

анализа таких систем.

7

 Для достижения указанной цели решаются следующие задачи:

1) Изучить существующие модели адаптивных дискретных систем с

целью определения классов систем, для которых целесообразно

осуществлять поиск решений задач анализа и синтеза.

2) Развить математическую модель адаптивных дискретных систем,

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

3) Исследовать предложенную полиномиальную модель дискретных

систем и известную модель КДА на эквивалентность.

4) Разработать методы и алгоритмы решения задач синтеза и анализа

адаптивных дискретных систем, заданных полиномами с рациональными

коэффициентами.

5) Найти ограничения на длину восстанавливающих

последовательностей для решений задачи синтеза адаптивных дискретных

систем, заданных перестановками.

6) Разработать комплекс программ, позволяющий конструировать

адаптивные программные системы на основе принципов автоматного

программирования.

Объект и предмет исследования

Объектом исследования являются адаптивные дискретные системы.

Предметом исследования являются модели и методы, позволяющие

обеспечить адаптивность системы за счет ее функциональной избыточности.

Методы исследований

Основу исследования составляют численные методы, методы теории

полугрупп и групп, теории конечных детерминированных автоматов,

системного анализа и их применение для решения задач анализа и синтеза

функционально избыточных дискретных систем, моделируемых полиномами

и перестановками.

Предложенные методы и алгоритмы реализованы в виде

специализированного комплекса программ, разработанного на языке

8

программирования C#. При проектировании комплекса программ были

использованы известные шаблоны проектирования.

Научная новизна

1) Развита математическая модель адаптивных дискретных систем,

отличающаяся способом задания поведения системы, а именно полиномами с

рациональными коэффициентами. Данная модель расширяет класс

моделируемых систем по сравнению с системами, моделируемыми

полиномами с целочисленными коэффициентами.

2) Для предложенной модели разработаны методы решения задач

синтеза и анализа адаптивных дискретных систем, что позволяет расширить

класс систем, для которых решаются данные задачи.

3) Для систем, поведение которых моделируется перестановками,

проведена оценка эффективности различных решений задачи синтеза,

которая обеспечивает возможность выбора решения с минимальной длиной

восстанавливающей последовательности.

4) Предложен новый шаблон проектирования программных систем,

отличающийся тем, что с помощью него можно разрабатывать адаптивные

программные системы. С применением данного шаблона разработан

комплекс программ, генерирующий адаптивные программные системы на

основе принципов автоматного программирования.

Практическая значимость

Методы, предложенные в диссертационной работе, могут быть

использованы при решении таких практически значимых задач, как

проектирование адаптивных дискретных систем и управление ими. В

частности, разработанный комплекс программ, позволяет автоматически

генерировать код программной системы на основе ее автоматной модели,

проектировать адаптивные программные системы, а также исследовать

существующие программные системы на адаптивность.

9

 Основные положения, выносимые на защиту

1) Предложенная математическая модель, описывающая поведение

дискретной системы полиномами с рациональными коэффициентами,

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

синтеза и анализа адаптивной дискретной системы.

2) Эквивалентность предложенной модели дискретной системы –

полиномов с рациональными коэффициентами и известной модели КДА

доказана за счет применения известных алгебраических методов.

3) Разработанные методы решения задач синтеза и анализа адаптивной

дискретной системы, заданной полиномами с рациональными

коэффициентами, позволяют проектировать адаптивные дискретные системы

при наличии временного резерва и исследовать существующие системы на

адаптивность.

4) Выявленные ограничения на длину восстанавливающих

последовательностей для некоторых систем, моделируемых перестановками,

позволяют оценить эффективность решения задачи синтеза адаптивных

дискретных систем.

5) Предложенный шаблон проектирования и разработанный комплекс

программ может быть использован любым исследователем для разработки

программных систем на основе принципов автоматного программирования, в

том числе для разработки адаптивных программных систем.

Соответствие диссертации паспорту научной специальности.

Указанная область исследования соответствует паспорту специальности

05.13.18 – математическое моделирование, численные методы и комплексы

программ, а именно: пункту 1 – «Разработка новых математических методов

моделирования объектов и явлений.»; пункту 3 – «Разработка, обоснование и

тестирование эффективных вычислительных методов с применением

современных компьютерных технологий»; пункту 4 – «Реализация

эффективных численных методов и алгоритмов в виде комплексов

10

проблемно-ориентированных программ для проведения вычислительного

эксперимента».

Апробация работы

О результатах исследования докладывалось на следующих

конференциях.

Всероссийские: всероссийская научная конференция "Проблемы

управления в социально-экономических и технических системах" Саратов

2013г.; всероссийский конгресс молодых ученых, Санкт-Петербург 2013г.

Международные: XVIII-th International Open Science Conference,

Воронеж январь 2013г., ММТТ-26, Саратов 2013г.; международная научная

конференция ICIT 2014 «Информационно-коммуникационные технологии в

науке, производстве и образовании», Саратов 2014 г., международная

научно-практическая конференция «Инновационное развитие современной

науки», 31 Уфа 2014 г.

Работа многократно обсуждалась на межкафедральных научных

семинарах Международного факультета прикладных информационных

технологий СГТУ им. Гагарина Ю.А.

Структура и объем диссертации

Работа состоит из введения, четырех глав, заключения и списка

использованной литературы, включающего 94 наименования.

В первой главе описаны общие характеристики адаптивных

дискретных систем, проанализированы несколько известных способов

моделирования таких систем. В частности, рассмотрены системы, заданные

полиномами с целочисленными коэффициентами, перестановками и

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

синтеза и анализа адаптивной системы в терминах подстановок.

Во второй главе полиномиальная модель адаптивной системы

расширяется за счет введения рациональных коэффициентов. Доказывается

эквивалентность этой модели и модели системы, заданной подстановками.

11

Для предложенной модели приведены частные решения задач синтеза и

анализа адаптивной дискретной системы.

В третьей главе исследуются различные решения задачи синтеза для

систем без потери информации, т.е. систем, моделируемых перестановками.

Для этих решений находятся ограничения на длину восстанавливающей

последовательности, что позволяет сделать вывод об эффективности

решения задачи синтеза адаптивной дискретной системы.

Четвертая глава посвящена апробации предложенных в работе

методов. В качестве примера дискретной системы рассматриваются

программные системы, а в качестве их модели – автоматная модель.

Описывается структура и функции комплекса программ, позволяющего по

автоматной модели программы строить ее исходный код, а также решать

задачи синтеза и анализа адаптивных программных систем. Приводится

пример использования данного комплекса программ при разработке системы

отслеживания программных ошибок и исследования ее на адаптивность.

В заключении приводятся основные результаты диссертационного

исследования.

12

Глава 1. Математические модели и методы

исследования адаптивных дискретных систем

1.1 Общая характеристика математических моделей

адаптивных дискретных систем

В данной работе исследуются адаптивные дискретные системы, причем,

предполагается, что адаптивность системы достигается за счет

функциональной избыточности. Одними из основополагающих исследований

математических моделей дискретных систем, адаптивность которых

возможна за счет функциональной избыточности, являются работы

К.Шеннона, М.Минского, Дж. фон Неймона. Они предложили различные

модели универсального автомата (машины, устройства).

Исследованиям теории автоматов посвящены работы таких ученых как

А. Гилл [16], М. Минский, К. Шеннон, Дж. Фон Нейман [36, 75], А.М.

Богомолов, Д.В. Сперанский [9, 10], В.И. Варшавский [11, 12], М.А.

Гаврилов и др. [14], В.М. Глушков [17, 18], С.В. Яблонский [90], Р.И.

Григорчук, В.В. Некрашевич, В.И. Сущанский [20-22], В.Б. Кудрявцев и др.

[28], О.П. Кузнецов [29, 30], М.А. Айзерман и др. [1, 2], В.Г. Лазарев, Е.И.

Пийль [30], В.А. Твердохлебов [63, 64], Я.М. Барздинь, Н.Е. Кобринский,

Б.А. Трахтенброт [7, 27, 65], Дж. Ульман [66] и многих других.

Впервые термин универсальный автомат ввел А.Тьюринг. Он доказал,

что возможно построить универсальный автомат, однако в своих

исследованиях ограничил роль автомата выполнением вычислительных

функций. По А.Тьюрингу, универсальный автомат – это автомат, способный

изменить закон своего функционирования в зависимости от

последовательности входных данных. Изначально в таком автомате

отсутствуют функции, зависящие от состояния и входного слова автомата.

13

 В своей работе «Общая и логическая структура автоматов», Дж. фон

Неймон [36] отмечал, что для решения сложных задач классический подход к

теории автоматов имеет свои недостатки: большие габариты составных

элементов и ограниченная надежность их работы. В результате исследований

была предложена концепция универсального автомата, отличного от

универсального автомата Тьюринга. Автомат Дж. фон Неймона предполагает

не изменяемость законов своего функционирования, а разработку нового

автомата.

В рамках данного исследования, универсальным будет называться

автомат, который способен моделировать работу другого автомата за счет

последовательности входных сигналов. Таким образом, несколько входных

сигналов универсального автомата будут индуцировать такую смену

состояний, какую индуцировал бы один сигнал исследуемого автомата.

Такую последовательность сигналов будем называть восстанавливающей

последовательностью.

Задача построения универсального автомата изучалась такими учеными,

как А.П. Горяшко [19], Э.А. Якубайтис [91] и др. Они считали

универсальный автомат моделью, с помощью которой возможно

проектирование универсальных и многофункциональных модулей. Основной

идеей, изложенной в их работах, является перенастройка структуры

технического объекта для его адаптации к изменившейся внешней среде.

Универсальный автомат как модель функционально избыточной

системы впервые был рассмотрен А.А. Сытником, который ввел понятие

автомата-перечислителя. В его работах [52, 53] модель такого автомата

используется для решения задачи восстановления системы после

возникновения эксплуатационных неисправностей, однако позже было

показано, что данная модель может быть использована для более широкого

спектра задач. Теоретические аспекты универсального автомата-

перечислителя исследуются в работах Н.С. Вагариной, Н.И. Посохиной, К.П.

Вахлаевой [13, 41, 42, 55], а также и другими учеными. В этих работах задачи

14

теории универсальных автоматов решаются для отдельных классов

дискретных систем. Решением задач теории универсальных автоматов

занималась Т.Э.Шульга [83, 85]. В ее работах рассматривались классы

автоматов, заданных семействами полиномов с рациональными

коэффициентами и семействами обобщенных подстановок.

Таким образом, автомат является известной и широко используемой

моделью. В работе рассмотрены конечные детерминированные

автоматы (КДА), то есть автоматы с конечными множествами входных

сигналов и состояний, для которых всегда точно и однозначно определены

переходы из одного состояния в другое. На данный момент широко

исследованы следующие способы задания функции перехода автоматов:

матрица переходов и граф переходов. Однако данные способы не всегда

удобны для решения задач теории автоматов. Для решения некоторых задач

теории автоматов используются такие способы задания автомата как:

семейства обобщенных подстановок, семейства полиномов с

целочисленными коэффициентами и семейства перестановок.

При анализе способа задания КДА необходимо определить, любой ли

КДА может быть представлен данным способом. Например, не любой КДА

может быть задан семейством полиномов с целочисленными

коэффициентами, однако некоторые задачи теории автоматов удобно

решаются для автоматов такого класса. Расширить класс систем,

моделируемых полиномами, можно за счет введения рациональных

коэффициентов.

Рассмотрим класс систем, поведение которых моделируется семейством

полиномов. Заметим, что композиция двух полиномов в свою очередь также

является полиномом. Будем говорить, что семейство полиномов порождает

другой полином, если этот полином может получиться путем композиции

некоторого числа полиномов из заданного семейства. Тогда семейство

15

полиномов в общем случае может породить бесконечное число других

полиномов.

Пусть дана система А, моделируемая семейством полиномов I. Пусть I* -

множество полиномов, порожденных семейством I. Будем говорить, что

система А является универсальной для системы В, моделируемой семейством

полиномов I1, тогда и только тогда, когда 𝐼1 ⊆ 𝐼 ∗ .. Тогда будем говорить, что

система А может моделировать работу системы В за счет функциональной

избыточности. Возьмем в качестве примера системы, моделируемой

системой полиномов, конечный детерминированный автомат.

В качестве базовой модели дискретной системы выбран конечный

детерминированный автомат (КДА)

A=(X,S,), (1.1.1)

где 𝑆 = {𝑠0 , … , 𝑠𝑚−1 } – конечное непустое множество внутренних

состояний автомата, m – количество состояний автомата;

𝑋 = {𝑥1 , … , 𝑥𝑛 } – конечное непустое множество входных сигналов

автомата, n – количество входных символов автомата;

𝛿: 𝑋 × 𝑆 → 𝑆– функция переходов автомата.

Введем обозначение

𝑡 = 𝑥1 𝑥2 … 𝑥𝑘 – некоторая последовательность входных сигналов

автомата;

𝛿𝑡 (𝑠) = 𝛿𝑥𝑘 (… (𝛿𝑥1 (𝑠)) … . ) - преобразование, индуцируемое

последовательностью входных символов автомата.

X * - множество различных между собой последовательностей входных

сигналов автомата А.

Занумеруем состояния автомата натуральными числами S ={0,1,...,m-1}

и представим функцию переходов данного автомата в виде обобщенных

подстановок:

𝑠 = 0 𝑠1 = 1 … 𝑠𝑚−1 = 𝑚 − 1

𝛿𝑥 = ( 0 ′ ), xX. (1.1.2)

𝑠0 𝑠1′ … ′

𝑠𝑚−1

16

 Обозначим s = (0,1,…,m-1). Для краткости также будем использовать

запись подстановки (1.1.2) в виде  x (s)  ( s0 , s1 ,..., sm1 ) .

Приведем пример дискретной системы, функция переходов которой

задается семейством подстановок.

Пример 1.1.1.

Рассмотрим классический пример автомата, приведенный в книге

А. Гилла «Введение в теорию автоматов»[16]. Дано: английский текст,

составленный из 26 букв алфавита и пропусков, просматривается с целью

подсчета числа слов, начинающихся с un или кончающихся на d (таких, как

«understand», «united» и т. д.). Для простоты пропуски обозначим буквой π, а

все другие буквы, кроме d, n и u, —буквой λ.

Построим на этих входных данных автомат А. Будем считать, что

состояния автомата занумерованы следующим образом:

новое слово;

ждать нового слова;

появление u;

появление u-n;

появление u-n-d.

Тогда автомат А (X,S,δ) примет вид:

X={d, n, u, π, λ},

S= {0, 1, 2, 3, 4},

 0 1 2 3 4  0 1 2 3 4  0 1 2 3 4

 d :  ;  n :  ;  u :  ;

 1 1 1 4 4   1 1 3 1 3   2 1 1 1 3 

 0 1 2 3 4 0 1 2 3 4

  :  ;   :  .

0 0 0 0 0  1 1 1 1 3 

Заметим, что при введении входного слова, состоящего из нескольких

символов, в автомате индуцируется серия переходов из одного состояния в

другое. Если функция переходов состояния автомата представлена

семейством подстановок, то реакции автомата на введённое входное слово

17

будет соответствовать подстановка, являющаяся произведением подстановок

автомата. Пусть было введено входное слово 𝑥1 𝑥2 . Тогда подстановка

𝛿𝑥1𝑥2 (𝑠), соответствующая реакции автомата на входное слово 𝑥1 𝑥2 будет

равна:

𝛿𝑥1𝑥2 (𝑠) = 𝛿𝑥1 (𝑠)𝛿𝑥2 (𝑠) = 𝛿𝑥2 (𝛿𝑥1 (𝑠)).

Конец примера

В качестве модели адаптивной дискретной системы может выступать

известная модель универсального автомата. Приведем формальное

определение универсального автомата.

Определение 1.1.1 [85]

Пусть задано семейство автоматов {Ai  ( X i , S ,  (i ) )}iI , |S| = m. Автомат

А = (Х,S,) назовем универсальным для семейства автоматов { Ai }iI , если

(x  X i )(i  I ) (t x  X * )( t x ( s)   x(i ) (s)), где s  (0,..., m  1) ,

т.е. для любого входного сигнала х любого автомата из семейства { Ai }iI

существует последовательность входных сигналов автомата A,

индуцирующая преобразование, эквивалентное преобразованию,

индуцируемому сигналом x автомата из семейства { Ai }iI .

Последовательность t i, будем называть восстанавливающей

последовательностью.

Нахождение восстанавливающей последовательности является важным

этапом работы с универсальными автоматами, так как именно

восстанавливающие последовательности позволяют моделировать работу

одного автомата другим автоматом.

Приведем пример универсального автомата.

Пример 1.1.2.

Пусть дано 2 автомата: А = (X,S,A) и В = (X,S,B), где

 0 1 2  0 1 2 В  0 1 2 0 1 2

 xA :   ,  x :   ,  x :   ,  x :   .

A В

 2 2 0  2 1 1   2 0 0  1 1 2 

1 2 1 2

18

 Причем, автомат А является универсальным для автомата В. Построим

восстанавливающие последовательности ti для автомата В. Заметим, что

подстановка  xB порождается суперпозицией следующих подстановок:  xA ,

1 1

 xA и  xA . Действительно:

2 1

0 1 2 B  0 1 2

 '1   xA ( xA )   ,  x   xA ( '1 )   .

 0 2 2   2 0 0 

1 2 1 1

Таким образом, восстанавливающая последовательность для первого

входного сигнала автомата В состоит из следующих входных сигналов

автомата А: t1 = (x1, x2, x1). Аналогично доказывается, что восстанавливающие

последовательности t2 = (x1, x2). Таким образом, первому входному символу

автомата В ставится в соответствие последовательность из трех входных

символов автомата А, а второму входному символу- последовательность из

двух.

Конец примера

Заметим, что при использовании универсального автомата, вместо

моделируемого увеличивается время реакции системы. Действительно,

каждому входному сигналу моделируемого автомата ставится в соответствие

несколько входных сигналов универсального. Несмотря на то, что мы можем

не считывать промежуточные данные системы, требуется время на их

обработку и соответствующую смену состояния. Тогда для минимизации

времени требуется наложить разумные ограничения на длину

восстанавливающей последовательности.

Так как нами рассматриваются дискретные системы, то длительность

работы системы будем определять как количество тактов системы, которые

потребовались на обработку входной последовательности сигналов.

19

 1.2 Основные задачи математического моделирования

адаптивных дискретных систем.

Очевидно, что для того, чтобы система была функционально

избыточной, необходимо, чтобы некоторые ее части могли изменять свои

законы функционирования. Следовательно, требуется разработать методику

обнаружения узлов системы, которые могут моделировать работу других

узлов (как уже существующих в системе, так и тех, которые могут

понадобиться позднее), то есть надо иметь возможность выбрать или

спроектировать такой узел, который может моделировать работу семейства

выбранных узлов.

В терминах автоматов это означает, что нам необходимо найти такой

универсальный автомат, который сможет смоделировать работу семейства

автоматов. Задача по нахождению такого автомата получила название задачи

синтеза. При этом задача синтеза состоит не только в нахождении

универсального автомата, но и в нахождении его восстанавливающих

последовательностей для каждого из исходных автоматов.

Другой задачей является задача нахождения семейства автоматов,

которые могут быть смоделированы работой заданного автомата – задача

анализа универсального автомата. Как правило, один достаточно

масштабный автомат (с 4 и более состояниями и несколькими входными

символами) может моделировать работу большого числа других автоматов.

Это приводит к тому, что решение задачи синтеза состоит из

многочисленного семейства автоматов. Однако не всегда требуется

нахождение всех автоматов, для которых заданный является универсальным.

В некоторых случаях разумно наложить некоторые ограничения на искомый

результат.

20

 Важной частью решения задач синтеза и анализа универсального

автомата является составление соответствующих восстанавливающих

последовательностей. Причем, как было замечено ранее, чем меньше длина

восстанавливающей последовательности, тем больше будет временная

эффективность разрабатываемой на основе универсальных автоматов

системы.

Приведем формальные постановки задач синтеза и анализа

универсального модуля системы в терминах подстановок.

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

систем АI={Ai| i = 1..n } задается семейством подстановок Δi = {δ1i, δ2 i, … δn i}.

Обозначим за Δ* замыкание множества Δ относительно операции

суперпозиции. Требуется построить такую систему A, поведение которой

задается семейством подстановок Δ = {δ1, δ2, … δn} и для которой

выполняется следующее условие:

𝛥𝑖 ⊆ 𝛥∗ , где 𝑖 ∈ 1. . 𝑛.

Задача анализа: Пусть дана система A, поведение которой задается

семейством подстановок Δ = {δ1, δ2, … δn}. Требуется построить семейство

систем АI={Ai| i = 1..n }, заданное семейством подстановок Δi = {δ1i, δ2 i, …

δn i}, такое , что

𝛥𝑖 ⊆ 𝛥∗ , где 𝑖 ∈ 1. . 𝑛.

В общем случае задачи синтеза и анализа автоматов являются

алгоритмически неразрешимыми [84]. Однако возможно выделить такие

классы КДА, для которых существует решение этих задач. В данной

диссертации рассмотрены следующие классы автоматов:

 автоматы, заданные семействами перестановок;

 автоматы, заданные семействами подстановок;

 автоматы, заданные семействами полиномов.

В работах[79, 82, 85] приводятся основные положения, присутствующие

при разработке любого метода построения универсального автомата общего

21

вида. Эти положения используются для решения задачи синтеза

универсального автомата, заданного семейством полиномов с

целочисленными коэффициентами, однако данные положения справедливы

для решения задачи синтеза любого универсального автомата.

Рассмотрим КДА, заданные семействами подстановок. Заметим, что для

автомата с m состояниями, его все всевозможные автоматные

преобразования будут представлять из себя симметрическую полугруппу

Список литературы диссертационного исследования кандидат наук Сластихина Мария Дмитриевна, 2015 год

Список использованных источников:

1. Айзерман М.А. и др. Логика. Автоматы. Алгоритмы. М.:

Физматгиз, 1963. 140 с.

2. Айзерман М.А., Алескеров Ф.Т. Выбор вариантов. Основы теории.

М.: Наука, 1990. 236 с.

3. Алешин С.В. О базисах в группах автоматных подстановок

//Дискретный анализ. Новосибирск, 1970. Вып. 7. С. 3-8.

4. Алешин С.В. Свободная группа конечных автоматов // Вестник

МГУ. Сер. 1. Мат., мех. 1983. Вып. 4. С. 12-14.

5. Ахо A., Ульман Дж. Теория синтаксического анализа, перевода и

компиляции. — М.: МИР, 1978. — Т. 1. — 612 с.

6. Ахо А., Сети В. Ульман Дж. Компиляторы: принципы,

технологии и инструменты. М.: Издательский дом «Вильямс», 2003. 786 с.

7. Бардзинь Я.М., Калниньш Я.Я. Универсальный автомат с

переменной структурой // Автоматика и вычислительная техника. 1974. №2.

С. 9‑18.

8. Богомолов А.М. и др. Эксперименты с автоматами. Киев:

Наукова Думка, 1973. 144 с.

9. Богомолов А.М., Грунский И.С., Сперанский Д.В. Контроль и

преобразование дискретных автоматов. Киев: Наукова Думка, 1975. 174 с.

10. Богомолов А.М., Сытник А.А. Универсальные конечные

автоматы/ Доклады АН СССР. 1987. Т. 294. №3. С. 525-528.

11. Варшавский В.И. Апериодические автоматы. М.: Наука, 1976.

424 с.

12. Варшавский В.И. Коллективное поведение автоматов. М.: Наука,

1973. 407 с.

13. Вахлаева К.П. Применение управляющих функций для настройки

системы автоматов на заданное поведение в перечислительной

93

форме// Теоретические проблемы информатики и её приложений: Сб. науч.

тр. –Саратов: Изд-во Сарат. ун-та, 2004. Вып. 6. С. 61–67.

14. Гаврилов М.А., Девятков В.В., Пупырев В.И. Логическое

проектирование дискретных автоматов. М.: Наука, 1977. 352 с.

15. Гамма Э. Приемы объектно-ориентированного проектирования.

Паттерны проектирования / Э. Гамма, П. Хелм. - СПб.: Питер, 2007. – 366 с.

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

272 с.

17. Глушков В.М. Абстрактная теория автоматов / Успехи мат. наук,

1961. Т. 14. Вып. 5. С. 3‑62.

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

476 с.

19. Горяшко А.П. Логические схемы и реальные ограничения. М.:

Энергия, 1982. 184 с.

20. Григорчук Р.И, Некрашевич В.В., Сущанский В.И. Динамические

системы, автоматы и бесконечные группы / труды Математического

института им. В.А. Стеклова. М.: Наука, 2000. Т. 231. C. 134-214.

21. Григорчук Р.И, Некрашевич В.В., Сущанский В.И. Динамические

системы, автоматы и бесконечные группы / труды Математического

института им. В.А. Стеклова. М.: Наука, 2000. Т. 231. C. 134-214.

22. Григорчук Р.И, Некрашевич В.В., Сущанский В.И. Динамические

системы, автоматы и бесконечные группы / труды Математического

института им. В.А. Стеклова. М.: Наука, 2000. Т. 231. C. 134-214.

23. Джош Смит. Приложения WPF c шаблоном проектирования

модель-представление-модель представления / Джош Смит // MSDN

Magazine. 2009. №2.

24. Иванов Е.А, Шульга Т.Э., Сластихина М.Д. Программа State

Machine Generator [Электронный ресурс]. – Режим доступа:. http://state-

machine-generator.blogspot.com. – (Дата обращения 01.09.2014)

94

 25. Калужнин Л. А., Сущанский В. И. Преобразования и

перестановки: Пер. с укр.—2-е изд., перераб. и доп. — М.: Наука. Главная

редакция физико-математической литературы, 1985. — 160 с.

26. Карачун В. В., Мельник В. Н. Структурная избыточность как

средство повышения точности курсоуказания // Известия ЮФУ. Технические

науки. 2011. №3 (49). URL: http://cyberleninka.ru/article/n/strukturnaya-

izbytochnost-kak-sredstvo-povysheniya-tochnosti-kursoukazaniya (дата

обращения: 02.10.2015).

27. Кобринский Н.Е., Трахтенброт Б.А. Введение в теорию

конечных автоматов. М.: Физматгиз, 1962. 404 с.

28. Кудрявцев В.Б., Алешин С.В, Подколзин А.С. Введение в теорию

автоматов. М.: Наука, 1985. 319 с.

29. Кузнецов О.П. Сети из языков// Автоматика и телемеханика.

1980. №6. С. 152-161.

30. Кузнецов О.П.. Адельсон-Вельркий Г.М. Дискретная математика

для инженера. М.: Энергоатомиздат, 1988. 480 с.

31. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. М.:

Энергоатомиздат, 1989. 328 с.

32. Ляпин Е.С. Полугруппы. М.: Физматгиз, 1960. 592 с.

33. Макаров В. О порядках элементов группы автоматных

перестановок // Вестник МГУ. Сер. 1. Мат., мех. 1991. Вып. 4. С.86-87.

34. Марченков С.С. О числе максимальных подгрупп в группах

автоматных подстановок // Дискретный анализ и исследование операций.

Cep. 1. 2004. Т. 11. №2. С. 73-79.

35. Многофункциональные автоматы и элементная база цифровых

ЭВМ / под ред. В.А.Мищенко. М.: Радио и связь, 1981. 240 с.

36. Нейман Дж. Теория самовоспроизводящихся автоматов. М.:

Мир, 1971. 382 с.

37. Павский В. А., Павский К. В. Стохастическое моделирование и

оценки размера структурной избыточности масштабируемых

95

распределенных вычислительных систем // Известия ЮФУ. Технические

науки . 2014. №12 (161). URL: http://cyberleninka.ru/article/n/stohasticheskoe-

modelirovanie-i-otsenki-razmera-strukturnoy-izbytochnosti-masshtabiruemyh-

raspredelennyh-vychislitelnyh-sistem (дата обращения: 02.10.2015).

38. Павский В. А., Павский К. В., Хорошевский В. Г. Математическая

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

структурной избыточностью // Известия ЮФУ. Технические науки. 2012.

№5. URL: http://cyberleninka.ru/article/n/matematicheskaya-model-i-raschet-

pokazateley-funktsionirovaniya-vychislitelnyh-sistem-so-strukturnoy-

izbytochnostyu (дата обращения: 03.06.2015).

39. Пархоменко П.П. О технической диагностике. М.: Знание, 1969.

64 с.

40. Пархоменко П.П., Согомонян Е.С. Основы технической

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

средства. М.: Энегоиздат, 1981. 320 с.

41. Посохина Н.И. Об одном подходе к решению задачи синтеза

автоматов-перечислителей // Теоретические проблемы информатики и ее

приложений. Саратов: ГосУНЦ «Колледж», 1997. Вып. 1. С. 101-109

42. Посохина Н.И., Шульга Т.Э. Об одном подходе к построению

автомата-перечислителя // Методы кибернетики и информационные

технологии. Саратов: ГосУНЦ «Колледж», 1997. Вып. 1. С. 113-115.

43. Сластихина М.Д. Адаптивное программное обеспечение.

Достоинства и недостатки./ Сластихина М.Д.// Проблемы управления в

социально-экономических и технических системах: сборник научных статей.

– Саратов: Издательский центр «Наука» , 2013 г. - С. 29-31

44. Сластихина М.Д. Анализ тональности текстов/ Сластихина М.Д.,

Шульга Т.Э.// Математические методы в технике и технологиях ММТТ-26:

сб. трудов XXVI Междунар. науч. конф. Т.8. Саратов, 2013 г. - С. 36-38

45. Сластихина М.Д. О вопросах решения задач синтеза и анализа

конечных автоматов, заданных полиномами с рациональными

96

коэффициентами./ Сластихина М.Д.// Сборник тезисов докладов конгресса

молодых ученых, Выпуск 1. – СПб: НИУ ИТМО, 2013 г. - С 55-56

46. Cластихина М.Д. О вопросах решения задач синтеза и анализа

конечных автоматов./ Сластихина М.Д.// Материалы 51-й Международной

студенческой конференции «Студент и научно-технический прогресс»:

Информационные технологии. Новосибирский государственный

университет. Новосибирск. 2013 г. С 216.

47. Сластихина М.Д. О подходе к проектированию функционально

избыточных систем, заданных автоматами специального класса/ Сластихина

М.Д., Сытник А.А., Шульга Т.Э. // Вестник СГТУ 4 (73), Саратов: Сарат. гос.

техн. ун-т, 2013г., С.167-175.

48. Сластихина М.Д. Особенности парадигмы автоматного

программирования/ Сластихина М.Д., Шульга Т.Э.// Математические методы

в технике и технологиях ММТТ-26: сб. трудов XXVI Междунар. науч. конф.

Т.9. Саратов, 2013 г. - С. 36-38

49. Сластихина М.Д. Разработка программного обеспечение для

автоматизации работы компании по анализу мнения покупателей/

Сластихина М.Д.// Участники школы молодых ученых и программы

УМНИК: сб. трудов XXVI Междунар. науч. конф. Саратов, 2013 г. - С. 153-

154

50. Сластихина М.Д. Решение задачи анализа для класса конечных

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

коэффициентами/ Сластихина М.Д., Шульга Т.Э.// «Modern informatization

problems in the technological and telecommunication systems analysis and

synthesis», 2013 г. № 13. С.356-360

51. Сластихина М.Д. Решение задачи синтеза для автоматов с

различным числом состояний./ Сластихина М.Д.// Инновационное развитие

современной науки: сборник статей Международной научно-практической

конференции. 2014 г. - С. 221-223

97

 52. Сытник А.А. Восстановление поведения сложных систем.

Саратов: Изд-во СГУ, 1992. 192 с.

53. Сытник А.А. Перечислимость при восстановлении поведения

автоматов: доклады РАН. 1993. Т. 238. С. 25-26.

54. Сытник А.А. Синтез универсальных автоматов // Методы и

системы технической диагностики. 1987. № 7. С. 12-23.

55. Сытник А.А., Вагарина Н.С. Модели автоматов-перечислителей

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

международной конференции «Автоматизация проектирования дискретных

систем». Минск: ОИПИ НАН Беларуси, 2004. Т. 1. С. 79-86.

56. Сытник А.А., Посохина Н.И., Шульга Т.Э. Об одном подходе к

решению задачи синтеза автоматов-перечислителей // Теоретические

проблемы информатики и ее приложений. Саратов: ГосУНЦ «Колледж»,

1998. Вып. 2. С. 103-116.

57. Сытник А.А., Шульга Т.Э. О восстановлении систем,

моделируемых автоматами // Интеллектуальные системы. Научный журнал.

М.: Изд-во МГУ, 2005. Т. 9. Вып. 1‑4. С. 265-279.

58. Сытник А.А., Шульга Т.Э. Об одном методе синтеза

отказоустойчивых систем // Информационные технологии в науке,

производстве и социальной сфере: сб. науч. тр.; под ред. Ю.В. Гуляева.

Саратов: Изд-во «Научная книга», 2005. С. 122-131.

59. Сытник А.А., Шульга Т.Э. Проектирование отказоустойчивых

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

поведения // Автоматизация проектирования дискретных систем: материалы

Четвертой международной конференции. Минск: Институт технической

кибернетики НАН Беларуси, 2001. Т. 3. С. 37-45.

60. Сытник А.А., Шульга Т.Э. Числовые методы функционального

восстановления поведения систем // Автоматика и телемеханика. 2003. Вып.

10. С.123-130.

98

 61. Сытник А.А., Шульга Т.Э., Кунявская А.Н. Анализ и синтез

универсального-автомата перечислителя: тезисы докладов международной

конференции, посвященной памяти А.М. Богомолова Саратов: изд-во

Саратов. ун-та. 2002. С.70-71.

62. Сытник А.А., Шульга Т.Э., Папшев С.В. Управление поведением

мехатронных систем на основе свойств функциональной избыточности //

Мехатроника, автоматизация, управление. 2008. №12. С. 41-44.

63. Твердохлебов В.А. Логические эксперименты с автоматами.

Саратов: Изд-во СГУ, 1988. 184 с.

64. Твердохлебов В.А. Логические эксперименты с автоматами.

Саратов: Изд-во СГУ, 1988. 184 с.

65. Трахтенброт Б.А., Бардзинь Я.М. Конечные автоматы.

Поведение и синтез. М.: Наука, 1970. 400 с.

66. Ульман Дж. Вычислительные аспекты СБИС. М.: Радио и связь,

1990. 480 с.

67. Фатьянова М.Д. Задание автоматов с помощью семейства

полиномов с рациональными коэффициентами/ Фатьянова, М.Д. // Наука и

общество. Серия «Информационные технологии», 2011. - С. 113-116.

68. Фатьянова М.Д. Использование системы GAP для решения задач

теории автоматов/ Фатьянова, М.Д.// Проблемы социально-экономического

развития России, 2010. - С. 104-105

69. Фатьянова, М.Д. О задании конечного автомата с помощью

семейства полиномов/ Фатьянова, М.Д.// Модернизация экономики и

общества: новое качество поткризисного развития, 2011. - С 110-111.

70. Цетлин М.Л. Исследования по теории автоматов и

моделированию биологических объектов. М.: Наука, 1969. 317 с.

71. Чакань Б. Герег Ф.О. О группе автоматных подстановок //

Кибернетика. 1965. Вып. 5. C. 50-53.

72. Шалыто А., Туккель Н. Программирование с явным выделением

состояний// "Мир ПК", 2001. №8, C.116-121; №9, С.132-138.

99

 73. Шалыто А.А. SWITCH-технология. Алгоритмизация и

программирование задач логического управления. СПб.: Наука. – 1998.

74. Шалыто А.А., Туккель Н.И. Switch-технология — автоматный

подход к созданию программного обеспечения «реактивных» систем//

Программирование, 2001. №5, C.45—62.

75. Шеннон К. и др. Автоматы: сб. статей / под ред. К. Шеннона. М.:

Иностранная литература, 1956. 403с.

76. Шопырин Д.Г. Графическая нотация наследования автоматных

классов / Шопырин Д.Г., Шалыто А.А. //Программирование. 2007. № 5, с.62-

74.http://is.ifmo.ru/works/_12_12_2007_shopyrin.pdf

77. Шульга Т.Э. Библиотека функций GroupAutomata //

http://www.seun.ru/faculty/FIIT/KTOIT/GroupAutomata.rar (дата обращения

22.04.2009).

78. Шульга Т.Э. Метод нахождения длины восстанавливающих

последовательностей для систем без потери информации / Математические

методы в технике и технологиях: сб. трудов XXII Междунар. науч. конф.: в

10 т. Псков: Изд-во Псков. гос. политех. ин-та, 2009. Т. 2. C. 70-73.

79. Шульга Т.Э. Метод построения восстанавливающих

последовательностей для систем без потери информации // Системы

управления и информационные технологии. 2009. № 1.3(35). С. 407-411.

80. Шульга Т.Э. Метод построения перечислимого множества

автомата, моделируемого семейством многочленов / Теоретические

проблемы информатики и ее приложений. Саратов: ГосУНЦ

«Колледж», 2001. Вып. 4. С. 148-156.

81. Шульга Т.Э. Необходимые условия моделируемости автоматных

функций степенным многочленом // Теоретические проблемы информатики и

ее приложений. Саратов: ГосУНЦ «Колледж», 1998. Вып. 2. С. 145-153.

82. Шульга Т.Э. О возможностях восстановления поведения

сложных систем: сборник научных трудов всероссийской военно-

100

технической конференции «Проблемы совершенствования ракетных

комплексов». Саратов: Изд-во Саратовского филиала ВАУ, 1999. С 30-34.

83. Шульга Т.Э. О возможностях восстановления поведения сложных

систем / Актуальные проблемы военной науки и образования: сборник

научных докладов Академии военных наук, Саратовское отделение.

Саратовский филиал военного артиллерийского университета. Саратов, 2000.

С. 231-233.

84. Шульга Т.Э. О классе систем, разрешимом относительно задачи

управления поведением на основе свойств функциональной избыточности //

Вестник СГТУ. 2008. № 4. С. 57‑64.

85. Шульга Т.Э. Об универсальной перечислимости автоматов

специального класса // Социально-экономическое развитие России:

Проблемы, поиски решения: сб. науч. тр. по итогам научно-

исследовательской работы СГСЭУ в 2004 г. Саратов: Изд. центр СГСЭУ,

2005. Ч. 2. С. 115-116.

86. Шульга Т.Э. Численные критерии восстановимости поведения

КДА степенным многочленом // Теоретические проблемы информатики и ее

приложений. Саратов: ГосУНЦ «Колледж», 1997. Вып. 1. С. 132-137.

87. Шульга Т.Э., Ковальская А.С. О методе решения задачи

диагностирования нейронной сети // Автоматизация проектирования

дискретных систем: материалы шестой международной конференции.

Минск: ОИПИ НАН Беларуси, 2007. С. 237-245.

88. Шульга Т.Э., Ковальская А.С. Постановка задач

диагностирования неисправности и функционального восстановления в

теории нейронных сетей по аналогии с теорией конечных

детерминированных автоматов / Математическое и информационное

обеспечение экономической деятельности: альманах. Саратов: Саратовский

государственный социально-экономический университет, 2006. С. 81-86.

89. Шульга Т.Э., Ковальская А.С., Сорокина Е.В. Задачи

диагностирования и функционального восстановления поведения в теориях

101

автоматов и нейронных сетей // Вестник Саратовского государственного

социально-экономического университета. Саратов: Изд-во СГСЭУ, 2006.

№14(3). С. 131-133.

90. Яблонский С.В. Введение в дискретную математику. М.: Наука,

1979. 272 с.

91. Якубайтис Э.А. Логические автоматы и микромодули. Рига:

Зинатне, 1975. 260 с.

92. Philip K. McKinley, Seyed Masoud Sadjadi, Eric P. Kasten, Betty

H.C. Cheng. Composing Adaptive Software. IEEE Computer, July 2004. IEEE

Computer Society, 2004.

93. M. Aksit, Z. Choukair. Dynamic, Adaptive and Reconfigurable

Systems Overview and Prospective Vision/ Proc. 23rd Int?l Conf. Distributed

Computing Systems Workshops (ICDCSW03), IEEE CS Press, may 2003

94. P.K. McKinley et al. A Taxonomy of Compositional Adaptation/ tech.

report MSU-CSE-04-17, Dept. Computer Science and Engineering, Michigan State

Univ., 2004

102