Введение к работе
Актуальность темы. Понятие системы является центральным понятием созданной в 60-х годах новой научной дисциплины - теории систем. К одним из самых интересных и еще недостаточно разработанных задач этой теория относятся задачи восстановления и организации целенаправленного поведения систем. В процессе эксплуатации сложных технических систем происходят нарушения их законов функционирования. Хотя причины возникновения и характер нарушений могут быть различны, но само это явление связано с материальной природой систем, а значит принципиально неизбежно. Применительно к сложным системам Дж. фон Нейман указывал, что "...неисправности компонент...существенная и неотъемлемая часть их работы". Способность технической системы к восстановлению поведения означает возможность продолжения ее заданного закона функционирования после возникновения и обнаружения неисправности. В общем случае задача восстановления поведения может рассматриваться как задача организации целенаправленного поведения системы, то есть задача перехода от текущего поведения системы (не обязательно неисправного) к любому заданному.
Основным методом восстановления поведения на сегодняшний день является резервирование, то есть использование дублей некоторых составляющих системы, цель которых - воспроизводить требуемое поведение соответствующей составляющей в случае возникновения неисправности. При этом процесс восстановления основывается да так называемой аппаратурной избыточности системы. П.П. Пархоменко и Е.С. Согомонян отмечают, что восстановление поведения системы может применяться как для восстановления правильного функционирования (первоначально заданного поведения), так и для восстановления ее исправного состояния, то есть для исправления всех обнаруженных дефектов. В условиях отсутствия резервирования и высокой стоимости или принципиальной невозможности физического устранения возникшего дефекта целесообразно рассматривать именно первый подход, так называемое самовосстановление. Процесс восстановления в этом случае основан только на функциональной избыточности системы, то есть на функциональных возможностях, заложенных в техническом объекте при его создании. Поэтому задачу восстановления в подобной постановке называют задачей функционального восстановления поведения (ФВП) системы. Для дискретных систем с памятью она впервые была сформулирована А.А. Сытником.
В данной работе в качестве математической модели системы при
решении задачи самовосстановления поведения рассматривается
конечный детерминированный автомат (КДА). Исследованию теории
автоматов, а также вопросам их возможного приложения посвящен ряд
работ таких отечественных и зарубежных специалистов, как
М.А.Айзерман, М.Арбиб, Я.М.Барздинь, А.М.Богомолов,
В.И.Варшавский, МАГаврилов, АГилл, В.М.Глушков,
Н.Е.Кобринский, Б.А.Трахтенброт, В.Б.Кудрявцев, СйАлешин, А.С.П0ДК0ЛЗИН, О.ПКузнецов, В.Г.Лазарев, Е.И.Пийль, М.Минский, К.Шеннон, Дж.фон Нейман, Д.В.Сперанский, В.АТвердохлебов, ДжУльман, М.Л.ЦЄТЛИН, С.В.Яблонский и другие.
Конечный детерминированный автомат как математическая модель реального объекта при решении задачи ФВП требует двоякого рассмотрения. С одной стороны, автоматы можно рассматривать с преобразовательной точки зрения, то есть изучать свойства данного автомата через рассмотрение преобразования входных последовательностей в выходные, а с другой - автомат может быть определен в перечислительной форме, то есть описанием автомата является множество выходных последовательностей, которые он генерирует. Если первая точка зрения на поведение автомата выросла в серьезную научную дисциплину с большим числом работ, специфическими методами и своеобразной проблематикой, получившую существенное развитие в нашей стране, то вторая точка зрения еще недостаточно разработана.
Традиционно проектирование технических объектов осуществлялось с ориентацией на преобразовательный способ переработки информации. Однако возникновение неисправности приводит к нарушению данного принципа. Поэтому концептуально процесс функционального восстановления поведения заключается в переходе от преобразовательного способа описания закона функционирования к перечислительному.
Фундаментальной основой для решения этой задачи является теория универсальных автоматов. Ее возникновение связано с появлением работ К. Шеннона, М. Минского, Дж. фон Неймана, А. Тьюринга, определивших основные направления исследования. Универсальный автомат - это автомат, способный моделировать, порождать, воспроизводить (соответственно по Шеннону, Минскому и фон Нейману) заданный спектр поведений или объектов. Фон Нейман впервые предсказал, что "...благодаря тесной связи задач саморемонта и самовоспроизведения результаты по самовоспроизведению могут решить проблему надежности". Развитию теории универсальных
автоматов посвящены работы В.Б. Кудрявцева, В.А. Буевича,
М. Дэвиса, Р. Петера, Э.В. Евринова, И.В. Прангншвили,
В.И. Варшавского, В.А. Мищенко, ЯМ. Барздиня, В.М. Глушкова,
исследующие универсальность на множествах
ограниченно-детерминированных функций, булевых функций, машин Тьюринга и конечных детерминированных автоматов с последующей интерпретацией для комбинационных и последовательностных устройств.
В терминологии универсальных автоматов способность системы к самовосстановлению означает, что автомат, описывающей «неисправное» поведение должен быть универсальным для автомата, моделирующего «исправное» поведения системы. Как показано А.А. Сытником, задача построения универсального автомата, а следовательно, и задача ФВП относительно произвольного семейства КДА является алгоритмически неразрешимой. Поэтому, в настоящее время предпринимаются попытки выделить классы, для которых эта задача имеет решение. Можно предложить два принципа выделения разрешимых классов. Первый подход опирается на рекурсивный механизм при описании частных типов конечно-автоматных систем. Их закон функционирования предполагается реализованным из базисных элементов, для которых найден единый алгоритм восстановления поведения. Второе направление предполагает разработку алгоритмов восстановления поведения непосредственно при изучении конкретных тігаов законов функішонирования систем. В настоящей работе для выделения разрешимого класса автоматов используется второй подход. В качестве модели конкретного типа закона функционирования системы выбирается КДА, в котором каждая функция переходов представима степенным многочленом с целыми коэффициентами. Исследование данной числовой модели представляется перспективным, так как использование алгебраического аппарата (разработанного гораздо лучше, чем аппараты теории автоматов и теории полугрупп) позволило бы сделать изучение поведение систем более эффективным.
Цель работы состоит в выделении класса конечных детерминированных автоматов, разрешимого относительно задачи функционального восстановления и построении для этого класса методов организации восстановительных процедур.
Для достижения указанной цели были поставлены и решены следующие задачи:
изучение числовой модели автомата;
описание класса автоматов, допускающих моделирование семейством степенных многочленов (ССМ);
- решение задачи синтеза универсального автомата,
моделируемого ССМ;
-решение задачи анализа универсального автомата, моделируемого ССМ;
- получения метода построения восстанавливающей
последовательности относительно заданной неисправности для
автомата, моделируемого ССМ.
Научная новизна. К новым результатам, полученным в данной работе, можно отнести следующие:
расширение понятия числовой модели автомата за счет допущения о рациональности коэффициентов степенных многочленов, моделирующих поведение автомата;
критерии моделируемости автомата ССМ, как с целыми, так и с рациональными коэффициентами;
метод построения множества, перечислимого автоматом, моделируемым ССМ;
критерий универсальности автомата, моделируемого ССМ;
метод построения для автомата описанного класса семейства автоматов, для которых заданный является универсальным (решение задачи анализа);
метод построения для заданного семейства автоматов описанного класса универсального автомата (решение задачи синтеза);
метод построения восстанавливающей последовательности для автомата, моделируемого ССМ.
Теоретическая и практическая ценность. Полученные результаты имеют как теоретическое, так и прикладное значение и могут быть использованы в дальнейших теоретических исследованиях, а также в приложениях теории автоматов: в технической диагностике, в теории восстановления поведения сложных систем, в информатике.
Методы исследования. В работе используются методы дискретной математики и математической кибернетики. Использование числовой модели автомата позволило применять в работе также методы алгебры, теории чисел и теории полутрупп.
Апробация работы. Основные результаты работы докладывались и обсуждались на первой всероссийской научной конференции молодых ученых и аспирантов «Новые информационные технологии, разработка и аспекты применения», (Таганрогский радиотехнический университет, 1998), на всероссийской военно-технической конференции "Проблемы совершенствования ракетных комплексов" (Саратов, 1998), на IV международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов 99"
(МГУ, 1999), на семинарах кафедры математической кибернетики и компьютерных наук н кафедры теоретических основ информатики и информационных технологий (СГУ, 1997-2000).
Публикации. Основные результаты работы содержатся в 7 публикациях автора, список которых приведен в конце автореферата.
Объем и структура работы. Работа представлена на 99 страницах машинописного текста, состоит из оглавления, введения, 3 глав и списка литературы. Библиография состоит из 62 названий.