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

10-7

2257

На правах рукописи

Шульга Татьяна Эриковна

МАТЕМАТИЧЕСКИЕ МОДЕЛИ ФУНКЦИОНАЛЬНО ИЗБЫТОЧНЫХ ДИСКРЕТНЫХ СИСТЕМ

Специальность 05.13.18- «Математическое моделирование, численные методы и комплексы программ»

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Саратов-2010

Работа выполнена в ГОУ ВПО «Саратовский государственный технический университет»

Научный консультант: доктор технических наук,

профессор Сытник Александр Александрович

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

профессор Кулагин Владимир Петрович

доктор технических наук, профессор Прохоров Сергей Антонович

доктор технических наук, профессор Львов Алексей Арленович

Ведущая организация: Институт проблем точной механики

и управления РАН, г. Саратов

Защита диссертации состоится 1 декабря 2010 года в 13.00 часов на заседании диссертационного совета Д. 212.242.08 в Саратовском государственном техническом университете по адресу: 410054, г. Саратов, ул. Политехническая, 77, Саратовский государственный технический университет, корп. 1, ауд. 319.

С диссертацией можно ознакомиться в научно-технической библиотеке ГОУ ВПО «Саратовский государственный технический университет»,

С авторефератом можно ознакомиться на сайте www.sstu.ru

Автореферат разослан « Щ » р/сти^},2010 г.

Ученый секретарь диссертационного совета

'/1/1 А.А.Терентьев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Для модификации поведения системы характерно использование двух основных типов избыточностей: аппаратной (структурной) и функциональной (временной). Аппаратная избыточность подразумевает введение в состав системы дополнительных резервных элементов, которые реализуют требуемое поведение. Функциональная избыточность предполагает использование свойств текущего закона функционирования для формирования на выходах требуемой совокупности реакций только на основе имеющегося в данный момент или искусственно создаваемого резерва времени. При этом для формирования на выходе требуемой совокупности реакций на вход следует подавать специальные последовательности входных символов, которые будем называть восстанавливающими. Восстанавливающая последовательность -это последовательность входных символов, при подаче которой в любом текущем состоянии система в качестве последнего выходного символа генерирует требуемый выходной символ. Система обладает функциональной избыточностью относительно заданной совокупности требуемых поведений, если возможно построить восстанавливающие последовательности для каждой требуемой реакции системы из данной совокупности. Функциональная избыточность может выявляться в созданной системе с целью получения требуемой реакции, а также целенаправленно создаваться на этапе проектирования системы.

Одним из первых авторов, подробно рассмотревшим понятие «адаптивность», является Я.З. Цыпкин, указавший, что адаптивность системы достигается за счет возможности настройки режима ее функционирования для получения некоторого спектра требуемых реакций. Однако в его работах не рассматриваются вопросы достижения адаптивности на основе функциональной избыточности. Вопросами избыточности в рамках проблемы отказоустойчивости занимались представители советской школы технической диагностики М.Ф. Каравай, Е.С. Согомонян, П.П. Пархоменко, Ю.Г Савченко, однако в их работах основное внимание уделено аппаратной избыточности.

Основы математического моделирования дискретных систем, способных реализовать некоторый спектр поведений, заложены в работах К.Шеннона, М.Минского, Дж. фон Неймона, А.Тьюринга, предложивших различные модели универсального автомата (машины, устройства). Универсальный автомат способен моделировать, порождать, воспроизводить заданный спектр поведений или объектов, соответственно по Шеннону, Минскому, фон Неймо-ну. Изучение универсальных конечных автоматов осуществлялось Э.В. Евреиновым и И.В. Прангишвили, А.П. Горяшко, В.А. Мищенко, Э.А. Якубайтисом и многими другими с целью построения универсальных и

3

многофункциональных модулей. Однако, превалирующей в этих работах была идея о достижении универсальности за счет перенастройки структуры технического объекта. Для описания функционально избыточных систем A.A. Сытником введена модель универсального автомата-перечислителя, однако в его работах эта модель используется только для решения задачи восстановления системы после возникновения различного рода неисправностей на этапе эксплуатации системы. Модель универсального автомата-перечислителя исследовалась также Н.С. Вагариной, Н.И. Посохиной, К.П. Вахлаевой и другими для отдельных классов дискретных систем, однако эти исследования имеют чисто теоретический характер и не затрагивают вопросы создания и эксплуатации функционально избыточных систем.

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

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

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

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

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

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

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

о систем без потери информации,

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

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

Методы исследований. При выполнении работы использованы методы системного и комбинаторного анализа, теории автоматов, теории полугрупп, теории чисел. Исследование основывается на формальных доказательствах с содержательной интерпретацией постановок задач и полученных результатов.

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

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

1. Сформулированы основные задачи математического моделирования функционально избыточных дискретных систем на содержательном уровне и в терминах выбранной математической модели (универсального автомата-перечислителя):

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

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

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

- задача реализации требуемых поведений дискретной системы на основе функциональной избыточности (задача построения восстанавливающих последовательностей).

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

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

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

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

6. Разработан комплекс проблемно-ориентированных программ в открытой свободно распространяемой системе GAP (система компьютерной алгебры, представляющая всемирный научный проект, объединяющий специалистов в области алгебры, теории чисел, математической логики и т.д.), реализующий все предложенные методы для работы с универсальными групповыми автоматами.

7. Исследована автоматная модель регистров различных типов, а именно регистров с последовательным приемом и параллельной выдачей информации, сдвиговых регистров, регистров с параллельным приемом и последовательной выдачей информации, регистров памяти. На основе свойств преобразований, реализуемых регистрами с последовательным приемом и параллельной выдачей информации при подаче входных сигналов 0 и 1, разработаны методы построения восстанавливающих последовательностей для данного класса объектов, методы синтеза универсальных перечислителей.

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

Практическая ценность, реализация результатов работы. Результаты диссертационной работы могут быть использованы при решении таких практически значимых задач, как проектирование и эксплуатация адаптивных систем. Метод проектирования функционально избыточной программной системы использован при разработке АИС «Управление инфраструктурой научно-образовательной среды» по проекту «Работы по анализу и выбору базовых показателей, используемых в зарубежных странах для оценки использования и воздействия ИКТ на сферу образования, и разработке методик анализа данных, технологии сбора и обработки информации на основе выбранных показателей» (в рамках ФЦП «Электронная Россия» (2002-2010 годы)) и при разработке регионального образовательного портала по заказу министерства образования Саратовской области, имеются соответствующие акты о внедрении. Теоретические результаты, представленные в диссертации, внедрены в учебный процесс в Саратовском государственном социально-экономическом университете (дисциплина «Теория вычислительных процессов и структур» для специальности 010503.65 «Математическое обеспечение и администрирование информационных систем») и в Саратовском государственном техническом университете (дисциплина «Методы разработки программного обеспечения» магистерской программы 55.28.13. «Сети ЭВМ и телекоммуникаций»).

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях: IV и VI Международных научных конференциях «Автоматизация проектирования дискретных систем CAD DD» (Минск, 2001, 2007), XXIV конференции молодых ученых МГУ (Москва, 2002), Международной научной конференции «Информационные технологии в естественных науках, экономике и образовании» (Саратов, 2002), V Международном конгрессе по математическому моделированию (Дубна, 2002), Всероссийской научной конференции «Научный сервис в сети Интернет» (Новороссийск, 2004), Всероссийской научно-практической конференции «Информационные технологии в образовании и науке» (Москва, 2006), XXII- XXIII Международных научных конференциях «Математические методы в технике и технологиях» (Псков, 2009, Саратов, 2010), постоянно действующем научном семинаре Института проблем точной механики и управления РАН (Саратов, 2009), X Международной научно-методической конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2010), конференциях по итогам научно-исследовательской работы СГСЭУ (Саратов, ежегодно в 2004 - 2010 гг.).

В полном объеме диссертация докладывалась в ГОУ ВПО «Саратовский государственный технический университет» и ГОУ ВПО «Саратовский государственный социально-экономический университет».

Публикации. По основным результатам диссертации имеется 38 публикаций, в т.ч. числе одна монотрафия и 11 статей в журналах, входящих в Перечень ВАК РФ.

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

1. Формулировка основных задач математического моделирования функционально избыточных дискретных систем в терминах универсальных автоматов-перечислителей позволяет применять при их решении аппарат теории автоматов и полугрупп. Доказательство алгоритмической неразрешимости этих задач для класса дискретных систем определяет основное направление исследований математических моделей функционально избыточных дискретных систем - исследование моделей частных классов дискретных систем.

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

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

7

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

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

5. Разработанный комплекс проблемно-ориентированных программ СгоирАи1оша1а, реализующий предложенные методы для работы с универсальными групповыми автоматами, может быть использован любым исследователем для решения задач выявления функциональной избыточности, проектирования и реализации требуемого поведения функционально избыточной системы без потери информации.

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

7. Предложенные схемы проектирования функционально избыточной программной системы основаны на принципах автоматного программирования и различных методах построения универсального автомата-перечислителя. Приведенная структура автоматных программ позволяет реализовать предложенные схемы на любом языке программирования как с помощью ЭлуксЬ-технологии, так и с помощью 1ЛаЫе8иа1сЬ-технологии.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы, включающего 192 наименования, и трех приложений. Работа изложена на 360 страницах, содержит 20 рисунков и 17 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

(!)

где д^ , , конечное множество внутренних состояний;

Х= {х,, , х „} - конечное множество входных сигналов; 6: X х 5 функция переходов.

Пронумеруем состояния автомата натуральными числами £={0, 1,..., т-1} и представим функцию переходов данного автомата в виде обобщенных подстановок: (0 1 т - Г|

Л-***- <2)

Обозначим 5 = (0,1,...,ю), ^ Для краткости также будем

использовать запись подстановки (2) в виде 6Х ($) = .

Поведение автомата (1) может быть описано функцией 5: Я х X' -> 5, где X'— множество слов алфавитах.

Определение 1.2.1. Пусть текущее поведение системы М моделируется автоматом А=(Х,Б,<5), Х={х1^с2,---уХп}, а требуемое - автоматом В = Х-{х\^сг,...^с„). Без ограничения общности будем считать К С5) * ^ СО * С0Д4, (*) = (0,-,^ СО = ^ (*). Система Мявля-

ется функционально избыточной системой относительно требуемых поведений , если (\/1,г = \,И)^1 еХ*) такое, что д[ (5) = (5). Последовательность ti будем называть восстанавливающей последовательностью для преобразования З'х (или для входного сигнала х().

Таким образом, система М обладает функциональной избыточностью, если возможно представить все автоматные преобразования автомата В, моделирующего требуемое поведение системы, через преобразования автомата А, моделирующего текущее поведение системы (рис. 1).

Требуемое поведение

ад

Текущее поведение

л* в V Х1,Х/1---Хг1 А

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

С алгебраической точки зрения, приложение последовательности входных сигналов индуцирует на множестве внутренних состояний преобразование, представляющее произведение преобразований, индуцируемых каждым из входных сигналов этой последовательности. При этом под произведением преобразований д СО • 5 (5) понимается преобразование 8Хг {5Х СО), обозначаемое как Зхл (5), т.е. все возможные преобразования, индуцируемые автоматом, представляют собой полугруппу преобразований относительно опе-

рации умножения, а автоматные подстановки {£л}*ел' - систему образующих этой полугруппы.

Построение восстанавливающей последовательности для преобразования 5'х. автомата В означает нахождение представления этого элемента в виде произведения элементов системы образующих автомата А, т.е. элементов {^гКел-- В алгебре это называется проблемой тождества. Известны системы образующих, в которых можно выразить любой элемент симметрической полугруппы, т.е. любое автоматное преобразование. Однако с точки зрения построения восстанавливающих последовательностей, интересны не только возможность самого выражения, но и его способ, количество элементов в этом выражении, т.е. длина восстанавливающей последовательности. Эти задачи являются не тривиальными и в теории полугрупп не решаются, т.к. предполагают исследование многочисленных систем образующих, для каждой из которых может быть предложено свое решение. Исследуя конкретные, практически значимые классы систем, можно выделять системы образующих полугруппы автоматных преобразований этих классов и именно для них решать проблему тождества.

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

Определение 1.2.4. Конечный детерминированный автомат А=(Х,8,&) является универсальным перечислителем для автоматов {Д}(еУ семейства I, если выполняется следующее условие: (V/€ /) ДХ'), где

= еЗЭ^еЛО £ (5') = $} - множество, перечислимое автоматом А,

ЦХ,') - множество, перечислимое автоматом Ап1 е I

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

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

Задача 1.3.1. Задача определения функциональной избыточности дискретной системы. Пусть задано текущее поведение дискретной системы, которое описывается с помощью конечного детерминированного автомата А.

Содержательная постановка задачи: определить класс поведений /, отличных от текущего, относительно которого дискретная система обладает функциональной избыточностью.

Постановка задачи в терминах теории универсальных автоматов (задача анализа универсального автомата): для автомата А построить семейство автоматов } для которого автомат А является универсальным.

Задача 1.3.2. Задача проектирования функционально избыточной системы. Пусть задан класс / требуемых поведений системы и каждое требуемое поведение г е / описывается автоматом А,. Таким образом, предполагается заданным семейство конечных детерминированных автоматов , моделирующих требуемые поведения системы.

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

Постановка задачи в терминах теории универсальных автоматов (задача синтеза универсального автомата): построить автомат А, задающий текущее поведение системы, который является универсальным для семейства автоматов {Л,},<=/

Задача 1.3.3. Задача определения возможности реализации требуемых поведений дискретной системы на основе функциональной избыточности. Пусть задано текущее поведение дискретной системы и класс / требуемых поведений системы, отличных от текущего. Пусть текущее поведение описывается с помощью конечного детерминированного автомата А, а каждое требуемое поведение, отличное от текущего, / е / - с помощью автомата А{.

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

Постановка задачи в терминах теории универсальных автоматов', для каждого автомата семейства Ы,}, проверить справедливость утверждения: А е ипА:, г е/, где - множество всех универсальных автоматов для автомата А,-.

Таким образом, для определения возможности реализации требуемых поведений системы на основе функциональной избыточности необходимо и достаточно показать, что автомат А является универсальным для семейства автоматов {А1}1

Если задача 1.3.1, задача 1.3.2 или задача 1.3.3 имеют положительное решение, то ставится задача реализации требуемого поведения. При этом считаются заданными: конечный детерминированный автомат А, моделирующий текущее поведение системы, и семейство конечных детерминированных автоматов {А, },е/, моделирующих требуемые поведения системы, для которого автомат Л является универсальным.

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

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

Постановка задачи в терминах теории универсальных автоматов: для каждого автомата А, семейства 7 построить множество отображений {ф<} ,е/, каждое из которых удовлетворяет условию щ(А) = А,,1 е 7, т.е. предложить метод построения восстанавливающих последовательностей автомата А, приложение которых моделирует все преобразования автоматов семейства

В диссертации показано, что такой метод можно сконструировать таким образом, чтобы он одновременно осуществлял построение восстанавливающих последовательностей и проверку принципиальной возможности их построения, т.е. являлся решением не только задачи 1.3.4, но и задачи 1.3.3. Кроме метода построения восстанавливающих последовательностей для решения данной задачи необходимо также определить механизмы и процедуры их приложения и снятия выходных реакций. Таким образом, решение задачи 1.3.4 подразумевает описание общей схемы реализации требуемых поведений функционально избыточной системы.

На основе результатов теории универсальных автоматов и теории полугрупп показана алгоритмическая неразрешимость поставленных задач на множестве дискретных систем (теорема 1.3.2).

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

Опишем общие подходы к решению поставленных задач.

Целесообразно выделить два типа реализации требуемых поведений функционально избыточных дискретных систем: реализация требуемых поведений структурно неизбыточной системы и реализация требуемых поведений системы с использованием модуля универсального перечислителя (МУП). В первом случае предполагается, что система обладает достаточной функциональной избыточностью для реализации заданного класса поведений, во втором -требуется введение в систему дополнительного (структурного) модуля, обладающего такой избыточностью. Для реализации требуемых

поведений структурно неизбыточной системы необходимо наличие модуля, который в работе назван модулем восстанавливающих последовательностей (МВП). В случае реализации требуемых поведений с использованием МУП, очевидно, предполагается второй обязательный модуль - модуль универсального перечислителя.

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

1. На вход МВП подается сигнал о необходимости настройки системы на требуемое поведение.

2. МВП отключает систему от внешних воздействий (с целью исключения возможных состязаний на входе системы).

3. На вход МВП подается некоторый входной сигнал х.

4. Модуль МВП для сигнала х выбирает восстанавливающую последовательность 1Х и соответствующие временные характеристики процесса реализации требуемого поведения, либо реализует алгоритм, вычисляющий последовательность ^ и ее длину.

5. МВП отключает выходы системы на время, определяемое длиной последовательности tx, т.е. до тех пор, пока не будут сформированы требуемые выходные реакции. Это действие осуществляется с целью не допустить выходных сигналов, предшествующих появлению исправной реакции. Возможен также вариант запоминания полученной реакции и ее выдачи в необходимый момент времени.

6. В случае структурно неизбыточной системы МВП подает восстанавливающую последовательность ^ на вход системы и после ее приложения, т.е. получения требуемой реакции, включает выход системы. В случае реализации требуемых поведений с использованием МУП модуль восстанавливающих последовательностей подает последовательность 1Х на вход МУП и после ее приложения передает последний выходной сигнал МУП на выход системы и включает его. После этого ожидается следующий входной сигнал.

Процесс реализации требуемых поведений в общем случае предполагает наличие в системе временной избыточности: продолжительность подачи восстанавливающих последовательностей должна «укладываться» в резервный промежуток времени между снятием выходных сигналов. В работе рассмотрены основные источники возникновения временной избыточности и возможные способы ее создания. Кроме того, предложен формальный способ описания временных характеристик процесса функционирования избыточных систем.

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

13

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

Тогда автомат ит = (Х, 5, Л), где {0,1,2}, 5= {0,1,..., т-\), Л= {¿ь, 6\, <%}, где функции ¿¡>, &1 представлены автоматными преобразованиями типа (3), является универсальным перечислителем для любого автомата с т состояниями. Построение для него восстанавливающих последовательностей, т.е. задача выразимости произвольного элемента полугруппы преобразований степени т через элементы системы образующих, - является неразрешимой. Однако она может быть решена при наложении ограничений на вид моделируемых автоматных подстановок.

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

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

Выход: универсальный перечислитель общего вида, совокупность восстанавливающих последовательностей.

1. Построение полугруппы Р автоматных преобразований, описывающих требуемое поведение системы, т.е. описание всех различных автоматных преобразований, индуцируемых последовательностями входных сигналов при требуемом поведении.

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

3. Определение механизма порождения всех элементов заданного множества автоматных преобразований через выбранную систему образующих. В случае необходимости допускается изменение системы образующих и повторение данного шага.

4. Разработка метода, определяющего для произвольного автоматного преобразования из заданного множества Р его конкретного представления через элементы системы образующих. Конструирование на этой основе восстанавливающих последовательностей для заданного класса требуемых поведений.

Кроме того, предлагается построение автомата с управляющим входным каналом, являющегося универсальным для любого автомата с т состояниями, который имеет вид:

где 5= {0, 1.....т-\}\ X - множество информационных входных сигналов;

А"- множество управляющих входных сигналов; Л^х^хЛ"}-^,

{$))), где хеХ, х'еХ\ 5 = (0, 1, ..., т-1); предста-

(3)

Ст=({ХуХ-}^,А),

(4)

вители классов эквивалентности автоматных преобразований на множестве {О, 1, т-1}; {Лу}^, - преобразования, являющиеся решениями уравнений , где х&Х(у- преобразование, эквивалентное 5Х).

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

Используя предложенные схемы, для одного и того же класса автоматных преобразований можно построить различные универсальные перечислители. Основными характеристиками универсального перечислителя, определяющими выбор перечислителя в качестве основы МУП, являются длина восстанавливающих последовательностей, число входных сигналов и состояний. Определить приоритеты среди указанных параметров позволяет содержательная интерпретация структуры средств реализации требуемых поведений. Число входных сигналов универсального перечислителя фактически равно числу входных каналов МУП, а число состояний универсального перечислителя - объему памяти МУП. Из двух этих характеристик наиболее критичным с точки зрения функционирования средств реализации требуемых поведений является объем памяти, следовательно, предпочтение у соотношения «максимальность числа входных сигналов» «минимальность объема памяти». В свою очередь, количество элементов в системе образующих полугруппы универсального перечислителя, а следовательно, и количество входных сигналов, влияет на длины восстанавливающих, последовательностей заданного автомата.

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

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

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

f¡(<s)=a0 +а^+а18г +...+а/5,(шос1ш),5 = (0,хеХ, (5)

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

Определение 2.2.1. Поведение автомата А вида (1) моделируется семейством многочленов {/„}уеХ вида (5), если (V* е х) преобразование 5, представимо многочленом /х, т.е. /х(з) = я,, т.е. автомат А вида (1) задан числовой моделью, если задано множество входных сигналов X = {х1,х2,...х#1}, количество состояний т и множество многочленов вида (5).

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

Теорема 2.2.1. Пусть т = 2"°р°1р2а1...ркак ,а0 £ 0,а, > 0,/' = 1,к - разложение числа состояний т автомата А вида (1) на простые множители. Тогда старшая степень / произвольного моделирующего многочлена вида (5) для данного автомата определяется по формуле / = г0 + т0 -1, где г0 - индекс полугруппы преобразований {5,52,...5Го+/Пп"1}, т0 - период полугруппы преобразований '}, которые вычисляются по формулам:

г0 =тах(а0,а,,..., ак), т0 = р"1'1 р">л НОК ([2"° '],/>,- 1,..., рк -1), где НОК - наибольшее общее кратное.

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

1. Задача нахождения коэффициентов моделирующего многочлена для заданной автоматной подстановки сводится к нахождению решения системы линейных алгебраических сравнений (СЛАС) вида

1 1 1

2 22 2'

5, S0 S2 ~S0

(mod/л) (6)

(m-1) (m-1)2 (m-1)'.

2. Если СJIAC вида (6) неразрешима, то для заданной автоматной подстановки невозможно построить моделирующий многочлен, т.е. не всякий автомат может быть представлен с помощью числовой модели.

3. Если СЛАС вида (6) разрешима, то в общем случае она имеет несколько решений, т.е. автоматная подстановка может моделироваться различными многочленами вида (5).

4. Если число состояний автомата т - простое число, система (6) имеет единственное решение. Это означает, что в этом случае для автоматной подстановки существует единственный моделирующий многочлен вида (5) (теорема 2.3.1).

5. Для построения числовой модели автомата необходимо для каждого входного сигнала х решить СЛАС вида (6), а именно найти хотя бы одно ее решение.

Кроме того, предложен метод, позволяющий построить для заданной автоматной подстановки семейство моделирующих многочленов или сделать вывод о невозможности числового моделирования данной подстановки (метод 2.2.1).

Так как не любой автомат допускает моделирование семейством многочленов, представляет интерес описание класса автоматов, допускающих такое моделирование. Такое описание основано на проведенном подробном исследовании свойств моделирующей матрицы автомата (матрица из СЛАС (6))-

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

Теорема 2.3.2. Пусть дан конечный детерминированный автомат А = (Х,5,6), |5] = т и каноническое разложение числа состояний автомата т

имеет вид т — р"] р"1 р°п Для того чтобы поведение автомата А моделировалось семейством многочленов вида (5), необходимо, чтобы любое его отображение переходов вида (2) удовлетворяло системе т-р\ сравнений, из которых т)-1 имеют вид

р -50) = 0(то<1т),£ = \,т1 -1,

а остальные имеют вид тхзк = тх$) (тос1/я),_/ = 1,/?, -1,1 < ку < (т - у) / /7,,

а, -1 а, _а„

где щ=рх* Р2—Рп

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

Теорема 2.3.3, Пусть дан конечный детерминированный автомат А = 1-51 = т и каноническое разложение числа состояний автомата т

имеет вид т ~ 2р, где р - простое число. Для того чтобы поведение автомата А моделировалось семейством многочленов вида (5), необходимо и достаточно, чтобы любое его отображение переходов вида (2) удовлетворяло следующей системе сравнений:

/75, -СР-1К =л„(тос! /и), (р + 1)5, + V! -(Р + 2К э0(то<1 т), (р- 1>2А+1 + *р+и2к -/>50 = 0(тос1 т),0<к<(р-2)/2, рг1 +(р-1)524 + = О(тосЫ) \<к<(р-\)/2,

-50) = 0(тоё2), \<к<р-\, 524+, =5,(тос12), 1<к<(т-\)/2.

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

гочленов с рациональными коэффициентами (теорема 2.3.4) и целыми коэффициентами (следствие 2.3.1).

Предложены способы доопределения немоделируемых, частично моделируемых и частично определенных автоматов до автоматов, допускающих числовое моделирование.

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

Определение 2.5.1. Пусть дан автомат А = (Х,8,£), X— х2,...^с„), который допускает моделирование семейством многочленов /, »/, »—> Д, Назовем множество Г^ различных элементов полугруппы, порожденных функциями /Х| ,/,2 >•••/,„, порождающим множеством многочленов автомата А.

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

Теорема 2.5.1. Автомат А=(Х,5,3), который допускает моделирование семейством многочленов {/х}хе:хл является универсальным перечислителем для семейства автоматов {Д}^ : А1 где А, допускает моделирование

семейством многочленов {/х')}хех1 » тогда и только тогда, когда

(V/ е 1)(Ух е X,) /х'] е РА , где Р*л - порождающее множество многочленов автомата А.

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

Основным результатом главы является решение задачи реализации требуемых поведений функционально избыточных систем, допускающих числовое моделирование, а именно метод построения восстанавливающей последовательности для заданного входного сигнала (метод 2.6.1). На входе метода считаются заданными автомат В = (Х,8,д) типа (1), многочлены

,1 = \,п вида (5), моделирующие требуемое поведение автомата, многочлен £Х/1(1 < И < ф g,л(•^)) вида (5), моделирующий текущее поведение автомата В при подаче входного сигнала дг/,. Выходом метода является последовательность входных символов порождающая после своего приложения структуру переходов внутренних состояний, соответствующую требуемому преобразованию, моделируемому функцией или вывод о невозможности реализации данного преобразования. Данный метод основан на свойствах полугруппы многочленов вида (5).

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

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

Определение 3.2.2. Автомат вида (1) называют групповым или перестановочным, если УхеХ функция переходов данного автомата представима в виде подстановки

Обозначим s = (1,..., т), sx =($,, —,sm) - перестановка на множестве

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

В работе приводятся формальные определения теории групповых автоматов, описываются их основные характеристики, приводятся примеры групповых автоматов. Кроме того, вводится понятие длины группового автомата, определяющей длины восстанавливающих последовательностей для данного автомата.

Определение 3.2.7. Длиной группы G в системе образующих Gen называют максимальную из длин ее элементов группы, где длина элемента группы - это минимальное число сомножителей из Gen в представлении элемента. Длиной группового автомата А будем называть длину его группы.

Из определения следует, что длина автомата, а значит, и длины восстанавливающих последовательностей для этого автомата, зависят от вида и количества подстановок, задающих функции перехода автомата.

Групповой автомат порождает некоторую подгруппу симметрической группы, соответствующей всему «спектру» преобразований группового автомата, поэтому группа автомата, универсального для всего класса групповых автоматов, должна быть симметрической.

Сформулированы задачи синтеза и анализа теории универсальных перечислителей для всего класса групповых автоматов с заданным числом состояний т (класса GAm). В качестве критерия универсальности автомата для данного класса используется следующее утверждение.

Утверждение 3.2.1. Групповой автомат с т состояниями является универсальным перечислителем для класса GAm тогда и только тогда, когда он порождает симметрическую группу степени т или, иными словами, когда его порядок равен т\

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

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

Теорема 3.3.1. Групповой автомат А=(Х, А\), |5]=т, \Х\=с1, функции переходов которого представлены множеством всех транспозиций А{={ (/,, /2), /, е5,/2 е5, /, }, является универсальным перечислителем для класса автоматов йАт. Длина восстанавливающей последовательности для данного универсального перечислителя относительно любого заданного преобразования с числом состояний т не превышает т-1.

Теорема 3.3.2. Групповой автомат А = (Х, 5, А2), = т>2, [Л^| = т-1, функции переходов которого представлены подстановками Л2 ={(1,0, / = 2,т }, является универсальным перечислителем для класса автоматов САт. Длина восстанавливающей последовательности для данного универсального перечислителя относительно любого заданного преобразования с числом состояний т не превышает 3(т/2-1)+1, если т — четное и 3[т/2]', если т — нечетное.

Теорема 3.3.3. Групповой автомат А~(Х, 5, Аг), |5]:=т>2, \Х\=т-\, функции переходов которого представлены подстановками А3 ={(/,1+1), / = 1,т-1}, является универсальным перечислителем для класса автоматов САт. Длина восстанавливающей последовательности для данного универсального перечислителя относительно любого заданного преобразования с числом состояний т не превышает т{т-1)/2.

Теорема 3.3.4. Групповой автомат А = (.X, 5, Д), = т>2, \Х\ = 2, функции переходов которого представлены подстановками Д ={(1,2), (1,2,...,т)}, является универсальным перечислителем для класса автоматов САт, причем его длина при т - 3 равна 2, а при т>3 больше длины универсального перечислителя с системой порождающих подстановок А3.

Теорема 3.3.5. Групповой автомат А=(Х, 5, А$), \8\=т>2, \Х\=2, функции переходов которого представлены подстановками А5 ={(1,2... т-1), (1,2,...,т)}, является универсальным перечислителем для класса автоматов бт1„„ причем его длина при т - 3 равна 2, а при т>3 меньше длины универсального перечислителя с системой порождающих подстановок Д.

1 Округление до целого вниз

В табл. 1 приведены зависимости между основными характеристиками универсальных перечислителей для класса САт (рассмотренных в теоремах 3.3.1-3.3.5), а именно зависимости между числом входных сигналов и, максимальными длинами восстанавливающих последовательностей с1 и числом состояний группового автомата т.

Таблица 1

Характеристики универсальных перечислителей _

Ах Аг Аз А 4;

т п п а п п ■■ 4 . п Ш '

3 3 - 2 '7 . 3 2 2 ы- 2 •; 2

4 6 3 3 2 2 -

5 10 4 4 2 2

6 15 5 5 Шт 2 2

7 21 6 6 2 2 Щъ

8 28 г Т., 7 7 2 2 '423

9 36 8 ^12 8 ■--■¿6Г 2 чш ■ 2 Л5

Данные зависимости количества входных сигналов и длин восстанавливающих последовательностей от числа состояний универсального перечислителя в графической форме представлены на рис. 2 и 3, соответственно. Из рисунков, в частности, видно, что автомат с системой образующих А\ обладает минимальными длинами восстанавливающих последовательностей, но максимальным количеством входных сигналов, а автоматы с системами образующих Д4 и - одинаковым количеством входных сигналов. При этом, автомат с системой Л5 имеет меньшую длину восстанавливающих последовательностей, чем автомат с системой Д.

Построены различные универсальные перечислители не только для всего класса групповых автоматов ОАт, но и для его подкласса автоматов, функции переходов которых реализуются только четными автоматными подстановками {теоремы 3.3.6, 3.3.7, 3.3.12).

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

Теорема 3.3.13. Пусть дан групповой автомат А = (£Д,<5), |5| = т>2, 1Х\ = п. Тогда с {¿}хеХ при условии, что Зх - нетождественная подстановка, существует автоматная подстановка у степени т такая, что автомат А' -{Б, X',{бу}), \Х]=2 является универсальным перечислителем для автоматов из класса САт. Исключение составляют автоматные подстановки: (1,2)(3,4),(1,3)(2,4),(1,4)(2,3).

5 6 7

Число состояний т

Рис.2. Зависимость числа входных сигналов от числа состояний универсальных перечислителей с системами образующих Д1-Д5

5 6 7

Число состояний т

Рис.З. Зависимость длин восстанавливающих последовательностей от числа состояний универсальных перечислителей с системами образующих Д1-Д5

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

Теорема 3.4.1. Групповой автомат А - (Х.Б.З) является универсальным перечислителем для семейства групповых автоматов {A¡}i : А1 = (Аг/,5,<5(,))

тогда и только тогда, когда (V/ е 1)(\/х е X,) е СА, где С?^ - группа автомата А.

Предложены методы построения всех универсальных перечислителей с определенным числом входных сигналов для заданного семейства автоматов (метод 3.4.1), построения универсального перечислителя с минимальным числом состояний для произвольного семейства групповых автоматов (метод 3.4.2) и для семейства групповых циклических автоматов (теорема 3.4.2), построения семейства автоматов с определенным числом входных сигналов, для которого заданный автомат является универсальным (метод 3.4.3).

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

мации, а именно метод построения восстанавливающей последовательности для заданного входного сигнала (метод 3.5.1). На входе метода с читается заданным групповой автомат А = (X.S.S), \Х\ = п, |5| = т с порождающими подстановками Sx,i = \,n, моделирующими текущее поведение системы; подстановка S\k (1 <h< n,S\h Ф 8Xh), моделирующая требуемое поведение системы при подаче входного сигнала xh. Выходом метода является последовательность входных символов th, порождающая после своего приложения структуру переходов внутренних состояний, соответствующую требуемому преобразованию, моделируемому подстановкой S'Xi, или вывод о невозможности реализации данного преобразования.

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

Как отдельный результат может рассматриваться разработанный комплекс проблемно-ориентированных программ GroupAutomata, предназначенный для работы с групповыми автоматами и реализующий основные методы теории универсальных автоматов, предложенные в "третьей главе диссертации, и содержащий 14 подпрограмм. GroupAutomata распространяется по лицензии BSD, вместе с библиотекой предоставляется подробное описание функций.

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

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

Рассматриваются четыре различных типа регистров, описываются принципы их функционирования. Каждый регистр представляет собой упорядоченную последовательность триггеров, число которых определяет его разрядность. Он может выполнять следующие логические операции над двоичными словами: прием и хранение слова, передачу слова в другой регистр, поразрядные логические операции, сдвиг слова влево или вправо на заданное число разрядов, преобразование последовательного кода слова в параллельный и обратно, установку регистра в начальное состояние. В зависимости от типа логической операции различают типы регистров: с последовательным приемом и параллельной выдачей информации - SIPO (serial-in parallel-out registers), с последовательным приемом и выдачей информации (сдвиговые регистры), регистры с параллельным приемом и последовательной выдачей информации PISO(parallel-in serial-out registers), регистры с параллельным приемом и выдачей информации (регистры памяти).

В качестве математической модели регистра рассматривается конечный детерминированный автомат вида А = (^,¿>,<5), где Х= {0,1}- множество входных сигналов, S — множество состояний, S.XxS—>S — функция переходов. Состояние регистра определяется набором состояний образующих его триггеров, каждое из которых, в свою очередь, может принимать одно из двух значений 0,1. Таким образом, ¿-разрядный регистр имеет 2к состояний, которые можно для простоты занумеровать натуральными числами S = (0,1, 2*-1}. Разрабатываются методы построения восстанавливающих последовательностей в предположении, что решается задача реализации требуемых поведений структурно неизбыточным объектом (т.е. без использования МУП). При этом под требуемым поведением понимается исправное поведение регистра.

В работе подробно изучается поведение регистров типа SIPO, осуществляющих сдвиг влево. Они занимают по своему целевому назначению промежуточное положение между сдвиговыми регистрами и регистрами памяти. Решив задачу построения восстанавливающих последовательностей для этого типа регистров, оказывается возможным решить ее и для сдвиговых регистров, и для регистров типа PISO, и для регистров памяти. Показано, что автоматные подстановки регистра данного типа имеют следующий вид:

д0 (s) = 2s = 2s + 2к = 2(5 + 2*"') = S0 (s + 2l~] )(mod 2*),

6X (s) = 2s + 1 = 25 + 1 + 2* = 2(5 + 2*"1 ) + ]=£, (j + 2*"' )(mod 2*).

Содержательный смысл полученных выражений (7) заключается в том, что следующее состояние регистра при подаче входных сигналов 0 и 1 совпадает для текущих внутренних состояний, значения которых отличаются на величину 2кл Для автоматных преобразований произвольного ¿-разрядного регистра это свойство назовем свойством симметричности. Это свойство важно при построении восстанавливающих последовательностей, т.к. позволит решение этой задачи свести к аналогичной задаче для систем без потери информации (метод 3.3.2). Кроме того, вид функций <50(i) и t5,(i) указывает на то, что они не могут быть получены друг из друга при помощи некоторой комбинации.

24

Показывается, что графы автоматных преобразований сигналов 0 и 1 изоморфны. Изоморфизм преобразований требуемого поведения указывает на их «одинаковость» при создании восстанавливающих последовательностей. Это свойство позволяет, изучив механизм построения восстанавливающих последовательностей для входного сигнала 0, относительно просто перенести полученные результаты как для входного сигнала 1, так и для произвольных сигналов регистров других типов. Таким образом, достаточно разработать метод построения восстанавливающих последовательностей для любого из входных сигналов регистра типа SIPO (сдвиг влево), например для нулевого, а затем модифицировать его.

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

Теорема 4.2.1. Если восстанавливающая последовательность íq для входного сигнала 0 произвольного ^-разрядного регистра существует, то при некоторых целых неотрицательных значениях чисел а0, ап она предста-вима в виде í0 =0°Ч0°\..10о"

Определение показателей степеней <з0, аа„ , и следовательно, конкретного вида восстанавливающей последовательности, связано с анализом функционального предназначения различных составляющих слова /0 с точки зрения их роли в синтезе преобразования S0 (5) = 2.y(mod 2*).

На основе этой теоремы, изученных свойств автоматных преобразований и метода, определяющего взаимовыразимость подстановок группового автомата, описаны следующие методы:

методы построения восстанавливающей последовательности для к-разрядного регистра типа SIPO (сдвиг влево и вправо) для преобразования, задающего текущий закон функционирования при подаче входного сигнала О (методы 4.2.1 и 4.2.3 соответственно);

методы построения восстанавливающей последовательности для к-разрядного регистра типа SIPO (сдвиг влево и вправо) для преобразования, задающего текущий закон функционирования при подаче входного сигнала 1 (методы 4.2.2 и 4.2.4 соответственно);

метод построения восстанавливающей последовательности для к-разрядного реверсного регистра (сдвиг влево) для преобразования, задающего текущий закон функционирования при подаче входного сигнала 0 (метод 4.2.5).

Работа методов продемонстрирована на примерах для двухразрядных регистров. В частности, для различных типов двухразрядных регистров в явном виде получены классы текущих поведений, для которых разрешима задача реализации требуемых поведений и соответствующие восстанавливающие последовательности, таблицы их длин. Например, в табл. 2 многообразие подстановок, реализующих текущее поведение двухразрядного регистра при подаче входного сигнала 0, разбито на шесть классов, для каждого класса указаны типы преобразований, входящих в него, и вид восстанавливающей последовательности.

Таблица 2

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

Вид преобразований, реализующих текущее поведение регистра при подаче входного сигнала 0 ае {0,1,2,3}, Ре {0,2}, у е {1,3}. Вид восстанавливающей последовательности

(а,0,а,2) 10

(2,0,у,1) 1000100

0,2,7,0) 10010

(7,2,7,0) 010

(а,2,0,1), (2,3, а,0) 100

(а,3,0,2) 10100

Для дискретных систем с памятью, построенных из регистров различных типов, исследуются вопросы синтеза универсальных перечислителей. Разрабатываемые методы представляют собой интерпретацию общих схем синтеза универсального перечислителя общего вида и универсального перечислителя с управляющим каналом. Для каждого из рассмотренных вариантов МУЛ предлагается метод построения восстанавливающих последовательностей. Вначале рассматриваются модули универсальных перечислителей, использующие в качестве модели универсальные перечислители с управляющим входным каналом, т.е. автоматы Ствида (4). Применение метода 3.3.2 к автомату Ст позволяет значительно уменьшить количество управляющих входных сигналов, однако приводит к увеличению длительности процесса реализации требуемого поведения. Затем строятся модули универсального перечислителя, основанные на модели универсального перечислителя общего вида 11т, функция переходов-выходов которого состоит из элементов минимального порождающего множества вида (3). Использование универсального перечислителя типа ит в качестве МУП обеспечивает минимальность числа входных сигналов при синтезе восстанавливающих последовательностей, однако приводит к увеличению длительности процесса реализации требуемого поведения. Для устранения этого недостатка при одновременном увеличении числа входных сигналов применяется универсальный перечислитель с расширенной системой образующих по сравнению с системой образующих автомата ит. Проведенный анализ взаимовлияния основных характеристик построенных универсальных перечислителей позволяет исследователю сделать обоснованный выбор варианта МУП, исходя из имеющихся у него средств и условий для проведения процедур реализации требуемого поведения. Разрабатываемые методы продемонстрированы на примере построения различных универсальных перечислителей для реверсивного двухразрядного регистра.

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

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

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

Основной принцип автоматного программирования - описание алгоритма моделью конечного автомата. Основным объектом автоматной программы является состояние. На этапе проектирования требуется явно определить все состояния (обычно их обозначают символами А, В, С и т.д.) и применять для их различения только одну многозначную управляющую переменную (например, переменную state символьного типа). Состояние автоматной программы - это группа строк этой программы, в которой ожидается локальное событие. Локальным событием в автоматной программе можно считать положительный результат (не нулевое значение) вычисления некоторого логического выражения. Локальное событие обычно обозначают символом Ху и отождествляют с буквой входного алфавита конечного автомата. В конкретном состоянии может ожидаться не одно, а несколько локальных событий, из которых наступает всегда только одно. После определения всех состояний программы необходимо явно определить и все возможные переходы между состояниями. Переходом в автоматной программе называется переход от текущего состояния, например, В, в новое состояние, например, С, при наступлении локального события ХВс, приписанного к состоянию В. При этом переменная состояния state='B' изменяется на state='C' и совершается последовательность действий на переходе YBc• Следует отметить, что в любой автоматной программе в начальном состоянии А не ожидается ни одно локальное событие и осуществляется безусловный переход в состояние В с выполнением действий Удв на этом переходе.

27

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

ного символа совершаются переходы и соответствующие действия на переходах, и явным заданием таблицы переходов автомата в виде двумерного массива. Данные способы задания автомата соответствуют двум основным технологиям автоматного программирования, так называемым 8\\ТТСН-технологии и IfTab]eSwitch-тexнoлoгии. В работе приводятся примеры автоматных программ, созданных по данным технологиям, на языке С.

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

Пример общей схемы автоматного алгоритма приведен на рис. 4.

Рис. 4. Общий вид автоматного алгоритма

Основным результатом главы являются различные схемы проектирования функционально избыточной программной системы на основе автоматной модели. Пусть программная система Р должна реализовывать набор п требуемых поведений. Следовательно, она должна представлять собой универсальный перечислитель для программных систем Р\, Рг.....Л» реализующих

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

Схема 5.3.1 представляет собой способ построения универсального перечислителя, для которого длины восстанавливающих последовательностей в общем случае больше 1. Его суть заключается в следующем. Для каждого из требуемых поведений Р\, Р2 Р„ разрабатывается автоматная модель, при

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

К преимуществам программ, разработанных в соответствии с данной схемой, можно отнести следующие их свойства: компактность кода (программа содержит реализацию только одного автомата), неизбыточность кода,

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

при выполнении программы.

Однако предложенная схема имеет и недостатки. Ее реализация является трудоемким процессом, т.к. разработчику программной системы необходимо не только спроектировать п схем автоматных программ, но решить нетривиальную задачу построения универсального перечислителя. Внесение изменений в данную программу, например добавление новой настройки и соответствующих восстанавливающих последовательностей требует изменения в общем случае кода нескольких состояний, т.о. данный подход реализует принцип параметрической адаптации.

В схемах 5.3.2 и 5.3.3 строится универсальный перечислитель, который представляет собой обычное объединение всех функций каждого из требуемых поведений Ри Рг,- -, Рп, т.е. длина восстанавливающей последовательности относительно любого входного символа любой из систем Р\, Рг, - Рп всегда равна 1 и восстанавливающая последовательность универсального перечислителя совпадает с данным входным символом. Реализация такого перечислителя возможна двумя способами.

В первом случае (схема 5.3.2) для каждой из систем Ри Рг,---, Р» разрабатывается автоматная модель, которая реализуется в виде отдельной функции Aj i~l,n.B главной программе в зависимости от настройки г на одно из требуемых поведений вызываются соответствующие автоматные функции. Основным достоинством данной схемы является простота ее реализации. Причем проектирование и реализация функций автоматов Aj i = l,n могут осуществляться независимо друг от друга разными разработчиками. Кроме того, код программы, построенной по данной схеме, может быть организован таким образом, чтобы количество настроек и имена функций (модулей), реализующих поведение системы при этих настройках, считывались из входных файлов, что позволяет при введении новой настройки обойтись без модификации главной программы. Таким образом, данный подход реализует прин-

цип композиционной адаптации. Однако программа, построенная таким образом, обладает серьезным недостатком — дублированием кода одинаковых состояний в разных функциях Л, г = 1, п.

Во втором случае (схема 5.3.3) реализуется один автомат-перечислитель, содержащий функции переходов для всех состояний систем с указанием настройки для их выполнения. Полученный таким образом алгоритм реализуется автоматной программой такого же вида, что и программа, полученная в результате применения схемы 5.3.1. Единственным формальным отличием является возможное наличие в состояниях автомата общих действий, выполняемых независимо от перехода (что ведет к уменьшению дублирования кода). Фактически программа, разработанная по схеме 5.3.3, будет содержать дополнительные переходы между состояниями в зависимости от настроек, т.е. на схеме автомата в общем случае будет большее количество дуг. Однако реализация дуги и реализация пометки на уже существующей дуге с точки зрения программного кода не представляют между собой различия, поэтому это свойство полученной схемы не является ее недостатком. Кроме того, в программе отсутствуют «искусственные» присвоения истинного значения входным сигналам, цель которых имитация подачи следующего символа восстанавливающей последовательности. Внесение изменений, а именно, добавление новой настройки, в программный код, разработанный таким образом, проще, чем модификация кода, созданного по схеме 5.3.1, так как не подразумевает проектирование восстанавливающих последовательностей и, следовательно, их реализацию.

Разработка модели автоматной программы по схеме 5.3.3 значительно менее трудоемка, чем разработка аналогичной программы по схеме 5.3.1, т.к. определение числа состояний универсального перечислителя и построение универсального перечислителя происходят формальным образом. Следовательно, использование схемы 5.3.3 имеет такие преимущества перед использованием схемы 5.3.1, как простота разработки и модификации программной системы, более ясная логика программы. Поэтому можно сделать вывод, что использование схемы 5.3.1 целесообразно только в том случае, когда действия на переходе при подаче входных сигналов х совпадают с последовательностями действий на переходах при подаче восстанавливающих последовательностей Ь.

Для каждой из предложенных схем проектирования функционально избыточной программной системы приведена структура автоматных программ, разработанных по данным схемам в соответствии с такими популярными технологиями автоматного программирования как Б^ТСН-технология и ИТаЫе8у/ксЬ-технология, продемонстрирована реализация данных схем на простом примере. Схема 5.3.3 использована при разработке АИС «Управление инфраструктурой научно-образовательной среды» по проекту «Работы по анализу и выбору базовых показателей, используемых в зарубежных странах для оценки использования и воздействия ИКТ на сферу образования, и разработке методик анализа данных, технологии сбора и об-

работки информации на основе выбранных показателей» (в рамках ФЦП «Электронная Россия» (2002-2010 годы)), а схема 5.3.2 - при разработке регионального образовательного портала по заказу министерства образования Саратовской области.

Приложение 1 содержит формальные доказательства большинства утверждений глав 1-3, приложение 2 описание и листинг комплекса программ (ЗгоирА1ота1а, разработанного в ходе исследования, приложение 3 -примеры функционально избыточных автоматных программ.

ЗАКЛЮЧЕНИЕ

В диссертационной работе предложены и исследованы математические модели и методы создания и эксплуатации функционально избыточных систем. В результате проведенных исследований получены следующие теоретические и практические результаты.

1. Сформулированы основные задачи математического моделирования функционально избыточных дискретных систем. Обосновано применение теории универсальных автоматов-перечислителей и теории полугрупп в качестве математического аппарата исследований. Доказана алгоритмическая неразрешимость поставленных задач для класса конечных детерминированных автоматов, тем самым определено основное направление развития исследований- создание частных методов решения поставленных задач для частных классов систем. В качестве таких классов выбраны класс систем, поведение которых описывается многочленами, класс систем без потери информации и различные типы регистров.

2. Определены основные характеристики универсального автомата-перечислителя как математической модели функционально избыточной системы: количество состояний и входных сигналов, длины восстанавливающих последовательностей и изучено их взаимовлияние. Предложены два типа модели функционально избыточной системы: универсальный автомат-перечислитель общего вида и универсальный автомат-перечислитель с управляющим каналом и показано, что схема их синтеза основана на определении элементов системы образующих полугруппы универсального автомата. Предложена общая схема реализации требуемых поведений функционально избыточной системы. Описаны состав средств реализации требуемых поведений, их функции, временные характеристики процесса функционирования избыточных систем. Рассмотрены различные типы систем с временной избыточностью, источники ее возникновения и возможные пути ее создания.

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

31

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

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

5. Разработан комплекс проблемно-ориентированных программ GroupAutomata, реализующий предложенные методы для работы с универсальными групповыми автоматами. Комплекс может быть использован любым исследователем в открытой свободно распространяемой системе GAP для решения задач определения функциональной избыточности, проектирования и реализации требуемых поведений функционально избыточной системы без потери информации.

6. Предложены методы построения восстанавливающих последовательностей для регистров различных типов, а именно регистров с последовательным приемом и параллельной выдачей информации, сдвиговых регистров, регистров с параллельным приемом и последовательной выдачей информации, регистров памяти. Для этого исследованы свойства автоматных преобразований, реализуемых регистрами при подаче входных сигналов 0 и 1. Получены в явном виде восстанавливающие последовательности для двухразрядного регистра с последовательным приемом и параллельной выдачей информации двухразрядного реверсного регистра. Описаны методы синтеза универсальных перечислителей для различных типов регистров.

7. Разработаны схемы проектирования автоматной модели функционально избыточной программной системы. Полученный результат демонстрирует возможности использования предложенных методов проектирования функциональной системы при решении такой актуальной задачи как разработка адаптивного программного обеспечения. Для каждой из схем проанализированы ее достоинства и недостатки, на языке С приведена структура автоматных программ, разработанных по данным схемам в соответствии со SWITCH-технологией и IfTableSwitch-технологией.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Монографии

1. Шульга Т.Э. Управление дискретными системами на основе функциональной избыточности/ А А. Сытник, Т.Э.Шульга. Саратов : Изд-во СГСЭУ, 2009. 196 с.

Статьи в журналах перечня ВАК

2. Шульга Т.Э. Числовые методы функционального восстановления поведения систем/ АА. Сытник, Т.Э. Шульга //Автоматика и телемеханика. 2003. Вып. 10. С. 123-130.

3. Шульга Т.Э. О восстановлении систем, моделируемых автоматами/ A.A. Сытник, Т.Э. Шульга // Интеллектуальные системы: научный журнал. М.: Изд-во МГУ, 2005. Т. 9. Вып. 1-4. С. 265- 279.

4. Шульга Т.Э. Задачи диагностирования и функционального восстановления поведения в теориях автоматов и нейронных сетей/ Т.Э. Шульга, A.C. Ковальская, Е.В. Сорокина// Вестник Саратовского государственного социально-экономического университета. 2006. №14(3). С.131-133.

5. Шульга Т.Э. Управление поведением мехатронных систем на основе свойств функциональной избыточности/ A.A. Сытник, Т.Э. Шульга, C.B. Папшев // Мехатроиика, автоматизация, управление. 2008. №12. С.41-44.

6. Шульга Т.Э. О классе систем, разрешимом относительно задачи управления поведением на основе свойств функциональной избыточности/ Т.Э. Шульга //Вестник Саратовского государственного

uтехнического университета. 2008. № 4, С.57-64.

7 Шульга Т.Э. Метод построения восстанавливающих последовательностей для систем без потери информации/ Т.Э. Шульга// Системы управления и информационные технологии. 2009. № 1.3(35). С. 407-411.

8. Шульга Т.Э. Математические модели потери устойчивости неоднородных цилиндрических оболочек от неравномерной радиальной нагрузки/ Э.В. Антоненко, Т.Э. Шульга // Известия Саратовского университета. Новая серая. Математика. Механика. Информатика. 2009. Т. 9. Вып, 3. С. 79-83.

9. Шульга Т.Э. Об управлении поведением регистров на основе свойств функциональной избыточности/ A.A. Сытник, Т.Э. Шульга// Вестник Саратовского государственного технического университета. 2009. №3 (40). С. 107-114.

Ю.Шульга Т.Э. Задачи синтеза и анализа теории управления поведением систем на основе свойств функциональной избыточности для класса групповых автоматов/ A.A. Сытник, Т.Э. Шульга, Н.С. Вагарина // Вестник Самарского государственного аэрокосмического университета. 2009. №4 (20). С. 248-255.

11.Шульга Т.Э. О длине восстанавливающих последовательностей для систем без потери информации/ Т.Э. Шульга// Вестник Самарского

государственного аэрокосмического университета. 2009. № 4. № 4 (20). С. 255-262.

12.Шульга Т.Э. Общая схема управления дискретными системами на основе функциональной избыточности/ Т.Э. Шульга//Современные технологии. Системный анализ. Моделирование. 2010. №1(25). С. 167-175.

Журнальные статьи и доклады на конференциях

13.Шульга Т.Э. Численные критерии восстановимости поведения КДА степенным многочленом/ Т.Э. Шульга// Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ «Колледж», 1997. Вып.1. С. 132-137.

14.Шульга Т.Э. Об одном подходе к построению автомата-перечислителя/ Н.И. Посохина, Т.Э. Шульга// Методы кибернетики и информационные технологии. Саратов: ГосУНЦ «Колледж», 1997. Вып.1. С. 113-115.

15.Шульга Т.Э. Об одном подходе к решению задачи синтеза автоматов-перечислителей/ A.A. Сытник, Н.И. Посохина, Т.Э. Шульга// Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ «Колледж», 1998. Вып.2. С. 103-116.

1 б.Шульга Т.Э. Необходимые условия моделируемости автоматных функций степенным многочленом/ Т.Э. Шульга// Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ «Колледж», 1998. Вып.2. С. 145-153.

17.Шульга Т.Э. О некоторых аспектах задачи восстановления поведения сложных систем/ Т.Э. Шульга // Новые информационные технологии: разработка и аспекты применения: тез. докл. Первой Всерос. науч. конф. молодых ученых и аспирантов. Таганрог: ТГУ, 1998. С. 150-151.

18.Шульга Т.Э. О возможностях восстановления поведения сложных систем/ Т.Э. Шульга // Проблемы совершенствования ракетных комплексов: сб. науч. тр. Всерос. военно-технической конф. Саратов: Изд-во Сарат. филиала ВАУ, 1999. С. 30-34.

19.Шульга Т.Э. О моделировании автоматных функций/ Т.Э. Шульга// Ломоносов 99: тез. докл. IV Междунар. конф. студентов и аспирантов по фундаментальным наукам. М.: Изд-во МГУ, 1999. С.255-256.

20.Шульга Т.Э. О возможностях восстановления поведения сложных систем/ Т.Э. Шульга// Актуальные проблемы военной науки и образования: сб. науч. докладов Академии военных наук. Саратов: Изд-во Сарат. филиала ВАУ, 2000. С. 231-233.

21.Shulga Т.Н. On Some Methods Of Discrete Systems Goal-Directed Behavior Generating/ A.A. Sytnik, N.I. Posohina, Т.Е. Shulga // The Fourth Conference of the SCI (Systemics, Cybernetics and Informatics). Orlando, Florida, USA,

2000. P.47-48.

22.Шульга Т.Э. Метод построения перечислимого множества автомата, моделируемого семейством многочленов/ Т.Э. Шульга // Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ «Колледж»,

2001. Вып.4. С. 148-156.

23.Шульга Т.Э. Проектирование отказоустойчивых дискретных систем на основе принципов функционального восстановления поведения/ А.А. Сытник, Т.Э. Шульга// Автоматизация проектирования дискретных систем: материалы Четвертой Междунар. конф.: в 3 т. Минск: Ин-т техн. кибернетики НАН Беларуси, 2001. Т. 3. С. 37-45.

24.Шульга Т.Э. Анализ и синтез универсального автомата-перечислителя/ А.А. Сытник, Т.Э. Шульга, А.Н. Кунявская// Тез. докл. Междунар. конф., посвященной памяти A.M. Богомолова. Саратов: Изд-во Сарат. ун-та, 2002. С.70-71.

25.Shulga Т.Е. Mathematical models of intellectual systems goal-directed behavior generating/ A.A. Sytnik, Т.Е. Shulga // V international congress on mathematical modeling: book of abstracts Dubna, 2002. Vol. II. P. 133-134.

26. Шульга Т.Э. О методе построения восстанавливающей последовательности для автомата, моделируемого семейством многочленов/ Т.Э. Шульга // Труды XXIV конф. молодых ученых. М.: Изд-во Моск. ун-та, 2002. С. 154-157.

27.Shulga Т.Е. Mathematical models of Discrete Systems Goal-Directed Behavior Generating/ A.A. Sytnik, Т.Е. Shulga// International Journal of Computing Anticipatory. Belgium. Published by CHAOS. 2003. Vol. 14. P.299-310.

28.Shulga Т.Е. Functional Renewal of Behavior of Systems: Numerical Methods/ A.A. Sytnik, Т.Е. Shulga// Automation and Remote Control. 2003. Vol. 64, № 10. P. 1620-1634.

29.Шульга Т.Э. О новых подходах к решению задачи синтеза универсального автомата/ Ю.О. Седина, Т.Э. Шульга// Теоретические проблемы информатики и ее приложений: межвуз.сб. Саратов: Изд-во Сарат. ун-та, 2004. Вып.6. С. 175-180.

30.Шульга Т.Э. Об универсальной перечислимости автоматов специального класса/ Т.Э. Шульга//Социально-экономическое развитие России: проблемы, поиски решения: сб. науч. тр. по итогам науч.-исслед. работы СГСЭУ в 2004 г.: в 2 ч. Саратов: Издат. центр СГСЭУ, 2005. 4.2. С. 115-116.

31.Шульга Т.Э. Об одном методе синтеза отказоустойчивых систем/ А.А. Сытник, Т.Э. Шульга//Информационные технологии в науке, производстве и социальной сфере: сб. науч. тр./ под ред. акад. Ю.В. Гуляева. Саратов: Научная книга, 2005. С.122-131.

32.Шульга Т.Э. Постановка задач диагностирования неисправности и функционального восстановления в теории нейронных сетей по аналогии с теорией конечных детерминированных автоматов/ Т.Э. Шульга, А.С. Ковальская //Математическое и информационное обеспечение экономической деятельности: альманах. Саратов: Издат. центр СГСЭУ, 2006. С. 81-86.

33.Шульга Т.Э. О методе решения задачи диагностирования нейронной сети/ Т.Э. Шульга, А.С. Ковальская// Автоматизация проектирования дискретных систем: материалы Шестой Междунар. конф. Минск: ОИПИ НАН Беларуси, 2007. С. 237-245.

Ю-2777®

34.Шульга Т.Э. Программные решения систем интеграции данных и корпоративной информации/ Т.Э. Шульга// Интернет и инновации: практические вопросы информационного обеспечения инновационной деятельности: материалы Междунар. науч.-практ. конф. Саратов: СГТУ,

2008. С.246-250.

35.Шульга Т.Э. Метод построения восстанавливающих последовательностей для систем без потери информации/ Т.Э. Шульга//Информационные технологии моделирования и управления. 2009. №2(54). С. 276-283.

36.Шульга Т.Э. Метод нахождения длины восстанавливающих последовательностей для систем без потери информации/ Т.Э. Шульга //Математические методы в технике и технологиях: сб. трудов XXII Междунар. науч. конф.: в 10 т. Псков: Изд-во Псков, гос. политех, ин-та,

2009. Т.2. С.70-73.

37.Шульга Т.Э. О длине группы автомата/ Т.Э. Шульга//Социально-экономическое развитие России: сб. науч. тр.: в 2 ч. Саратов: Издат. центр СГСЭУ, 2009. 4.1. С. 131-133.

38.Шульга Т.Э. Задачи управления функционально избыточными системами/ Т.Э. Шульга // Информатика: проблемы, методология, технологии: материалы X Междунар. науч.-метод. конф.: в 3 т. Воронеж: Изд-во ВГУ,

2010. Т.2. С. 283-284.

2010181653

Шульга Татьяна Эриковна МАТЕМАТИЧЕСКИЕ МОДЕЛИ ФУНКЦИОНАЛЬНО ИЗБЫТОЧНЫХ ДИСКРЕТНЫХ СИСТЕМ Автореферат

Корректор О.А. Панина

Подписано в печать Бум. офсет. Тираж 100 экз.

27.09.10 Усл. печ. л. 2,0

Заказ 308.

Формат 60x84 1/16 Уч.-изд. л. 2,0 Бесплатно

Саратовский государственный технический университет 410054, Саратов, Политехническая ул., 77 Отпечатано в Издательстве СГТУ. 410054, Саратов, Политехническая ул., 77

2010181653

Введение

ГЛАВА 1. Анализ моделей, методов и задач математического моделирования функционально избыточных дискретных систем

1.1. Введение

1.2. Общая характеристика математических моделей функционально избыточных дискретных систем

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

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

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

ГЛАВА 2. Математические модели функционально избыточных дискретных систем, допускающих числовое моделирование

2.1. Введение

2.2. Числовая модель дискретной системы

2.3. Исследование свойств числовой модели

2.4. Способы доопределения математических моделей для систем, не допускающих числовое моделирование

2.5. Задачи определения функциональной избыточности и проектирования для класса систем, допускающих числовое моделирование

2.6. Метод построения восстанавливающей последовательности для класса систем, допускающих числовое моделирование

ГЛАВА 3. Математические модели функционально избыточных систем без потери информации

3.1. Введение

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

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

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

3.5. Метод построения восстанавливающей последовательности для класса систем без потери информации

ГЛАВА 4. Математические модели функционально избыточных регистров различных типов

4.1. Введение

4.2. Методы построения восстанавливающих последовательностей для регистров различных типов

4.3. Задача проектирования функционально избыточных регистров различных типов

ГЛАВА 5. Проектирование функционально избыточной программной системы

5.1. Введение

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

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

Одним из факторов, определяющих эффективность использования сложных и, как следствие, дорогостоящих технических систем, является длительность их эксплуатации. В свою очередь, длительность эксплуатации определяется не только надежностью, но и способностью системы изменяться в соответствии с быстро меняющимися требованиями внешней среды. Поэтому современные технические средства должны обладать соответствующей функциональной гибкостью, возможностью изменения параметров и режимов работы, поддерживать определенные процедуры настройки. Данные требования принято называть требованиями адаптивности или адаптируемости. В русскоязычной научной литературе четкой дифференциации этих терминов нет. В английском языке слова «адаптивность» и «адаптируемость» имеют различные значения. Систему называют адаптивной (adaptive), если она автоматически меняет свое поведение при изменении внешних условий, т.е. меняются алгоритмы ее функционирования, но состав и структура остаются неизменными. Адаптируемая (adaptable) система - эта система, которая может быть изменена с помощью внешних воздействий, например, за счет изменения структуры. В данной диссертационной работе рассматриваются вопросы, связанные с разработкой и эксплуатацией адаптивных систем. Отметим, что требования адаптивности являются одними из основных требований не только к сложным техническим объектам и системам автоматического управления [1, 50, 102, 144], но и к современным программным [147] и социально-экономическим системам [41, 44, 51].

Адаптивность системы достигается наличием в ней некоторой избыточности. Для модификации поведения характерно использование двух основных типов избыточностей: структурной (аппаратной) и функциональной (временной) [101]. Структурная избыточность подразумевает введение в состав системы дополнительных резервных копий элементов, на которые может быть возложена задача реализации заданного функционирования при выходе из строя одной из основных частей или при необходимости модификации поведения системы. Функциональная избыточность предполагает возможность использовать свойства текущего закона функционирования для формирования на выходах требуемой совокупности реакций только за счет имеющегося в данный конкретный момент или искусственно создаваемого резерва времени (организация «повторного счета», повторный запуск логической операции и т.п. [62, 73, 112, 148]). При этом для формирования на выходе требуемой совокупности реакций на вход следует подавать специальные последовательности входных символов, которые будем называть восстанавливающими. Восстанавливающая последовательность - это последовательность входных символов, которая, будучи применима при любом текущем состоянии системы, в качестве последнего выходного символа даст требуемый выходной символ. Если возможно построить восстанавливающие последовательности для каждой требуемой реакции из некоторой заданной совокупности реакций, то будем говорить, что система обладает функциональной избыточностью относительно заданной совокупности требуемых поведений или что существует возможность реализации требуемых поведений на основе функциональной избыточности. Функциональная избыточность может выявляться в созданной системе с целью получения требуемых (отличных от текущих) реакций, а также целенаправленно создаваться на этапе проектирования системы, в том числе с целью восстановления ее поведения в случаях предполагаемых неисправностей [117, 120, 126].

Одним из первых авторов, подробно рассмотревшим понятие «адаптивность» в рамках теории систем автоматического управления, является Я.З. Цыпкин [143]. В его работе указывается, что адаптивность системы достигается за счет возможности управления ее поведением с целью получения некоторого спектра требуемых реакций. Формирование теории управления как точной научной дисциплины относится к середине XX века и на сегодняшний день имеет различные направления, активно развивающиеся как в нашей стране, так и за рубежом [5, 66]. Большой вклад в развитие этой теории внесли и представители отечественной школы технической диагностики, занимающиеся, в частности, проблемами отказоустойчивости [56, 57, 98, 101, 112, 117, 118]. Именно в их работах заложены основы теории управления с целью получения некоторого спектра требуемых поведений, однако основное внимание в них уделено аппаратной избыточности.

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

Основы математического моделирования дискретных систем, способных реализовать некоторый спектр поведений на основе функциональной избыточности, заложены в работах К.Шеннона, М.Минского, Дж. фон Неймо-на, предложивших различные модели универсального автомата (машины, устройства). Универсальный автомат - это автомат, способный моделировать, порождать, воспроизводить (соответственно по Шеннону, Минскому и фон Нейману) заданный спектр поведений или объектов. Возможность реализации заданного класса требуемых поведений системы означает, что автомат, описывающий текущее поведение, должен быть универсальным для автоматов, моделирующих требуемые поведения.

Изучение универсальных конечных автоматов осуществлялось Э.В. Евреиновым и И.В. Прангишвили [53], А.П. Горяшко [46], В.А. Мищенко [102], Э.А. Якубайтисом [181] и многими другими с целью построения универсальных и многофункциональных модулей. Однако, превалирующей в этих работах была идея о достижении универсальности за счет перенастройки структуры технического объекта. Для описания функционально избыточных систем A.A. Сытником введена модель универсального автомата-перечислителя, однако в его работах эта модель используется только для решения задачи восстановления системы после возникновения различного рода неисправностей на этапе эксплуатации системы[120, 121]. Модель универсального автомата-перечислителя исследовалась также Н.С. Вагариной, Н.И. Посохиной, К.П. Вахлаевой [34, 115,116,136] и другими для отдельных классов дискретных систем, однако эти исследования имеют чисто теоретический характер и не затрагивают вопросы создания и эксплуатации функционально избыточных систем.

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

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

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

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

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

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

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

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

- разработка и внедрение средств реализации требуемых поведений системы, которые должны находиться во взаимодействии со средствами диагностирования, осуществляющими выработку сигнала о необходимости настройки системы на требуемое поведение;

- разработка и применение процедур реализации требуемых поведений системы;

- оптимизация процедур реализации требуемых поведений системы и их применения.

В качестве математической модели систем дискретного типа в работе рассматривается конечный детерминированный автомат. Традиционно при описании и проектировании технических объектов используются автоматы-преобразователи, т.е. закон функционирования системы задается как совокупность преобразований входных последовательностей автомата в выходные. Данная точка зрения на автоматы выросла в серьезную научную дисциплину с большим числом работ, специфическими методами и своеобразной проблематикой [см., например, 2, 4, 26, 31, 35, 42, 46, 58, 61, 69, 93, 133, 141]. Однако решение задачи настройки системы на заданное поведение требует другого способа ее описания: в виде множества выходных последовательностей, которые способна генерировать система, и соответствующих им входных воздействий. Такое описание дают автоматы-перечислители, свойства которых еще недостаточно изучены. Среди последних работ, посвященных проблемам перечислимости в теории автоматов, следует отметить работы A.A. Сытника, Н.И.Посохиной, Н.С. Вагариной [105, 120, 121, 123].

В качестве основной математической модели функционально избыточной дискретной системы в работе рассматривается универсальный автомат-перечислитель. Именно в терминах теории универсальных автоматов-перечислителей в диссертации сформулированы основные задачи математического моделирования функционально избыточных дискретных систем:

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

- задача проектирования системы, обладающей функциональной избыточностью (задача синтеза универсального автомата-перечислителя);

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

- задача реализации требуемых поведений дискретной системы на основе функциональной избыточности (задача построения восстанавливающих последовательностей для универсального автомата-перечислителя);

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

Решение данного круга задач с точки зрения практики представляет значительные математические трудности. Одновременно поиск ответов на поставленные вопросы в рамках чисто математических рассуждений неперспективен в связи с их четко выраженным прикладным характером. Продемонстрируем справедливость данного утверждения на примере задачи построения восстанавливающих последовательностей.

Задача заключается в нахождении последовательности входных сигналов системы, при подаче которых вне зависимости от текущего состояния системы формируется требуемый выходной сигнал. Фактически это означает представление требуемого автоматного преобразования через произведение преобразований, реализуемых при текущем поведении системы. С точки зрения теории полугрупп эта задача сводится к задаче выразимости элемента полугруппы через элементы системы образующих этой полугруппы (проблема тождества). В алгебре известны системы образующих, в которых можно выразить любой элемент симметрической полугруппы (т. е. любое автоматное преобразование). Однако с точки зрения построения восстанавливающих последовательностей, интересна не только возможность самого выражения, но и его способ, количество элементов в этом выражении (длина восстанавливающей последовательности).

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

В работе A.A. Сытника была показана алгоритмическая неразрешимость задачи синтеза универсального автомата-перечислителя относительно произвольного семейства [120]. На основании этого факта, а также неразрешимости проблемы тождества в теории полугрупп в работе доказывается алгоритмическая неразрешимость поставленных задач для произвольного класса дискретных систем. Этот результат определяет основное направление исследований - решение задач математического моделирования функционально избыточных систем для отдельных классов дискретных систем.

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

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

Одним из важных последствий отказа от преобразовательной формы описания поведения является необходимость задания временного графика снятия правильных реакций на выходе системы. Если момент появления требуемого выходного сигнала не согласуется с изначальным режимом работы системы, то необходимо осуществить их «состыковку». Осуществить данное действие можно только при наличии в системе некоторого временного резерва или его искусственного создания. В диссертации рассматриваются основные источники возникновения временной избыточности и предлагается формальный способ описания временных характеристик процесса реализации требуемых поведений.

Для определения методов решения задач математического моделирования функционально избыточных систем для частных классов необходимо выработать некоторые общие подходы к решению задач проектирования систем с функциональной избыточностью и определения функциональной избыточности системы. Данные задачи решаются как задачи синтеза и анализа универсальных автоматов-перечислителей. При решении задачи синтеза универсального перечислителя предлагаются две общие схемы:

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

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

В соответствии с данными схемами могут быть построены различные универсальные автоматы-перечислители. Выбор того или иного из них в качестве основы модуля универсального перечислителя определяется его основными характеристиками (объемом памяти, длительностью процесса реализации требуемых поведений, количеством входных сигналов), взаимовлияние которых оценено в диссертации.

В ходе выполнения работы были использованы методы системного и комбинаторного анализа, теории автоматов, теории полугрупп, теории чисел. Исследование основывается на формальных доказательствах с содержательной интерпретацией постановок задач и полученных результатов.

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

В диссертации получены следующие результаты, характеризующиеся научной новизной.

1. Сформулированы основные задачи математического моделирования функционально избыточных дискретных систем на содержательном уровне и в терминах выбранной математической модели (универсального автомата-перечислителя).

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

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

4. Исследована математическая модель систем, допускающих так называемое числовое моделирование - автоматы, функции переходов которых представлены многочленами специального вида в кольце вычетов по модулю m (где m - число состояний системы). На основе теории чисел при исследовании разрешимости определенной системы сравнений по модулю m получены различные условия моделируемости автоматной подстановки многочленом. На основе свойств полугруппы, порождаемой рассматриваемыми многочленами, решены задачи анализа и синтеза универсального автомата-перечислителя, предложены критерии универсальности, метод построения восстанавливающих последовательностей.

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

6. Разработан комплекс программ GroupAutomata [166] в открытой свободно распространяемой системе GAP (система компьютерной алгебры, представляющая всемирный научный проект, объединяющий специалистов в области алгебры, теории чисел, математической логики и т.д.) [192], реализующий все предложенные методы для работы с универсальными групповыми автоматами.

7. Исследована автоматная модель регистров различных типов, а именно регистров с последовательным приемом и параллельной выдачей информации, сдвиговых регистров, регистров с параллельным приемом и последовательной выдачей информации, регистров памяти. На основе свойств преобразований, реализуемых регистрами с последовательным приемом и параллельной выдачей информации при подаче входных сигналов 0 и 1, разработаны методы построения восстанавливающих последовательностей для данного класса объектов, методы синтеза универсальных перечислителей.

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

Работа представлена на 360 страницах, состоит из оглавления, введения, 5 глав, заключения, списка литературы и трех приложений.

В главе 1 проводится анализ математических моделей функционально избыточных дискретных систем, формулируются основные задачи математического моделирования функционально избыточных дискретных систем, доказывается их алгоритмическая неразрешимость для класса дискретных систем, определяются основные направления исследований. Кроме того, предлагается общая схема реализации требуемых поведений системы на основе функциональной избыточности, описываются состав и функции средств реализации требуемых поведений, изучаются общие подходы к решению поставленных задач математического моделирования функционально избыточных дискретных систем.

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

В главе 3 рассматриваются системы без потери информации, т.е. системы, которые допускают моделирование так называемыми групповыми автоматами. Функции переходов групповых автоматов представлены перестановками на множестве внутренних состояний, что дает возможность использовать мощный алгебраический аппарат теории групп перестановок при решении задач разрабатываемой теории. Для класса систем без потери информации решаются задачи синтеза и анализа универсальных перечислителей. Предлагается универсальные перечислители для класса групповых автоматов, которые оцениваются с точки зрения длин восстанавливающих последовательностей. Также предлагается метод построения восстанавливающих последовательностей для произвольного группового автомата.

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

Глава 5 посвящена демонстрации возможностей использования методов проектирования функционально избыточных систем при решении такой актуальной задачи как разработка адаптивного программного обеспечения [49, 118, 159, 160]. Адаптивные программы это программы, в которые заложена такая дополнительная функциональность, которая позволяет им реагировать на изменившиеся требования со стороны окружающей среды без перепрограммирования. При разработке адаптивного программного обеспечения оказывается возможным применение методов синтеза универсального перечислителя в том случае, если программная система спроектирована на основе принципов автоматного программирования. В главе предлагаются различные схемы проектирования автоматной модели функционально избыточной программной системы. Для каждой из схем проанализированы ее достоинства и недостатки, приведена структура автоматных программ, разработанных по данным схемам в соответствии с популярными технологиями автоматного программирования.

Каждая глава диссертации начинается введением, в котором кратко перечисляются основные, полученные в ней, результаты и указывается их роль в общей схеме проводимых рассуждений. Применение основных методов, предлагаемых в диссертации, продемонстрировано на примерах. Формальные доказательства большинства утверждений вынесены за рамки основного текста и помещены в приложение 1. Приложение 2 содержит описание и листинг комплекса программа ОгоирА1;ота1а, разработанного в ходе исследования, приложение 3 - примеры функционально избыточных автоматных программ. В заключении работы приводятся основные результаты, полученные в диссертации.

ЗАКЛЮЧЕНИЕ

В диссертационной работе предложены и исследованы математические модели и методы создания и эксплуатации функционально избыточных систем. В результате проведенных исследований получены следующие теоретические и практические результаты.

1. Сформулированы основные задачи математического моделирования функционально избыточных дискретных систем. Обосновано применение теории универсальных автоматов-перечислителей и теории полугрупп в качестве математического аппарата исследований. Доказана алгоритмическая неразрешимость поставленных задач для класса конечных детерминированных автоматов, тем самым определено основное направление развития исследований- создание частных методов решения поставленных задач для частных классов систем. В качестве таких классов выбраны класс систем, поведение которых описывается многочленами, класс систем без потери информации и различные типы регистров.

2. Определены основные характеристики универсального автомата-перечислителя как математической модели функционально избыточной системы: количество состояний и входных сигналов, длины восстанавливающих последовательностей и изучено их взаимовлияние. Предложены два типа модели функционально избыточной системы: универсальный автомат-перечислитель общего вида и универсальный автомат-перечислитель с управляющим каналом и показано, что схема их синтеза основана на определении элементов системы образующих полугруппы универсального автомата. Предложена общая схема реализации требуемых поведений функционально избыточной системы. Описаны состав средств реализации требуемых поведений, их функции, временные характеристики процесса функционирования избыточных систем. Рассмотрены различные типы систем с временной избыточностью, источники ее возникновения и возможные пути ее создания.

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

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

5. Разработан комплекс проблемно-ориентированных программ GroupAutomata, реализующий предложенные методы для работы с универсальными групповыми автоматами. Комплекс может быть использован любым исследователем в открытой свободно распространяемой системе GAP для решения задач определения функциональной избыточности, проектирования и реализации требуемых поведений функционально избыточной системы без потери информации.

6. Предложены методы построения восстанавливающих последовательностей для регистров различных типов, а именно регистров с последовательным приемом и параллельной выдачей информации, сдвиговых регистров, регистров с параллельным приемом и последовательной выдачей информации, регистров памяти. Для этого исследованы свойства автоматных преобразований, реализуемых регистрами при подаче входных сигналов 0 и 1. Получены в явном виде восстанавливающие последовательности для двухразрядного регистра с последовательным приемом и параллельной выдачей информации двухразрядного реверсного регистра. Описаны методы синтеза универсальных перечислителей для различных типов регистров.

7. Разработаны схемы проектирования автоматной модели функционально избыточной программной системы. Полученный результат демонстрирует возможности использования предложенных методов проектирования функциональной системы при решении такой актуальной задачи как разработка адаптивного программного обеспечения. Для каждой из схем проанализированы ее достоинства и недостатки, на языке С приведена структура автоматных программ, разработанных по данным схемам в соответствии со БШТСН-технологией и иЕТаЬ1е8\уйс11-технологией.

1. Автоматизация производства и промышленная электроника / под ред. А.И. Берга, В.А. Трапезникова. М.: Советская энциклопедия, 1962. Т. 1. 424 с.

2. Автоматы: сб. статей / под ред. К. Шеннона. М.: Иностранная литература, 1956. 403с.

3. Айзерленд К, Роузен М. Классическое введение в современную теорию чисел. М.: Мир, 1987. 415 с.

4. Айзерман М.А. и др. Логика. Автоматы. Алгоритмы. М.: Физматгиз, 1963. 140 с.

5. Айзерман М.А. Краткий очерк становления и развития классической теории регулирования и управления // Автоматика и телемеханика. 1993. №7. С. 6-18.

6. Айзерман М.А., Алескеров Ф.Т. Выбор вариантов. Основы теории. М.: Наука, 1990. 236 с.

7. Алгебраическая теория автоматов, языков, полугрупп: сб. статей / под ред. М. Арбиба. М.: Статистика, 1975. 335 с.

8. Алешин C.B. О базисах в группах автоматных подстановок //Дискретный анализ. Новосибирск, 1970. Вып. 7. С. 3-8.

9. Алешин C.B. Свободная группа конечных автоматов // Вестник МГУ. Сер. 1. Мат., мех. 1983. Вып. 4. С. 12-14.

10. Ахо А., Сети В. Ульман Дж. Компиляторы: принципы, технологии и инструменты. М.: Издательский дом «Вильяме», 2003. 786 с.

11. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: МИР, 1978. — Т. 1. — 612 с.

12. Байцер Б. Архитектура вычислительных комплексов. Том 1. М.: Мир. -1974.

13. Баранов С.И. Синтез микропрограммных автоматов. JL: Энергия. 1979.

14. Бардзинь Я.М., Калниньш Я.Я. Универсальный автомат с переменной структурой // Автоматика и вычислительная техника. 1974. №2. С. 9-18.

15. Беллман Р. Процессы регулирования с адаптацией. М.: Наука, 1964. 359 с.

16. Богомолов A.M. и др. Эксперименты с автоматами. Киев: Наукова Думка, 1973. 144 с.

17. Богомолов A.M., Грунский И.С., Сперанский Д.В. Контроль и преобразование дискретных автоматов. Киев: Наукова Думка, 1975. 174 с.

18. Богомолов A.M., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во СГУ, 1986. 240 с.

19. Богомолов A.M., Сытник A.A. Классы эквивалентности полугруппы преобразований конечного автомата // Методы и системы технической диагностики. 1984. № 3. С. 3-12.

20. Богомолов A.M., Сытник A.A. Универсальные конечные автоматы/ Доклады АН СССР. 1987. Т. 294. №3. С. 525-528.

21. Богомолов A.M., Твердохлебов В.А. Диагностика сложных систем. Киев: Наукова Думка, 1974. 128 с.

22. Богомолов A.M., Твердохлебов В.А. Целенаправленное поведение автоматов. Киев: Наукова Думка, 1975. 123 с.

23. Боревич З.И., Шафаревич И.Р. Теория чисел. М.: Наука, 1985. 451 с.

24. Брауэр В. Введение в теорию конечных автоматов. М.: Радио и связь, 1987. 392 с.

25. Брыль В.Н. Опыт разработки и внедрения информационной системы автоматизации управления производством// «Производство электроники», №5, 2007 г., «САПР и графика», №12, 2007 г.

26. Буевич В.А. Построение универсальной о.-д. функции с двумя переменными // Проблемы кибернетики. 1965. № 15. С. 249-252.

27. Бусленко Н.П. Моделирование сложных систем. М.: Наука, 1978. 399 с.

28. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. М.: "Изд-во Бином", СПб: "Невскийдиалект". 1998.

29. Буч Г., Рамбо Д., Джекобсон А. Язык UML. Руководство пользователя. М.: ДМК.-2000.

30. Вагнер В.В. Теория полугрупп и ее приложение. Саратов: Изд-во СГУ, 1965. С. 3-179.

31. Ван дер Варден Б.Л. Алгебра. М.: Наука, 1979. 623 с.

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

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

34. ВахлаеваКЛ. Применение управляющих функций для настройки системы автоматов на заданное поведение в перечислительной форме//Теоретические проблемы информатики и её приложений: Сб. науч. тр. -Саратов: Изд-во Сарат. ун-та, 2004. Вып. 6. С. 61-67.

35. Виноградов ИМ. Основы теории чисел. М.: Наука, 1981. 176 с.

36. Волкова В.Н., Денисов A.A. Основы теории систем и системного анализа. СПб.: Изд-во СПбГТУ, 1997. 510 с.

37. Гаврилов М.А., Девятков В.В., Пупырев В.И. Логическое проектирование дискретных автоматов. М.: Наука, 1977. 352 с.

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

39. Глухое М.М. О числовых параметрах, связанных с заданием конечных групп системами образующих / труды по дискретной математике М.: ТВП, 1997. Т 1. С. 43-65.

40. Глухое М.М., Елизаров В.П., Нечаев A.A. Алгебра: учебник в 2-х томах. М.: Гелиос АРВ, 2003. Т. 2. 416 с.

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

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

43. Глушков В.М., Капитонова Ю.В., Летичевский A.A. Теоретические основы проектирования дискретных систем // Кибернетика. 1977. №6. С. 5-20.

44. Глушков В.М., Цейтлин Г.Е., Ющенко E.JT. Алгебра, языки, программирование. Киев: Наукова Думка, 1974. 328 с.

45. Гороховский С. С., Рысцов И.К. Об изоморфизме графов отображений // Кибернетика. 1982. № 6. С. 45-52.

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

47. Грант Р. Современный стратегический анализ. СПб.: Питер, 2008. 210 с.

48. Григорчук Р.И, Некрашевич В.В., Сущанский В.И. Динамические системы, автоматы и бесконечные группы / труды Математического института им. В.А. Стеклова. М.: Наука, 2000. Т. 231. С. 134-214.

49. Гурьянов В.И. Адаптивная программная система как фабрика приложений // Материалы VI научно-практической конференции «Проблемы информатизации социальных систем: региональный аспект». Чебоксары: ГОУ ВПО ЧГПУ, 2008. - С. 253-254.

50. Дискретная математика и математические вопросы кибернетики / под ред. C.B. Яблонского и О.Б. Лупанова. М.: Наука, 1979. 311 с.

51. Долгов А.П. Адаптивность свойств и параметров систем управления запасами к требованиям логистического менеджмента. СПб.: Новый век, 2001. 244 с.

52. Драгалин А.Г. Математический интуиционизм. Введение в теорию доказательств. М.: Наука, 1979. 256 с.

53. Евреинов Э.В., Прангишвили КВ. Цифровые автоматы с настраиваемой структурой. М.: Энергия, 1974. 240 с.

54. Ершов Ю.Л. Математическая логика. М.: Наука, 1979. 380 с.

55. Заде Л. Общая теория систем. М.: Мир, 1966.

56. Зыков А.А. Основы теории графов. М.: Наука, 1987. 381 с.

57. Иванов Ю.И, Югай В.Л. Микропроцессорные устройства систем управления. Таганрог: Изд-во ТРТУ, 2005. 133 с.

58. Ищенко А.А. Межорганизационный электронный бизнес в России:особенности создания, эволюция развития и выгоды использования. 2004. №1. С. 81-91.

59. Ищенко А. А. Современные тенденции управления межорганизационным электронным бизнесом в России. М.: ВИНИТИ, 2004. 224 с.

60. Казначеев В.И. Диагностика неисправностей цифровых автоматов. М.: Сов. Радио, 1975. 256 с.

61. Кальман Р., Фальб П., Арбиб М. Очерки по математической теории систем. М.: Мир, 1971.400 с.

62. Капитонова Ю.В. Об изоморфизме абстрактных автоматов // Кибернетика. 1965. № 4,5.

63. Каравай М.Ф. Математические основы отказоустойчивости / материалы VII Всесоюзного совещания по технической диагностике и отказоустойчивости. Саратов: Изд-во Сарат. ун-та. 1990. №1. С. 3-8.

64. Каравай М. Ф., Согомонян Е. С. Анализ надежностных характеристик самопроверяемых избыточных структур // Автоматика и телемеханика. 1979. № 8. С. 105-119.

65. Карпов Ю.Г. Теория автоматов. СПб.: Питер, 2003. 208 с.

66. Кейслер Г., Чей Ч. Теория моделей. М.: Мир, 1977. 614 с.

67. Клир Дж. Системология. Автоматизация решения системных задач. М.: Радио и связь, 1990. 539 с.

68. Кобринский Н.Е., Трахтенброт Б.А. Введение в теорию конечных автоматов. М.: Физматгиз, 1962. 404 с.

69. Коваленко А.Е., Гула В.В. Отказоустойчивые микропроцессорные системы. Киев: Техника, 1986. 149 с.

70. Кон 77. Универсальная алгебра. М.: Мир, 1968. 352 с.

71. Корноушенко Е.К. Обобщенная постановка задачи о проверке правильности функционирования конечного автомата // Техническая кибернетика. Известия АН СССР. 1977. № 2. С. 109-115.

72. Кострикин А.И. Введение в алгебру. М.: Наука, 1977. 495 с.

73. Красовский A.A. Развитие и становление современной теорииуправления: синергетика и проблемы теории управления / под ред. A.A. Колесникова. М.: ФИЗМАТЛИТ, 2004. С. 13-35.

74. Кратко М.И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов /доклады АН СССР. 1964. Т. 155. № I. С. 35-37.

75. Кристофпдес Н. Теория графов. М.: Мир, 1978. 432 с.

76. Кудрявцев В.Б., Алешин С.В, Подколзин A.C. Введение в теорию автоматов. М.: Наука, 1985. 319 с.

77. Кузин JI.T. Основы кибернетики. М.: Энергия, 1974. 584 с.

78. Кузнецов Б.П. Последовательно-событийные автоматы //Приборы и системы. Управление, контроль, диагностика, 2001. № 5.

79. Кузнецов Б.П. Психология автоматного программирования BYTE Россия, 2000, №11.

80. Кузнецов О.П. Сети из языков// Автоматика и телемеханика. 1980. №6. С. 152-161.

81. Кузнецов О.П. Адельсон-Вельркий Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. 480 с.

82. Кун С. Матричные процессоры БИС. М.: Мир, 1991. 672 с.

83. Курош А.Г. Курс высшей алгебры. М.: Наука, 1975. 345 с.

84. Курош А.Г. Теория групп. М.: Наука, 1967. 648 с.

85. Кушников В.А., Резчиков А.Ф., Цвиркун А.Д. Управление в человеко-машинных системах с автоматизированной процедурой коррекцией целей // Автоматика и телемеханика. 1998. № 7.

86. Лазарев В.Г., Пить Е.И. Синтез управляющих автоматов. М.: Энергоатомиздат, 1989. 328 с.

87. ЛарьерЖ.Л. Системы искусственного интеллекта. М.: Мир, 1991. 568 с.

88. Ленг С. Алгебра. М.: Мир, 1968. 563 с.

89. Липаев В.В. Программно-технологическая безопасность информационных систем. М.: МИФИ, 1997. - 144 с.

90. Лупанов О.Б. О синтезе некоторых классов управляющих систем //

91. Проблемы кибернетики. 1963. Вып. 10. С. 53-97.

92. Любченко B.C. От машины Тьюринга к машине Мили. «Мир ПК», № 8/02

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

94. Макаров В. О порядках элементов группы автоматных перестановок // Вестник МГУ. Сер. 1. Мат., мех. 1991. Вып. 4. С.86-87.

95. Малышенко Ю.В., Чипулис В.П., Шаршунов С.Г. Автоматизация диагностирования электронных устройств. М.: Энергоатомиздат, 1986. 216 с.

96. Мальцев А.И. Алгебраические системы. М.: Наука, 1970. 392 с.

97. Марченков С. С. О числе максимальных подгрупп в группах автоматных подстановок // Дискретный анализ и исследование операций. Сер. 1. 2004. Т. 11. №2. С. 73-79.

98. Матиясевич Ю.В. Диофантовы множества // Успехи математических наук. 1972. Вып. 5. С. 185-222.

99. Медведев Ю.Т. О классе событий, допускающих представление в конченом автомате // Автоматы: пер. с англ. М., 1956. С.385-401.

100. Мелихов А.Н. и др. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. 294 с.

101. Мендельсон Э. Введение в математическую логику. М.: Наука, 1971. 320 с.

102. Месарович М., Такахара Я. Общая теория систем: математические основы. М.: Мир. 1978. 256 с.

103. Многофункциональные автоматы и элементная база цифровых ЭВМ / под ред. В.А.Мищенко. М.: Радио и связь, 1981. 240 с.

104. Моисеев H.H. Математические задачи системного анализа М.: Наука, 1981. 488 с.

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

106. Новиков П. С. Конструктивная математическая логика с точки зренияклассической. M.: Наука, 1977. 323 с.

107. Опадчий Ю.Ф., Глудкин О.П., Гуров A.M. Аналоговая и цифровая электроника. М.: Горячая линия Телеком, Радио и связь, 2005. 768 с.

108. Ope О. Приглашение в теорию чисел. М.: Наука, 1980. 126 с.

109. Основы технической диагностики / под ред. П.П. Пархоменко. М.: Энергия, 1976. Ч. I. 464 с.

110. Парнзек Б., Шварц С. О мультипликативной полугруппе классов вычетов по модулю m // Математика. 1960. №4. С. 26.

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

112. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики, оптимизации алгоритмов диагностирования, аппаратурные средства. М.: Энегоиздат, 1981. 320 с.

113. Первозванский A.A. Курс теории автоматического управления. М.: Наука / гл. ред. физ-мат. лит. 1986. 616 с.

114. Пнкар С. О базисах симметрической группы // Кибернетический сборник. 1965. Вып. I. С. 7-34.

115. Полосуев A.M. О некоторых теоретико-числовых функциях. М.: Знание, 1972. 30 с.

116. Посохина Н.И. Об одном подходе к решению задачи синтеза автоматов-перечислителей // Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ «Колледж», 1997. Вып. 1. С. 101-109

117. Посохина H.H., Шулъга Т.Э. Об одном подходе к построению автомата-перечислителя // Методы кибернетики и информационные технологии. Саратов: ГосУНЦ «Колледж», 1997. Вып. 1. С. 113-115.

118. Проскуряков КВ. Числа и многочлены. М.: Просвещение, 1965. 282 с.

119. Рассел С., Норвиг П. Искусственный интеллект: современный подход (AIMA) = Artificial Intelligence: A Modern Approach (AIMA). — 2-е изд. — M.: «Вильяме», 2007. — С. 1424.

120. Риордан Дж. Введение в комбинаторный анализ. М.: Иностранная литература, 1963. 287 с.

121. Робинсон А. Введение в теорию моделей и математику алгебры. М.: Наука, 1967. 376 с.

122. Романкевич A.M. и др. Структурно-временная избыточность в управляющих схемах. Киев: Вища школа. 1979. 153 с.

123. Савельев П.В., Коняхин В.В. Функционально-логическое проектирование БИС. М.: Высшая школа, 1990. 156 с.

124. Савченко Ю.Г. Цифровые устройства, нечувствительные к неисправностям элементов. М.: Советское радио, 1977. 176 с.

125. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1988. 384 с.

126. Седина Ю.О., Шулъга Т.Э. О новых подходах к решению задачи синтеза универсального автомата // Теоретические проблемы информатики и ее приложений: межвузовский сборник. Саратов: Изд-во Сарат. ун-та, 2004. Вып.6. С. 175-180.

127. Серпиский В. О решении уравнений в целых числах. М.: Государственное издательство физико-математической литературы, 1961. 88 с.

128. Слисенко А. О. Сложные задачи теории вычислений // Успехи математических наук. 1981. Вып. 6. С. 21-104.

129. Согомонян Е.С. Отказоустойчивые избыточные структуры // Автоматика и телемеханика. 1986. № 10. С. 135-143.

130. Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы. М.: Радио и связь, 1989. 207 с.

131. Срибнер Л.А. Программируемые устройства автоматики. К.: Техшка. 1982.

132. Строгонов Р.П. Управляющие машины и их применение. М.: Высшая школа, 1978. 264 с.

133. Сытник A.A. Восстановление поведения сложных систем. Саратов: Изд-во СГУ, 1992. 192 с.

134. Сытник A.A. Перечислимость при восстановлении поведения автоматов:доклады РАН. 1993. Т. 238. С. 25-26.

135. Сытник A.A. Синтез универсальных автоматов // Методы и системы технической диагностики. 1987. № 7. С. 12-23.

136. Сытник A.A., Вагарина Н.С. Модели автоматов-перечислителей при проектировании отказоустойчивых дискретных систем: материалы V международной конференции «Автоматизация проектирования дискретных систем». Минск: ОИПИ HAH Беларуси, 2004. Т. 1. С. 79-86.

137. Сытник A.A., Посохина Н.И., Шулъга Т.Э. Об одном подходе к решению задачи синтеза автоматов-перечислителей // Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ «Колледж», 1998. Вып. 2. С. 103-116.

138. Сытник A.A., Шулъга Т.Э. О восстановлении систем, моделируемых автоматами // Интеллектуальные системы. Научный журнал. М.: Изд-во МГУ, 2005. Т. 9. Вып. 1-4. С. 265-279.

139. Сытник A.A., Шулъга Т.Э. Об одном методе синтеза отказоустойчивых систем // Информационные технологии в науке, производстве и социальной сфере: сб. науч. тр.; под ред. Ю.В. Гуляева. Саратов: Изд-во «Научная книга», 2005. С. 122-131.

140. Сытник A.A., Шулъга Т.Э. Числовые методы функционального восстановления поведения систем // Автоматика и телемеханика. 2003. Вып. 10. С.123-130.

141. Сытник A.A., Шулъга Т.Э., Кунявская А.Н. Анализ и синтезуниверсального-автомата перечислителя: тезисы докладов международной конференции, посвященной памяти A.M. Богомолова Саратов: изд-во Саратов, ун-та. 2002. С.70-71.

142. Сытпик А.А., Шулъга Т.Э., Папшев C.B. Управление поведением меха-тронных систем на основе свойств функциональной избыточности // Мехатроника, автоматизация, управление. 2008. №12. С. 41-44.

143. Твердохлебов В.А. Логические эксперименты с автоматами. Саратов: Изд-во СГУ, 1988. 184 с.

144. Тоценко В.Г. Структурный синтез на сдвиговых регистрах заданной длины автоматов Мура со встроенными схемами контроля //Автоматика и телемеханика. 1973. № 12. С. 127-133.

145. Трахтенброт Б.А., Бардзинъ Я.М. Конечные автоматы. Поведение и синтез. М.: Наука, 1970. 400 с.

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

147. Феррари Д. Оценка производительности вычислительных систем. М.: Мир, 1981. 376 с.

148. Фрумкин М.А. Алгоритмы решения систем линейных уравнений в целых числах // Исследования по дискретной оптимизации. М.: Наука, 1976. С. 97-127.

149. Функционально-ориентированные процессоры / под ред. В.Н. Смолова. Л.: Машиностроение, 1988. 224 с.

150. Харари Ф., Паш ер Э. Перечисление графов. М.: Мир, 1977. 324 с.

151. Хоредж Ф. Преобразования, определяемые конечными автоматами // Проблемы кибернетики. 1963. Вып. 3. С. 23-26.

152. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. 516 с.

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

154. Цифровая вычислительная техника / под ред. Э.В. Евреинова. М.: Радиои связь, 1991. 464 с.

155. Цыпкин Я.З. Адаптация и обучение в автоматических системах. М.: Наука, 1968. 399 с.

156. Цыпкин Я.З. Основы теории автоматических систем. М.: Наука, 1977. 560 с.

157. Чаканъ Б. Герег Ф.О. О группе автоматных подстановок // Кибернетика. 1965. Вып. 5. С. 50-53.

158. Чегис И.А., Яблонский C.B. Логические способы контроля электрических схем / труды математического института им. В.А. Стеклова. 1958. Т. 51. С. 226-269.

159. Ченг Б., Саджади С., Маккинли Ф., Кастен Э. Композиционная адаптация программ Открытые системы. 2004. Вып. 9 // http://www.osp.ru/os/2004/09/184557/ (дата обращения 14.10.2009)

160. Черняк Л. Адаптируемость и адаптивность // Открытые системы. 2004. Вып. 9 // http://www.osp.ru/os/2004/09/184560/ (дата обращения 14.10.2009)

161. Шагаев КВ. Определение неисправности аппаратуры программными средствами восстановления вычислительного процесса //Автоматика и телемеханика. 1990. №3. С. 151-161.

162. Шалыто А., Туккелъ Н. Программирование с явным выделением состояний// "Мир ПК", 2001. №8, С. 116-121; №9, С.132-138.

163. Шалыто A.A. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука. 1998.

164. Шалыто A.A., Туккелъ Н.И. Switch-технология — автоматный подход к созданию программного обеспечения «реактивных» систем// Программирование, 2001. №5, С.45—62.

165. Шапошников И.Г. О некоторых системах образующих симметрической и знакопеременной групп, допускающих простую программную реализацию // Дискретная математика. М.: Наука, 2004. Т. 16. Вып 1. С. 114-120.

166. Шульга Т.Э. Библиотека функций GroupAutomata // http://www.seun.ru/faculty/FIIT/KTOIT/GroupAutomata.rar (дата обращения 22.04.2009).

167. Шульга Т.Э. Метод построения восстанавливающих последовательностей для систем без потери информации // Системы управления и информационные технологии. 2009. № 1.3(35). С. 407-411.

168. Шульга Т.Э. Метод построения перечислимого множества автомата, моделируемого семейством многочленов / Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ «Колледж», 2001. Вып. 4. С. 148-156.

169. Шульга Т.Э. Необходимые условия моделируемости автоматных функций степенным многочленом // Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ «Колледж», 1998. Вып. 2. С. 145-153.

170. Шульга Т.Э. О возможностях восстановления поведения сложных систем: сборник научных трудов всероссийской военно-технической конференции «Проблемы совершенствования ракетных комплексов». Саратов: Изд-во Саратовского филиала ВАУ, 1999. С 30-34.

171. Шульга Т.Э. О классе систем, разрешимом относительно задачи управления поведением на основе свойств функциональнойизбыточности // Вестник СГТУ. 2008. № 4. С. 57-64.

172. Шулъга Т.Э. Численные критерии восстановимости поведения КДА степенным многочленом // Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ «Колледж», 1997. Вып. 1. С. 132-137.

173. Шулъга Т.Э., Ковальская А. С. О методе решения задачи диагностирования нейронной сети // Автоматизация проектирования дискретных систем: материалы шестой международной конференции. Минск: ОИПИ НАН Беларуси, 2007. С. 237-245.

174. Щербаков Е.С. Достоверность работы цифровых устройств. М.: Машиностроение, 1989. 224 с.

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

176. Якубайтис Э.А. Логические автоматы и микромодули. Рига: Зинатне, 1975. 260 с.

177. Babcsanty I., Nagy A. Mealy-automata in which the output-equivalence is acongruence//Acta Cyberneitca. 1994. Vol. 11. No. 3.P. 121-126.

178. Borosh J., Frankel A.S. Exact solutions of linear equations rational coefficients by congruence techniques // Math, of Comput. 966. 20:93. P. 107-112.

179. Delgado M., Linton S., Morais J. Automata a GAP package version number 1.11 // http://www.gap-system.org/Packages/automata.html (дата обращения 31.05.2008).

180. Harel D. Statecharts: A Visual Formalism for Complex Systems. Science of Computer Programming. 1987. Vol. 8, P. 231 274.

181. Muntyan Y., Savchuk D. GAP package AutomGrp Current version number 1.1.4 // http://www.gap-system.org/Packages/automgф.html (дата обращения 31.05.2008).

182. Sytnik A.A. Shulga Т.Е. Mathematical models of intellectual systems goal-directed behavior generating // Book of abstracts «V international congress on mathematical modeling» Dubna. 2002. Volue II. P. 133-134.

183. Sytnik A. A. Synthesis of universal finite automats // Jecture Notes in Computer Scince. Springer-Verlad. 1987. T. 278. P. 432-435.

184. Sytnik A.A., Shulga Т.Е. Functional Renewal of Behavior of Systems: Numerical Methods // Automation and Remote Control. Vol. 64. No. 10, 2003. P. 1620-1634.

185. Sytnik Alexander A., Posohina Natalia I., Shulga Tatiana E. On Some Methods Of Discrete Systems Goal-Directed Behavior Generating // The Fourth Conference of the SCI (Systemics, Cybernetics and Informatics), Orlando, Florida, USA, 2000.

186. Sytnik A.A., Shulga Т.Е. Mathematical models of Discrete Systems Goal-Directed Behavior Generating // International Journal of Computing Anticipatory. Belgium. Published by CHAOS. Volume 14. P. 299-310.

187. The GAP Group, GAP Groups, Algorithms, and Programming, Version 4.4.10, 2007//The GAP Group http://www.gap-system.org (датаобращения22.04.2009).