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

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

РЗУН Ирина Геннадьевна

МЕТОДЫ СИНТЕЗА И АНАЛИЗА ПРОХОДИМЫХ АВТОМАТОВ В УПРАВЛЕНИИ ТЕХНОЛОГИЧЕСКИМИ ПРОЦЕССАМИ

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

Автореферат

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

Саратов 2005

Работа выполнена в Саратовском государственном университете им. Н.Г. Чернышевского

Научный руководитель-

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

Официальные оппоненты:

доктор технических наук, профессор Твердохлебов Владимир Александрович

кандидат физико-математических наук, доцент

Богомолов Сергей Анатольевич

Ведущая организация

Институт проблем управления РАН, г.Москва

Защита состоится

г. в

на

заседании диссертационного совета К 002.227.01 при Институте проблем точной механики и управления РАН по адресу: 410028, Саратов, ул. Рабочая, 24.

С диссертацией можно ознакомиться в научно-технической библиотеке Института проблем точной механики и управления РАН

Автореферат разослан

г.

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

Актуальность темы. Значение автоматных моделей в решении задач проектирования и технического диагностирования, . изучении процессов формирования и передачи сигналов в живых системах, систематизации и оптимизации управляющих воздействий в экономике стало причиной интенсивных исследований теории автоматов как математической модели сложных систем. Исследованию теории автоматов и вопросам их возможного применения в различных отраслях науки и техники посвящено большое количество работ отечественных и зарубежных авторов. Следует отметить исследования Дж. фон Неймана, А. Гилла, В.М. Глушкова, СВ. Яблонского, П.П. Пархоменко, М.Ф. Каравая, В.Б. Кудрявцева, Б.А. Трахтенброта, A.M. Богомолова, А.Ф. Резчикова, В.А. Твердохлебова, А.А. Сытника.

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

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

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

состояний и подавтоматов. В её основе лежат свойства бесповоротности состояний в процессе их изменения.

Актуальность и необходимость дальнейшего исследования проблемы эффективного управления ТП с учётом диагностирования дефектов в изделиях и технологических операциях и определили выбор темы, целей и задач диссертационной работы. Возникает потребность в разработке математического аппарата, средствами которого можно: 1) определять правильные ТП; 2) представлять ТП с учётом выбранного множества дефектов; 3) решать вопросы интеграции нескольких правильных ТП в единый технологический процесс. Пункты 1) и 2) позволяют разрабатывать стратегии управления технологическими процессами с учётом возникновения дефектов, выделять правильные ТП, выбирать оптимальные правильные стратегии управления и оптимальные стратегии с учётом дефектов.

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

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

- найти специфическое свойство дискретных технологических процессов и определить связь этого свойства со свойством конечных дискретных динамических систем в форме КДА;

- найти основные особенности, соответствующие классу КДА, определяющие бесповторные траектории;

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

- исследовать в классе проходимых КДА операции объединения и пересечения проходимых и частичных проходимых подавтоматов;

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

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

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

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

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

Выносимые на защиту результаты. Работа посвящена исследованию проблем функционирования КДА на основе выделения определенного типа состояний.

В работе получены следующие результаты:

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

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

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

4. В классе проходимых КДА исследованы операции объединения и пересечения. Показана замкнутость класса проходимых автоматов относительно операции объединения и пересечения.

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

6. Разработаны и обоснованы методы поиска стратегии управления технологическими процессами на основе выделения проходимых и частичных проходимых КДА.

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

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

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

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

Новыми являются: исследования классов проходимых и частичных проходимых подавтоматов относительно теоретико-множественных операций объединения и пересечения, их верхних и нижних границ состояний, множеств проходимых состояний;

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

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

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

Достоверность и обоснованность результатов. Все полученные результаты строго доказаны.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на семинарах и конференциях, в том числе международных в Саратовском государственном университете им. Н.Г. Чернышевского, в Новороссийском филиале Кубанского университета (Новороссийск, 2002-2004), Саратовском государственном социально-экономическом университете, Институте проблем точной механики и управления РАН (Саратов, 2002-2004), Центральном научно-исследовательском институте измерительной аппаратуры (Саратов, 2004).

Публикации. По теме диссертации опубликовано 5 статей в сборниках научных трудов и материалах конференций.

Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы из 86 наименований. Объём работы составляет 112 страниц текста, в том числе 3 таблицы и 17 рисунков.

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

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

б

В первой главе рассматриваются известные дискретные структуры: конечные детерминированные автоматы типов Мили и Мура; преходящие, тупиковые и изолированные подавтоматы. Анализируется как возможность применения некоторых известных методов теории экспериментов с КДА к распознаванию технологических процессов, так и невозможность применения некоторых методов. Известные методы теории экспериментов с автоматами базируются на изменениях состояний автомата в целях эксперимента. Вводится класс подавтоматов и автоматов, в который включены дискретные математические структуры, обладающие свойствами не повторять при функционировании своих состояний. Вводимый класс КДА назван классом проходимых автоматов. В зависимости от свойств автомата, подавтоматом которого является проходимый подавтомат, и в соответствии с прикладываемыми к автомату последовательностями входных сигналов, проходимый подавтомат может многократно участвовать в функционировании автомата. Это позволяет представлять в технологических схемах циклические процессы, в состояниях которых содержатся все ингредиенты.

Определение 1.1. Конечным детерминированным автоматом типа Мили называется система пяти объектов A=(S,X,Y,S,X), где S,X и Y-соответственно множества состояний, входных и выходных сигналов, а S- функция переходов вида S:SxX-*S, Л - функция выходов X:SxX-+Y. Состояния и сигналы предполагаются распределенными в абстрактном целочисленном неотрицательном времени соответствии с

уравнениями s(t + l)=S(s(t),x(t)), y(t)=A(s(t),x(t)).

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

1) х(1),дс(2),...,*(<).....jc(fc) - команды на выполнение технологических

операций;

2) j(1),s(2).....j(i),...jc(i) - цепочка технологических состояний,

элементами которой являются пары: где -состояние

изделия в момент - средства выполнения технологических

операций;

3) y(l),y(2).....y(t),..,,y(k) - последовательность результатов контроля.

Процесс выполнения технологической операции x(t), применённый

к технологическому состоянию s(t) по закону, представленный функцией: S: S х X -»5, переводит технологическое с о с т о я в новое технологическое состояние Первой компонентой

состояния являются изделия, полученные из изделия,

представленного в состоянии в результате применения к нему

технологической операции х(t). Технологический процесс определяется в соответствии с разработанной рациональной последовательностью технологических операций. Такой последовательностью является:

х(1),х(2),...,*(/).....jc(fc). В соответствии с этой последовательностью для

каждой операции определяются средства её выполнения: ресурсы, орудия труда и т.д. После каждой технологической операции проводится контроль правильности операций. При задании технологии определяются последовательность технологических операций и последовательность средств Выходные сигналы автомата y(t) е Y представляют результаты контроля выполненной операции. Функцией S:SxX->S определяется результат технологической операции, где

S(s(t),x(t)) = S((a(t), /7(0), x(t)) = s(t +1) = (a(t +1), уЗ(/+1)). В последовательности равенств функция S определяет, что технологическое состояние изделия в результате реализации операции, предписанной

командой средствами выполнения операции переведено в

технологическое состояние a(t+1). Средство /}(t+1) в соответствии со смыслом технологического процесса является определённым технологической картой. Функция определяет зависимость

между результатами контроля изделия и вариантами дефектов.

На основании модели всё множество правильных

технологических процессов представляется как множество путей в дереве, ограниченных висячими вершинами, интерпретируемыми как завершённый правильный ТП. В дереве, соответствующем произвольному технологическому процессу, возможны пути с повтором вершин, что соответствует наличию дефектов, и пути без повторов вершин. Одним из основных способов задания КДАявляется его определение диаграммой Мура, т.е. графом GÀ = (S,p).

С использованием автоматной модели бесповоротность состояний процесса, задаваемого начальным состоянием jse5 и управляющей последовательностью реХ', определяется условием

<yomk-ï)<^ï<.j^k)^*j)~>s(sll,prlp)^s(So,prJp)},rm *=\р\ и |/>|<Н-Определение 1.2. Пусть C=(S,X,5) - автомат без выходов и ses. Множество состояний UcS} где будет

называться множеством достижимых состояний автомата С из состояний S. Для каждых seS и хеХ состояние ô(s,x) будем называть 1-преемником (или преемником) состояния

Определение 1.3. Пусть A=(S,X,Y,â,A)- КДА (полностью или частично определенный). Состояние se S будем называть: ^-проходимым, где если для любого определено;

абсолютно К-проходимым, где KeN, если для любого деХк состояние

является - проходимым (состояния, из которых переходы не

определены, полагаются О-проходимыми); 3) ^-возвратным состоянием, если существует такое

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

перевод которых в себя словами длины невозможен или для которых переходы не определены.

Определение 1.4. Целое неотрицательное число будем называть глубиной проходимости состояния 5 автомата А, если: состояние 5 является абсолютно К„ - проходимым; состояние * не является абсолютно ЛГ0+1 проходимым.

Определение 1.5. Пусть А = (5, X, У, 5, А)- КДА. Подавтомат а = (5„Х,У,5„Х.), где S.cS, <5. хХ)хЯ, и Л„ = Лп(5. хХ)хУ будем

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

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

Определение 1.6. Изолированный подавтомат а = (.5„Х,У,3,,Я.) будем называть неразложимым изолированным подавтоматом, если для любого множества состояний подавтомат

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

подавтоматом.

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

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

Определение 1.8. КДА (всюду определенный) будем называть проходимым автоматом, если в соответствующей ему диаграмме Мура множество вершин диаграммы, имеющих петли, не пусто; если есть дуги, исходящие из вершин с петлями, то они входят только в вершины с петлями; если в диаграмме отсутствуют контуры, образованные из вершин без петель.

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

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

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

Определение 2.1. Пусть а = подавтомат конечного

детерминированного автомата А* (Б,ХМ,Л). Верхней границей

подавтомата а будем называть такое подмножество состояний, для

которого выполняются условия

(V*€€бХ'.)8.($\р)** и (^ебеХ'.)8а(з'.р) = *.

Нижней границей подавтомата а будем называть такое подмножество с 5, состояний, для которого выполняются условия: (V* е 5ДЭ*е Ха)ёа(*,х) = 5аХУр е Х*)<5а (*./>) е 5а;

Множество будем называть множеством внутренних

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

Определение 2.2. Подавтомат а = (5.,-У,Г,<У,,Я,) автомата будем называть проходимым подавтоматом, если у подавтомата а существуют верхняя граница состояний , нижняя граница состояний 5, и выполняется условие

т.е. у подавтомата могут быть циклы

только из состояний множества

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

Определение 2.3. Частичный подавтомат а = (3^,Х,У,5Ш,Х,) автомата будем называть частичным проходимым подавтоматом, если верхняя граница и множество неграничных состояний у него определены как у проходимого подавтомата, а нижняя граница состояний образована состояниями, из которых переходы не определены.

Определение 2.4. Пусть А=(Я,Л',6) - КДА и а = (5т,Х,8,) частичный проходимый подавтомат автомата А (проходимый подавтомат). Подавтомат а будем называть частичным проходимым подавтоматом (проходимым подавтоматом) с максимальной верхней границей состояний, если для любых

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

Теорема 2.1. Пусть А = (8,Х,3) - конечный детерминированный автомат, а = {5й,Х,5.) и Ь = (Зь,Х,ё^)- его проходимые подавтоматы. Верхняя граница состояний и нижняя граница состояний подавтомата с = (5а и^,X,5йид„) определяются равенствами

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

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

Теорема 2.2. Пусть А=(5,Х,3) - конечный детерминированный автомат, а-{!5„Х,5,,) подавтомат автомата А, удовлетворяющий условиям: в диаграмме Мура Д, подавтомата а имеется точно один контур подмножество состояний удовлетворяет условию

верхней границы состояний; подмножество является множеством

достижимых из IV состояний.

Тогда любое (непустое) подмножество И с {«,,«, является

нижней границей состояний частичного проходимого подавтомата с верхней границей состояний если в таком подавтомате £/ остается множеством состояний, достижимых из Ж

Теорема 2.3. В теореме показано, что сильно связный автомат не имеет проходимых подавтоматов.

Глава завершается замечанием о построении всех проходимых подавтоматов для заданного автомата.

В третьей главе представлены основные результаты, характеризующие свойства операций объединения и пересечения в классах проходимых и частичных проходимых подавтоматов представлены в третьей главе диссертации. Проходимые и частичные проходимые подавтоматы являются частями целого, т. е. частями автоматов. Автоматы являются теоретико-множественными структурами, так как образованы из трех множеств 5,ДГ и У и отношениями на них. Функции переходов 8 и функции выходов Я И /I как отношения могут рассматриваться в виде аргументов для теоретико-множественных операций объединения и и пересечения П. Эти операции могут быть взяты за основу для декомпозиции автомата в подавтоматы и композиции подавтоматов.

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

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

Теорема 3.1.Пусть А=(8,Х,5) -КДАи а = (3,,Х,8.)} Ь=($„,Х,6ь)

- частичные проходимые подавтоматы автомата А. Тогда: 1) подавтомат является частичным проходимым подавтоматом; 2) подавтомат может содержать циклы, т. е. не являться

частичным проходимым подавтоматом.

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

Теорема 3.2. Существуют конечные детерминированные автоматы вида и их частичные проходимые подавтоматы для

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

Теорема 3.3. Данная теорема показывает, что класс проходимых подавтоматов замкнут по операциям объединения и пересечения.

В теоремах 3.4 и 3.5 содержатся правила вычисления верхних и нижних границ состояний для проходимых подавтоматов. Рассмотрены два случая: границы подавтоматов содержатся в границе автомата и границы подавтоматов выделяются в автомате произвольно.

Теорема 3.4. Пусть л = (5,лг,£) - КДА и а = (5.,ь = (зь,х,зь) -проходимые подавтоматы автомата А, для которых выполняется условие

Тогда верхние границы состояний соответственно проходимых подавтоматов А, =(5й Г\5ь,Х,б. Г)£4) и и^.Л'.г.и^) определяются равенствами: 5(аПЬ)=57п5^,

Теорема 3.5. Пусть А=(3,Х,8)- КДА, а = (5.,л',<5.)и Ь=(.5ь,Х,8,)- его

проходимые подавтоматы и выполняются условия ЗыжБл. Тогда

верхние границы состояний соответственно проходимых

подавтоматов определяются

равенствами:

= П54)1)(5. П14)1)(5» = (5. иЛ)-((Л ПО, где

IV = ^ е 1а Л16 & ((V«' е5аКУхЕ *) * л V (У«* е е Х)5{э',х) * 5)}.

Понятия частичного проходимого и проходимого подавтоматов определены на основе свойств диаграммы Мура. В теореме 3.6 эти свойства конкретизированы как свойства состояний подавтоматов.

Теорема 3.6. Подавтомат конечного детерминированного автомата является частичным проходимым подавтоматом тогда и только тогда, когда каждое из его состояний удовлетворяет одному из следующих условий: 1) состояние является 0 - проходимым (т.е. переходы из состояния не определены); 2) если состояние не является 0 - проходимым, то оно - проходимо для любого (состояние не принадлежит

множеству достижимых из него состояний).

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

Теорема 3.7. Пусть А=(5,Х,У,5,Х) - проходимый (конечный детерминированный) автомат, у которого множество 1 - проходимых состояний не пусто. Тогда у автомата А существуют два подавтомата

удовлетворяющие условиям: подавтомат является частичным проходимым подавтоматом;

подавтомат является рефлексивным изолированным подавтоматом;

существует такое доопределение на множестве функции до функции и функции до функции что

Глава завершается методом построения множества всех подмножеств состояний автомата, которые являются нижними границами состояний проходимых подавтоматов.

Метод построения множества всех нижних границ состояний проходимых подавтоматов.

1. В множестве состояний £ выделяется подмножество IV, тех состояний, которым в диаграмме Мура для автомата А соответствуют вершины с петлями. Полагаем

2. Из подмножества состояний W¡ исключаются все те состояния, из которых достижимо, по крайней мере, одно состояние, не принадлежащее

Полученное множество полагаем множеством Если при

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

3. Для полученного при реализации этапа 2 множества состояний строится разбиение где для каждого подмножество

является множеством состояний, связанных переходами состояний (компонентой связности в диаграмме Мура для автомата А).

4. Множество АС1 строится как результат замыкания множества

по операции объединения множеств

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

При построении автоматной модели технологических процессов предполагается, что состояние технологического процесса в

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

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

процесса. Каждое состояние и входной сигнал однозначно

определяют состояние и выходной сигнал или

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

разделить признаки операции и признаки состояний технологического процесса, рассмотрим автомат Мура В={8,Х,У,8,р), где 5,Х,У и 5 имеют тот же смысл, что и для автоматов Мили, отображение вида Это позволяет последовательности состояний ш технологического процесса сопоставлять последовательность выходных сигналов: Ь=мЫм(3(.1а>х1,))"М(3(1(,>РУ)- Естественным является предположение о том, что возможные дефекты технологического процесса ограничены дополнительными предположениями. Рассмотрим предположение, когда независимо от момента времени при нарушении технологического

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

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

= о > -РП /О) и <г>(<5( . РП , И^о >Р>°) = где

ОИйс^ //(■*. Р> 0 = /¿СОМ«*рг,+\р))..-м(8рг1+\.....ср)), где с=|До<(5с-1.

Рассмотрим - КДА типа Мура и отображение

вида Тогда состояние технологического процесса, заданного

начальным состоянием 10еЗ последовательностью р = и

отображение при однозначно определено наблюдаемой

последовательностью выходных сигналов, если разрешим предикат

где р = ф0).

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

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

технологических процессов); (конкретный

технологический процесс без нарушений).

Требуется проверить разрешимость предиката <р<ф) = .М<р) &Р'(зо,рХ<р) &....&Г'(*о,р,с-1,<р)&Го(50,<р)

(выполнение предиката Р[з„,р,<р) означает, что по наблюдаемым признакам состояний технологического процесса однозначно определяется возникновение дефекта, время (место в процессе) возникновения дефекта и дефектное состояние процесса).

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

отличии последовательностей выходных сигналов автомата от одной эталонной последовательности. Последовательность состояний

•••*/,) и последовательность множеств состояний М.^С^о»^,^))'—.^(^О«*/,»^"-*!,)), совмещенные в

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

Ы^о.*,, ))).........*,.])

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

6(яо>Р>*)*И где 0 = <р(3(зо,ргир))

н(50,р,^)=нх50,рх<р)&нхз0,ра,д>)&..лн^0,р>с-1^)&н^0,<р\ с = \р\_

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

Заданы: 1) КДА типа Мура В=(5,Х,У,3,//); 2) отображение <р вида

<р:5-¥р(5)\ 3) состояние и входная последовательность

Требуется проверить разрешимость (выполнимость) предиката Н(хя,р,<р)= Н'(з0,р,1,<р)у Н'^0,р,2,<р)ч......\/Н'(за,р,с-\,<р)

Теорема 4.1. Предикаты Р^,р,<р) и Н^,р,<р) алгоритмически

разрешимы.

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

Метод проверки диагностируемости технологического процесса. Исходные данные: А = (5,X,У,5,X), р = Х^Х^ • ••Х^ />($).

1.

2.

4. Для каждого j,0£j¿c и каждых 5,$'еЛ/Десли |а/;|>2)

проверяется неравенство х{5,р1)ф (Л(\и,/)- отметка состояния

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

Рассматриваемая в методе диагностируемость соответствует пассивному эксперименту с автоматом А, то есть, только наблюдению признаков состояний технологического процесса. Если рассматриваемый технологический процесс не оказался диагностируемым, то при реализации метода обнаруживаются состояния, для которых требуется изменить средства, условия или режим диагностирования. Метод позволяет точно определить, какое состояние технологического процесса (представляющее запланированное состояние или состояние с дефектом) неотличимо от других состояний. Это позволяет выявить места для повышения эффективности диагностирования состояний технологического процесса. В случае, когда требуется только проверять, является ли реализованный технологический процесс соответствующим запланированному, решается задача контроля (по некоторым ГОСТам задача проверки работоспособности).

Метод проверки контролепригодности технологического процесса.

Для каждого и каждого проверяется

неравенство Х{5,р1)*Х{з1),р1).

Если все определенные в неравенства выполняются, то технологический процесс, определенный данными по

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

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

ЗАКЛЮЧЕНИЕ

В результате исследований получены следующие результаты:

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

«преходящего» подавтомата А. Гилла и представляющего свойство функционирования без повторения пройденных состояний.

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ

1. Рзун И.Г. Функциональная декомпозиция конечных автоматов / И.Г. Рзун // Теоретические проблемы информатики и ее приложений: Межвуз. сб. науч. тр. Саратов: Изд-во Сарат. гос. ун-та, 2002. Вып. 4. С. 120-126.

2. Рзун И.Г. Функциональные свойства при декомпозиции конечных автоматов / И.Г. Рзун // Аспирант и соискатель. 2003. № 3 (16). С. 26-31.

3. Рзун И.Г. Эффективность программных средств в процессе управления / И.Г. Рзун // ИНФ0-2000: Сб. науч.-метод. тр. Новороссийск: Новороссийский филиал Кубанского гос. ун-та, 2000. С. 32-38.

4. Рзун И.Г. Об одном подходе к распознаванию автомата с изменениями состояний в циклах/ А.А. Сытник, А.Н. Кунявская, И.Г. Рзун // Теоретические проблемы информатики и ее приложений: Межвуз. сб. науч. тр. Саратов: Изд-во Сарат. гос. ун-та, 2002. Вып. 5. С. 150-153.

5. Рзун И.Г. О некоторых свойствах проходимых автоматов / И.Г. Рзун, А.А. Сытник // Теоретические проблемы информатики и ее приложений: Межвуз. сб. науч. тр. Саратов: Изд-во Сарат. гос. ун-та, 2004. Вып. 5. С.170-174.

РЗУН Ирина Геннадьевна

МЕТОДЫ СИНТЕЗА И АНАЛИЗА ПРОХОДИМЫХ АВТОМАТОВ В УПРАВЛЕНИИ ТЕХНОЛОГИЧЕСКИМИ ПРОЦЕССАМИ

Автореферат

Корректор О.А.Панина Лицензия ИД №06268 от14.11.01

Подписано в печать 25.05.05

Бум. тип. Усл.печ.л. 1,0

Тираж 100 экз. Заказ 212

Саратовский государственный технический университет

410054, Саратов, ул. Политехническая, 77

Копипринтер СГТУ, 410054, Саратов, ул. Политехническая, 77

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

■■лЛГ-íf iiifX'

ÎiijîÈiïrtï»

1 3 ИЮЛ 2005 » uwt^rfu}

ЧШ

Введение.

Глава I. Конечный детерминированный автомат и классификация подавтоматов.

Проходимые автоматы.

Глава II. Проходимые и частичные проходимые подавтоматы, верхние и нижние границы состояний.

Глава III. Операции объединения и пересечения проходимых и частичных проходимых подавтоматов.

Глава IV. Приложение проходимых и частичных проходимых подавтоматов.

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

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

Математическая модель в виде конечного детерминированного автомата без выходов А = где S - конечное множество состояний, X - конечное множество входных сигналов, ад- функция переходов вида 5: Sx X S, может описывать процессы, если полагать, что

-s e S - состояние процесса,

- x e X — причина изменения состояния,

- S(s,x) — новое состояние процесса, где 6 определяет свойства процесса. С использованием автоматной модели бесповоротность состояний процесса, задаваемого начальным состоянием SQ е S и управляющей последовательностью р е X*, определяется условием: (V0 < i < к - lXvi <j< k)[i{j S(s0,PriP) ф s(s0,PrjPl где к = \Р\ и |/>| < |s|.

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

Конечный детерминированный автомат как структура с полностью определенной функцией переходов 5: S*X-+S в траектории изменений состояний, не меньшей по длине чем \s\ + l, должен иметь цикл (или петлю).

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

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

Конечный детерминированный автомат (типа Мили) А = (5,Х,:к,5,Л) используется как логико-функциональная модель, формализующая логические и функциональные связи ингредиентов, на основе следующей интерпретации:

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

- входной сигнал соответствует технологической операции;

- выходной сигнал y(t) рассматривается как информация обратной связи, характеризующая (производственный) процесс, порождаемый ^(г) и *(/);

- состояние s(r + l) = <5(s(f),*(/)) соответствует ингредиентам, полученным из s(t) в результате реализации x(t).

- Такая интерпретация представлена схемой: технологическая набор v операция . набор ингредиентов \ / ингредиентов и отличается от схем, исследуемых в большинстве работ, например, Первозванский А.А. ([59], 1975) исследует схему вида технологическая \ продукт / технологическая операция \ J. операция » в которой связь устанавливается между операциями через продукты, т.е. затрачиваемые или выпускаемые ингредиенты. В этой же работе полагаются типовыми следующие структуры: - последовательная, сходящаяся, сходящаяся - расходящаяся, структура с реверсом (материальной обратной связью (с. 21). «Функционирование производственной системы может быть математически описано как процесс изменения состояния агрегатов системы (переходов с одной операции на другую) и процесс изменения состояния складов (изменения количества продуктов, хранящихся в них . ([59], с.37)>>.

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

Обоснование выделенного основного положения состоит в том, что повторение состояния s(t) через к тактов (s(*) = s(t + к)) в траектории изменений состояний автомата А соответствует: лишней» части технологического процесса, так как в состоянии автомата представлены все ингредиенты, включая промежуточные или конечные продукты; увеличение длительности технологического процесса (который моделирует автомат А); затрата ресурсов на «лишние» технологические операции; преодоление трудностей при организации возврата к моменту t + к к тем же ингредиентам, которые имелись в момент t.

В работе Ч.Хоара [78] исследуются взаимодействующие последовательные процессы. Как отмечает автор «основная идея заключается в том, что эти системы (вычислительные системы, непрерывно действующие и взаимодействующие со своим окружением - пояснение соискателя) без труда можно разложить на параллельно работающие подсистемы. (с.9).» Это другая постановка задач, отличная от цели диссертации. Имеется совпадение в некоторых исследуемых вопросах, например, Ч.Хоар рассматривает свой подход, как основу для избежания таких ошибок как зацикливание ([78], с.10.). Им даются «строгие определения понятия процесса и способов построения процессов ([78], с.10.)». Сравнение подхода к анализу процессов, проведенного Ч.Хоаром, и подхода, принятого в диссертации, показывает их существенное различие. Более четко позиция Ч.Хоара представлена в его понимании «процесса как математической абстракции взаимодействия системы и ее окружения ([78], с. 14).» В диссертации технологический процесс предполагается полностью определенным свойствами конечного детерминированного автомата, являющегося математической моделью возможных вариантов отношений ингредиентов и технологических операций.

Каждый реальный ингредиент (работник и т.п.) имеет интервал времени, в течение которого он существует и эффективно участвует в процессе производства. В автоматной модели этот интервал стянут в точку и, следовательно, стянут в точку и, следовательно, совмещен во времени с другими ингредиентами. Аналогичное предположение принимается для технологических операций и является достаточно распространенным («Считается, что конкретное событие в жизни объекта происходит мгновенно, т.е. является элементарным действием, не имеющим протяженности во времени (Ч.Хоар, [78], с. 18)». Этим предположением реальная протяженность существования (или использования) ингредиентов и действия технологических операций исключается из рассмотрения и основным полагается следование операций относительно принятого абстрактного времени.

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

Для решения вопросов анализа, синтеза, оптимизации и распознавания траекторий состояний, технологических процессов одного свойства предшествования и следования во времени технологических операций недостаточно. В связи с этим отношение порядка предшествования и следования во времени для операций дополняется отношением «близости» между состояниями технологического процесса.

В основу идей и средств, с помощью которых состояния технологических процессов характеризуются как «близкие» (допускающие переход технологического процесса из одного состояния в другое) или как не допустимые для непосредственного следования, состояний друг за другом, в диссертации взяты работы М. Арбиба [1], [2] и [5]. Идея М. Арбиба построить дискретный аналог непрерывности на базе отношения толерантности, то есть, рефлексивного и симметричного отношения, может быть использована для определения близких, допустимых переходов, состояний. Для этого в диссертации рассматриваются бинарные отношения толерантности р1,р2,.,рсо, каждое из которых задается пары «близких» для переходов состояний. Если, например, бинарное отношение р{ вида р{ сSxS содержит пару (s^s^Je р,., то изменение в технологическом процессе состояния sv на состояние s допустимо по смыслу технологических действий. Набор бинарных отношений р1,р2,.,ра) вида Pi a SxS, где \<i<co, имеющих содержательную интерпретацию как «близость» состояний (набор ингредиентов) технологических процессов, позволяет давать достаточно глубокую и полную характеристику технологическим схемам. Используя бинарное отношение на множестве состояний s технологического процесса можно, например, задавать близость» состояний, которые только по одному из градиентов различаются количественно. Переходы между такими состояниями определяются возможностями транспортных средств и наличием должного количества ингредиента для транспортировки. Покрытие технологической схемы бинарными отношениями, характеризующими содержательные варианты «близости» состояний, принципиально углубляет возможности использования предлагаемого формализма для решения задач поиска, анализа, оптимизации и распознавания стратегии управления производством.

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

В первой главе диссертации рассматриваются известные дискретные структуры: конечные детерминированные автоматы типов Мили и Мура; проходящие, тупиковые и изолированные подавтоматы. На содержательном уровне вводятся новые виды подавтоматов: проходимые подавтоматы и частичные проходимые подавтоматы. Определяются /С-проходимые и абсолютно iC-проходимые состояния автоматов. Здесь же анализируется возможность применения известных методов теории экспериментов с конечными детерминированными автоматами к распознаванию технологических процессов и поясняется невозможность применения таких методов: известные методы теории экспериментов с автоматами базируются на изменениях состояний автомата в целях эксперимента. В технологических процессах изменения состояний определяются спецификой технологического процесса.

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

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

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

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

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

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

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

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

В теореме 3.3 показано, то класс проходимых подавтоматов замкнут по операциям объединения и пересечения.

В теоремах 3.4 и 3.5 содержатся правила вычисления верхних и нижних границ состояний для проходимых подавтоматов. Разделены два случая: границы подавтоматов содержатся в границе автомата и границы подавтоматов выделяются в автомате произвольно.

Понятия частичного проходимого и проходимого подавтоматов определены на основе свойств диаграммы Мура. В теореме 3.6 эти свойства конкретизированы как свойства состояний подавтоматов. В теореме 3.7 содержится существенная характеристика строения проходимого подавтомата:

- существование у автомата частичного проходимого подавтомата,

- существование у автомата рефлексивного (состояния с петлями) изолированного подавтомата,

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

Рассмотрен пример (таблица 3.1 и рис.3.4) проходимого автомата с указанием верхней и нижней границ состояний, множества проходимых состояний. Глава 3 завершается методом построения множества всех подмножеств состояний автомата, которые являются нижними границами состояний проходимых подавтоматов.

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

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

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

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

Теоремой 4.1 показывается алгоритмическая разрешимость предикатов, которые представляют решения задач.

В этой главе приводятся разработанные методы:

- Метод проверки диагностируемости технологического процесса,

- Метод проверки контролепригодности технологического процесса,

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

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

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

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

ЗАКЛЮЧЕНИЕ

1. Введено понятие проходимого автомата, являющееся конкретизацией понятия "преходящего" подавтомата (А. Гилл, [3], с. 45) и представляющего свойство функционирования без повторения пройденных состояний. Найдена интерпретация проходимых автоматов как моделей технологических процессов, вычислительных процессов и др.

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

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

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

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

Новыми являются:

1. Arbib М. Automata theory and control theory: a rapprochement, Automatica, 3: 161-189. 1966.

2. Arbib M. Tolerance automata, Kybernetik, 3: 223 233, 1967.

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

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

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

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

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

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

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

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

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

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

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

14. Богомолов С.А. О восстановлении автомата по экспериментам. Дискретная математика. 1989. Т.1. Вып.1. С. 135-146.

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

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

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

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

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

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

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

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

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

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

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

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

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

28. Глушков В.М. Синтез цифровых автоматов, Наука, М., 1962.

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

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

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

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

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

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

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

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

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

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

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

40. Каток А.Б., Хасселблат Б. Введение в современную теорию динамических систем, М., 1999.

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

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

43. Креницкий А. П. Информационное обеспечение САПР. Материалы зимней школы по управлению вычислительными и контрольно -измерительными комплексами. Саратов. Изд-во СГУ. 1990.

44. Креницкий А.П. Информационные среды САПР дискретных систем. Доклады РАЕН (секция информатики и кибернетики). Выпуск 2. Саратов. Изд- во ГУНЦ "Колледж" . 1997.

45. Креницкий А.П. Об одном подходе к созданию информационного обеспечения САПР дискретных систем. Теоретические проблемы информатики и ее приложений. Саратов. Изд- во ГУНЦ "Колледж". 1997.

46. Креницкий А.П., Сытник А.А. Универсальные модели и информационные технологии в проектировании дискретных систем. Материалы Всероссийской конференции "Телематика- 97". С-Петербург. 1997.

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

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

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

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

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

52. Мур Э. Умозрительные эксперименты с последовательностными машинами. Автоматы, ИИЛ. М., 1956.

53. Нахапетян Е.Г. Диагностирование оборудования гибкого автоматизированного производства. Наука, М., 1985.

54. Нейлор Т. Машинные иметационные эксперименты с моделями экономических систем, Мир, М., 1975.

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

56. Осетинский Н.И. Обзор некоторых результатов по современной теории систем. Математические методы в теории систем, Мир, М., 1979.

57. Основы автоматизации машиностроительного производства. Высшая школа, М., 1999.

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

59. Первозванский А.А. Математические модели в управлении производством, Наука. М., 1975.

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

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

62. Рзун И.Г. Функциональная декомпозиция конечных автоматов. Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений Вып 4.- Саратов.- Изд-во Сарат.ун-та. 2002. С. 120-126

63. Рзун И.Г. Функциональные свойства при декомпозиции конечных автоматов Журнал актуальной научной информации «Аспирант и соискатель», № 2003 г. с.219-225

64. Рзун И.Г. Эффективность программных средств в процессе управления. Сборник научно-методических трудов. Новороссийский филиал Кубанского государственного университета. Новороссийск, НГМА. 2000 г. С.45-47

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

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

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

68. Сытник А.А., Креницкий А.П. Информационные технологии в проектировании дискретных систем. Материалы семинара "Интеллектуальные средства диагностирования РЭА". Ленинград. 1991.

69. Сытник А.А., Рзун И.Г. О некоторых свойствах проходимых автоматов. Межвузовский сборник научных трудов. Теоретические проблемы информатики и ее приложений Вып 5.- Саратов.- Изд-во Сарат.ун-та. 2004. С. 170-174.

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

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

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

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

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

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

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

77. Хоар Ч. Взаимодействующие последовательные процессы. Мир. М., 1989.

78. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. Москва, Санкт-Петербург-Киев. 2002.

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

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

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

82. Шалыто А.А. Алгоритмизация и программирование задач логического управления. Наука, С.-Петербург, 1999.

83. Шпур Г., Краузе Ф.-Л. Автоматизированное проектирование в машиностроении. М., Машиностроение, 1988.

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

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