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

РГЗ 0J

, , Г ) г - . / ' ' Т

Министерство наукн, высшей школы и технической политики Российской Федерации

Московский ордена Трудового Красного Знамени горный институт

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

ДЕДЕГКАЕВ Альберт Гагеевич

УДК 658.512.22.011.56 (043.3)

ТЕОРИЯ И ПРАКТИКА АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ ПАРАЛЛЕЛЬНО ФУНКЦИОНИРУЮЩИХ

СИСТЕМ ЛОГИЧЕСКОГО УПРАВЛЕНИЯ НА ОСНОВЕ [АРАКТЕРИЗАЦИИ РАЗЛОЖИМОСТИ ЗАКс"А УПРАВЛЕНИЯ

Специальность 05.13.12 — «Системы автом, тизации проектирования (промышленность)»

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

Л1оскпа 1993

Работа выполнена в Северо-Кавказском ордена Дружб народов горно-металлургическом институте и в Московско ордена Трудового Красного Знамени горном институте.

Научный консультант ■-г"-.- академик ГОРБАТОВ В. А. ' ,

* ' /' ; Официальные оппоненты: 11 академик, проф;, докт. техн. наук КОРЯЧКО В. П., ■ : чл.гКор.,-проф.,- докт. техн. наук ЛОХИН В. М.,

' Защита - диссертации состоится «....»■. . . 1993 /2

в /Н. час. ка заседании специализированного совет

Д-053.12.12 Московского горного института по адресу: 117931 Москва, Ленинский проспект, 6.

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

■' Автореферат диссертации разослан « . . . » . . 1993 Ученый секретарь специализированного совета

; проф.,- докт.. техн. наук ФРОЛОВ А. Б.

Ведущая организация — ВНИИ «Альтаир».

проф., докт. техн. наук ТОРХОВ В. 3

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

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

Актуальность проблемы. Большой класс технических систем составляют системы с сосредоточенными параметрами. Параметры могут быть конструктивными: процессор, технологический участок ГАП, память и т. д.; функциональными: алгоритм, величина потока, объем изготовляемой продукции и др. Существенный подкласс этих систем с сосредоточенными параметрами образуют логико-вычислительные системы — программно-аппаратные комплексы, системы управления гибким производством, локальные системы управления технологическим процессом. Описание функционирования систем этого класса осуществляется средствами логического управления. Для автоматизации проектирования таких систем удобной формализацией являются модели СЛУ, которые могут быть представлены функциями на графах. При разработке- математического обеспечения САПР и с целью борьбы с информационным взрывом в ЭВМ решается большой класс оптимизационных задач, порождаемых проблемой уменьшения размерности задач с помощью их декомпозиции. С другой стороны, повышение качества сводится к ослаблению функциональной связности проектируемых систем, которое определяет увеличение их безотказности, уменьшение взаимного влияния компонент системы. Последнее требование определяет вид декомпозиции, а именно — параллельной.

Параллельная декомпозиция соответствует мультипликативной операции декартова произведения. С помощью этой операции решается задача синтеза оптимального распределения процессов по ЭВМ ЛВС при создании отказоустойчивого программного обеспечения. Элементами одного из множеств в этом случае являются ЭВМ сети, а другого — решаемые задачи. Элементы декартова произведения находятся с учетом ограничений, порождаемых функцией совместимости задач, заданной кратностью резервирования каждой задачи и требуемой эффективностью использования вычислительных ресурсов. " : " *

Операция декартова произведения множеств служит эффективным средством, формализации и ряда других задач, таких! "как оптимальное'распределение изделий по обрабатывающим центрам, Оптимальное распределение файлов по дисковым устройствам, оптимальное распределение трансНорта по карьерам и т. д. Решение этих задач сопровождает создание различного рода автоматизированных систем обработки ^информации и управления, среди которых выделим системы логического управления СЛУ, обеспечивающие распараллеливание- управления.

4 Проблема построения Декомпозиции СЛУ исследовалась в работах ряда отечественных и зарубежных ученых, которые создали алгебраическую теорию разложения автомата на-несколько более простых автоматов. Задача декомпозиции автоматов впервые была поставлена Хартманисом (1961 .г.),: который ДЛя её решения предложил специальный язык — язык разбиений со свойством -подстановки (СП-разбиений) ¡и' определил некоторые алгебраические операции над разбиениями. В результате развития языка СП-разбиений Хартманисом совместно со Стирнзом была создана '(1964 г.) абстрактная математическая система — алгебра пар,'-которая определила единую математическую основу всех результатов, полученных на основе изучения пар разбиений. -

"Для расширения возможностей этого подхода Нобуеки, Тадаши. Нориоши предложили (1974 г.) расширение Этой алгебры до алгебры троек, четверок, ..., п-к, что, в свою очередь, "было основано на использовании свойств соответствующих разбиений. ! . -

В работах -Йоли и Гинзбурга (Т964 г.) построение декомпозиции основано на нахождении униформных допустимых разбиений, являющихся частным случаем СП-разбйеввй. Предложенный Кохави метод основан на нахождении ' автомата, эквивалентного заданному, на множестве состояний кб-торого существует хотя бы одно разбиение со свойством под--становки. :

Расширив понятие СП-разбиений введением ПС-связКИ, О. П. -Кузнецов .исследовал (1969 г.) задачу параллельной де-

композиции с разделением входов. Предложенный им,;метод примерам к.сравнительно узкому классу^автоматов, являющемуся подклассом автоматов с, СП-разбиением-.на-; множестве состояний. . , , - г- -.... Более,,полное исследование-проблемы.- связанной; е -деком--подицией, конечных автоматов, содержится в-цикле работ,: выполненныхпод руководством.-; академика-, Л; • Н-.<М'елихова,-В .основу,разработанных-методор и. алгоритмов декомпозиции здесь-положено нахождение; подстановок множества состоя-.' ний. автомата, приводящих, -матрицу смежности^ соответствующего графа к диагональному виду. В свою очередь, иахожде-. ние таких-подстановок требует, перебора-пар разбиений, что практически не реализуемо при разложении автоматов реальной сложности и приводит к необходимости поиска различного рода, эвристических приемов сокращения .перебрра.

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

Принципиально иной подход к решению задачи декомпозиции был предложен в начале 70-х годов [2, 3].-. Он состоит в нахождении и учете запрещенных фигур графа переходов автомата, определяющих его разложимость. В качестве инструмента решения задачи разработан аппарат многокомпо: нентной; раскраски графа, который дозволяет- находить па» раллельную декомпозицию автомата без. громоздкого анализа свойств разбиений на множестве его состояний и-независимо от существования разбиений с заданными свойствами.

Связь темы диссертации с государственными научными программами. Работа выполнялась в рамках Программы исследований в области естественных - наук до 2000 года АН СССР, тема 12.9.1.1.15 «Создание элементов автоматизированного проектирования и управления горнодобывающими предприятиями», Программы Гособразования СССР, Министерства науки, высшей школы и технической политики РФ, раздел 6-.«Разработка теоретических основ проектирования и

создания автоматизированных' и- роботизированных техноло"-" тий "добычи-и -переработки твердых полезных ископаемых», отраслевых Программ Минсудпрома «Парус» и «Компас»:

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

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

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

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

1. Метод преобразования модели, описывающей функционирование СЛУ в модель, определяющую ее структуру и позволяющую установить объективные условия разложимости исходного закона управления на основе определения связно: ста нетерминальных символов по входным терминальным символам '[23].

2.. Идентификация СЛУ и характеризация параллельной декомпозиции "систем различных классов по соответствующей этому классу формализации с целью выбора базовых алгоритмов и программных модулей для проектирования подсистем, параллельное функционирование которых эквивалентно функционированию исходной системы [1, 12, 32].

3. Метод сведения задачи построения параллельной декомпозиции СЛУ к специальной задаче раскраски графов — многокомпонентной раскраске графа зацепления, определяющего функциональную связность состояний исходной модели; процедура преобразования графа переходов заданной СЛУ и полученной раскраски в графы переходов компонент разложения, декартово произведение которых содержит исходный граф [2, 14, 16, 23, 31].

4. Нахождение запрещенных фигур преобразования модели исходной системы в модели компонент разложения при заданных ограничениях на размеры компонент и степень автономности их работы для каждой из предложенных формализации в зависимости от класса системы [9, 11, 20, 22].

5. Методы преобразования моделей расширением носителя, сужением сигнатуры по отношению зацепленное™ и рас-

ширением сигнатуры по отношению идентификации к виду, позволяющему получить удовлетворительное решение [19, 26, 28]. • • , -б. Математическое обеспечение в виде совокупности алгоритмов, реализующих предложенные модельные преобразования, и программное обеспечение в виде пакета прикладных программ, отдельные- модули которого реализуют разработанные в работе или известные ранее алгоритмы, и позволяющее получать в целом решение- задачи, параллельной декомпозиции автоматных операторов '[4, 8, 30].

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

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

Практическое значение работы заключается в разработке:

— методики идентификации СЛУ, и рекомендаций по использованию той или иной формализации в зависимости от класса проектируемого устройства управления; •

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

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

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

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

— алгоритмов модельных преобразований и вычислений,

позволяющих осуществлять автоматизированное проектирование параллельно функционирующих СЛУ по заданному в виде функций на графах закону управления;

— пакета прикладных программ, содержащего совокупность программных модулей, последовательность включения которых зависит от класса проектируемого устройства и бсу-ществляется с помощью программы «Диспетчер».

Реализация результатов работы. На основе полученных результатов разработана система управления погрузочно-транспортными операциями у капитальных рудоспусков и спуско-подъемными операциями на шахтных стволах Ар'хон-ского и Згидского рудников Садонского свинцово-цинкового комбината..

Спроектировано устройство управления процессов спекания на агломерационной машине для завода «Электроцинк».

Разработанный декомпозиционный подход был применен при проектировании системы управления внутришахтным электровозным транспортом и погрузочно-разгрузочными работами на руднике «Молибден» Тырныаузского вольфрамо-молибденового комбината.

В рамках отраслевых программ Минсудпрома «Парус» и «Компас» результаты работы использованы при создании САПР бортовой автоматики . систем жизнеобеспечения корабля.

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

Апробация работы. Основные положения работы докладывались и получили одобрение на семинарах «Оптимизация дискретных систем управления» (Москва, 1972, 1979), «Прикладные вопросы теории систем и системотехники» (Москва, 1973), «Вопросы автоматизированного логического проектирования устройств управления процессами и объектами в промышленности» (Челябинск, 1973), зональной научно-технической конференции «Разработка и внедрение систем автоматизированного проектирования в машиностроении» (Ижевск, 1983), на Всесоюзных симпозиумах «Логическое управление» и координационных совещаниях «Математическое обеспечение интеллектуальных систем САПР — ГАП (Москва, 1977; Баку, 1979; Курск, 1980; Каунас, 1980; Орджоникидзе, 1981; Алушта, 1982; Тбилиси, 1983; Куйбышев, 1985; Ташкент, 1986; Устинов, 1987; Орджоникидзе, 1988; Феодосия, 1989; Симеиз, 1990; Новый Свет, 1991); на Всемирном конгрессе 1ТБ-92 «Информационные коммуникаций, сети, системы и технологии» (Москва, 1992).

Публикации. Основное содержание диссертации отражено в 32 научных работах, в том числе в 1 авторском свидетельстве.

. Автор выражает искреннюю признательность академику В. А. Горбатову за научные консультации и методическую помощь при подготовке диссертации.

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

Постановка задачи параллельной декомпозиции и ее решение с помощью многокомпонентной раскраски графов.

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

Наиболее универсальным видом декомпозиции, обеспечивающим максимально возможное быстродействие, с одной стороны, и минимальную связность ■— с другой, является параллельная декомпозиция с общим входом н общим выходным преобразователем. Ей соответствует разложение графа переходов заданного автомата G =-<5, U> в частичное декартово произведение графов

G, = <S,, U\>\ G2 = <S2, i/2>; ..., Gn — <Sn, Un > такое, что Gern Gh где Gt—граф переходов г'-го компонентного автомата. Построение декомпозиции связано с необходимостью установления взаимнооднозначного соответствия <р между состояниями исходной системы и последовательностями, образованными состояниями компонент разложения. Сложность выполнения этой процедуры оценивается числом всевозможных вариантов соответствия

CifjiS;!...!^!! ,

где 5 — множество состояний исходной СЛУ; St — множество состояний i-й компоненты разложения. В идеальном случае

|S|~|S,XS2X...XSJ и N = S! .

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

ки эффективных алгоритмов нахождения соответствия:^, со-'; храняющего автоматность исходной СЛУ в компонентах разложения, необходимо исследовать причины нарушения свойства автоматкости и описать их формальным образом; т.'е/ необходимо сформулировать и решить характеризационную проблему. . .

При построении некоторой компоненты разложения v входной вектор Хк B3BemHeáeT дугу {sv¡, ,s„ .}, если в заданном автомате есть переход из состояний, отождествленных с: Sv¿, в состояния, отождествлённые с s,-, и этот переход осуществляется по Хк, где 5V¡ —'i-e состояние v-ro компонентно- . го автомата, а также i-я вершина графа переходов v-ro компонентного автомата. •' •'.

Если-состояния sa и sb, для которых переход по входу Хк определен, отождествить с s„a, а состояния sc= F (sa, и ?¡i — F (sf Хк) с sv? и соответственно, то функция Пе-' реходов v-ro компонентного автомата в.точке (sVy. , будет вычисляться неоднозначно, т. е. F (s4XK)-= svp и F (siaXK) = Sv7 одновременно, что свидетельствует о нарушении свойства автоматнОсти в v-й компоненте разложения.-

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

/е/={1,2, ..., |/|}; /е J 2, ..., |У|}, '

значение каждого из которых идентифицирует некоторую вершину графа переходов соответствующей компоненты разложения, - Значение каждого индекса будем ассоциировать с . некоторой краской,' а последовательность индексов — со спектром красок. Теперь задача состоит в. раскраске вершин графа переходов таким образом, чтобы любые две вершины, являющиеся началами одинаково взвешенных дуг с разными концами, не были соцветны ни в одной из соответствующих компонент спектра. Исключение составляют случаи, когда обе дуги-петли или обе дуги образуют одни и те же вершины. Для решения этой задачи предложено строить вспомогательный неориентированный граф G3 = <S, Ц3">, называемый графом .зацепления; носитель которого совпадает; .с носителем графа перехода, а сигнатурой С73 является отношение зацепленности, определяемое выражением

((И А'к, Хт)(Х<<=Хп))(Р^Хк)^*> & F(SjXa) =

& (t ^ а) &(/ = р) & (/ =. Р) & (/ ~ a) ->.{sh Sjj. s U3; {1)

Ребро- (5,, 5;) взвешивается вектором Хк, а так как условию (1) в общем случае может удовлетворять множество различных входных векторов, то-д = <51{/3> является мульти-графом и кратные ребра заменяются одним, взвешенным дизъюнкцией соответствующих входных векторов.

Наряду с и 5;} еI/ для обозначения отно-

шения зацепленности состояний будут также использоваться выражения SlRsJ (Ха, Х?,...,ХК) и соответственно.

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

В случае двухкомпонентной раскраски расширение сигнатуры осуществляется единственным образом по раскраске впервой компоненте. В общем же случае задача оптимального расширения сигнатуры решается, как и задача формирования спектра, поразрядно и перед раскраской в очередной компоненте часть вершин, соцветных в предшествующих компонентах, соединяются между собой, а ранее введенные связи '(SJ&■R') могут исключаться. При этом общее число спектров должно быть больше числа вершин графа, так как некоторые спектры исключаются из раскраски. Действительно, пусть число компонент га = 3 (г, /, к) и состояния за, Яр. 57 соцвётНы в первой компоненте, 4 = £р ='»7 =1. Соединив между собой вершины я*, 5з и яу и задавшись спектром одной из них, например —"(£* = /а = к* =1), мы тем самым исключаем из раскраски спектры

V (¿= 1, /= 1, к = 2); (£ = 1,/ = 1, /с = 3),..„- -' (1 = 1,/ = 1, к-ЧА'!), ' ; . : (г = 1, / = 2, /с = 1), (г = 1, У = 3, /с = 1) , ...,'

. (г - 1, / - |/|,'к= I); ' ' . ■ . .

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

то в принципе могут быть использованы все спектры, т. е. можно избежать избыточности, но при этом непредсказуемо меняются характеристики графа. Так как не существует строгой зависимости ДА (О) = / , я,), где Д/г (<7)—приращение хроматического числа графа при включении в него ребра {я,, 5/}, то для решения практических задач предлагается использовать оценки, основанные на учете вводимых в сигнатуру ребер, пар ребер, троек и т. д., в образовании тех или иных структур графа, в частности полных подграфов. Пусть, например, в сигнатуру графа вводится ребро {я,, и

нужно в подмножествах (классах соцветности) 50ь $02.....

50к, каждое из которых состоит из вершин, соцветных по всем уже сформированным компонентам спектра, найти пары {ха, я?}, которые целесообразно соединить между собой на этом шаге для сохранения условия /г (й)+Ак где к (й)—хроматическое число графа до расширения его сигнатуры; —число красок в у-й компоненте спектра. Для этого предлагается выполнить следующую последовательность процедур:

1) выбрать пару б]) и проверить выполнение условий:

> от, — 2 и — 2;

/ вэ) = 2;

irs.fl Гвр|>те, — 1,

где ра — степень вершины в*, / (в», )—расстояние между вершинами я* и Гя* — окрестность единичного радиуса вершины Яя;

2) если одно из условий п. 1 не выполняется, то перейти к п. 5;

3) вычислить величину р = | {Гя* П Гя?} II {5а,

4) если, р>т, то перейти к п. 1;

5) расширить О ребром {Яа, я?}.

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

J(s„s,) =-—-, (2)

где = |Г5; | —число единиц в ¿-м столбце матрицы смежности й3] /и — | Г5(- П Гзу | — число единиц в пересечении

1-ГО И /-Г0 столбцов. J (st, Sj)= 0-f-°o. При / (s(. , Sj) =0 включение {s;, s/} в сигнатуру не меняет плотности графа, а с ростом / растет вероятность ее увеличения, в частности, если J (si . Sj) =00 и пересечение окрестностей s, и Sj —полный подграф, то его плотность увеличится на 1 включением {$/, Sj). Использование оценки (2) предполагает последовательный подход к решению задачи; по min I выбирается пара вершин из первого класса соцветности, затем — из вто. . \S\

рого и т. д. до тех пор, пока не найдем- пар

для

2(п — 1)

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

ной совокупности ^(«ii. sm> ■■

2(п~\)

= .2

¡=1

Sjj, . •

2 -г

1 fr

5к?)

и

■2f,j+fj

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

Решение задачи декомпозиции при заданных ограничениях

Изложенный подход основан на предположении, что при заданных значениях мощностей множеств красок по компонентам возможна раскраска графа зацепления спектром красок. ^Однако в практике проектирования в условиях заданных ограничений часто возникает ситуация, когда для раскраски графа зацепления по некоторой компоненте необходимо 'больше заданного числа красок. Это может свидетельствовать .как об объективной неразложимости автомата требуемым образом, так и о несовершенстве используемых методов. Если автомат небольшой размерности, то в некоторых случаях можно осуществить такую коррекцию раскраски, при которой число красок уменьшается без порождения нарушений автоматности. Пусть в л>гй компоненте раскраски граф зацепления содержит одну запрещенную фигуру и некоторая краска ш,- соответствует одной только вершине Среди вершин графа найдем такие я*, что

^ЯМ*«, хь ..., Хг)

и

F (sK. Xa) = sa0s„ = F (slt Xa); F (sK, X?) = sb0s< = F(sh

F (sK, X-,,) = s¡0sf = F (s„ X4),

где Ф — отношение соцветности вершин.

Предположим, что вершине sk, удовлетворяющей (3), соответствует краска тк. Если среди вершин графа зацепления, смежных с sit не найдется ни одной, соцветной с sK, то раскраску вершины sr можно изменить с тг па т„, .уменьшив тем самым на единицу число красок.

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

В качестве такого преобразования используется сужение сигнатуры графа. Пусть для v-ro компонентного автомата задано ограничение |Sv|<mv и соответственно необходимо раскрасить граф зацепления по v-й компоненте т» красками. Запрещенными фигурами такой раскраски будут квазиполные подграфы квазиплотпости т, + 1. Поиск распределения квазиполных подграфов, определяющего эффективность сужения сигнатуры, связан с большими вычислительными трудностями, поэтому на практике учитывают распределение не квазиполных' подграфов, а полных подграфов, характеризующих первое распределение.

Целью сужения сигнатуры подграфа -является расщепле-' ние запрещенных фигур раскраски, т. е. уменьшение eFO плотности. При удалении ребра {s,-, Sy} полный граф G плотности р (G) расщепляется на два полных подграфа Gj и G2,

таких, что р (б)) = р (С2) = р (в) — 1 и е Б] <= С2, т. е. удаление одного ребра из полного графа приводит к уменьшению его плотности на единицу. Если удалить еще одно ребро }, то будет выполняться одно из двух условий:

1. [(/£=/) у (яг = V (к —}) V (т =/)] & [(«„.

В первом случае {зт, 5К} смежно с {5(, Зу} и'удаление 18т, 5к! не изменит плотности графа. Но плотность одного из подграфов О] или С2 уменьшится на единицу.

Во втором случае ({$„,, 5К} не смежно с 5у}) при удалении плотность графа уменьшается на единицу и становится равной р (б)—2. Удаление п ребер полного графа уменьшает его плотность на п, если удаляемые ребра попарно не смежны. Полученный при этом граф будет содержать а„+1 полных подграфа плотности р (б) —п, где а„ — п — член геометрической прогрессии со знаменателем д = 2 и первым членом а0 — 1.

Если же среди удаленных ребер содержатся смежные, то плотность полученного графа равна р (О) — (п— 2 (я4—1)).

I

где а(—количество удаленных ребер, инцидентных г-й вершине, причем каждое ребро считается один раз. Отметив, что целью удаления ребра {5/, Яу} является соцветная раскраска вершин я,- и SJ, укажем некоторые свойства сужения сигнатуры.

1. Если из полного графа О плотности р (б) удалить два смежных ребра я,-} и {я,-, я*}, то ребро оказывается тоже удаленным, так как вершина я,- соцветна и с Sj, и с Як • При этом исходный граф распадается на три полных подграфа плотности р (й)—2 каждый.

2. Удаление п ребер, каждое из которых смежно хотя бы с одним из остальных, равносильно удалению полного подграфа, образованного всеми вершинами, коинцидентными удаляемым ребрам. Если таких вершин п, то полученный граф будет содержать п полных подграфа плотности р (С?)— п + 1 каждый.

Оценим влияние сужения сигнатуры на результат декомпозиции. Пусть удалено ребро {зг, взвешенное вектором

Хк и Р (з1,5к) — 5гФ5^ = Р(8], Л'к), Я/ФЯ/. Тогда в г-й компоненте разложения 5, и 5у отождествляются с некоторым состоянием в, , а 5а и яр — с разными состояниями и яу^ и функция переходов г-го компонентного автомата {X, 5У) в точке с координатами (Хк, ) вычисляется неоднозначно. Для восстановления автоматности компонентного автомата

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

Sv, s,), (4)

где х — индекс компоненты, в которой s*. Ф s * , что означает введение нежелательных межкомпонентных связей. Количество возникающих межблочных связей зависит от выбранного варианта расщепления запрещенных фигур. Если расщепление произведено удалением п попарно несмежных ребер, каждое из которых взвешено одной буквой, то система функций переходов v-й компоненты будет содержать М<2п функций вида (4). Такой же эффект в смысле уменьшения плотности графа достигается удалением всех ребер полного подграфа плотности р = п+ 1. В этом случае (п + 1)< < iWlcn (п + 1), причем первое неравенство справедливо, если все удаленные ребра имеют, один и тот же вес, второе — если все веса попарно различны. Кратные ребра учитываются соответствующее число раз. Для оценки вариантов расщеп-ния запрещенных фигур предложен функционал

¡_ 1WI

т\\ '

где [Uj] — множество удаляемых ребер; {Хк} — множество входных терминальных символов, взвешивающих эти ребра.

При наличии нескольких вариантов расщепления, характеризующихся одинаковыми значениями |{t/y}|, выбирается тот, для которого 1 = 1 rain. Это позволяет получить более простую схему восстановления автоматности компонентных автоматов.

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

Полный граф плотности р (G) содержит Cpfo) запрещенных фигур при раскраске красками т. Для некоторых значений р (G) и m фактическое построение всех запрещенных фигур и их минимальное расщепление связано со значительными техническими трудностями и удобнее расщеплять запрещенные фигуры постепенным уменьшением плотности максимально полных подграфов, которое осуществляется следующим образом. Пусть задан граф зацепления G3 =<5, U> и все его максимально полные подграфы G3i =<S<f Uа > плотности р (53/) >т. Построим двухвходовую двоичную таблицу Т, столбцы которой соответствуют подграфам

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

| 1, если ребро содержится в /-м полном подграфе;

^ ) 0 — в противном случае.

Найдем минимальное покрытие столбцов этой таблицы ее строками и из графа зацепления исключим все ребра, вошедшие в найденное покрытие. Получим графы С31 и для них повторим описанную процедуру. После г повторений получим граф С3(г' = <5, >, не содержащий запрещенные фигуры. Для числа шагов ¡г справедливо выражение

1<г<р(0)тах-яг. (5)

Нижний предел этого неравенства достигается, если для всех 031 р (О 31 ) = т + I. Кроме того, нижний предел достигается, если для любого найдется р (О:,,-)—т максимально полных подграфа й31

/ее у, |/| (о, р{в3 ¡)>т+ 1,

таких, что

VU^J)(U¡{}UJ)Ф 0, (6)

V (/, у, А) П С/у П ¿Л) = 0- (7)

Действительно, чтобы плотность полного графа р (С3<)> >ш стала равной т, достаточно из этого графа удалить р (С3/) —т ребер. Для этого в рассматриваемом случае необходимо, чтобы удаляемые ребра входили в минимальное покрытие таблицы Т, а это означает, что должно выполняться неравенство (6). С другой стороны, если допустить, что

Я (Л *е=У)(£/, П и} П ик) = {и.} Ф 0,

то удаление ребра £/, уменьшает на единицу плотности максимальных полных подграфов С7г, (3/, С?к.

Чтобы уменьшить на единицу плотности оставшиеся |/|—2 полных подграфов, требуется удалить не более чем |/|—2 ребер, т. е. общее число удаленных ребер составит |/| — 1 =р (С?/)—гп—1, а это означает, что после удаления ребер, вошедших в минимальное покрытие таблицы Г, граф зацепления еще содержит, по крайней мере, одну запрещенную фигуру к г Это убеждает в необходимости выполнения (6). Следует указать, что при определении минимального покрытия учитываются не только удаляемые ребра, вошедшие в покрытие, но и те ребра, удаление которых обусловлено удалением ребер, вошедших в покрытие. Так, например, если покрытие содержит элементы Sj} и , $„}, то нужно учесть ребро 5К}, которое тоже окажется

удаленным. Верхний предел неравенства ^(5) достигается, если среди максимально полных подграфов найдется хотя бы один С?31 = <5^31 > так, что р ((?,,) = р (С3 )тах >т + 1 и П = 0 для любого у, кроме, быть может, одного или же П = 0 для некоторых к = 1, 2,..., к и П 51=5, П Ь'2=

Наибольший практический интерес представляет' случай, когда г в (5) принимает некоторое промежуточное значение.

г

Тогда возникает задача нахождения покрытия Гс = ш1п2 тч

1=1

при г = гт1г|. Величина г зависит от выбора минимального покрытия и обратно пропорциональна в общем случае величине гДе Л/ — число единиц в произведении строк

г и /, вошедших в выбранное покрытие, а суммирование производится по всем парам элементов покрытия. ,

Если в результате расщепления запрещенных фигур изложенными методами мы не достигаем заданной степени ав* тономности функционирования компонент разложения при сохранении их размеров в заданных пределах, то возникает необходимость привлечения более сложных процедур для поиска приемлемого варианта расщепления запрещенных фигур, смысл которых состоит в нахождении 0' а 1)3 таких, что если {5/, з^^и', то его удаление не порождает нарушений автоматности переходов.

Для того чтобы Sj е и\ необходимо' и достаточно

(V X е (А'о П [Р^Х) — (8)

1 } .

где X—множество входных терминальных символов, для которых! переход из состояния определен.

Достаточность. Пусть условие (8) справедливо. Покажем, что (5/, Предположим, что в рассматриваемой ком-

поненте вершины 5, и «з раскрашены краской дк, а вершины 5, и Я/ —красками уг и д.- соответственно. Без ограничения общности можно положить XsíГ\XsJ = Xl. Тогда система функций переходов содержит следующие две функции, определяемые раскраской вершин: SJ, дь-Р-, (<7К, Х()

и 9с = /\(<7к. Л",). Допустив о = 6, убеждаемся, что соцвет-ная раскраска 5, и не порождает нарушений автоматно-сти, т. е. {йу} е £/'.

Необходимость. Пусть {5(, 5/}е£У'. Предположим, что не выполняется условие (8), т. е. справедливо утверждение

(а ^р е= (X*. п Хч))((Р (5,, Хр)) = заФз? = Р Xр)).

Тогда если 5; и Sj раскрашены в рассматриваемой компоненте <7Ь, а 5а и 5¡5 — и дъ соответственно, то система

функций переходов будет содержать нарушение автоматно-сти в виде

^(<7к. Хр) = я, и Хр) -

Из этого следует } ¿У7, что противоречит условию. Так

как уменьшение числа красок может быть достигнуто только за счет устранения запрещенных фигур, то нас интересует множество и, элементами которого являются ребра, принад- • лежащие запрещенным фигурам. Вместе с тем может оказаться, что и' = 0. В этом случае возможность устранения запрещенных фигур связывается с нахождением (У такого, что

(у Хе^.ПХ,;.))«^^, Х)=5„ =

Пусть Л^. П Х3 — Хр и Х^ П Х^ — X»., поскольку еУ,

то Т7 (я,, Хр.) = = Р (з?, Хр.). Из следует я

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

5;} е и". Если и" = 0, то аналогичным образом находится и'" и т. д.

Необходимость поиска '11', и",... вызвана тем, что по графу зацепления нельзя установить, неизбежна ли неоднозначность функций переходов при заданных ограничениях без фактического построения функций. Это связано с потерей информации о свойствах автоматного оператора при выполнении преобразования Для частичной компенсации дефицита информации и" с целью нахождения оптимального сужения сигнатуры вводится понятие степени зацепленности состояний. Степенью зацепленности состояний 5; и Б] будем называть величину рг/-, равную максимальному значению длины входной последовательности, допустимой для и Яу-и переводящей автомат из в а из Sj—в 5?, где а р. Из определения графа зацепления очевидно {5,, 113

и {5,, ил ->- =0. Для определения степени

зацепленности состояний и необходимо выполнить следующие преобразования над автоматом, заданным матрицей соединений. По матрице соединений С автомата строится граф =<5, из > согласно (1), находятся пары состояний с ри = 0 и пары соответствующих несмежных вершин графа зацепления.

. Строится матрица С2 = СС. При построении С2 операция умножения соответствующих элементов строки и столбца заменяется некоммутативной операцией приписывания элемента-столбца к элементу строки справа, а операция сложения заменяется на дизъюнкцию. Элемент (г, /) матрицы С2 состоит из всех возможных входных последовательностей длины 2, переводящих автомат из состояния ъ Sj. По матрице С2 строится граф 03<2>=< 5, С1/2) >, сигнатура которого определяется соотношением

2

17

{.s„ s,-} e í/3'2) ^ 3 /K«ai (Sh = =

где s¡ /к,2) — состояние, в которое переходит автомат из'£г при поступлении на его вход некоторой последовательности входных терминальных символов длины 2. По графам1 G3 и G3<2> находятся {s¡, Sy}P..„r согласно' выражению jsj, Sy} е.

Аналогично строятся графы G'-3}, G(4\... и находятся множества {s¡, Sj] р;у = 2, 3,.... В общем случае

(Р ¡j = P)+~{s„sJ}<=U¿''-»\ÜS. Состояния s¡ и Sj будем называть 1-зацепленными, если. p¡;- =1; 2-зацепленными, если p¡ ¡ =2, и т. д.; оо — зацепленными будем называть состояния, если

V/>({«„ S)} es U3"»-*{S¡,

При построении зависимой раскраски используется свойство графов зацепления h(G3iK}) ^ k(G3lKil)) и последова-гёльность G3, G3|2), G3(3>, ... строится до тех пор, пока не получим h /nv. На каждом шаге G3iK) G3<"+1> строится множество U3(K)\U 3{к+1\ в результате чего получаем последовательность

В построенных множествах выделяются подмножества, состоящие из ребер графа зацепления, каждое из которых содержится в хотя бы одной запрещенной фигуре раскраски тч красками. Выделенные ребра сопоставляются строками матрицы 7, столбцы которой соответствуют запрещенным фигурам. На пересечении г-й строки с /-м столбцом ставится метка, если í-e ребро графа зацепления содержится в /'-й запрещенной фигуре, прочерк — в противном случае. Нахождение пар смежных вершин, соцветность которых не приводит к неоднозначности функции переходов, осуществляется с помощью выбора соответствующего покрытия столбцов таблицы Т ее строками. Любое из покрытий Т содержит обязательно один элемент, для которого р = рШах>. т. е. один элемент из множества £/3(л-1>\£/1(я'. В качестве такого элемента выбрано, допустим, ребро {s¿, Sy}, взвешенное входной последовательностью ХК1, Хка,..., ХкВыполнение условия s¡ <Ps¿ порождает ограничения на раскраску, а именно

(s¡ Ф Sj) -> (s, Ф S-t) ~у (s-, Ф Sí) . •. -ч- (si Ф s*),

причем

sa = sí(A'K1); sp==sy(A'K,); s7 =s,(A'K,, Хк2)\ Si-Sj(XKi, Хх,)\...\ XK2, Хка^), ~ ¿j{XKÍ, Хщ, ••.) ^кл-l)»

где я, (Хки Хк„ ...) — состояние, в которое перейдет автомат из 5/ при поступлении на его вход последовательности Хк2,....

Согласно свойству транзитивности отношения Ф из множества 1/ выделяются некоторые подмножества, каждое из которых состоит из; попарно соцветных вершин. В таблице Т вычеркиваются строки, соответствующие ребрам-, концы каждого из которых входят в одно выделенное подмножество, и столбцы, покрываемые этими строками. В оставшейся части таблицы вновь выбирается строка, соответствующая новому значению р'тах, и повторяется описанная процедура до тех пор, пока не будут расщеплены (покрыты) все запрещенные фигуры. Если среди полученных на каждом из шагов подмножеств найдутся такие, пересечение которых не пусто, то их объединяют, образуя окончательное разбиение множества на подмножества соцветных вершин. В том случае, если полученная раскраска не удовлетворяет заданным ограничениям, переходят к иным значениям ртзх, р'тах . ••• и т. д.

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

Назовем степенью неопределенности перехода , рав-

к

ную числу дуг, исходящих из и взвешенных буквой Хк. Пусть в результате раскраски по у-й компоненте вершины 5,, 52, ...,5Г графа переходов б оказались соцветными и пусть 5, (Л*к) = 5*, 5г<Хк) — «3, .... 5Г(Л'К)=51. Если вершины 5«, 5т попарно несоцветны в у-й компоненте, то в графе

переходов б, для вершины в-,1 будем иметь = (, где

¿«г —вершина графа переходов, соответствующая раскраске вершин вь Это означает, что из вершины я,/ для

одного и того же входного состояния имеется ( различных переходов. Чтобы ликвидировать эту неопределенность, нужно иметь возможность различать состояния, в которых находятся блоки памяти автомата, соответствующие графам переходов Сь бг,...,(? 1, б,+ ,,..., С этой целью в каждом из блоков необходимо предусмотреть дополнительные элементы.

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

2*

19

у 11 V 12- V 1* -/ 21 V 22 •/ • . V I1 V I2 У

.,11 ..12 .. 18 .. 21 22 .. 2(7 il т2 ' " .."т4.

2 1 л2 ) ■•■< 'г » л2 > '2 > • ■! '-2 1 • • • I 2 ' 2 ) • • •' 2 i

у 11 .."12 .. 1г) .. 21 .. 22 'Ы v ш1 ш2 ' у со",

лт >. т > • • ■ I '*т i лт .> лт . > • ■ • >.лт >••■■) 'т <•:•> '-т. >• • • > /ж . >

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

Для •/■¡"с = -/-max ' имеет место: -

2<ymax<|5,|X|Sa|X ... X|S,-:,|X|5i+,lX ... X|S„|.

С целью оптимального расширения памяти будем находить минимальную длину сочетания компонент спектра красок, на которой можно различить все'состояния' автомата. Пусть граф зацепления содержит полный подграф: 'G3f — = <S[, Ui>, все ребра которого взвешены входным терминальным символом Хк, а все вершины раскрашены краской р по v-й компоненте. Тогда в графе переходов Gv для вершины sp возможно л < |S,-| переходов по одному .входному символу Хк. Чтобы восстановить однозначность л различных переходов v-й компоненты разложения G*. взвешенных, бук-" вой Хк, необходимо расширить соответствующий., блок, памяти /V = logv элементами, где d — число устойчивых состояний элемента памяти, а Д — знак взятия ближайшего большего целого. .

Пусть минимальная длина сочетания компонент спектра равна /т1п = Г и состоит из компонент W\, W2,..., Wi . Раскраска по каждой из компонент Wj разбивает множество вершин графа 5,- на К^ч непересекающихся подмножеств, для различения которых требуется по logd'KWj элементов памяти. Тогда для восстановления автоматности всех переходов из sp взвешенных Хк потребуется элементов памяти

А/, = log, Кт + log, Kw + ... + log, Kw!. (9)

Аналогичные выражения получаются для остальных полных подграфов графа, все вершины которых соцветны в некоторой компоненте. Для нахождения A^in, при котором могут быть ликвидированы все нарушения автоматности переходов во всех компонентах разложения, недостаточно иметь значения (Nsi)mln.

Абсолютно минимальное значение находится перебором по всем i и а не-только по / = /min. В тех же случаях, когда ограниченные вычислительные возможности не позволяют находить абсолютно минимальное значение N, используется следующая упрощенная процедура:

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

— выбираются максимальные по всем I значения соответствующих членов сумм (9). Полученная таким способом сумма (9) и определит искомое значение N.

Характеризация разложимости автомата на основе анализа

графов переходов автономных автоматов по входным терминальным символам

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

Состояниям автомата, удовлетворяющим условию (1), в графе переходов соответствуют вершины, образующие:

— путь;

— контур;

— несвязность вершин;

— различные сочетания перечисленных структур.

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

Действительно, пусть граф переходов автомата содержит путь длиной /, все дуги которого взвешены входным вектором Тогда в графе зацепления имеется полный подграф плотности р (С3) = I, все ребра которого взвешены Хк и для раскраски графа необходимо /г > / красок. Результат сужения сигнатуры этого подграфа существенно зависит от выбора удаляемого ребра, а именно от расстояния в графе переходов между вершинами 5,- и являющимися концами удаляемого ребра. Если это расстояние равно единице, то все вершины рассматриваемого подграфа оказываются соцвет-ными в каждой из компонент. Вместе с тем, выделив путь в автономном графе, можно установить некоторую регулярность присвоения индексов (красок) без ограничений на число красок и без порождения нарушений автоматности.

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

Пусть граф переходов автономного автомата по входному вектору Хк содержит контуры длиной I,. Обозначим через /вр те из которые являются простыми числами, а через и |5г|—максимально допустимые значения мощностей множеств состояний компонент разложения и сформулируем следующие теоремы.

Теорема 1. Если /пр тах> 1|, |52|, то граф переходов автомата непредставим в виде частичного декартова произведения двух графов с заданными мощностями множеств носителей и Бг- Действительно, пусть |52| <^Пршах и пусть контур состоит из вершин 5Л + Ь 5л + 2, ..., 5Л+/Пр1т,ах. Отображение 5К—(51/, 52(), где 5„е5, ХцЕ«,, 52уе52, будем строить покомпонентно, т. е. сначала построим одно из допустимых если такие существуют, а затем построим одно из допустимых 5« 5и • 52у , если такие существуют. Согласно условию теоремы, при построении для некоторого 5П+/П5ц должно принять значение, которое оно имело для 5п + р, где р <с т. Тогда для 5/г+т+,.51< примет значение, которое оно имело для и т. д., т. е. имеет место периодическое повторение упорядоченных (т — р) значений

Допустим р = 1. Тогда длина периодической упорядоченной последовательности равна т — 1, а так как т — 1 не является делителем /пртах то изменение значения вц при переходе из вершины + /„ртах к вершине 5л + 1 не соответствует упорядоченной последовательности принимаемых в, значений, что приводит к нарушению автоматности переходов первой компоненты.

Пусть теперь Кр<т. В этом случае установившаяся периодическая упорядоченная последовательность значений 51и не содержит первого значения «и, а так как контур замкнутый, то опять приходим к нарушению автоматности переходов. Рассмотренные два значения р исчерпывают все возможные случаи. В результате получили нарушение автоматности переходов уже при построении «к-»-^/. при этом можно не рассматривать построение £к5и52у и считать теорему доказанной.

Следствие 1. Если какой-либо из графов автономных автоматов содержит контур нечетной линии, то автомат непредставим в виде декартова произведения при |5!|<2 или |52|<2.

Теорема 2. Если граф переходов автономного автомата содержит контур длиной / = (XV и ц = еу, причем любое раз-

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

Доказательство. Гак как I = |iv, то для построения соответствия достаточно взять |i разных значений su, сопоставить их ц вершинам контура, составляющим путь, и, не прерывая пути, v раз повторить взятые значения su в одном и том же порядке. Повторив это построение для второй компоненты, мы сопоставим каждой вершине контура пару isu, S2j) таким образом, что автоматность переходов в компонентах разложения не будет нарушена.

Однако из-за того, что ¡г = ev, начиная с вершины sn + ц, всем последующим, будут соответствовать те же пары (sH , s2y), что и предыдущим, т. е. построенное соответствие не является взаимооднозначным, что и доказывает теорему.

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

|«S2|>v. В этих ограничениях знак равенства имеет место только в том случае, если заданный автомат представляет собой контур длиной /, в котором все дуги взвешены входным вектором Хк .

Распространив полученные результаты на общий случай, когда число компонент п > 2, можно сформулировать утверждение: если заданы ограничения на мощности носителей компонентных автоматов |51|<ть [S2 [ < т2,..., [5„ [ <tnn, то необходимым условием разложимости является max 1<т0,

Хк

где т0 — наименьший общий знаменатель чисел ть т2, ..., тп.

Практический учёт влияния различных структур автономных автоматов на результаты декомпозиции связан с необходимостью их выявления в заданном графе переходов. Для этой цели предложено использовать процедуру возведения в степень матрицы соединений автомата С, в которой опущены диагональные элементы. В матрице С2 опускаются диагональные элементы и элементы, образованные парами различных терминальных символов. Начиная с 1 = 3, над матрицей С' осуществляются следующие преобразования, имеющие целью формирование списка путей и контуров автономных автоматов длиной I

Если элемент (£, является последовательностью

одинаковых символов, то он сохраняется в матрице, в противном случае первые I — 1 одинаковых символа, идентифицированные номером строки ¡', заносятся в список путей длиной / — 1 автономного автомата по соответствующему входному вектору, а элемент из матрицы исключается.

Если г = / и элемент (/, /) состоит из одинаковых символов, то он заносится в список контуров длиной I, а из матрицы исключается, в противном случае i — 1 первых символа заносятся в список путей, а элемент (¿, /) исключается из матрицы. Процесс возведения в степень продолжается до тех пор, пока хоть один элемент 1-й степени матрицы соединений будет представлять собой последовательность / одинаковых входных терминальных символов.

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

/' = ш,Хга3Х...Хт„, (10)

где /и^^,!, т2 <1521, ...,

При раскраске вершин контура по у-й компоненте т* красками вершины, расстояние между которыми в преобразованном контуре равно тV, оказываются соцветными, а ребра, соединявшие эти вершины в графе зацепления, исключаются. Число красок для раскраски вершин пути автономного автомата задается произвольно как расстояние между двумя ближайшими соцветными вершинами.

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

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

Модуль «Зацепление» реализует алгоритм преобразования графа переходов автомата 6=<{5г}, {II (XУк )}> в граф зацепления С3 =<5, /У(> согласно (1). Входной информацией модуля является квадратная матрица соединений заданного автомата, выходной — треугольная матрица смежности графа зацепления. Процесс построения матрицы смежности графа зацепления сводится к проверке выполнения условия (1) для каждой пары состояний 5г и Sj. Элемент строящейся треугольной матрицы смежности графа зацепления (г, у) равен единице, если в матрице соединений заданно-

го автомата имеются элементы (/, т) и (/, п), идентифицированные одной и той же входной терминальной буквой Хк, причем (тфп) & (¡' = т) & (/ = п).

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

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

Р = Р\ ■ Р2,

где р 1—число анализируемых строк; р2 — число сравнений

л —1 л'

для одной пары и = 2 ^ а/а>: —максимальное зна-

I- 1 1

чение кратности дуг, исходящих из я,-; N — мощность носителя-исходной модели.

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

р2= еЛ^2,

где б < 1 определяется коэффициентом заполнения матрицы соединений и распределением входных символов. При а] = = иг = ... = а„ = 1 получим

^ М1 — /V»

/?, =- и -.

2 2

Модуль «Подграфы» реализует известный алгоритм нахождения максимально пустых подграфов, основанный на построении дерева с анализом окрестностей и неокрестностей вершин. Модуль используется также для нахождения максимально полных . подграфов. Входной информацией модуля при нахождении максимально пустых подграфов является треугольная матрица смежности графа зацепления, а при нахождении полных, подграфов — матрица смежности инверсного графа. Итогом работы модуля в зависимости от режима могут быть списки максимально пустых или максимально полных подграфов, являющихся запрещенными фигурами раскраски.

• . Модуль «Покрытия», в зависимости от настройки, позволяет находить минимальное покрытие вершин графа его мак-

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

Модуль «Раскраска» преобразует максимально пустые подграфы, образующие найденное покрытие, к такому виду, что

У(^,/)(5|,П5/)=0, причем = т!п(1^1Я/Ч),

где 5—1-й максимально пустой подграф, вошедший в минимальное покрытие. После такого преобразования всемэле-ментам каждого из подмножеств вершин присваивается некоторый индекс (краска).

Модуль «Степень зацепленности» осуществляет последовательное возведение в степень матрицы соединений графа переходов с последующим построением графа зацепления соответствующей степени. На каждом шаге после построе-фа зацепления к-й степени формируется список ребер таких, что и1 е из{к~и и С11 е из1к), т. е. находится разность . Работа модуля продолжается до тех пор, пока все ребра, образующие минимальное покрытие запрещенных фигур раскраски, не войдут в одну из формируемых разностей.

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

Модуль «Контуры» Обеспечивает нахождение контуров автономных автоматов по входным терминальным символам. Контуры длиной / находятся последовательным-возведением в степень I матрицы смежности исходного автомата. Каждый шаг возведения в степень сопровождается исключением из полученной матрицы всех элементов, содержащих -хотя бы два различных символа, а также включением в список контуров диагональных элементов, образованных единственным символом.

Модуль «Компоненты» позволяет строить таблицы переходов компонент разложения по матрице соединений задан-

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

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

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

л |{*г}| 1 . и -

которая меняется в пределах —I. Ннжнии предел 0 — достигается в автономных автоматах по одному терминальному символу Хк, а верхний предел достигается, если ни один из терминальных символов не взвешивает более одного перехода в автомате. Оба крайних случая не представляют практического интереса, так как не соответствуют реальным устройствам управления. Эксперименты проводились для различных значений мощности носителя модели 5 сигнатуры и и величины С

Установлено, что от параметров |5| и \и\ исходной модели зависит прежде всего время решения задачи. Мощности носителей компонент разложения 1| зависят от |5| и Ф, а число нежелательных межблочных связей — от СПо величине <3 можно характеризовать условно класс автоматов, к которому принадлежит проектируемый. Так, значениями С}, близкими к нижнему пределу, характеризуется класс микропрограммных автоматов, в которых при незначительном числе входных терминальных символов, соответствующих микропрограммам, реализуется множество внутренних переходов, обеспечивающих выполнение необходимых микро-

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

Значениями <2, близкими к верхнему пределу, характеризуются автоматы контроля и диагностики. В графах переходов таких автоматов доля вершин, которым инцидентны одинаково взвешенные исходящие дуги, как правило, незначительна и мал коэффициент плотности графа зацепления, что позволяет при его раскраске заданным числом красок обходиться без специального преобразования сигнатуры,' а при построении компонент не возникает необходимости в межблочных связях, поскольку автоматность всех переходов обеспечена правильной многокомпонентной раскраской. При построении декомпозиции автоматов контроля и диагностики используются модули «Зацепление», «Подграфы», «Покрытие», «Раскраска» и «Компоненты».

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

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

исполнительными органами. Формальное задание закона управления, реализуемого проектируемой системой, было получено' в результате диалога «заказчик — разработчик» в виде ориентированного взвешенного графа G =<S, U>, каждая из 137 вершин которЬго соответствует некоторому состоянию устройства управления. Дуги графа взвешены значениями входных 24-х компонентных векторов. Каждой компоненте вектора соответствует один из датчиков сигналы с которых-характеризуют ход процесса спекания и поступают по 24- входным каналам. Наиболее существенные длй процесса факторы контролируются группами датчиков:

- Dь D2 — содержание серы в агломерате; • £>3, Dit D5 — теплоизлучение слоя на сбросе агломерата;

-- D g, Z)7, Ds — температура отходящих газов;

D.,, D;o, Dn — разрежение вакуумных камер;

D\2, Du — скорость фильтрации газов;

£)15, Z)16, Di7 — скорость движения аглоленты;

Di8, -Dig, D2q — содержание Q2 в отходящих газах;

£>2ь D22, D2s — содержание Н2Опар в отходящих газах; : D24 — уровень материала в бункере оборотного ' агломерата.

Различные сочетания значений этих факторов образуют входное множество X ={хи х2,..., .tg?}, где X; = (хи, x2i ,..., хги)-

v Выходное множество Y = {уи у2,...,у 12} образовано сигналами управления исполнительных органов, с помощью которых изменяются такие характеристики, как скорость аглоленты (yi), дозировка воды (//5), дозировка газа (уб), соот-йошение шихты и оборотного агломерата ш/о (г/з) и др. Кроме того, выходные сигналы управляют опросом групп датчи: ков в зависимости от хода процесса. Для реализации системы управления тремя параллельно функционирующими подсистемами'' с заданными ограничениями на- их размеры' |S,]<8, |S2|<8, |5з| <4 был построен граф зацепления. G - <5, U:.>. на множествё вершин которого необходимо'" построить- трехкомпопентную раскраску ' с мощностями мно- " жест.ч красок m!=8, т2 — 8, тз = 4. Плотность графа зацепления р (G3) = 5 и в результате раскраски по первой компоненте m = 8 красками множество вершин разбивается на восёмь классов соцветности. В пределах каждого из классов Ki находятся оценки (2) и перед раскраской по второй компоненте сигнатура графа зацепления расширяется отношени-ём: идентификации в соответствии с этими оценками.

В результате получили граф G' — <S, U'y, плотность' которогЬ р (G') — 8; и так как он не содержит квазиполных подграфов, то раскраска'во второй компоненте осуществлена; т2 — 8 красками. Для раскраски по третьей, последней ком1-; поненте вершины, соцветные в первых двух компонёнтах, "со-'

29 7

единили между собой, а ранее введенные связи исключили. Полученный граф G" =<S,U"> содержит три полных подграфа плотности р = 5, которые образуют множество запрещенных фигур раскраски четырьмя красками. Для их расщепления достаточно исключить из графа два ребра {s17, 5вз} и {s42, s56}. Однако такое расщепление не является оптимальным, так как удаление ребра {s42, s56} с последующей соцветной раскраской вершин s42 и s56 приводит к нарушению автоматности переходов в третьей компоненте и соответственно—к неоднозначности вычисления функций, выхо: дов.

При поступлении сигналов с датчиков Dь D3, D6, что свидетельствует о недостатке воды для смачивания агломерационной шихты, система управления должна вырабатывать команду на увеличение дозировки воды (у5), однако в силу нарушения автоматности может быть выработана и другая команда у3 — уменьшение соотношения ш/о, т.-е. нарушено свойство управляемости и для его восстановления необходимо нарушить автономность функционирования третьей подсистемы (допустить межблочные связи). Для нахождения оптимального расщепления запрещенных фигур была применена процедура построения ряда степеней графа зацепления с целью выявления пар состояний с наименьшей степенью зацепленности. Построив множество (J3\U3(2) находим минимальное покрытие его элементами запрещенных фигур. Оно состоит из ребер (s17, s83}, {s46, s91} и {s36, ^119}, взвешенных входными векторами Х2и Х43 и Х&т соответственно. ВЫПОЛНИВ УСЛОВИЯ СОЦВеТНОСТИ S170S83, S46 Ф S91 И S35 Ф

119, необходимо ВЫПОЛНИТЬ Sl7 ^583 (Х21), S46 (Х43) Ф

S91 №з) И s36 (Х87) Фзпэ (Х87), а так как {s,7 (А21), ss3 (Х2,)}, {¿46 (Х43) S9, (Х43)}, {s36 (X87), sug (X87)}ei/3, то все требования соцветности были выполнены и система реализована тремя автономно работающими подсистемами заданных размеров. ■

Система управления на основе декомпозиции реализуемого ею закона была разработана также для автоматизации управления наиболее трудоемкими технологическими операциями обмена вагонеток в околоствольном дворе клетевого ствола; обмена и откатки на поверхности на руднике «Молибден» Тырныаузского вольфрамо-молибденового комбината. <

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

положение толкателей, стопоров и др. В соответствии с конкретной технологической ситуацией система 1 управления вырабатывает такие команды (г/ь у2.....о^), как «открыть (закрыть)' ворота», «пустить толкатель», «пустить опрокидыватель», «открыть тормоз» и др. Необходимые модельные преобразования и процедуры был и выполнены, как и в предыдущем случае, с помощью разработанных инвариантных средств. В итоге была построена система управления, состоящая из четырех параллельно функционирующих подсистем. Предложенные средства автоматизации внедрены в описанных производствах, о чем имеются соответствующие справки о внедрении.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

7. Создано матобеспечение САПР СЛУ, содержащее как известные ранее алгоритмы, так и специально разработанные автором, для выполнения- предложенных:-модельных- преобразований.

8. Создано программное обеспечение в виде пакета прикладных программ, состоящего из программных модулей, ре-; ализующих предложенные алгоритмы. Взаимодействие - от* дельных модулей обеспечивается программой «Диспетчер», Результатом работы системы .являются законы функционирования компонентных подсистем, представленные функциями на графах. : - • - •

9. Полученные научные результаты, предложенные и разработанные методы и средства были использованы при.-проектировании ряда устройств управления технологическими процессами горнодобывающей и . перерабатывающей отраслей и внедрены на заводе «Электроцинк», Тырныаузском вольфрамо-молибденовом комбинате, Садонском свинцово-цинковом комбинате.

Основное содержание диссертации изложено в следующих работах:

1. Дедегкаев А. Г. Некоторые свойства автоматных операторов, -fie допускающих параллельную декомпозицию.— В кн.: Оптимизация, дискретных систем уЦравления.— ГВЦ Госплана СССР, 1972, с. 120—126.^

2. Горбатов В. А., Дедегкаев А. Г. Запрещенные фигуры при парал; дельной декомпозиции автоматов.— В кн.: Оптимизация дискретных' си"-стем управления.— ГВЦ Госплана СССР, 1972, с. 113—120.,

3. Горбатов. В. А., Дедегкаев А. Г. Метод расщепления запрещенных фигур при построении параллельной декомпозиции систем.— В кн.: Прикладные вопросы теории систем ' и системотехники.— МДНТП им, Ф. Э. Дзержинского,: 1973, с. 86—94. "'.'

4. Горбатов В. А., Дедегкаев А. Г., Челноков Н. И. Синтез'управляющих автоматов. :Т. И,—МЭИ, ' 1970, гос. per. № 700218447, с. 22—37.

5. Горбатов В. А., Дедегкаев А. Г., Макаренков С. В. Автоматизация синтеза логических структур на элементах «Аполлон».— МЭИ, 1970, гос. per. № 69034649, с. 64—71.

6. Горбатов В. А., Дедегкаев А. Г., Кузин Л. Т. Автоматизация функционального , проектирования систем логического ' управления.— МИФИ, 1972, гос. рег. № 72007624, с. 48—59.

7. Дедегкаев А. Г. Алгоритмы разложения микропрограммного автомата,—В кн.: Автоматизированные системы проектирования.— МДНТП, 1975, с. 18—24.

8. Дедегкаев А. Г. Декомпозиция нелинейных микропрограмм.— В кн.: Логическое управление в промышленности.— МДНТП, 1977, с. 34—38.

. • 9. Дедегкаев А. Г. Уменьшение связности графа зацепления автоматного графоида.— В кн.: Оптимизация дискретных систем управления.— МДНТП, 1979, с. 52—56.

10. Дедегкаев А. Г. Последовательная декомпозиция не полностью определенных абстрактных автоматов.— В кн.: Логическое управление.— М.: Энергоиздат, 1981, с. 16—19.

II. Дедегкаев А. Г. Расщепление запрещенных фигур параллельной декомпозиции абстрактных автоматов оптимальным расширением памяти.— В кн.: Разработка и внедрение систем автоматизированного проектирования в машиностроении.— Ижевск: ИМИ, 1983, с. 35—39. • ■ 12. Дедегкаев А. Г. Использование зависимой раскраски графов при построении декомпозиции автоматных операторов.— В кн.: Логическое управление в промышленности.— Ижевск, ИМИ, 1984, с. 13—17.

13. Гольдфарб В. И., Дедегкаев А. Г., Торхов В. Л. Повышение производительности труда на основе внедрения систем автоматизированного проектирования и гибких автоматизированных производств. Изв. вузов.— Цветная металлургия, 1985, № 2, с. 112—114.

14. Дедегкаев А. Г. Поразрядное формирование спектра красок.— В кн.: Логическое управление в промышленности.—• Куйбышев: КПИ, 1985, с. 33—36. -

15. Рязанов В. А., Дедегкаев А. Г., Богомолов В. М. Об одном варианте решения проблемы ГАП в пирометаллургии.— В кн.: Математическое обеспечение интегрированных систем САПР—ГАП. Материалы VI координационного совещания.—Куйбышев, 1985, с. 107—109.

16. Дедегкаев А. Г., Арзуманян Г. М. Способ формирования спектра красок вершин графа.— В кн.: Автоматизированное проектирование меха-ноэлектронных систем.— Устинов, 1985, с. 34—38.

17. Дедегкаев А. Г., Дзагоева Ф. X. Приближенное решение задачи соседнего кодирования автоматов.— В кн.: Логическое управление в промышленности.—Куйбышев: КПИ, 1985, с. 92—94.

18. Богомолов В. М., Дедегкаев А. Г., Рязанов В. П. Устройство для управления процессом спекания на агломерационной машине. А. с. № 1691413 (СССР).

19. Дедегкаев А. Г. Оптимальное сужение сигнатуры графа при его раскраске.— В кн.: Логическое управление в промышленности.— Ташкент, АН СССР, 1986, с. 12—15.

20. Дедегкаев А. Г., Арзуманян Г. М. Способ нахождения полных подграфов заданной мощности носителя.— В кн.: Логическое управление в промышленности.— Ташкент, АН СССР, 1986, с. 155—157.

21. Рязанов В. П., Дедегкаев А. Г., Богомолов В. М. Дискретная модель управления в непрерывных металлургических процессах.— В кн.: Логическое управление в промышленности.— Ташкент, АН СССР, 1986, с. 9—11.

22. Дедегкаев А. Г., Арзуманян Г. М. Частотно-матричный способ нахождения максимальных полных подграфов графа.— В кн.: Логическое управление с использованием ЭВМ.— Москва—Ижевск, 1987, с. 34—35.

23. Рязанов В. П., Дедегкаев А. Г., Богомолов В. М. Некоторые аспекты взаимодействия САПР логического управления с информацией об объекте проектирования.— В кн.: Логическое управление с использованием ЭВМ.— Москва — Ижевск, 1987, с. 141 — 143.

24. Дедегкаев А. Г. Последовательное формирование спектра красок при многокомпонентной раскраске графа.— В кн.: Логическое управление с использованием ЭВМ.— Москва — Орджоникидзе, АН СССР, 1988, с. 30—35.

25. Рязанов В. П., Дедегкаев А. Г., Богомолов В. М. Дискретная модель металлургического процесса — источник информации об объекте проектирования на уровне достоверного события.— В кн.: Логическое управление с использованием ЭВМ.— Москва — Орджоникидзе, АН СССР, 1988, с. 336—339.

26. Дедегкаев А. Г., Арзуманян Г. М. Использование раскраски графов для распределения задач по процессорам мультипроцессорной системы. Тезисы докладов на НТК СКГМИ.— Орджоникидзе, 1988, с. 17—19.

27. Дедегкаев А. Г., Рязанов В. П. Влияние информации об объекте проектирования на структуру САПР логического управления.— В кн.: Логическое управление с использованием ЭВМ.— Москва — Симферополь, АН СССР, 1989, с. 183—185.

28. Дедегкаев А. Г. Повышение эффективности метода разложения систем логического управления.— В кн.: Логическое управление с использованием ЭВМ.— Москва—Феодосия, 1991, с. 203—205.

29. Рязанов В. П., Дедегкаев А. Г., Богомолов В. М. Экологические аспекты формирования банка данных САПР.— В кн.: Логическое управление с использованием ЭВМ.— Москва—Симеиз, АН СССР, 1990, с. 84—87.

30. Рязанов В. П., Богомолов В. М., Дедегкаев А. Г. Выработка импульсных воздействий на объект автоматизированного проектирования.— В. кн.: Логическое управление с использованием ЭВМ.— Москва — Феодосия, 1991, с. 76—79.

31. Дедегкаев А. Г., Рязанов В. П. Разработка модели логического управления нестационарными металлургическими процессами.— В кн.: Информационные коммуникации, сети, системы и технологии,— М., 1992, с. 134—135.

32. Рязанов В. П., Дедегкаев А. Г. Влияние информации об объекте проектирования на уровне достоверного события на решение частных задач логического управления.— В кн.: Информационные коммуникации, сети, системы и технологии.— М., 1992, с. 136—140.