Содержание к диссертации
Введение
Глава 1. Математические модели и методы исследования адаптивных дискретных систем 13
1.1 Общая характеристика математических моделей адаптивных дискретных систем 13
1.2 Основные задачи математического моделирования адаптивных дискретных систем . 20
1.3.Выводы 29
Глава 2. Математические модели и методы проектирования адаптивных систем, заданных полиномами 30
2.1. Моделирование дискретных систем полиномами с рациональными коэффициентами 30
2.2. Решение задачи синтеза для дискретных систем, заданных полиномами 38
2.3. Решение задачи анализа для дискретных систем, заданных полиномами 42
2.4.Выводы 54
Глава 3. Математические модели адаптивных дискретных систем без потери информации 55
3.1. Моделирование дискретных систем без потери информации с помощью перестановок 55
3.2. Анализ эффективности решений задачи синтеза адаптивных дискретных систем, заданных перестановками 64
3.3. Выводы 71
Глава 4. Разработка комплекса программ для исследования адаптивности программных систем 72
4.1. Шаблоны проектирования автоматных программ 72
4.2 Функции и структура комплекса программ SMG 78
4.3 Апробация комплекса программ SMG при разработке программной системы отслеживания ошибок и исследовании ее адаптивности 86
4.4. Выводы 90
Заключение 91
Список использованных источников: 93
- Основные задачи математического моделирования адаптивных дискретных систем
- Решение задачи синтеза для дискретных систем, заданных полиномами
- Анализ эффективности решений задачи синтеза адаптивных дискретных систем, заданных перестановками
- Функции и структура комплекса программ SMG
Введение к работе
Актуальность темы
Современные требования к системам различного класса (например, программным) ориентированы на обеспечение их адаптивности к изменяющимся внешним условиям. В работе рассматриваются дискретные адаптивные системы, моделируемые полиномами с рациональными коэффициентами и перестановками. Под дискретной понимается система, находящаяся в любой момент времени в одном из состояний, и преходящая из состояния в состояние под воздействием сигналов входных в определенные моменты времени. При этом предполагается, что множества состояний системы и входных сигналов конечны.
Адаптивность системы может быть достигнута, в частности, за счет
наличия в ней функциональной избыточности. Под избыточностью
понимают наличие таких модулей системы (универсальных), которые могут
реализовать поведение других модулей. Функциональная избыточность
обеспечивается за счет некоторого временного ресурса, который необходим
для подачи на вход универсального модуля последовательности сигналов.
Такую последовательность называют восстанавливающей
последовательностью.
При исследовании функциональной избыточности любой дискретной
системы можно выделить два типа задач: задачу синтеза (проектирование
функциональной избыточности на этапе создания системы) и задачу анализа
(выявление наличия функциональной избыточности в уже созданной
системе). Заметим, что эффективность решения задачи синтеза адаптивной
системы определяется минимизацией длины восстанавливающей
последовательности.
Если система моделируется семейством конечных детерминированных
автоматов (КДА), то функциональная избыточность в этой системе может
быть описана моделью универсального автомата. Использование
универсальных автоматов для проектирования функционально избыточных систем исследуется в работах А.А. Сытника, Т.Э. Шульги, Н.С. Вагариной, Н.И. Посохиной, К.П. Вахлаевой. При этом было доказано, что общего решения задач синтеза и анализа универсальных автоматов не существует. Поэтому в настоящее время предпринимаются попытки выделить классы автоматов, для которых можно предложить частные решения.
Например, в работах Шульги Т.Э. приведено решение задачи анализа для автоматов, заданных полиномами с целочисленными коэффициентами. При этом доказано, что не каждый КДА может быть задан указанным способом. Следовательно, требуется расширить класс автоматов, для которых решаются задачи синтеза и анализа функционально избыточных систем, в частности, за счет введения полиномов с рациональными коэффициентами.
Другим классом систем, для которых целесообразен поиск частичных решений задач синтеза и анализа является класс систем, моделируемых
перестановками определенной длины. Для таких систем существуют решения задачи синтеза, однако не для всех из них найдены ограничения на длину восстанавливающей последовательности.
Цель и задачи работы
Целью данной работы является развитие математических моделей адаптивных дискретных систем, заданных полиномами с рациональными коэффициентами, а также перестановками, и разработка методов синтеза и анализа таких систем.
Для достижения указанной цели решаются следующие задачи:
-
Изучить существующие модели адаптивных дискретных систем с целью определения классов систем, для которых целесообразно осуществлять поиск решений задач анализа и синтеза.
-
Развить математическую модель адаптивных дискретных систем, заданных полиномами за счет введения рациональных коэффициентов.
-
Исследовать две модели дискретных систем на эквивалентность: полиномы с рациональными коэффициентами и КДА.
-
Разработать методы и алгоритмы решения задач синтеза и анализа адаптивных дискретных систем, заданных полиномами с рациональными коэффициентами.
-
Найти ограничения на длину восстанавливающих последовательностей для решений задачи синтеза адаптивных дискретных систем, заданных перестановками.
-
Разработать комплекс программ, позволяющий конструировать адаптивные программные системы на основе принципов автоматного программирования.
Объект и предмет исследования
Объектом исследования являются адаптивные дискретные системы. Предметом исследования являются модели и методы, позволяющие обеспечить адаптивность системы за счет ее функциональной избыточности.
Методы исследований
Основу исследования составляют численные методы, методы теории полугрупп и групп, теории конечных детерминированных автоматов, системного анализа и их применение для решения задач анализа и синтеза функционально избыточных дискретных систем, моделируемых полиномами и перестановками.
Предложенные методы и алгоритмы реализованы в виде
специализированного комплекса программ, разработанного на языке программирования C#. При проектировании комплекса программ были использованы известные шаблоны проектирования.
Научная новизна
1. Развита математическая модель адаптивных дискретных систем,
отличающаяся способом задания поведения системы, а именно полиномами с рациональными коэффициентами. Данная модель расширяет класс
моделируемых систем по сравнению с системами, моделируемыми полиномами с целочисленными коэффициентами.
-
Для предложенной модели разработаны методы решения задач синтеза и анализа адаптивных дискретных систем, что позволяет расширить класс систем, для которых решаются данные задачи.
-
Для систем, поведение которых моделируется перестановками, проведена оценка эффективности различных решений задачи синтеза, которая обеспечивает возможность выбора решения с минимальной длиной восстанавливающей последовательности.
-
Предложен новый шаблон проектирования программных систем, отличающийся тем, что с помощью него можно разрабатывать адаптивные программные системы. С применением данного шаблона разработан комплекс программ, генерирующий адаптивные программные системы на основе принципов автоматного программирования.
Практическая значимость
Методы, предложенные в диссертационной работе, могут быть использованы при решении таких практически значимых задач, как проектирование адаптивных дискретных систем и управление ими. В частности, разработанный комплекс программ, позволяет автоматически генерировать код программной системы на основе ее автоматной модели, проектировать адаптивные программные системы, а также исследовать существующие программные системы на адаптивность.
Основные положения, выносимые на защиту
-
Предложенная математическая модель, описывающая поведение дискретной системы полиномами с рациональными коэффициентами, позволяет расширить класс систем, для которых могут быть решены задачи синтеза и анализа адаптивной дискретной системы.
-
Эквивалентность предложенной модели дискретной системы – полиномов с рациональными коэффициентами и известной модели КДА доказана за счет применения известных алгебраических методов.
-
Разработанные методы решения задач синтеза и анализа адаптивной дискретной системы, заданной полиномами с рациональными коэффициентами, позволяют проектировать адаптивные дискретные системы при наличии временного резерва и исследовать существующие системы на адаптивность.
-
Выявленные ограничения на длину восстанавливающих последовательностей для некоторых систем, моделируемых перестановками, позволяют оценить эффективность решения задачи синтеза адаптивных дискретных систем.
-
Предложенный шаблон проектирования и разработанный комплекс программ может быть использован любым исследователем для разработки программных систем на основе принципов автоматного программирования, в том числе для разработки адаптивных программных систем.
Соответствие диссертации паспорту научной специальности.
Указанная область исследования соответствует паспорту специальности 05.13.18 – математическое моделирование, численные методы и комплексы программ, а именно: пункту 1 – «Разработка новых математических методов моделирования объектов и явлений.»; пункту 3 – «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»; пункту 4 – «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента».
Апробация работы
О результатах исследования докладывалось на следующих
конференциях: ежегодная всероссийская научная конференция «Проблемы управления в социально-экономических и технических системах» Саратов 2013-2015гг.; всероссийский конгресс молодых ученых, Санкт-Петербург 2013г; международная научная конференция «XVIII-th International Open Science Conference», Воронеж, 2013г.; международная научная конференция «Математические методы в технике и технологиях - ММТТ-26», Саратов 2013г.; международная научная конференция «Математические методы в технике и технологиях - ММТТ-28», Саратов 2015г.; международная научная конференция «Информационно-коммуникационные технологии в науке, производстве и образовании», Саратов, 2014 г.; международная научно-практическая конференция «Инновационное развитие современной науки», 31 Уфа 2014 г.
Работа многократно обсуждалась на межкафедральных научных семинарах Международного факультета прикладных информационных технологий СГТУ им. Гагарина Ю.А.
Публикации
По результатам диссертационной работы опубликовано 14 печатных работ, в том числе 3 статьи в журналах, включенных в перечень ведущих периодических изданий ВАК РФ, и одно свидетельство о регистрации авторских прав на ЭВМ.
Структура и объем диссертации
Работа состоит из введения, четырех глав, заключения, списка использованной литературы, включающего 94 наименования, и приложений.
Основные задачи математического моделирования адаптивных дискретных систем
В данной работе исследуются адаптивные дискретные системы, причем, предполагается, что адаптивность системы достигается за счет функциональной избыточности. Одними из основополагающих исследований математических моделей дискретных систем, адаптивность которых возможна за счет функциональной избыточности, являются работы К.Шеннона, М.Минского, Дж. фон Неймона. Они предложили различные модели универсального автомата (машины, устройства).
Исследованиям теории автоматов посвящены работы таких ученых как А. Гилл [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] и многих других.
Впервые термин универсальный автомат ввел А.Тьюринг. Он доказал, что возможно построить универсальный автомат, однако в своих исследованиях ограничил роль автомата выполнением вычислительных функций. По А.Тьюрингу, универсальный автомат – это автомат, способный изменить закон своего функционирования в зависимости от последовательности входных данных. Изначально в таком автомате отсутствуют функции, зависящие от состояния и входного слова автомата. В своей работе «Общая и логическая структура автоматов», Дж. фон Неймон [36] отмечал, что для решения сложных задач классический подход к теории автоматов имеет свои недостатки: большие габариты составных элементов и ограниченная надежность их работы. В результате исследований была предложена концепция универсального автомата, отличного от универсального автомата Тьюринга. Автомат Дж. фон Неймона предполагает не изменяемость законов своего функционирования, а разработку нового автомата.
В рамках данного исследования, универсальным будет называться автомат, который способен моделировать работу другого автомата за счет последовательности входных сигналов. Таким образом, несколько входных сигналов универсального автомата будут индуцировать такую смену состояний, какую индуцировал бы один сигнал исследуемого автомата. Такую последовательность сигналов будем называть восстанавливающей последовательностью.
Задача построения универсального автомата изучалась такими учеными, как А.П. Горяшко [19], Э.А. Якубайтис [91] и др. Они считали универсальный автомат моделью, с помощью которой возможно проектирование универсальных и многофункциональных модулей. Основной идеей, изложенной в их работах, является перенастройка структуры технического объекта для его адаптации к изменившейся внешней среде.
Универсальный автомат как модель функционально избыточной системы впервые был рассмотрен А.А. Сытником, который ввел понятие автомата-перечислителя. В его работах [52, 53] модель такого автомата используется для решения задачи восстановления системы после возникновения эксплуатационных неисправностей, однако позже было показано, что данная модель может быть использована для более широкого спектра задач. Теоретические аспекты универсального автомата перечислителя исследуются в работах Н.С. Вагариной, Н.И. Посохиной, К.П. Вахлаевой [13, 41, 42, 55], а также и другими учеными. В этих работах задачи теории универсальных автоматов решаются для отдельных классов дискретных систем. Решением задач теории универсальных автоматов занималась Т.Э.Шульга [83, 85]. В ее работах рассматривались классы автоматов, заданных семействами полиномов с рациональными коэффициентами и семействами обобщенных подстановок.
Таким образом, автомат является известной и широко используемой моделью. В работе рассмотрены конечные детерминированные автоматы (КДА), то есть автоматы с конечными множествами входных сигналов и состояний, для которых всегда точно и однозначно определены переходы из одного состояния в другое. На данный момент широко исследованы следующие способы задания функции перехода автоматов: матрица переходов и граф переходов. Однако данные способы не всегда удобны для решения задач теории автоматов. Для решения некоторых задач теории автоматов используются такие способы задания автомата как: семейства обобщенных подстановок, семейства полиномов с целочисленными коэффициентами и семейства перестановок. При анализе способа задания КДА необходимо определить, любой ли КДА может быть представлен данным способом. Например, не любой КДА может быть задан семейством полиномов с целочисленными коэффициентами, однако некоторые задачи теории автоматов удобно решаются для автоматов такого класса. Расширить класс систем, моделируемых полиномами, можно за счет введения рациональных коэффициентов.
Рассмотрим класс систем, поведение которых моделируется семейством полиномов. Заметим, что композиция двух полиномов в свою очередь также является полиномом. Будем говорить, что семейство полиномов порождает другой полином, если этот полином может получиться путем композиции некоторого числа полиномов из заданного семейства. Тогда семейство полиномов в общем случае может породить бесконечное число других полиномов.
Пусть дана система А, моделируемая семейством полиномов I. Пусть I -множество полиномов, порожденных семейством I. Будем говорить, что система А является универсальной для системы В, моделируемой семейством полиномов I 1, тогда и только тогда, когда І± Я Г.. Тогда будем говорить, что система А может моделировать работу системы В за счет функциональной избыточности. Возьмем в качестве примера системы, моделируемой системой полиномов, конечный детерминированный автомат.
Решение задачи синтеза для дискретных систем, заданных полиномами
Основным вопросом, связанным с решением задач теории универсальных автоматов, является проблема выбора способа представления функции переходов автомата. Так как некоторые задачи теории универсальных автоматов являются алгоритмически неразрешимыми в общем случае, то принято искать их решения для особых классов автоматов. В частности, накладывают ограничения на вид функции переходов автомата.
В ряде работ исследуются автоматы, заданные семейством полиномов с целочисленными коэффициентами. Основной работой по данной теме является статья[54]. Авторы данной статьи нашли решение некоторых задач теории универсальных автоматов при условии, что функция переходов задана семейством полиномов с рациональными коэффициентами. Однако главным недостатком исследования является то, что не каждый автомат может быть задан семейством полиномов с целочисленными коэффициентами.
Будем говорить, что поведение конечного автомата А определяется семейством полиномов {fx}xeX с рациональными коэффициентами, если подстановка из семейства {дх}хеХ представима в виде (2.1.1) для каждого X; єI, т.е. fx.(s) = Sx(s). Будем говорить, что в таком случае подстановка 8Х эквивалентна полиному fx.
Заметим, что в числителе каждой дроби находится полином (ш-1)-ой степени, а в числителе - произведение чисел. Следовательно, каждый член суммы является полиномом (т -1)-ой степени с рациональными коэффициентами.
Очевидно, что сумма полиномов с их коэффициентами также будет являться полиномом с рациональными коэффициентами II. Докажем, что для любой модели системы, заданной полиномами вида (2.1.1), можно построить модель той же системы, заданную подстановками вида (1.1.2). 1) Из множества полиномов, задающих модель системы, выберем произвольный полиному ). 2) По определению, полином f(s) на множестве S = {0,1,…,т-1} принимает целочисленные значения из того же множества. 3) Вычислим значения полинома на числах 0, 1, будет задавать то же преобразование, что и полином f(s). 5) Так как полином был выбран произвольно, то аналогичным образом могут быть получены и остальные подстановки, моделирующие поведение системы.
Таким образом, было доказано, что для любой модели системы, заданной подстановками, можно построить модель этой же системы, заданной полиномами с рациональными коэффициентами вида (2.1.1) и наоборот.
Заметим, что в данной теореме не только доказывается эквивалентность двух моделей, но и предлагаются методы перехода от одной модели к другой. Приведем пример перехода от модели системы, заданной полиномами, к модели системы, заданной подстановками.
Пусть задан конечный автомат А , определяемый семейством полиномов с рациональными коэффициентами {fx}xeX, причем число состояний автомата равно трем. Выберем произвольную функцию fx из заданного семейства функций и вычислим ее значения на множестве 0,2 . Пускай
Кроме того, при применении входной последовательности порождается суперпозиция подстановок, а следовательно и суперпозиция функций, в результате чего могут получаться полиномы больших степеней. При этом, так как в общем случае никаких ограничений на количество состояний и на степень полинома не накладывается, то возникает вопрос о том, как получить полином минимальной степени. Заметим, что поведение одной и той же системы может быть в общем случае задано разными полиномами. Тогда найдутся два полинома, описывающих одно и тоже поведение. В этом случае, оба полинома будут эквивалентны какой-либо подстановке. Введем формальное определение. Определение 2.1.2.
Будем говорить, что два полинома f\ (s) и fi(s) эквивалентны на множествеS = 0..m-1, где т - целое число, если они оба эквивалентны какой-либо подстановке вида (1.1.2) длиной в т элементов.
Так как полином f(s) принимает только целочисленные значения на множестве S, то для него существует равная ему подстановка S(s). Найдем данную подстановку, вычислив соответствующие значения функции/я). Так как доказано, что для любой подстановки существует равный ей полином/і(5 ), степень которого не превышает (т-1), найдем этот полином по схеме, представленной в теореме.
Анализ эффективности решений задачи синтеза адаптивных дискретных систем, заданных перестановками
Рассмотрим класс систем без потери информации. Данный класс систем примечателен тем, что для него существует взаимно-однозначное отображение входной последовательности в выходную. За счет этого по выходной реакции системы всегда можно установить входную. В качестве модели системы без потери информации может выступать автомат, который так же называется автоматом без потери информации.
Без ограничений на общность можно рассматривать автомат A (S, X, 8) (см. главу 1) в качестве автомата без потери информации. В этом случае взаимно-однозначным должно быть отображение S. В первой главе в качестве модели дискретной системы были рассмотрены семейства подстановок. Однако известно, что подстановка не представляет из себя взаимно-однозначное отображение и, следовательно, автомат, функция переходов которого представляет из себя семейство подстановок, не является автоматом без потери информации.
Рассмотрим частный случай - подстановку, во второй строке которой отсутствуют повторяющиеся элементы. Она представляет из себя взаимнооднозначное отображение из одного конечного множества в другое. Такие подстановки называются перестановками. Если некоторая система задана семейством перестановок, то ее можно назвать системой без потери информации.
Дадим формальное определение перестановки: Определение 3.1.2 [25]
Множество всех перестановок множества X (т.е. биекций X Х) с операцией композиции образуют группу, которая называется симметрической группой или группой перестановок X.
Таким образом, система без потери информации может моделироваться автоматом в том случае, если его функция переходов задана семейством перестановок.
Приведем формальное определение автомата, функция переходов которого зада семейством перестановок. Определение 3.1.3 [85] Автомат вида A = (X,S,8), Х = {х1,х2,...хп}, S=m, б : X х S - S называют групповым или перестановочным, если \/XGX функция переходов данного автомата представима в виде перестановки X Обозначим S = (1,...,m), sx = ( 0,..., m_1) - перестановка. Заметим, что в данной главе нумерация состояний автомата задается с 1. Данные изменения были внесены, так как в работе используется традиционный для теории групп способ задания перестановок. Приведем пример автомата, заданного семейством перестановок.
Заметим, что функции переходов данного автомата заданы перестановками, а, следовательно, автомат является групповым автоматом.
Конец примера Рассмотрим алгебраические основы групповых автоматов. Очевидно, что так как такие автоматы задаются семействами перестановок, то для них будут справедливы известные алгебраические факты из теории групп. Определение 3.1.4[85]
Операцией умножения двух подстановок степени т будем называть последовательное выполнение двух подстановок степени т.
Умножение подстановок обладает следующими свойствами: - умножение подстановок п-й степени при Й 3 не коммутативно; умножение подстановок ассоциативно; для любой подстановки А справедливо равенство АЕ=ЕА=А, где
Так как рассматриваются конечные автоматы, то семейство перестановок, задающих автомат, конечно, а значит оно замкнуто относительно операции умножения. Известно, что для каждой перестановки можно найти обратную ей. Тогда очевидно, что семейство перестановок с алгебраической точки зрения является группой.
Заметим, что семейство перестановок 8 ,8 ,..., 8Хп вида (3.1.3), задающих автомат А вида (3.1.1), порождает конечную группу отображений GA=(sx1,SX2,...,SXn) = {s). Элементы группы 8X1 ,8X2 ,...,8Xn представляют собой систему образующих этой группы. Будем называть их порождающими подстановками группы автомата.
Элементы этой группы имеют вид /л/л /jk , где 0 р. aj , aj -порядок элемента 8 . Обозначим множество всех различных элементов
Групповые автоматы имеют следующее свойство: при заданном начальном состоянии по выходной последовательности можно всегда определить входную последовательность. Групповые автоматы также называют автоматами без потери информации.
Исследованию автоматных групп посвящены работы [57,64,80], однако в данной главе свойства группы автоматных подстановок будут изучаться с целью их использования для решения поставленных задач математического моделирования функционально избыточных систем.
Заметим, что любой групповой автомат может быть преобразован в автомат, заданный семейством полиномов с рациональными коэффициентами. Действительно, воспользовавшись формулой 2.1.2 можно по каждой перестановке получить полином, эквивалентный ей. Однако не любой автомат, заданный полиномами, может быть преобразован в групповой автомат. То есть класс групповых автоматов является подклассом класса автоматов, заданных полиномами с рациональными коэффициентами.
Заметим, что для любого автомата можно найти всевозможные различные реакции автомата на последовательности входных сигналов. При этом, если автомат задан перестановками, то эти реакции будут представлять из себя группу перестановок. Очевидно, что чем больше элементов содержит группа автомата, тем больший спектр поведения он может задать. Введем понятие порядка автомата. Определение 3.1.5[85]
Найдем порядок автомата A из примера 3.1.1.Для этого замкнем множество относительно операции суперпозиции, или другими словами построим всевозможные различные реакции автомата на последовательности входных сигналов.
Функции и структура комплекса программ SMG
При создании автоматных программ разработчик может использовать систему State Machine Generator для автоматического преобразования графа переходов автомата в исходный код. Результатом работы системы является набор файлов с расширением .cs (при использовании XSLT шаблонов для языка программирования «C#.NET»), которые представляют собой классы автомата в соответствии с модифицированным шаблоном State Machine. Разработчик может добавить эти файлы к уже существующему проекту в любой среде разработки для Microsoft.NET, например, Microsoft Visual Studio. После добавления файлов в проект разработчику остается только реализовать методы интерфейса автомата для конкретных состояний. Таким образом, система «State Machine Generator» позволяет ускорить процесс разработки программного обеспечения и использовать преимущества автоматного программирования.
При эксплуатации системы было выяснено, что наиболее целесообразным является ее использование для описания бизнес логики разрабатываемого приложения. Однако, при проектировании приложения с использованием автоматной парадигмы программирования, усложняется процесс внесения изменения в программный код системы. В частности, для изменения бизнес логики системы требуется изменение графического изображения автомата, генерация нового программного кода на основе изображения и затем интеграция этого кода с остальными слоями приложения.
Такой подход к разработке неудобен при проектировании масштабных приложений. Внесение изменений в код приложения без использования графической модели может повлечь за собой появление нежелательных ошибок и требует наличие специальных технических навыков.
Следовательно, при разработке программной системы разумно закладывать в нее функциональную избыточность на этапе проектирования. В этом случае проектируется система с заданным универсальным автоматом. Для автомата формируется файл с настройками, обеспечивающий необходимое поведение системы. При необходимости внесения небольших изменений в программу достаточно изменить файл с настройками.
Очевидно, что такой способ проектирования системы позволяет снизить время разработки системы, не требует специальных технических навыков. Однако время реакции разработанной системы увеличивается, что приводит к невозможности разработки системы реального времени. Тем не менее, для большинства систем временная задержка незначительна и, следовательно, допустима. 4.3 Апробация комплекса программ SMG при разработке программной системы отслеживания ошибок и исследовании ее адаптивности
В качестве примера, в рамках диссертации была разработана адаптивная дискретная система отслеживания программных ошибок Bug Detector (BD). В ней происходит отслеживание ошибок после их обнаружения тестировщиком некого программного продукта (ПП). Данная система может применяться в отделах тестирования для контроля процесса исправления ошибок. Для того, чтобы построить автоматную модель системы требовалось выделить типовые состояния ошибки ПП. Для классификации состояния ошибки ПП используется следующие нумерация и обозначения:
В графическом редакторе комплекса SMG был построен автомат, моделирующий процесс обработки ошибки. Для этого в графическом редакторе были добавлены состояния ошибки в виде узлов графа и операции, выполняемые над ошибкой, в виде дуг графа (см. рис 4.3.1). Заметим, что в представленном на рис. 4.3.1. автомате представлены не все связи, в нем для наглядности отсутствует состояние «Ошибка», занумерованное нулем, в которое переходит система при неправильной для данного состояния операции. Например, если ошибка отправлена на исправление, то ее нельзя пометить как устраненную. Это действие переведет систему в состояние ошибки.
Исследуем систему BD на наличие в ней функциональной избыточности. Для этого решим задачу анализа для автомата, представленного на рисунке 4.3.1, т.е. построим класс автоматов, для которых он является универсальным. Функции переходов рассматриваемого автомата, могут быть представлены полиномами fi(s),i = х± ...х9, где s -состояния автомата, а каждому входному сигналу системы соответствует свой полином. Степень и коэффициенты этих полиномов вычисляются по следующей схеме: 1. Для каждого входного сигнала формируется матрица вида (2.1.1).
На основе полученных таким образом полиномов, используя метод 2.3.3 второй главы диссертации, найдем решение задачи анализа автомата. В данном примере, этим решением является класс автоматов А, содержащий 386 автоматов, для которых автомат, изображенный на рисунке 4.3.1, является универсальным. Таким образом, найдено семейство систем, моделируемых автоматами класса А, для которых рассматриваемая система BD является функционально избыточной.
Приведем пример использования данной функциональной избыточности: пусть в системе BD появится входной сигнал нового типа «исправить ошибку и пометить как проверенную», переводящий автомат на рисунке 4.3.1 из состояния Assign в состояние Closed. Этому входному сигналу соответствует следующий полином:
Заметим, что при решении задачи анализа было выявлено, что полином f (s) можно заменить эквивалентным ему преобразованием, а именно /х3С/х20)) (которое соответствует подаче восстанавливающей последовательности сигналов за номерами х2и х3на вход универсального модуля). Таким образом, можно адаптировать систему BD к новым внешним условиям, не изменяя ее. 4.4. Выводы
В данной главе описывается предложенный в работе комплекс программ, предназначенный для построения исходного кода программы по ее автоматной модели. На основе данного комплекса проходит апробация предложенных методов решения задач синтеза и анализа.
Комплекс программ разработан на основе ряда известных шаблонов проектирования. Кроме того, в работе предложен новый шаблон проектирования, позволяющий строить программные системы, моделируемые несколькими автоматами. Программный комплекс использовался для разработки системы отслеживания ошибок. Эта система исследована на адаптивность. Выявлено, что она является универсальным модулем для 386 систем.