Введение к работе
Актуальность темы. В процессе эксплуатации сложных технических
систем неизбежно возникают неисправности, они связаны с
материальной природой систем и, следовательно, изменением во
времени, поэтому устранить вероятность появления дефекта
принципиально нельзя. Однако можно предусмотреть своевременную
амортизацию неполадок, то есть быстрое и достоверное обнаружение
неисправностей и устранение их последствий. Организация
восстановления поведения (ВП) сложной системы включает как
обеспечение восстанавливаемости поведения объекта на этапе его
проектирования, а также самодиагностирование и
самовосстановление объекта в процессе функционирования, так и
применение спектра восстановительных процедур, основанных на том
или ином виде резервирования. Традиционные методы структурного
восстановления поведения сохраняют изначальную
преобразовательную форму поведения за счет подключения
исправного дубля-резерва. Невозможность или нецелесообразность их
реализации инициирует применение функционального
восстановления, которое опирается на принцип обучения Я.З.Цыпкина и переход к перечислительной форме представления текущего поведения. Математические модели сложных систем позволяют оценить поведение системы с двух точек зрения: если закон функционирования задан как отображение множества последовательностей входных сигналов в множество последовательностей выходных сигналов, то есть представляет собой преобразование некоторого множества, то говорят, что реализуется модель поведения в преобразовательной форме. Если закон функционирования задан как перечисление всех последовательностей входных сигналов индуцирующих данный выходной сигнал, то говорят о реализации модели поведения в перечислительной форме. Автоматы, реализующие эти две модели, называются автоматами-преобразователями и автоматами-перечислителями соответственно. В случае функционального ВП текущий закон функционирования выступает как "обучающаяся" система, которая после приложения специальных "обучающих" последовательностей должна генерировать сигналы, эквивалентные реакциям исправного поведения - "необученной" системы. В процессе "обучения" (функционального восстановления) происходит отход от изначальных преобразовательных соотношений между входными и выходными сигналами, хотя последние в точности совпадают с реакциями
исправной технической системы. Анализ перехода от автоматов-преобразователей к автоматам-перечислителям и обратно позволяет выявить весь спектр функциональных особенностей поведения рассматриваемой системы. Вместе с тем, задача функционального ВП не сводится только к проблеме собственно восстановления поведения, в более общем ключе это задача приведения произвольного текущего поведения сложной системы (возможно, неисправного) к заданному виду. Формальная постановка задачи ВП была сделана) А.А. Сытником и В.А. Твердохлебовым:
Рассматриваемое множество / вариантов поведения сложной системы представлено множеством математических моделей поведения Г={у,}1е1- Множество П средств преобразования поведения сложной системы определено как множество отображений {a>,}v*N ввда a>r:Y'-+Y', гДе Г'=гиР для некоторых
дополнительных вариантов поведения Г, порожденных действиями средств преобразования поведения на Г. Правила F расшифровки преобразованных вариантов поведения сложной системы заданы отображением gF вида gF:P(T')->Y. Для заданных эталонного
(требуемого) варианта поведения у0 є Г и подмножества вариантов поведения Г0 (Г0 порождается учитываемым классом неисправностей сложной системы) требуется найти такое преобразование оєй, для которого выполняется условие: gF (й>(Г0,)) ={?"„}.
В общем случае (для произвольной сложной системы) задача ВП алгоритмически неразрешима, но она может быть решена при наложении на поведение системы (и, соответственно на математическую модель ее поведения) определенных ограничений. Однако, знание, что в данном конкретном случае задача ВП разрешима еще не дает ответа на вопрос, каким методом ВП следует воспользоваться. Поэтому несомненно важно установить связь между методами моделирования и восстановления поведения и условиями, накладываемыми на систему. Математические модели функционального восстановления поведения должны адекватно описывать в формальных терминах изменения в принципах обработки, синтеза и анализа вход-выходных соответствий. Целью исследования математической модели является получение информации о наличии или отсутствии предпосылок в наблюдаемом неисправном поведении для возврата к исправному.
В теории систем используются два подхода к моделированию поведения: моделирование при помощи конечных
детерминированных автоматов и моделирование при помощи полугрупп преобразований. В первом случае, при помощи формального аппарата теории КДА рассматривается некоторое преобразование, заданное через рекурсивные конструкции, и поведение системы как "черного ящика" изучается с точки зрения распознавания внутренних состояний модели, тестирования и построения тестов различного вида, а также исследования взаимосвязи компонент системы, опираясь на конструкцию системы и/или соответствие между входами и выходами системы как "черного ящика". Теория полугрупп в основном опирается на теорию множеств и рассматривает всевозможные преобразования, осуществляемые системой как отображения на некотором множестве, которые в свою очередь являются элементами множеств и подмножеств, а также (с введением операций над отображениями) - групп, полугрупп, колец и полей. В этом случае, преобразования, осуществляемые системой рассматриваются с точки зрения построения из них других преобразований, обладающих заданными свойствами.
Исследованию общей теории автоматов, а также вопросов их возможного прикладного использования посвящено большое число работ отечественных и зарубежных специалистов: М.А. Айзерман, М. Арбиб,, ЯМ. Барздинь, Б. А. Трахтенброт, А.М. Богомолов, Д.В. Сперанский, В.И. Варшавский, М.А. Гаврилов, В.М. Глушков, А. Гилл, Н.Е. Кобринский, Б.А. Трахтенброт, В.Б. Кудрявцев, О.П. Кузнецов, В.Г. Лазарев, Е.И. Пийль, М. Минский, К. Шеннон, Дж. фон Нейман, В.А. Твердохлебов, Дж. Ульман, М.Л. Цетлин, СВ. Яблонский и многие другие.
Способность математической модели поведения дискретной системы с памятью имитировать работу некоторого объекта рассматривается в рамках проблематики универсальных автоматов, являющейся одним из разделов общей теории автоматов. Её возникновение связано с появлением работ К. Шеннона, М. Минского, Дж. фон Неймана, наметивших основные направления исследований. М.Минский отмечает "...определенная категория множеств элементов "универсальна" в том смысле, что из таких элементов можно собрать машины, реализующие произвольные ... функции". В этой же работе элемент назван универсальным, если некоторое; достаточно большое множество объектов "обладает некоторыми подобными свойствами этого элемента или отличающимися лишь в количественном отношении". В.М. Глушков называет автомат универсальным, если "любой алгоритм может быть представлен в виде конечного набора выполняемых этим автоматом
команд, программ работы и фактически реализован им при условии игнорирования ограничений, накладываемых конечностью памяти автомата". В работах К.Шеннона и А.Тьюринга показана возможность построения машины Тьюринга универсальной в том смысле, что на ней можно выполнять любые вычисления. Универсальная машина воспроизводит работу частной, если "описание последней наносится на ленту универсальной машины по определенному коду, подобно начальной последовательности". Затем МДэвис и Р.Петер получили ряд условий, определяющих в явном виде метод построения команд универсальной машины Тьюринга. Обобщение универсальной вычисляющей машины с целью построения универсальной конструирующей машины рассматривалось Дж.фон Нейманом. Универсальность машины заключалась, в её способности к самовоспроизведению, "...процесс начинается с одного экземпляра универсального конструктора и его описания, а заканчивается двумя экземплярами этого комплекса". Фон Нейман впервые предсказал, что "...благодаря тесной связи задач саморемонта и самовоспроизведения результаты по самовоспроизведению могут решить проблему надежности". Дальнейшие исследования понятия "универсальность" были посвящены уточнению и конкретизации указанных подходов на множествах нулевых функций и конечных детерминированных автоматов с последующей интерпретацией для комбинационных и последовательностных устройств. Достаточно условно можно выделить три основных направления в этих работах.
В рамках первого изучались проблемы использования универсальных элементов при синтезе и анализе систем искусственного интеллекта;, способных к адаптации и обучению. Работы ВИ. Варшавского, ЯМ. Барздиня, М.Л. Цеглина развивали идеи, высказанные Дж. фон Нейманом.
Изучение универсальных булевых функций и конечных автоматов проводилось Э.В. Евреиновым и И.В. Прангишвили, А.П. Горяшко, В.А. Мищенко, Э.А. Якубайтисом и многими другими с целью построения универсальных и многофункциональных модулей. Превалирующей в этих работах была идея о достижении универсальности за счет перенастройки структуры технического объекта, что во многом близко концепции Ml Минского. Прикладная значимость подобных результатов обусловлена их использованием в настоящее время при разработке отказоустойчивых систем, опирающихся на введение аппаратурной избыточности и допускающих проведение реконфигурационных мероприятии.
Достаточно долго вне рамок активных исследований
оставалось предположение К. Шеннона и А. Тьюринга о возможности перенастройки универсальной машины за счет изменения режима внешних воздействий, а также их самих. Иными словами, идея К. Шеннона и А. Тьюринга заключалась в построении машины Тьюринга, имитирующей заданное поведение с точки зрения генерации требуемых выходных реакций. Очевидна аналогия этого подхода с рассматриваемыми принципами функционального восстановления.
Интерес представляет, в первую очередь, взаимосвязь между этими подходами к моделированию поведения данной системы. Для ее исследования в работе предложен третий подход - моделирование поведения через системы линейных алгебраических сравнений, при этом возможность ВП зависит от свойств степенных многочленов, моделирующих поведение сложной системы и матричных систем алгебраических сравнений, построенных на их основе. При построении и исследовании такой модели используются методы алгебры и теории чисел, поэтому она получила название числовой л/одели. Она по> своей сути является промежуточным звеном между конечно-автоматной и полугрупповой моделями, строится на основе функций переходов и выходов конечно-автоматной модели и использует методы алгебры и теории чисел для исследрвания полугруппы автоматных отображений полугрупповой модели. В общем случае, ограничения, накладываемые на сложную систему для возможности применения методов алгебры и теории чисел, определяют весь класс дискретных систем, допускающих моделирование, исследование и восстановление поведения через рассмотрение свойств числовой модели. Так как аппарат теории конечных автоматов и аппарат теории полугрупп разработаны гораздо меньше, чем алгебраический аппарат, то введение взаимнооднозначного соответствия между автоматной, полугрупповой и числовой моделями сложных систем позволило бы сделать исследование сложной системы более эффективными, в частности, заменить неэффективные переборные алгоритмы, используемые в теории полугрупп на алгебраические методы исследования свойств матриц меньшей сложности. Однако, если между автоматной и полугрупповой моделями существует взаимно-однозначное соответствие, то при построении числовой модели поведения ограничения, накладываемые на сложную систему, определяют и ограничения на автоматную и полугрупповую модели. Данная работа исследует эти ограничения, а также рассматривает конструктивные методы построения, исследования и применения числовой модели для
моделирования и восстановления поведения сложной системы. Цель работы состоит в представлении нового подхода к исследованию свойств, моделированию и восстановлению поведения сложной системы - через рассмотрение свойств ее специальным образом построенной числовой модели, в частности, через исследование моделирующей системы линейных алгебраических сравнений (СЛАС) и матрицы Вандермонда как матрицы коэффициентов СЛАС. Для достижения указанной цели поставлены и решены следующие задачи:
построение числовой модели поведения по заданной автоматной
модели (в качестве автоматной модели взят автомат Медведева);
анализ числовой модели и выявление ее связи с автоматной и
полугрупповой моделями сложных систем;
получение метода выделения класса автоматов, допускающих
числовое моделирование;
оценка ранга матрицы Вандермонда и вспомогательных числовых
функций;
нахождение ранга матрицы Вандермонда для произвольного
числа состояний автомата;
построение автомата Медведева по его числовой модели;
нахождение семейства моделей (и/или его представителей) по
заданному автомату Медведева;
Исследованы вопросы специфики моделирования и
восстановления поведения для многокомпонентных автоматов
как подкласса класса автоматов, допускающих восстановление
поведения с помощью числовой модели. Научная новизна. В работе впервые получены следующие результаты:
представлена числовая модель поведения сложной системы;
дана схема построения числовой модели по заданной автоматной
модели (в качестве автоматной модели взят автомат Медведева);
получена оценка сложности числовой модели в зависимости от
числа состояний исходного автомата Медведева, при ее
получении использовалась связь числовой и полугрупповой
моделей поведения;
получены оценки для вспомогательных числовых функций,
используемых при исследовании ранга матрицы Вандермонда;
найден ранг матрицы Вандермонда для произвольного числа
состояний автомата;
дан метод выделения класса автоматов, допускающих числовое
моделирование;
дана схема построения автомата Медведева по его числовой модели;
дан метод нахождения семейства моделей (и/или его представителей) по заданному автомату Медведева; исследованы вопросы моделирования и восстановления поведения для многокомпонентных автоматов (как отдельного подкласса класса автоматов, допускающих восстановление поведения с помощью числовой модели). Теоретическая и практическая ценность. Полученные результаты имеют как теоретическое, так и прикладное значение и могут быть использованы в дальнейших теоретических исследованиях в теории функциональных систем, а также в приложениях теории автоматов, в технической диагностике, в информатике.
Методы исследования. В работе используются методы алгебры, теории чисел и теории полугрупп. Для решения поставленных задач были разработаны модификации существующих алгебраических методов преобразования систем линейных алгебраических уравнений в поле действительных чисел для применения их к системам линейных алгебраических сравнений в целочисленном кольце. Апробация работы. Основные результаты настоящей докладывались и обсуждались на конференции «Проблемы технической кибернетики» (Ульяновск, 1996), на конференциях «Интеллектуальные системы и компьютерные науки (МГУ, 1996, 1997), на конференции the First International Conference CASYS'97 on Computing Anticipatory SYStems (Liege, Belgium, 1997), на семинарах кафедры математической кибернетики (СГУ, 1997-2000), на семинарах кафедры теоретических основ информатики и информационных технологий (СГУ, 1997-2000).
Публикации. Основные результаты работы содержатся в 9 статьях автора, список которых приведен в конце автореферата. Объем и структура работы. Работа выполнена на 98 страницах машинописного текста, состоит из оглавления, введения, 3 глав, списка литературы и приложения. Библиография состоит из 51 названия.