Управление поведением дискретных систем с памятью при функциональном восстановлении на основе периодических последовательностей тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Гвоздюк Илья Вячеславович

• Гвоздюк Илья Вячеславович
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Гвоздюк Илья Вячеславович

Введение

Глава I. Восстановление поведения дискретных систем на основе конечно-автоматных моделей

1.1. Алгоритмическая неразрешимость восстановления поведения дискретных систем относительно произвольного класса неисправностей

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

1.3. Формальная модель дискретной системы с памятью при решении восстановления поведения в режиме зацикливания

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

последовательностей

Глава 2. Исследование свойств модели поведения дискретных систем с памятью на основе структурной формы их задания

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

2.2. Классификация формальных моделей поведения дискретных систем, на

основе свойств функций алгебры логики

Глава 3. Достаточные условия решения задачи функционального восстановления поведения дискретных систем с памятью на основе

периодических последовательностей

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

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

3.3. Достаточные условия для восстановления поведения автоматных моделей дискретных систем с память методом восстанавливающих

периодических последовательностей

Глава 4. Восстановление поведения дискретных систем с памятью с использованием автоматного представления нейронных сетей

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

4.2. Построение метода решения задачи синтеза для нейронной сети как автоматной модели поведения дискретной системы с памятью

4.3. Исследование сетевых топологий информационно-коммуникационных

систем автоматными моделями

Заключение

Список использованной литературы

Приложение

Приложение

Введение диссертации (часть автореферата) на тему «Управление поведением дискретных систем с памятью при функциональном восстановлении на основе периодических последовательностей»

Введение

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

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

Выход из строя /или отсутствие в силу сложностных, ценностных и прочих ограничений/ аппаратурного резервирования порождает вопрос: "Можно ли использовать свойства текущего /в условиях существования неисправностей/ закона функционирования технической системы для формирования на её выходах требуемой совокупности правильных исправных реакций?" Ответ на него предполагает изучение имевшейся в данный момент времени функциональной избыточности технической системы, а также возможных вариантов её целенаправленного создания на этапе проектирования. Восстановление поведения технических объектов, осуществляемое на указанных принципах, впервые было введено

А.А. Сытником [56] и названо функциональным. Затем, функциональное восстановление дискретных систем с памятью достаточно подробно исследовалось его учениками Т.Э. Шульгой, Н.С. Вагариной, О.В. Мещеряковой, Н.И. Посохиной, К.П. Вахлаевой, С.Ю. Дронкиным, А.Н. Кунявской и др.

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

Модель конечного детерминированного автомата является, несмотря на ряд определенных недостатков, наиболее используемой при формальном описании поведения такого класса технических объектов как дискретные системы с памятью. Конечные автоматы и всевозможные их приложения подробно рассматривались большим количеством авторов. К их числу следует отнести, например, Э. Мура, А. Гилла, В.М. Глушкова А.М. Богомолова, П.П. Пархоменко, В.А. Твердохлебова, М.Ф. Каравая, Э.В. Евреинова, И.В. Прангишвили, В.И. Варшавского, Я.М. Барздиня, В.Б. Кудрявцева.

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

Поэтому, одной из актуальных задач является рассмотрение и выделение разрешимых классов и типов технических объектов или, в

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

В диссертационной работе рассматриваются два подхода к выделению такого рода классов поведений дискретных систем с памятью. Точнее, два взаимоследующих и взаимодополняющих подхода. Вначале, исследуется структурная форма представления конечно-автоматных моделей и выделяются их типы в зависимости от классов булевских функций, описывающих их переходы-выходы. Затем, используется результат В.А. Твердохлебова [11] о виде графов функции переходов-выходов с точки зрения периодических последовательностей. Последние, в рамках теории экспериментов с автоматами, подробно изучались А.Н. Кунявской [62]. Принципиальное отличие предлагаемого подхода заключается в применении идеи В. А. Твердохлебова о «периодичности» к анализу и синтезу восстанавливающих последовательностей для обеспечения повышения управляемости о и отказоустойчивости дискретных систем с памятью.

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

Цель работы конкретизируется решением следующих вопросов и задач:

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

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

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

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

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

Научная новизна работы соответствует п. 2, 10, 11, 13 паспорта специальности 05.13.01 «Системный анализ, управление и обработка информации» и заключается в следующем:

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

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

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

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

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

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

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

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

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

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

Соответствие работы паспорту специальности

Диссертационная работа вносит вклад в следующие области исследований, перечисленные в паспорте специальности 05.13.01 «Системный анализ, управление и обработка информации»:

1) Формализация и постановка задач системного анализа, оптимизации, управления, принятия решений и обработки информации.

2) Методы и алгоритмы интеллектуальной поддержки при принятии управленческих решений в технических системах.

3) Методы и алгоритмы прогнозирования и оценки эффективности, качества и надежности сложных систем.

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

Практическая значимость работы состоит в использовании предложенных методов повышения отказоустойчивости технических объектов дискретного типа с памятью. В частности, для информационно-коммуникационных систем и различных сетевых структур. Разработанные методы и программ использовались при выполнении исследований госбюджетных НИР Саратовского государственного технического университета (СГТУ) имени Гагарина Ю.А.:

«Разработка методов дискретного анализа семантики слабоструктурированных систем» (2013-2016 гг.).

Апробация результатов диссертации

Результаты работы докладывались на международных научных конференциях: На ХХ юбилейной Всероссийской научной конференции «Инжиниринг предприятий и управление знаниями» (ИП &УЗ- 2017,

Международной научно-практической конференции «Информационно-коммуникационные технологии в образовании, производстве и научных исследованиях» Ю^ (Саратов 2017, 2018), Международной научно-технической конференции «Перспективные информационные технологии (ПИТ)» (Самара, 2017, 2018).

Основные публикации

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

Структура и объем диссертации

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

Глава 1. Восстановление поведения дискретных систем на основе

конечно-автоматных моделей

1.1. Алгоритмическая неразрешимость восстановления поведения дискретных систем относительно произвольного класса неисправностей

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

Традиционно технические объекты проектируются с ориентацией на преобразовательный способ переработки информации. Закон функционирования в этом случае предполагает реализацию отображения А: XУ * (X *, У* - множества последовательностей входных сигналов

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

Определение 1.1. Пусть задан конечный детерминированный автомат А=(8,Х,УДХ), реализующий семейство отображений {Ь3}, б^Б, вида: X * ^ У * и генерирующий множество выходных последовательностей Ь(Х") = (д (Уs Е 8)(Ур Е X * )Иа (р) = д}. Тогда под поведением конечного

детерминированного автомата А как преобразователя (как перечислителя) будем понимать семейство отображений {Ь3}, б^Б (множество Ь(X*) представимых (генерируемых) этим автоматом.

Определение 1. 2. Предположим, что возникновение неисправности в конечном детерминированном автомате А=($>,Х,У,6,)) приводит к замене семейства отображений (Ь3), б^Б, представимых автоматом А, на семейство

отображений {}, Под восстановлением поведения конечного

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

т) = [д (У* е эдур е 0)д = и'Хр)} = ь(х *)

Допустим, неисправность приводит к тому, что приложение к автомату некоторых входных сигналов х£Х приводит к «неисправному» выходному сигналу. Тогда для каждого "неисправного" входного сигнала х определяется "исправная" выходная реакция системы у, исходя из знания закона функционирования автомата до возникновения неисправности. Для этого выходного сигнала у строится множество ДУ) — х последовательностей входных сигналов, при подаче которых система генерирует реакцию у. Т.е. приложение к "исправному" автомату входного сигнала х должно быть равносильно приложению к "неисправному" автомату входной последовательности р=х1х2...хк, причем выходной сигнал у появится последним в цепочке у1у2^у, где )(б, х1), у2=)(&'(б), х2),..., у=)(б, р) при любом текущем состоянии б.

Таким образом, на первом этапе восстановления поведения определяется класс входных сигналов, приложение которых приводит к нарушению работы объекта: Х1 , Х2 . • • Хп'. Для них строятся множества У1, У2 ... Уп выходных реакций, генерируемых системой. Затем из каждого множества Ь(У1), Ь(У2), ... Ь(Уп ) выбирается (согласно ограничениям на решение задачи восстановления) некоторый представитель замены Р1, Р2 ... Рп .В общем случае Р1 - семейство последовательностей входных сигналов.

Наиболее просто задача восстановления поведения решается для конечных детерминированных автоматов без потери информации. Класс

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

Возможно следующее упрощение поставленной задачи. Конечный детерминированный автомат А = (Б, X, У, д, )) задается функцией переходов 6 и функцией выходов ).

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

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

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

Каждой неисправности 1^1 сопоставляется конечный автомат А1 (формальная модель реальной технической системы при неисправности {)-автомат А при неисправности I. Предполагается, что мы знаем законы функционирования каждого автомата из семейства {А}, 1Е1. Путем сравнивания таблиц переходов и выходов (графов переходов) автомата А и автомата А1 определяем множество неисправных входных сигналов Х0£Х.

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

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

В работе [56] доказана следующая теорема:

Теорема. Задача построения математической модели средств (систем) самовосстановления относительно произвольного класса неисправностей алгоритмически неразрешима.

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

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

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

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

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

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

Метод периодических последовательностей впервые был применен для решения задачи распознавания автомата в работе А.М. Богомолова и В.А. Твердохлебова [11]. В этой работе (теорема 23) показана общая структура процесса функционирования конечного детерминированного автомата под воздействиями периодических последовательностей. Здесь же приводится пример исключения из анализа вершин, не входящих в циклы, порождаемых приложением периодических последовательностей. При этом переходы состояний автомата будут определяться перемещением по циклу. Обычный граф автомата удобно заменить графом зацикливания автомата по входной периодической последовательности с периодом р. В вышеуказанной работе этот граф определяется следующим образом

^д(р)=(Б,ф), (Б,Б')Е ф ^ 5(Б,Р)= Б'

Имеет место следующая теорема. [11]

Теорема 2.

Для любого конечного автомата А и входного слова р:

1. граф 0А(р) состоит из конечного числа связных изолированных подгафов;

2. каждый связный изолированный подграф содержит один и только один элементарный цикл с точностью до циклического сдвига последовательности вершин;

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

о

3

5

Рис.1. Пример графа 0А(р)

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

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

Допустим, периодическая последовательность является восстанавливающей для неисправного сигнала х. Если состояния 1,2,3 автомата А2, соответствующего поведению в «неисправном» режиме функционирования, под воздействием этой периодической последовательности переходят в одно общее для них состояние б, то и для

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

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

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

Замечание 1.2. Граф зацикливания по входному слову р «неисправного» автомата должен содержать такое же количество циклов, что и граф «исправного» автомата под воздействием входного сигнала х с теми же множествами вершин циклов. Допустим граф автомата Ai под воздействием сигнала х имеет п циклов С;, l<i<n, С; = {sn, Si2,..., Sjm}, тогда граф зацикливания автомата А2 ("неисправное" поведение) под воздействием слова р имеет п циклов С; , где переходы состояний в цикле С; определяются какой-либо перестановкой множества элементов {sn, Si2,..., Sim}.

Рис.2. Граф зацикливания

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

В = па1 па 2 пап

произведение этих слов в различных степенях Ух "'Уп , В -

общий вид восстанавливающей последовательности.

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

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

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

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

Список литературы диссертационного исследования кандидат наук Гвоздюк Илья Вячеславович, 2018 год

Список использованной литературы

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

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

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

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

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

6. Баранов С.И. Цифровые устройства на программируемых БИС с матричной структурой. М. Радио и связь. 1986. 270 с.

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

8. Бахтурин Ю.А. Основные структуры современной алгебры. М. Наука. 1990. 318 с.

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

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

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

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

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

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

15. Бурбаки Н. Теория множеств. М. Мир. 1965. 455 с.

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

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

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

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

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

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

22. Гвоздюк И.В., Сластихин А.В., Шульга Т.Э. О возможностях моделирования гетерогенных информационных систем на основе агентного подхода //Вестник СГТУ №4 (77). 2014. С.167-175.

23. Гвоздюк И.В., Сытник А.А., Шульга Т.Э. О возможностях применения онтологического моделирования при разработки электронных видеоархивов//Инжиниринг предприятий и управление знаниями (ИП &УЗ-2017): Сборник научных трудов ХХ юбилейной Всероссийской научной конференции.28-28 апреля 2017г./ под науч.ред.Ю.Ф.Тельнова: в 2 т. -Москва; ФГБОУ ВО «РЭУ им. Г.В.Плеханова», 2017. Т.1. С. 111-116.

24. Гвоздюк И.В., Данилов Н.А., Сытник А.А., Шульга Т.Э. Моделирование управлением технических систем дискретного типа на основе автомата с изменениями состояний в циклах. Проблемы управления в социально-экономических и технических системах: сборник научных статей. -Саратов: Издательский центр «Наука», 2017.28-34.

25. Гвоздюк И.В. Об одном подходе к синтезу автоматных моделей при управлении технических систем дискретного типа. Проблемы управления в социально-экономических и технических системах: сборник научных статей. - Саратов: Издательский центр «Наука», 2017.25-28.

26. Гвоздюк И.В. Автоматное моделирование при восстановлении поведения одного класса нейронных сетей. Проблемы управления в социально-экономических и технических системах: сборник научных статей. -Саратов: Издательский центр «Наука», 2018.

27. Геллер С.И., Журавлев Ю.И. Основы логического проектирования цифровых вычислительных машин. М. Сов. радио. 1969 272 с.

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

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

30. Горяшко А.П. Логические схемы и реальные ограничения. М. Энергоиздат. 1982. 184 с.

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

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

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

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

35. Горбатов В.А. Основы дискретной математики. М. Высшая школа. 1986. 311 с.

36. Дроздов Е.А. Оптимизация структур цифровых автоматов. М. Сов. радио. 1975. 352 с.

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

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

39. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. М. Наука. 1971. 512 с.

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

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

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

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

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

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

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

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

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

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

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

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

52. Поспелов Д.А. Логические методы анализа и синтеза схем. М. Энергия. 1974. 368 с.

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

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

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

56. Сытник А.А. Перечислимость при восстановлении поведения автоматов. //Доклады РАН N 328 N 1.1993.

57. Сытник А. А. Восстановление поведения сложных систем. Саратов. Изд- во Сарат. ун-та. 1992. 192 с.

58. Сытник А.А. Методы и модели восстановления поведения автоматов. //Автоматика и телемеханика. 1992. N 11.

59. Сытник А.А., Гвоздюк И.В. Об одном методе моделирования сетевых информационных систем. //Вестник СГТУ 2015 №4 (81), Саратов: Сарат. гос. техн. ун-т, 2015г., С.157-164. ISSN 1999-8341.

60. А.А.Сытник, И.В.Гвоздюк. Об одном подходе к автоматному моделированию поведения информационно-коммуникационных систем. Перспективные информационные технологии (ПИТ-2018): Труды Международной научно-технической конференции / под ред. С.А. Прохорова. - Самара: издательство Самарского научного центра РАН, 2018. ISBN 978-5-93424-817-9. С. 194-199.

61. Сытник А.А., Ивженко С.П., Гвоздюк И.В. Оптимизация ресурсоёмких вычислительных задач на графическом процессоре// Известия Самарского научного центра Российской академии наук, т. 18, № 4(4), 2016. С. 835-838. ISSN 1990-5378.

62. Сытник А.А., Гвоздюк И.В. О некоторых свойствах дискретных моделей при управлении сложными системами. Проблемы управления в социально-экономических и технических системах: сборник научных статей. -Саратов: Издательский центр «Наука», 2017.79-84

63. Solopekina A.A., Sytnik A.A., Gvozduk I.V. Uncertainty interval evaluation. Перспективные информационные технологии (ПИТ-2017): Труды Международной научно-технической конференции / под ред. С.А. Прохорова. - Самара: издательство Самарского научного центра РАН, 2017. С.28-33.

64. Semezhev N., Solopekina A.A., Gvozduk I.V. Multiport modulator. Перспективные информационные технологии (ПИТ-2017): Труды Международной научно-технической конференции / под ред. С.А.

Прохорова. - Самара: издательство Самарского научного центра РАН, 2017. C. 33-37.

65. Сытник А.А., Шульга Т.Э., Данилов Н.А., Гвоздюк И.В. Математическая модель активности пользователей программного обеспечения. Международный научно-практический журнал * Программные продукты и системы*. 2018, том 31, № 1.Тверь. С. 79-84.

66. Сытник А.А., Шульга Т.Э., Кунявская А.Н. Анализ и синтез универсального автомата-перечислителя. //Тезисы докладов Международной конференции «Компьютерные науки и информационные технологии». Саратов. 2002 г.С. 70-71.

67. Сытник А.А., Шульга Т.Э. Управление дискретными системами на основе функциональной избыточности. //Саратовский государственный социально-экономический университет - Саратов, 2009. - 196с. ISBN 978-5-87309-8828.

68. Сытник А.А., Шульга Т.Э. Математические модели адаптивных дискретных систем. Монография //Саратов: Сарат. гос. техн. ун-т, 2015. 272с. ISBN 978-5-433-2947-2

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

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

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

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

сфере: сб. науч. тр.; под ред. Ю.В. Гуляева. Саратов: Изд-во «Научная книга», 2005. С. 122-131.

73. Твердохлебов В.А. Логические эксперименты с автоматами. Саратов. Изд-во Сарат. ун- та. 1988. 184.Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы. Поведение и синтез. М. Наука. 1970. 400 с.

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

75. Ушаков И.А. Построение высоконадежных систем. М. Энергия. 1974. 64 с.

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

77.Фридман А., Меннон П. Теория и проектирование переключательных схем. М. Мир. 1978. 580 с.

78. Харари Ф. Теория графов. М. Мир. 1973. 300 с.

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

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

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

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

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

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

Приложение 1.

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

Проект состоит из следующих файлов:

Auto.inc - классы моделирующие автоматы. Этот файл является центральным в программе.

Funct_choice.php - скрипт для выбора классов функций для памяти и комбинационной части автомата для автомата с одним входом.

Avtomat.php - скрипт для задания автомата с одним входом.

Avtomat2.php - скрипт для задания автомата с двумя входами.

Functioning.php - скрипт воспроизводящий работу автомата с одним входом

Functioning2.php - скрипт воспроизводящий работу автомата с двумя входами.

Funct - инициализационный файл для автомата с одним входом.

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

1) Сервер Apache + mod php4

2) В конфигурационном фале php должна быть разрешена работа с сессиями. Алгоритм и Объектно-ориентированная модель работы программы

Классы (auto.inc):

1) Класс auto - абстрактный автомат, от которого наследуют все остальные. Атрибуты: история входов, выходов, состояний, номер такта

функционирования, количество входов. Функции: задание количества входов.

2) Класс FSM - наследник auto. Моделирует автомат (2,2,2) c одним входом. Все поля и функции наследует от auto и добавляет свои. Новые атрибуты: функции выходов/ переходов(в виде ассоциативных массивов), текущее состояние, вход и выход. Функции: переход к следующему такту функционирования, конструктор

3) Класс FSM_2 - наследник FSM. Моделирует автомат (2,2,2) c двумя входами. Все поля и функции наследует от FSM и добавляет свои. Новые атрибуты: текущее состояние второго входа, история по второму входу. Переопределяет конструктор. Новая функция следующего такта функционирования.

Алгоритм:

1) Пользователю представляется выбор фундаментальных классов функций для памяти и комбинационной части автомата (funct_choice.php). Для их представления используются массив двойной вложенности первой размерностью 6, где массив второй вложенности с номером 0 - все функции, 1- сохраняющие 0, 2- сохраняющие 1, 3 - самодвойственные, 4 -линейные, 5-монотонные. Выбор пользователя определяется номером массива^уре1- для комбинационной части, $type2 - для памяти). С помощью механизма сессий происходит передача этих параметров следующему скрипту.

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

3) Пользователь, задавая входные слова автомата, получает возможность следить и управлять функционированием заданного автомата(functioning.php). При первом такте работы создается объект класса FSM(см. auto.inc), с параметрами указанными в предыдущих скриптах.

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

Ли1оЛпс

<?

// абстрактный автомат, от которого наследуют все остальные. class auto { var $in_history=array(); //история входов var $out_history=array(); // история выходов var $state_history=array(); // история состояний var $dimension; //кол-во входов var $step; // номер такта

function init_dimension($number) // задание кол-ва входов {

$this->dimension=$number;

}

}

// наследник auto. Моделирует автомат (2,2,2) c одним входом.

class FSM extends auto //- наследник auto. Моделирует автомат (2,2,2) c одним входом. { var $cur_in1; // текущий вход var $cur_state; // текущее состояние var $cur_out1; //текущий выход

var $delta=array(); //массив определяющий фунцию переходов var $lyampda=array(); // массив определяющий функцию выходов function FSM($number,$arg1,$state,$class1 ,$class2) //конструктор

{

$this->init_dimension($number);

$this->cur_in 1=$arg 1;

$this->cur_state=$state;

$this->lyampda=$class1;

$this->delta=$class2;

$this->step=0;

}

function make_step() // следующий такт {

array_push($this->in_history, $this->cur_in 1); array_push($this->out_history,$this->cur_out1); array_push($this->state_history,$this->cur_state); $this->cur_out1=$this->lyampda[" $this->cur_in1 $this->cur_state"]; $this->cur_state=$this->delta[" $this->cur_in 1 $this->cur_state" ]; $this->step++;

}

// наследник FSM. Моделирует автомат (2,2,2) c двумя входами.

class FSM_2 extends FSM

{

var $cur_in2; //текущий вход №2

var $in_history2=array(); //история второго выхода

function FSM_2($number,$arg1,$arg2,$state,$class1,$class2) //конструктор {

$this->init_dimension($number);

$this->cur_in 1=$arg 1;

$this->cur_state=$state;

$this->lyampda=$class1;

$this->delta=$class2;

$this->cur_in2=$arg2;

$this->step=0;

}

function mk_step() //следующий шаг

{

array_push($this->in_history, $this->cur_in 1); array_push($this->out_history,$this->cur_out1); array_push($this->state_history,$this->cur_state); array_push($this->in_history2,$this->cur_in2);

$this->cur_out1=$this->lyampda["$this->cur_in1$this->cur_in2$this->cur_state"]; $this->cur_state=$this->delta[" $this->cur_in 1 $this->cur_in2$this->cur_state" ]; $this->step++;

}

} ?>

Funct_choice.php

<? error_reporting(0);

echo "<A HREF='index.htm' name=back> Change FSM type </A>

<br>_<br>";

session_start(); // начало сессии (программное решение) echo "<FORM action='avtomat.php?".SID."' name=tye method=POST>"; echo "<p><IMG SRC='fsm(2,2,2).bmp'></p>"; // выбор класса функций для комбинационной части

// определяется двумя параметрам $type1 определяющим тип функций в массиве $t echo "<p>Choose function type for combinatorial part</p>"; $all=array(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15); $t0=array(0,1,2,3,4,5,6,7); $t1=array(1,3,5,7,9,11,13,15); $ts=array(3,5,10,12); $tl=array(0,3,5,6,9,10,12,15); $tm=array(0,1,3,5,7,15); $t=array($all,$t0,$t1,$ts,$tl,$tm); session_register("t");

echo "<select name='type1'> <option selected value=0>All functions</option> <option value=1>Zero preserving function</option> <option value=2>Unity preserving function</option> <option value=3>Self-dual function</option> <option value=4>Linear function</option> <option value=5>Monotone function</option>"; echo "</select>";

// выбор класса функций для памяти (аналогично комб. части) echo "<p>Choose function type for memory</p>"; echo "<select name='type2'> <option selected value=0>All functions</option> <option value=1>Zero preserving function</option> <option value=2>Unity preserving function</option> <option value=3>Self-dual function</option> <option value=4>Linear function</option> <option value=5>Monotone function</option>"; echo "</select>";

echo "<p><INPUT type=submit size=30 name=submit value='Continue'></p>"; echo "</FORM>";?>

Avtomat.php

<?

error_reporting(0);

echo "<A HREF='funct_choice.php' name=back> Init new FSM</A>

<br>_<br>";

session_start(); // открытие сессии (программное решение)

// считывание функций из инициализационного файла $f=array(); $args=array(); $function=array();

$input=fopen("/m/home/stas/public_html/funct","r");

while (!feof($input))

{

$str=fgets($input,4096); $f=explode(" ",$str);

foreach($f as $func) {

list($x,$y)=explode("-",$func); $f1[$x]=$y;

}

array_push($function,$f1);

unset($f);

unset($f1);

}

fclose($input);

// массивы определяющие комбинационную часть и память для автомата // $type1 и $type2 определяют принадлежность к классам и передаются из файла //funct_choive.php, также как и массив $t $com_func=$t [$type 1]; $mem_func=$t[$type2];

session_register("function"); session_register("t");

// выбор функции для комбинационной части автомата echo "<FORM action='functioning.php?".SID."' name=step method=POST>"; echo "Choose function for combinatorial part<br>"; echo "<TABLE CELLSPACING= 1 CELLPADDING= 1 border=1>"; $mass=array(0=>"00" ,1=>"01" ,2=>" 10" ,3=>" 11");

for ($k=0;$k<4;$k++) {

$temp=$mass[$k];

echo "<TR><TD>$temp</TD>";

foreach($com_func as $i)

{

$tmp=$function[$i] [$temp];

echo "<TD>$tmp</TD>"; }

echo "</TR>";

}

echo "<TR><TD>-</TD> ";

foreach($com_func as $key=>$i) {

if ($key==0) {

echo "<TD><input type=radio checked name='komb' value=$i></TD>";

}

else {

echo "<TD><input type=radio name='komb' value=$i></TD>"; }

}

echo "</TR>";

echo "</Table>";

// выбор функции для памяти автомата echo "Choose function for memory <br>";

echo "<Table><TR><TD><TABLE CELLSPACING= 1 CELLPADDING= 1 border=1>"; $mass=array(0=>"00" ,1=>"01" ,2=>" 10" ,3=>" 11");

for ($k=0;$k<4;$k++) {

$temp=$mass[$k];

echo "<TR><TD>$temp</TD>";

foreach($mem_func as $i)

{

$tmp=$function[$i] [$temp];

echo "<TD>$tmp</TD>"; }

echo "</TR>";

}

echo "<TR><TD>-</TD> ";

foreach($mem_func as $key=>$i) {

if ($key==0) {

echo "<TD>

<input type=radio checked name='mem' value=$i>

</TD>"; }

else

{

echo "<TD>

<input type=radio name='mem' value=$i> </TD>";

} }

echo "</TR>";

echo "</Table></TD><TD><IMG SRC='fsm(2,2,2).bmp'></TD></TR></Table>"; // Задание начального входа и состояния для автомата echo "Please, enter Initial state and input<br>";

echo "<Table><TR><TD>Initial state</TD><TD> <input type=text name=state value=0 size=1 maxlength=1></TD></TR>";

echo "<TR><TD>Initial input</TD><TD> <input type=text name=input value=0 size=1 maxlength=1></TD></TR></Table>";

echo " <input type='hidden' name='param' value=1 />";

echo "<INPUT type=submit size=30 name=submit value=' Begin functioning '> \n"; echo "</FORM>"; ?>

Functioning.php

<? error_reporting(0);

require ("/m/home/stas/public_html/auto.inc"); //использование классов из auto.inc echo "<A HREF='funct_choice.php' name=back> Init new FSM </A>

<br>_<br>";

session_start(); //начало сессий

if ($REQUEST_METHOD =="POST") {

$fun1=-1; $fun2=-1;

if ($param==1) // если первый такт работы

{

// echo "state=$state input=$input <br>";

if ((($input!="0") and ($input!="1")) or (($state!="0") and ($state!="1")) or ($state=="") or ($input==""))

//неверно заданы начальное состояние и вход. {

echo "Error: FSM functioning impossible. Please, enter correct initial state and input<br>";

}

else {

$fun1=$komb; $fun2=$mem;

//не заданы функции для комб. части и памяти автомата if (($fun 1 ==-1) or ($fun2==-1)) { echo "Error:Functions were not chosen <br>";

}

else {

// создание объекта класса FSM при первом такте автомата если заданы все функции //для комб. части и памяти автомата и корректно заданы нач. состяние и вход $fsm=new FSM(1,$input,$state,$function[$fun1],$function[$fun2]); echo "<br>"; session_register("fsm");

$fsm->make_step(); // проход первого такта функционирования }

}

}

if ($param==2) //если не первый такт работы {

$size=strlen($input);

for($i=0;$i<$size;$i++) {

$inp=$input[$i];

//если некорректно задан символ в входном слове, то функционирование //заканчивается на этом слове и пишется ошибка

if (($inp=='') or (($inp!="0") and ($inp!="1"))) {

$j=$i+1;

echo "<H3>Error at symbol $j : Functioning after this symbol was stopped </H3><br>";

break; }

// если все в порядке, совершается переход к следующему такту функционирования

else {

$fsm->cur_in 1 =$inp;

$fsm->make_step(); }

}

session_register("fsm"); //автомат с историей передается через механизм сессий }

}

Echo "<FORM action='functioning.php?".SID."' name=step method=POST>"; echo "Step $fsm->step <br>";

//ввод пользователем следующего входного слова echo "Please, enter input word";

echo "<Table><TR><TD width=35%><TABLE CELLSPACING=1 CELLPADDING= 1 border=1>";

echo "<TR><TD>Current state </TD> <TD> $fsm->cur_state </TD></TR>";

echo "<TR><TD>Current input word</TD> <TD><input type=text name=input value='' size=3 maxlength=64></TD></TR>";

echo "<TR><TD>Current output</TD> <TD>$fsm->cur_out1</TD></TR></Table></TD>"; $mass=array(0=>"00" ,1=>"01" ,2=>" 10" ,3=>" 11");

echo "<TD width=23%>Lympda <Table CELLSPACING= 1 CELLPADDING= 1 border=1>"; // вывод текущего состояния и выхода автомата for($q=0;$q<4;$q++)

{

$arg=$mass[$q]; $res=$fsm->lyampda[$arg];

echo "<TR><TD>$arg</TD> <TD>$res</TD></TR>";

}

echo "</Table></TD>";

echo "<TD width=23%>Delta <Table CELLSPACING= 1 CELLPADDING=1 border=1>";

for($q=0;$q<4;$q++) {

$arg=$mass[$q]; $res=$fsm->delta[$arg];

echo "<TR><TD>$arg</TD> <TD>$res</TD></TR>";

}

echo "</Table></TD><TD><IMG SRC='fsm(2,2,2).bmp'></TD> </TR></Table>";

echo " <input type='hidden' name='param' value=2 /> <P> </P>";

echo "<INPUT type=submit size=30 name=submit value- Next Step '> <br>";

$i=count($fsm->in_history);

echo "<p>FSM step history</p>";

echo "<TABLE CELLSPACING= 1 CELLPADDING= 1 border=1>"; echo "<TR><TD>Steps</TD>"; // вывод номера текущего такта

for($j=0;$j<$i;$j++) {

echo "<TD>$j</TD>";

}

echo "</TR>";

// вывод истории автомата по состояниям входам и выходам echo "<TR><TD>Inputs</TD>";

{

$temp=$fsm->in_history [$] ]; ееЬо "<TD>$temp</TD>";

}

echo "</ТЯ>";

echo "<TR><TD>states</TD>"; {

$temp=$fsm->state_h1story ВД ]; echo "<TD>$temp</TD>";

}

echo "<Л"Я>";

echo "<TR><TD>outputs</TD>"; {

$temp=$fsm->out_h1story [$j ]; echo "<TD>$temp</TD>";

}

echo "<Л^>"; echo "</TABLE>";

echo "</FORM>"; ?>

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

ScreenShots из программы

'3 Initialize FSM - Microsoft Internet Explorer Jn

Файл Правка Вид Избранное Сервис Справка ■

* . . в Э Л Назад Вперед Остановить Обновить Домой й Поиск Ссылк

Адрес ||] http://intercom,ru/~stas/avtomat,php?PHPSESSID=e74c04f5cbf3ea58cl3b06bcb090632j i^nepex

Init new FSM

Choose function for combinatorial part

|оо|сП[сП[Г[Г

^ТГГГГ

10 1 0 1 о [ГТ[Г[Г|о~|(Г

□ZZFi7"

Choose function for rnernoiy

[oo^[o [о [о fo pi pi П pi [oTfo fo pi П [о [о pi pi рГо fo П [о pi fo П fo П

рпрпгргргргргргрп

р|7г|7грг~рг~р<?~рг~рг~рг~

Please, enter Initial state and input Initial state [if Initial input |T

Begin functioning

XI —

xo

8(2)

Комбннацн онмая

«in

— fl(xl,x0) f2(xl,x0)

iL

3 Functioning of FSM - Microsoft Internet Explorer

Файл Правка Вид Избранное Сервис Справка J

* . * т о 1 & Назад Вперед Остановить Обновить Доиой & Поиск ССЫЛК1

Адрес 0 http ://intercom. ru/~stas/functioning.php?PHPSE5SID=e74c04f 5cbf3ea58cl 3b06bcb(_^J ^Перех

Init new FSM

Step 12

Please, enter input word

Current state 0

Current input word 1101

Current output 1

Lympda Delta

|ÖÖ[T Щ

[ÏÏ[i

00^ Щ

jopï ïï|ô

XI-

g£z)

Комбннацн онная чип

fl(xl,x(J) f2(xl,x0)

Next Step

FSM step history

Steps [0рГ[2[з[4[5[б[7[8[9рГС1рГТ inputs [о[Т[Т|о[Т[Т[Т|о[Т^|о~[Г

states |Т|0|0|0|Т|Т[Т|Т[0|0[Г[0" outputs |Ö[T[T[T|Ö|Ö|Ö|Öfi[r|Ö~

iL

Приложение 2. Программный текст основного модуля моделирующей

программы в среде Delphi 7

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Grids, Math, Excel2000, OleServer, ActiveX;

type

TForm1 = class(TForm) GroupBox1: TGroupBox; Edit1: TEdit; Label1: TLabel; Edit2: TEdit; Label2: TLabel; GroupBox2: TGroupBox; ww: TStringGrid; Label3: TLabel; Button1: TButton; GroupBox3: TGroupBox; Label5: TLabel; Button2: TButton; Button3: TButton; Edit3: TEdit; Label7: TLabel; Edit4: TEdit; Edit5: TEdit; Label4: TLabel; GroupBox4: TGroupBox; Edit6: TEdit; Edit7: TEdit; Label6: TLabel;

Label8: TLabel; Button4: TButton;

procedure Button1Click(Sender: TObject); function Test(Host, Port: integer): boolean; function TestZero(Host: integer): boolean; procedure Learn(Host, Port: integer); procedure Draw;

procedure Button4Click(Sender: TObject); procedure Button2Click(Sender: TObject); procedure Button3Click(Sender: TObject); private

{ Private declarations } public

{ Public declarations } end; const

MaxSize = 100; var

Form1: TForm1;

W: array[1..MaxSize,1..MaxSize] of extended; M, N: integer;

Hosts: array[1..10000] of integer;

Hits, Misses, Zeros: array[1..10000] of integer;

NCount, MCount: integer;

V, T: extended;

iCount: integer;

implementation {$R *.dfm}

procedure TForm1.Draw; var

i, j : integer; S: string; begin ww.Cells[0,0] := 'W';

for i := 1 to M do ww.Cells[i,0] := 'M'+IntToStr(i); for j := 1 to N do ww.Cells[0,j] := 'N'+IntToStr(j); for i := 1 to M do for j := 1 to N do begin Str(w[j,i]:0:3,S); ww.Cells[i,j] := S; end; end;

procedure TForm1.Button1Click(Sender: TObject); var

i, j, Code: integer; S : string; begin

MCount := StrToInt(Edit1.Text); NCount := StrToInt(Edit2.Text); M := ceil(ln(MCount+1)/ ln(2)); N := NCount; ww.RowCount := N+1; ww.ColCount := M+1;

for i := 1 to M do for j := 1 to N do w[j,i] := 0; Draw;

for i := 1 to MCount do Hosts[i] := 0; S := Edit3.Text; val(S,V,Code); S := Edit5.Text; val(S,T,Code); end;

function TForm1.Test(Host, Port: integer): boolean; var

i, j, Cur: integer;

Sum: array [1..MaxSize] of extended;

NRes: array[1..MaxSize] of integer; begin Cur := Host; i := 1;

for j := 1 to N do begin NRes[j] := 0; Sum[j] := 0; end;

while Cur <> 0 do begin for j := 1 to N do Sum[j] := Sum [j] + w[j,i] * (Cur mod 2); Cur := Cur div 2; inc(i); end;

for j := 1 to N do if Sum[j] >= T then NRes[j] := 1; Test := (NRes[Port] = 1); end;

function TForm1.TestZero(Host: integer): boolean; var

tmp: boolean; j: integer; begin tmp := false;

for j := 1 to N do tmp := tmp or Test(Host,j); TestZero := not tmp; end;

procedure TForm1.Learn(Host, Port: integer); var

MIn: array[1..MaxSize] of integer; NRes: array[1..MaxSize] of integer; i, j, Cur: integer;