Введение к работе
Актуальность темы. Одним из основных требований к современным системам (техническим объектам, программным, социально-экономическим системам и др.) является требование адаптивности, т.е. способности системы изменяться в соответствии с быстро меняющимися условиями внешней среды. Адаптивность системы достигается наличием в ней некоторой избыточности.
Для модификации поведения системы характерно использование двух основных типов избыточностей: аппаратной (структурной) и функциональной (временной). Аппаратная избыточность подразумевает введение в состав системы дополнительных резервных элементов, которые реализуют требуемое поведение. Функциональная избыточность предполагает использование свойств текущего закона функционирования для формирования на выходах требуемой совокупности реакций только на основе имеющегося в данный момент или искусственно создаваемого резерва времени. При этом для формирования на выходе требуемой совокупности реакций на вход следует подавать специальные последовательности входных символов, которые будем называть восстанавливающими. Восстанавливающая последовательность - это последовательность входных символов, при подаче которой в любом текущем состоянии система в качестве последнего выходного символа генерирует требуемый выходной символ. Система обладает функциональной избыточностью относительно заданной совокупности требуемых поведений, если возможно построить восстанавливающие последовательности для каждой требуемой реакции системы из данной совокупности. Функциональная избыточность может выявляться в созданной системе с целью получения требуемой реакции, а также целенаправленно создаваться на этапе проектирования системы.
Одним из первых авторов, подробно рассмотревшим понятие «адаптивность» является Я.З. Цыпкин, указавший, что адаптивность системы достигается за счет возможности настройки режима ее функционирования для получения некоторого спектра требуемых реакций. Однако в его работах не рассматриваются вопросы достижения адаптивности на основе функциональной избыточности. Вопросами избыточности в рамках проблемы отказоустойчивости занимались представители советской школы технической диагностики М.Ф. Каравай, Е.С. Согомонян, П.П. Пархоменко, Ю.Г. Савченко, однако в их работах основное внимание уделено аппаратной избыточности.
Основы математического моделирования дискретных систем, способных реализовать некоторый спектр поведений, заложены в работах К.Шеннона, М.Минского, Дж. фон Неймона, А.Тьюринга, предложивших различные модели универсального автомата (машины, устройства). Универсальный автомат способен моделировать, порождать, воспроизводить заданный спектр поведений или объектов, соответственно по Шеннону, Минскому, фон Неймону. Изучение универсальных конечных автоматов осуществляловь Э.В. Евреиновым и И.В. Прангишвили, А.П. Горяшко, В.А. Мищенко, Э.А. Якубайтисом и многими другими c целью построения универсальных и многофункциональных модулей. Однако, превалирующей в этих работах была идея о достижении универсальности за счет перенастройки структуры технического объекта. Для описания функционально избыточных систем А.А. Сытником введена модель универсального автомата-перечислителя, однако в его работах эта модель используется только для решения задачи восстановления системы после возникновения различного рода неисправностей на этапе эксплуатации системы. Модель универсального автомата-перечислителя исследовалась также Н.С. Вагариной, Н.И. Посохиной, К.П. Вахлаевой и другими для отдельных классов дискретных систем, однако эти исследования имеют чисто теоретический характер и не затрагивают вопросы создания и эксплуатации функционально избыточных систем.
Объект и предмет исследования. Объектом исследования являются дискретные системы, обладающие функциональной избыточностью. Под дискретной системой понимается система, имеющая конечное множество входных и выходных сигналов и находящаяся в любой момент времени в одном из конечного числа состояний, причем подача входных сигналов и, соответственно, смена состояния и снятие выходных реакций происходят только в определенные моменты времени. Предметом исследования являются математические модели и методы создания и эксплуатации функционально избыточных дискретных систем.
Цель и задачи исследования. Цель диссертационной работы - разработка и исследование математических моделей и методов создания и эксплуатации функционально избыточных дискретных систем.
Для достижения этой цели поставлены и решены следующие задачи:
формулировка основных задач математического моделирования функционально избыточных дискретных систем и исследование математических моделей функционально избыточных дискретных систем;
разработка общих схем решения задач математического моделирования функционально избыточных дискретных систем;
решение задач математического моделирования функционально избыточных систем для частных классов систем:
систем, допускающих так называемое числовое моделирование (моделирование многочленами специального вида),
систем без потери информации,
регистров, представляющих собой один из базовых элементов современной электронной техники;
реализация разработанных методов на примере построения математической модели функционально избыточной программной системы.
Методы исследований. При выполнении работы использованы методы системного и комбинаторного анализа, теории автоматов, теории полугрупп, теории чисел. Исследование основывается на формальных доказательствах с содержательной интерпретацией постановок задач и полученных результатов.
Обоснованность и достоверность научных результатов обеспечивается корректной математической постановкой задач, применением классических математических методов, использованием утверждений, строго доказанных формальными методами, данными численного эксперимента.
Научная новизна.
-
Сформулированы основные задачи математического моделирования функционально избыточных дискретных систем на содержательном уровне и в терминах выбранной математической модели (универсального автомата-перечислителя):
задача определения функциональной избыточности системы (задача анализа универсального перечислителя),
задача проектирования функционально избыточной системы (задача синтеза универсального перечислителя),
задача определения возможности реализации требуемых поведений дискретной системы на основе функциональной избыточности (задача получения критерия универсальности),
задача реализации требуемых поведений дискретной системы на основе функциональной избыточности (задача построения восстанавливающих последовательностей).
-
На основе результатов теории полугрупп и теории автоматов доказана алгоритмическая неразрешимость поставленных задач для всего класса дискретных систем, тем самым определено основное направление развития исследований математических моделей функционально избыточных дискретных систем – создание частных методов решения поставленных задач для частных классов систем.
-
Предложены два типа модели функционально избыточной системы (универсальный автомат-перечислитель общего вида и универсальный автомат-перечислитель с управляющим каналом) и показано, что схемы их синтеза основаны на определении элементов системы образующих полугруппы универсального автомата. Определены основные характеристики универсального автомата-перечислителя (количество состояний, количество входных сигналов и длины восстанавливающих последовательностей) и изучено их взаимовлияние. Описана общая схема реализации требуемых поведений функционально избыточной системы.
-
Исследована математическая модель систем, допускающих так называемое числовое моделирование - автоматы, функции переходов которых представлены многочленами специального вида в кольце вычетов по модулю m (где m – число состояний системы). На основе теории чисел при исследовании разрешимости определенной системы сравнений по модулю m получены различные условия моделируемости автоматной подстановки многочленом. На основе свойств полугруппы, порождаемой рассматриваемыми многочленами, решены задачи анализа и синтеза универсального автомата-перечислителя, предложены критерии универсальности, метод построения восстанавливающих последовательностей.
-
Исследована математическая модель систем без потери информации - групповые автоматы. Исследованы известные системы образующих симметрической группы степени m и длины групп автоматов, имеющих данные системы образующих. На основе этого предложены различные универсальные автоматы-перечислители для класса групповых автоматов, решены задачи анализа и синтеза универсального автомата-перечислителя, разработан метод построения восстанавливающих последовательностей.
-
Разработан комплекс проблемно-ориентированных программ в открытой свободно распространяемой системе GAP (система компьютерной алгебры, представляющая всемирный научный проект, объединяющий специалистов в области алгебры, теории чисел, математической логики и т.д.), реализующий все предложенные методы для работы с универсальными групповыми автоматами.
-
Исследована автоматная модель регистров различных типов, а именно регистров с последовательным приемом и параллельной выдачей информации, сдвиговых регистров, регистров с параллельным приемом и последовательной выдачей информации, регистров памяти. На основе свойств преобразований, реализуемых регистрами с последовательным приемом и параллельной выдачей информации при подаче входных сигналов 0 и 1, разработаны методы построения восстанавливающих последовательностей для данного класса объектов, методы синтеза универсальных перечислителей.
-
На основе сочетания принципов автоматного программирования и предлагаемых методов проектирования функционально избыточных систем разработаны схемы проектирования функционально избыточной программной системы.
Практическая ценность, реализация результатов работы. Результаты диссертационной работы могут быть использованы при решении таких практически значимых задач, как проектирование и эксплуатация адаптивных систем. Метод проектирования функционально избыточной программной системы использован при разработке АИС «Управление инфраструктурой научно-образовательной среды» по проекту «Работы по анализу и выбору базовых показателей, используемых в зарубежных странах для оценки использования и воздействия ИКТ на сферу образования, и разработке методик анализа данных, технологии сбора и обработки информации на основе выбранных показателей» (в рамках ФЦП «Электронная Россия» (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 статей в журналах, входящих в Перечень ВАК РФ.
Основные положения, выносимые на защиту.
-
Формулировка основных задач математического моделирования функционально избыточных дискретных систем в терминах универсальных автоматов-перечислителей позволяет применять при их решении аппарат теории автоматов и полугрупп. Доказательство алгоритмической неразрешимости этих задач для класса дискретных систем определяет основное направление исследований математических моделей функционально избыточных дискретных систем – исследование моделей частных классов дискретных систем.
-
Решения задач математического моделирования функционально избыточных дискретных систем - определение функциональной избыточности системы, ее проектирование, реализация требуемого поведения - основаны на построении перечислимого множества универсального автомата, определении элементов системы образующих полугруппы универсального автомата, определении механизма порождения требуемых автоматных преобразований через выбранную систему образующих.
-
Результаты исследования числовой модели автомата позволяют для заданного автомата определить возможность его представления семейством многочленов, построить семейство многочленов, доопределить автомат до автомата, допускающего это моделирование. Предложенные методы решения задач математического моделирования функционально избыточных систем для класса систем, допускающих числовое моделирование, основаны на исследования полугруппы многочленов в кольце вычетов по модулю m.
-
Результаты исследования групповых автоматов позволяют решить задачи математического моделирования функционально избыточных систем для класса систем без потери информации. Разработка универсальных перечислителей для этого класса основана на исследовании различных систем образующих симметрической группы степени m. Оценка длин групп автоматов с известными системами образующих позволила получить такую характеристику универсального перечислителя, как длина восстанавливающей последовательности.
-
Разработанный комплекс проблемно-ориентированных программ GroupAutomata, реализующий предложенные методы для работы с универсальными групповыми автоматами, может быть использован любым исследователем для решения задач выявления функциональной избыточности, проектирования и реализации требуемого поведения функционально избыточной системы без потери информации.
-
Результаты исследований автоматной модели регистров различных типов позволили разработать математические методы решения задач построения восстанавливающих последовательностей, методы синтеза универсальных перечислителей для данных регистров.
-
Предложенные схемы проектирования функционально избыточной программной системы основаны на принципах автоматного программирования и различных методах построения универсального автомата-перечислителя. Приведенная структура автоматных программ позволяет реализовать предложенные схемы на любом языке программирования как с помощью Switch-технологии, так и с помощью IfTableSwitch-технологии.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы, включающего 192 наименования, и трех приложений. Работа изложена на 363 страницах, содержит 8 рисунков и 5 таблиц.
