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

На правср цу^опис^ ^

Горбатов Александр Вячеславович} С Я Н'З ¿С»С/^

УДК 681.3.02

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

05.13.12 — «Системы автоматизации проектирования»

Автореферат диссертации на соискание ученой степени доктора технических наук

Москва —2000

Диссертация выполнена в Московском государственном горном университете.

г

Научный консультант

Лауреат Государственной премии СССР, проф., докт. техн. наук Л. П. Рябов

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

Заслуженный деятель науки РФ, проф., докт. техн. наук А. И. Галушкин, проф., докт. техн. наук Н. И. Федунец, Заслуженный деятель науки РФ, проф., докт. ф.-м. наук В. Ф. Крапивин

Ведущее предприятие

Московский государственный институт радиотехники, электроники и автоматики (технический университет)

Защита диссертации состоится 27 декабря 2000 г. в 14 час. 30 мин. на заседании диссертационного совета Д.053.12.12 в Московском государственном горном университете по адресу: 117935, Москва, Ленинский проспект, 6

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

Автореферат разослан 27 ноября 2000 г.

Ученый секретарь диссертационного совета:

доц., канд. техн. наук М. А. Редкозубое

Общая характеристика работы

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

высокопроизводительных информационных технологий, включая как решение проблем повышения быстродействия элементного уровня, так и организацию параллельных вычислительных процессов. На всех уровнях создания таких технологий при поиске оптимальных решений возникает проблема их перебора. Известно, что при линейном увеличении размерности пространства, в котором ищется оптимальное решение, число вариантов решения растет комбинаторно. Отсюда возникла проблема: понизить размерность пространства путем представления его в виде декомпозиции пространств меньшей размерности — проблема функциональной декомпозиции. Эта проблема многократно формулировалась известными учеными в период 1898—1937 г.г.: Анри Пуанкаре в 1898 г., в связи с большим интересом к электрическим (Дж. Кирхгофф) и магнитным (Дж. Максвелл) сетям, сформулировал топологическую проблему схемности: найти необходимые и достаточные условия реализации матрицы в виде электрической (магнитной) сети, элементы которой численно равны взаимной проводимости между соответствующими узлами сети, при этом сеть декомпозируется в сети меньшей размерности, если она содержит в качестве собственной подсети — двухполюсную сеть. Эта проблема до сих пор является открытой.

В 1937 г. в связи с развитием цифровой техники Клодом Шенноном была поставлена проблема декомпозиции булевых функций, важность решения которой сильно возросло в настоящее время в связи с широким использованием нейротехнологии в ведущих отраслях народного хозяйства — оборонной, финансовой, медицинской, горной, машиностроительной и др. Проблема К. Шеннона, несмотря на многочисленные исследования во всех ведущих странах мира оставалась нерешенной. Особенно ярко проявляется необходимость решения проблемы функциональной декомпозиции при проектировании средств hard-нейротехнологий (нейрочипы, нейроплаты, нейроускорители и др.), работающих в субмикронном диапазоне при реализации нейро-транспьютерных технологий. В силу отсутствия ее решения проблема проектирования

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

В экспериментальной нейрофизиологии показано, что процессы обработки информации в, коре головного мозга осуществляются согласно ¿-значной логике, при этом функционированию нейронов отвечает модель ¿-значной пороговой функции. Учитывая этот факт, а так : же тенденцию развития, вычислительной техники и информатики в сторону увеличения значности применяемых логик, в диссертации исследуется открытая . .проблема-, проектирования (синтеза) функциональных декомпозиций в ¿-значных логиках и для ее решения разрабатывается соответствующая теория,,обладающая свойством системности. Согласно принципу «об изоморфизме законов» JI. фон Берталанфи, теория со, свойством системности должна иметь хотя бы две различные предметные интерпретации; в диссертации рассматриваются две предметные интерпретации -нейронная и информационная.

Работа выполнялась в рамках научных исследований Московского государственного горного университета, и связана с исследованиями Ноттингемского университета, Ижевского государственного технического университета, выполняемыми по программе «Intelligent hybrid system approach and Internet-based collaboration for integration in computer aided design and manufacture» (раздел проекта INTAS).

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

комплексов на основе решения проблемы функциональной декомпозиции в k-значных логиках с учетом развития технологической базы производства электронных изделий в России и США.

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

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

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

• характеризацию декомпозируемости функций £-значной логики;

• на основе характеризации создание стратегии минимального расширения исходного пространства;

• разработку оценок разбиения исходного пространства на пространства меньшей размерности и процедур построения оптимального разбиения исходного пространства;

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

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

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

• проектирование топологии оптимальной нейронной сети с заданными ограничениями (количество синапсов нейрона и временной дебаланс сети);

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

- ¿-значных нейронов сотовой и каскадной структур, безотказно функционирующих в субмикронном диапазоне;

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

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

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

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

• разработанная характеризационная теория синтеза функциональных декомпозиций в ¿-значных логиках признана научным открытием (РАЕН, регистр. № ИК-16), что отмеченр дипломом и памятной медалью Академии «Автор научного открытия», посвященной лауреату Нобелевской премии Петру Леонидовичу Капице;

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

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

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

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

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

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

характеризационного анализа;

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

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

Практическая значимость и реализация результатов диссертационных исследований состоит:

• в разработке программных средств автоматизированного синтеза функциональных декомпозиций в ¿-значных логиках, состоящих из модулей РАЗЛОЖЕНИЕ, ПРОТИВОРЕЧИВОСТЬ, РАСКРАСКА—Н (Н — несовместная), РАСКРАСКА—С (С - совместная), РАСШИРЕНИЕ, ШТРИХОВКА, КОДИРОВАНИЕ, ДЕКОМПОЗИЦИЯ, и для проектирования нейронных сетей и информационных ускорителей — расширяющих модулей РАСПОЗНАВАНИЕ, ИЗОМОРФИЗМ, ДЕБАЛАНС и УСКОРИТЕЛЕЛЬ, образующих инструментальную среду в ПЭВМ 1ВМ РС, позволившую синтезировать функциональные декомпозиции для 2- и 3-значных функций от 16 переменных, с учетом кластерных переменных от 64 т 80, и проектировать однородные нейронные сети сотовой структуры сложностью до 10б вентилей и сети из каскадных нейронов до 108 вентилей;

• во внедрении разработанной инструментальной среды в практику реального автоматизированного проектирования ряда систем, в том числе нейроузлов управления теплотехническими объектами (НПО «Химсинтез»), нейроускорителей для логического управления микромехатронными системами реального времени (Ноттингемский университет, Ижевский государственный технический университет). Эксплуатация разработанных средств показало, что трудоемкость проектирования при известных подходах в среднем в 3 - 5 раз выше, сложность проекта — в среднем в 1,5 - 2 раза больше по сравнению с предлагаемым подходом;

• в применении разработанных инструментальных средств декомпозиции при выполнении запросов средней сложности в информационных системах эффект ускорения в 4 5 раз выше по сравнению с проводимой оптимизацией на основе

факторизации запроса, при запросах большой сложности -более чем в 10 раз.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на Международной конференции «Control systems and computer science» (Бухарест, 1991 г.), 14-м Международном симпозиуме «Логическое управление и интеллектуальные информационные технологии и стратегии» (Феодосия, 1991 г.), Всемирном конгрессе ITS-93 «Информационные коммуникации, сети, системы и технологии» (Москва, 1993 г.), Всемирном конгрессе IPTS-94 «Информационные процессы, технологии, системы, коммуникации и сети» (Москва, 1994 г.); 17-м Международном симпозиуме «Логическое управление и интеллектуальные информационные технологии и стратегии» (Варна, 1994 г.); Всемирном Конгрессе IPTS-95 «Информационные процессы, технологии, системы, коммуникации и сети» (Москва, 1995 г.),' Всемирном конгрессе «Информатизация», посвященном памяти А; Нобеля'(Ижевск, 1995 г.), Всемирном конгрессе IMCII-96 «Информационная математика, кибернетика и искусственный интеллект в' информациологии» (Москва, 1996 г.), Всемирном конгрессе «Информационная математика и искусственный интеллект в информациологии» (Ижевск, 1997 г.), V-й и VI-й Всероссийских конференциях "Нейрокомпьютеры и их применение" (Москва, 1999 г., 2000 г.).

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

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, трех приложений, списка использованной литературы из 101 наименования, содержит 76 таблиц и-91 рисунок.

Содержание работы

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

вычислительных комплексов таких, как нейро-транспьютерные системы.

Большой вклад в развитие теории проектирования цифровых средств внесли А. Абхъянкер, С. Акерс, С. Амарел, А. С. Амбарцумян, А. Ангер, А. Беркс, Д. Бохман, Е. А. Бутаков, Е. К. Войшвилло, М. А. Гаврилов, А. И. Галушкин, В. М. Глушков, М. Дертуозуос, Ю. И. Журавлев, В. П. Корячко, А. Кертис, О. П. Кузнецов, Р. Карп, У. Квайн, В. Ф. Крапивин, В. Г. Лазарев, Л Лефгрен, В. И. Левин, О. Б. Лупанов, В. М. Лохин, В. В. Макаров, С. Мурога, Е. Мак-Класски, У. Мак-Каллок, С. Окада, Г. Н. Поваров, П. П. Пархоменко, Д. А. Поспелов, У. Питтс, Е. И. Пийль, И. В. Прангишвили, Ф Розенблатт, Дж. Райт, В. Н. Рогинский, Л. С. Ситников, В. П. Сигорский, А. Л. Стемпковский, Б. А. Трахтенберг, X. Такахаши, Л. П. Рябов, Л. Л. Утяков, Н. И. Федунец, Дж. Хопкрофт, Дж. Хартманис, С. Чоу, Р. Чин, В. П. Чистов, В. И. Шестаков, Л. А. Шоломов, К. Шеннон, С. В. Яблонский, Э. А. Якубайтис и др.

При этом для случая к-значной логики исследовалась лишь проблема полноты (Я. Лукасевич, Э. Пост, С. В. Яблонский, А. В. Кузнецов, А. И. Мальцев, А. Саломаа, А. Тарски, Г. П. Гаврилов, Р. Линдон, В. Д. Соловьев и др.).

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

А. Пуанкаре была поставлена проблема схемности: синтезировать линейный граф С/, по заданной матрице инцидентности, при этом терм сопоставляется ребру графа (/¿. Было показано, что если граф Сл содержит 2-связный разделимый подграф (гамак), то граф а следовательно, и соответствующая ему функция, декомпозируемы. Несмотря на многочисленные исследования: С. Окада (1954 г.), С. Сешу (1955 г.), И. Седербаум (1959 г.), В. Майяда (1960 г.), В. X. Ким, Р. Т. Чин (1962 г.), Е. К. Войшвилло (1962 г.), Л. Лефгрен (1962 г.) и др., проблема определения при каких свойствах матрица инцидентности является схемной до сих пор является открытой. Был разработан (Л. Лефгрен, 1962 г.) лишь метод распознавания схемности путем фактического построения линейного графа на основе процедур перестановки подграфов, образования пути и соотношения Пуанкаре

С хА = 0 (mod 2), С — цикломатическая матрица, А — матрица инциденций графа GL.

Характеризационный подход.

Позже была поставлена проблема структурности (В. А. Горбатов, 1962 г.): синтезировать структурный граф GH = <К по заданной матрице инцидентности, при сопоставлении терма вершине графа Gh- Эта проблема была решена ее постановщиком на основе разработанного им аппарата характеризационного анализа, при этом было показано, что если граф GH Содержит гамак и/йли па-подграф, то граф GH и соответствующая ему функция декомпозируемы.

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

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

Для оценки качества функциональной декомпозиции функции / введем понятия дебаланса индексов вложения d(f) и ее сложности

W

Рекуррентно определим индекс вложения.

Индекс вложения предметной переменной х, равен нулю: fS(x,) = 0; индекс вложения функциональной переменной, аргументами которой являются только предметные переменные J[x\, хг, ..., xs) равен 1: р(/) = 1; индекс вложения функциональной переменной /, аргументами которой являются как предметные, так и функциональные переменные, равен ртах(ф|) + 1: W) = Ртах(ф|) + 1, ф, — функциональный аргумент функции/

Дебалансом d(f) индексов вложения декомпозиции функции f называется разность

dif) = Ргаах(фа) - Ртт(фР), (1)

фа, фр е {ф, | ф,- — аргумент функции/}.

Сложностью L(f) декомпозиции функции / называется сумма аргументов всех функциональных переменных ее декомпозиции

I(/)=E|{argcp,/ß(cp,)>0}| (2)

i

Эвристический подход на основе логической модели (эврикологический подход).

Фазным представлением i-й переменной л,- ¿-значной логики называется булево высказывание вида:

. _ fl, если х, = j; xnJe {0,1,..., Ar — l} 1 [О в противном случае. На основе фазного представления имеем обобщение разложения Шеннона для ¿-значной логики.

Утверждение 1. Любая к-значная функция разложима по s переменным в виде:

, Х2, •.Xs, Xs+ i, ..., Хп , Х2, ..., Xs,

S

V -Лстьсгг, + ...,*л)), (3)

........,аг) W

Да 1, а2, ..., Oj, xs + i, ..., х„) — остаточные функции, и — соответствующее предельное разложение

(УХ*1,*2,...,*Д/еЛ)(/(*1,*2.....*„) = V ¿хГ' (4)

/с{0.1.....i-1)

f j — j-я фаза функции /; операции v, & соответственно «»дизъюнкция», «»коньюнкция» булевой логики.

Сложность разложения (3) определяется порядком исключения переменных функции. Для определения оптимального порядка обобщено понятие булевой производной (С. Рид, 1959; Д. Бохман, 1964) для fc-значной логики:

д/(х„х2 х„...,х J л<0д)фл<01+1)}> (5)

ÖXj def

< (ст,) — оператор последовательного изменения аргумента:

<(ст,) о ст, е (О, 1, ...Д-2);/е > 2; + — операция неравнозначности, или

у(*„*2,...,*„...,о = iOo(VaJ(/(<(aJ=/(<(a,.+l)))

Производная 5-го порядка от функции ßx\, х2, ..., хп) по переменнымxai,ха2,...,ха5 определяется выражением вида:

d'f{xx,x2,...,xn)

.A<(CTai), <(CTa2), ..., <(СТа,)) +

Л<(С7а1+1), <(Оа2+ 1), < (СТа, + !))•

Весом г

dsf(xitx2,...,x„)

¿л« д'/{хих2,...,-хп)

производной .

.....д(ха1>ха2>-

3

по

переменным xcci, ха2,..., xas называется количество векторов (oai, aa2, ..., aas) при последовательном изменении разрядов которых и при фиксированном значении . остальных переменных, : 'функция / изменяет свое значение.

Чем больше значение веса производной

- д*/(х],х2,...,хп)

, тем

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

д*/(х1,х2,...,х„)л

шах г

Ч^миг.....

d{xal>xu2'—'xas).

•431 М,2.....s

Вводя понятие смешанной производной

d'/(xi,x2,...,xn) = _д_ def дх„.

дха1 дха2... дх,

д"']/(х{,х2,...,хп) дха1дха2... 8xa(s^

(8)

(9)

и определив связь производной 5-го порядка (7) с производными первого порядка (5) и смешанными (9), согласно (8) получаем функционал определения оптимального исключения переменных

^ % 4. А д2/

тах

V(a,,a2,...,a,)

v \ &л ' ¿k&úten

+ ... +

+ + ii, /2 .- -

57

+ ... ф

эу

ох а 8хп ... 8хи

(Ю)

Нижние индексы попарно не равны друг другу и принимают значения из множества {1,2,..., п}.

Недостатками этого подхода являются большие величины сложности декомпозиции £(/) и дебаланса индексов вложения с1(/), например, при исключении одной переменной в каскаде (слое)

значения этих величин определяются соответственно выражениями вида:

Ц/)~а(В)-(кп-1)-(к-1Г\ (11)

а(В) — константа, определяемая используемым базисом В, и

<т = п-1. (12)

Эврикостатистический подход.

При этом подходе предлагается приближенное решение первого этапа синтеза функциональной декомпозиции - этапа разбиения множества переменных функции^*,, х2, ..., х„).

Заданная функцияДхь х2, ..., *„),/е Л задается в виде таблицы Вейча, при этом исходное пространство Р(Х), X = (х|, х2, ..., хп) представляется в виде декартова произведения пространств Р(Ха), Р{ХЬ), Р{Х) = Р(Ха) х Р(ХЬ), ХаиХь = X; Ха п Хь = 0. Разбиения пространства Р(Х) на Р(Ха) и Р(Хь) оцениваются суммой средних квадратичных отклонений дисперсий значений остаточных функций разложения (3), соответствующих пространствам Р(Ха) и Р{Хь), при этом минимальное значение этой суммы соответствует оптимальному разбиению, при котором заданная функцияДхи х2, ..., хп) наиболее вероятно декомпозируема:

ст„ о) — значения функцииДхи х2, ..., х„) в соответствующих клетках матрицы Вейча.

Эврикокоалгебраический подход.

Декомпозиция заданной функцииД^ь х2, ..., х„) синтезируется на основе решения коалгебраического уравнения:

®"/ы(/) = (ф1,Ф2,...,Ф,), (И)

— внешняя функция, фь фг,..., ф5 — внутренние функции декомпозиции

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

Строчным графом противоречивости Gnp(Xa), называется граф <V,(U,Xj)>, где

v, о л"„ v, е v,xi 6 р{ха),

{v,«, v,p} £ U, а * р (В Xj, Xj е P{Xb)) (J{X,a, Xj) X/)), (15) Xj — вес ребра {v,«, v,p}. >

Столбцевым графом противоречивости Gnp(Xb) называется граф <K(U,Xd>, где

, ч<г+Х;,чеУ,Х;еР(Хь),

. .-{vja, у,р} е У, а ^ р о (В i Д- е Р, ^ Д, ЗД), (16) Х( — вес ребра {v7«, v,p}. ■ -.'j

Раскраской вершин графа G = <V, U> называется разбиение его носителя ^ V, = V, Vp. n = 0, а * р такое, что ;в каждом

подмножестве V, не найдется ни одной пары смежных вершин, при этом минимальное число этих подмножеств называется хроматическим числом h(G).

Внешняя функция Fbi определяется заданной функцией J{xu х2, ..., х„) и задается в виде соответствующей матрицы Вейча. Для вычисления матриц Вейча, определяющих внутренние функции ф„ / = 1, 2, ..., s, в диссертации предлагается процедура, основанная на анализе графов противоречивости для каждой внутренней функции. Проводимый анализ позволяет хотя бы одну из внутренних функций ф, представить в виде функциональной декомпозиции.

Стратегия построения функциональной декомпозиции на основе решения уравнения (14) во многом зависит от вида внешней функции Fbi, определяемой используемым базисом В = {6,}.

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

Рассмотрим точное решение проблемы синтеза функциональной декомпозиции в £-значных логиках. На основе введенного бинарного отношения противоречивости в множестве остаточных функций в диссертации доказано утверждение 2.

Утверждение 2.

£-значная функция Лх\, х2, ..., х„), X = (лгь х2, ..., хп) декомпозируема

тогда и только тогда, когда при представлении переменных X в виде Х = Ха и Хь найдутся разложения по аддитивной связке столбцевых и/или строчных остаточных функций такие, что сумма ближайших больших целых чисел логарифмов Ыа и/или Мь по основанию «к» меньше размерности заданной функции \Х\

+ (17)

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

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

В работе показана связь функциональной декомпозиции с разложением Шеннона и раскраской вершин графа. При задании функцииЛХ),ЛХ) е Рк,Х= (хи х2,..., хп) в виде двумерной ¿-значной матрицы Вейча или графа Кенига К{/) размерами А:'^0' х , Х~ Ха х Хь, соответственно исходное пространство Р(Х) представляется как декартово произведение пространств Р(Ха), Р(ХЬ)\ Р(Ха), Р(ХЬ) — сопряженные пространства, Р(Х) = Р(Ха) х Р(Хь), при этом строка взаимнооднозначно соответствует строчной, столбец — столбцевой остаточной функции разложения/{X}.

При задании функции ДА) в виде графа Кенига К(/), вершины одной доли взаимнооднозначно соответствуют точкам одного из пространств Р(Ха) и Р(ХЬ), вершины другой — точкам сопряженного пространства, при этом остаточная функция Дсть о2, .... ст5, х, + 1, ..., х„) определяется вершиной доли К{Ха), V, е К(Ха), V, (сть а2, ..., ст5) и сечением Г(у,) доли К(ХЬ), Г(у,} с К(ХЬ); остаточная функция

Х2.....х„ с5 +1, о, + 2, • •., а„) — вершиной у, о (ст5 +1, а, + ......ап), у,- е

К(ХЬ) и сечением Г(у,) доли К(Ха), Г(у,) с К{Ха).

Склеивание строк и столбцов рассматривается как раскраска вершин соответственно строчного Спр(Ха) и столбцевого Спр(Хь) графов противоречивости/ ■ '-1

На основе-этой связи утверждение 2 в терминах теории графов обладает свойством конструктивности в силу того, что найдена характеризация раскраски вершин графа в заданное число красок. Отсюда интерпретируя утверждение 2 в категориях теории графов, получаем утверждение 3.

Утверждение 3.

Функция ДХ), /[X) е Рк декомпозируема в виде ЛХ) = РЫХа), ц,2(Ха),..., ср.^), Т1,№), ц2(Хь),..., ХаиХь=Х,

тогда и только тогда, когда после редукции хроматических чисел &(СПр№)) и к(Спр(Хь)) при совместной раскраске строчного 6пр(Ха) и столбцевого СЩ,(ХЬ) графов противоречивости, выполняется неравенство (18)

[1оё^(бпр(Ха'))] + [1о&кд(Опр(Хь'))] < И, (18)

д(Спр(Ха')) — квазиплотность строчного графа противоречивости Си?{Х') = <К', иа>, иа с иа, Уа с Уа;

д(Спр(ЛУ)) — квазиплотность столбцевого графа противоречивости Спр№') = <П', 0Ь>, 0Ь с иь, Уь с Уь, полученных из графов противоречивости Опр{ХЫЬ)) = Спр = в результате сужения

сигнатуры и; расширения носителя соответствующего графа (?пр = <^(4), иаф)>, Уф) с Уф), С/ф) с иа{Ьу

При совместной раскраске графов противоречивости Спр(Ха) = <К, иа> и СП?(ХЬ) = <Уь,иь> в общем случае их сигнатуры состоят из двух частей С/н и £/з, 1/ц — независимая от раскраски вершин в сопряженном пространстве часть сигнатуры, определяемая

распределением значений функции ДХ) в пространстве Р(Х), согласно одному из соотношений (15), (16) и Из — зависимая часть сигнатуры, определяемая отношением соцветности вершин в сопряженном пространстве, а именно, при склеивании соцветных вершин в одном пространстве в сопряженном пространстве найдутся векторы, для которых выполняется одно из условий (15) или (16).

Если для выполнения соотношения (18) не требуется редукции ни одного из хроматических чисел /г((7Пр(Л"<,)) и й(С?пр(АУ), то имеем случай бесповторной декомпозиции: Ха п Хь = 0, в противном случае - повторной: ХапХь ф 0.

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

В зависимости от выполнения редукции хроматических чисел к(Сп?(Ха)) и /7(Спр(А^)) в работе предложены две стратегии синтеза функциональной декомпозиции: последовательная и параллельная.

Последовательная стратегия состоит из выполнения следующих процедур:

1. Декомпозиция исходного пространства Р(Х) в виде Р(Х) -Р(Ха) х Р(ХЬ), \Ха\ = [0,5|*|], \ХЬ\ = \Х\ - [0,5Щ], такое разбиение множества переменных X определяется минимизацией дебаланса индексов вложения.

2. Задание функции X) в виде матрицы Вейча или графа Кенига К(/) и построение графов противоречивости Опр(Ха) и С„Т(ХЬ).

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

4. Склеивание соцветных вершин рассматриваемого графа противоречивости и построение соответствующей матрицы Вейча или графа Кенига. . ' ;

5. Выполнение п. 3 и п. 4 для сопряженного пространства.

При параллельной стратегии синтеза функциональной декомпозиции в общем случае сигнатуры графов .противоречивости состоят из независимой С/ц и зависимой t/з частей. Для совместной раскраски графов противоречивости предложен критерий согласования отношений соцветности вершит ({v(A>), v(Xap)} € Rcom) & (J[Xaa,Xb^i[XaKXb^) ->

{v(x4a), V(Xbv)} £ Rcow- (19) (|v№a), v(Xbt)} e RC0UB) & (fiXaa, Xba) Хф)) ->

-> {v(Xaa)y v(Zap)} г Ream- (20)

Параллельная стратегия отличается от последовательной выполнением п. 3, в котором осуществляется параллельная редукция хроматических чисел с учетом (19) и (20), и отсутствием п. 5.

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

Исследована ' и решена проблема синтеза функциональной декомпозиции заданной размерности.

Утверждение 4.

Функция J[X),j{X) е Рк декомпозируема через функции Fh т|(, размерность каждой из которых не превышает заданного. числа s тогда и только тогда, когда после редукции хроматических'чисел при совместной раскраске графов противоречивости Gnp(Xa'), Grp(Xb')

, [log* h{ Gnp (Xa'))] + [log, h( Grp №'))] < J (21)

на каждом шаге синтеза.

Для предложенных стратегий синтеза функциональных декомпозиций разработана информационная технология расширения исходного пространства (штриховки входных векторов). Для расширения , (штриховки) входных векторов . предложены, два способа: с помощью «делегирования» переменных в сопряженное пространство или на основе построения специальных векторов штриховки Хаш, ХЬш1, длины .которых определяются хроматическими числами удаляемых (для выполнения соотношения (18)) подграфов G^p (Ха) и G'np (Хь) соответственно:

i*, j = [log* к g;v (XM g;p (Xa) a cnp(xa), (22)

Ы = [log, h{g„p№))], c;p (Хь) с gnp№). (23)

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

При синтезе функциональной декомпозиции f[X) большое значение имеет разбиение исходного множества переменных X, X =

Рассмотрим мультипликативную декомпозицию заданного пространства Р^Х), Pr{X) = Pk(Xa) х Рк(Хь). Будем искать декомпозицию, исходя из минимизации мощности объединения независимых сигнатур:

ПИП(|£/о11и иьи\), (24)

i

графов противоречивости.

Расширим понятие «расстояние по Хеммингу» для случая к-значной логики. Расстоянием по Хеммингу d(X,, Xj) называется количество переменных, значениями которых отличаются векторы Xi, Xj.

В зависимости от расстояния по Хеммингу d(Xh Xj), J[X,) ^flXj) при порождении элементов сигнатуры возможно три случая:

- d(Xh Xj) = 1 {v(X,), e UH, (25)

- d(Xb Xj) > [0,5^] -> {v№), v{Xj)} g UH, (26)

- [0,5^] > d(Xh Xj)> 1 {v(X,), v{Xj)} e UH или

{у(Х,), v(Xj)} £ UH. (27)

Векторы Xh Xj, для которых выполняется выражение (25) порождают ядро С/о независимой части сигнатур. Для минимизации (24) введем модель Ц1 = <{x, / ; = 1, 2, ..., п), сигнатура

которой представляет симметричные d(Xh ^)-арные отношения, и зададим ее в виде матрицы инцидентности Q(\j) = [qij\:

1, если j - ая переменная входит в г - ое подмножество переменных удовлетворяющих левой части (27)

<?Н (2В)

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

Для минимизации (24) будем синтезировать разбиение переменных {*,// = 1, 2.....п) на основе вычисления среднего

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

BS

«свойство образования переменными подмножества, удовлетворяющего левой части выражения (27)»:

min(|с/„з\ tu + №\ г/4) => min-T^i' =

'•■> i.j и/"-1) -,j\dS J

= ' lf{Xi)-2fXCjhf^)' (29)

f{x„ Xj) — недиагональные; ßxt), fix¡) — диагональные элементы частотной матрицы отношений F(vj/), F(\\i) = ßr(i|/) x Ö(v)> r — число переменных, удовлетворяющих левой части выражения (27).

Переменные, удовлетворяющие минимальному значению, включаются в одно из пространств Р{Ха) или Р(ХЬ), тогда векторы различных пространств отличаются максимальным, векторы одного пространства — минимальным образом, что в итоге минимизирует выражение (24).

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

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

wShin (!{{«} v(Xj) t RC0M}\Tl ■ (YdiX^X,)). (30)

Ä-значностшогики} J

Согласно (30), векторы с минимальным средним значением расстояния по Хеммингу будут кодироваться одним и тем же значением кодирующего символа ф„ г|7 (ф„ r[, s {0, 1, 1}),

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

Разработанная характеризационная теория синтеза функциональных декомпозиций была успешно применена на

практике при нейронной и информационной предметных интерпретациях.

Нейронная интерпретация теории.

Проектирование топологии многослойных нейронных сетей в настоящее время проводится эмпирически на основе метода проб и ошибок. В диссертации эта проблема рассматривается как естественная интерпретация проблемы синтеза функциональной декомпозиции заданной размерности, определяемой количеством синапсов у нейрона. Сейчас наиболее «отработанными» технологиями производства нейронов, функционирующих в условиях субмикронного диапазона, в России и США являются 4-синаптические нейроны. В диссертации разработана информационная технология и ее программная реализация автоматизированного проектирования сетей из однородных 4-синаптических нейронов сотовой структуры. Однородный 4-синаптический нейрон сотовой структуры описывается квазипороговой булевой функцией/^, х2, х3, х4) вида

ДХ], Х2, Хз, Х4)-

1,если£>,. -х,. =Р, (31)

1=1

О в противном случае,

и>, — вес /-го синапса эмулируется количеством горизонтальных цепей, на вход которых подается переменная х,; {Р, / Р1 — квазипорог} — эмуляция порога.

Горизонтальная цепь представляет собой последовательно включенные между собой ключи, при этом, если в рассматриваемой цепи нечетные ключи открываются переменной х„ а четные — х,, то в соседних цепях, наоборот, нечетные ключи открываются х,, четные — х(. Ключи, открывающиеся переменной х„ будем называть неинверсными, а открывающиеся переменной х, — инверсными ключами. В случае ¿-значной логики, к > 2, неинверсный ключ сопоставляется одной из фаз х"', х„ ст, е{0, 1, ..., к- 1}, инверсный

х,°' - (к- 1) фазам,

(32)

при этом он реализуется в виде параллельно соединенных (к - 1) ключей. В качестве неинверсной переменной выбирается фаза

переменной, которая соответствует этой цепи при настройке нейрона.

Настройка нейрона на заданную фазу Ста, ста е {0, 1, ..., к - 1} функции ДХ),ДХ) е Рк сводится к определению весов синапсов {м',}, множества разрешенных {Р,} и запрещенных {7}} квазипорогов, для определения которых решаются две системы уравнений. При определении топологии нейронной сети, реализующей у-ю фазу заданной функции /{X), для определения разрешенных квазипорогов каждое уравнение системы взаимнооднозначно определяется точкой Ха пространства Р{Х), в которой ДХа) = у, при определении запрещенных квазипорогов — точкой Хр, в которой .ДЛр) Ф у. Системы решены, если любые два квазипорога Pj и Т\ не равны друг другу:

\ . ., ..(33)

Решение систем оценивается значением функционала качества

фкач- -

Для уменьшения трудоемкости решения систем уравнений был введен граф неравенства весов GH = <{w,}, R2>, R2 с ({w,})2 — бинарное отношение «образование равных, с точностью до переименования РиТ, выражений для весов w/a, w,p»: {и>, w,p}' е R2, с помощью которого определялись начальные значения весов синапсов.

Для вычисления весов синапсов и квазипорогов был исследован подход, основанный на обучении с помощью итеративного градиентного алгоритма обратного распространения ошибки (error back popagation, Ф. Румельхарт, Дж. Хинтон, Р. Уильяме, 1986 г.) и показана его малая эффективность для рассматриваемого случая. Очевидно это связано с тем, что он используется для минимизации среднеквадратичного отклонения текущего выхода и заданного выхода нейронной сети, т. е. для случая, когда реализуется отображение «точка — многоточка», в рассматриваемом же случае реализуется отображение «точка — точка».

Для реального проектирования средств hard-нейротехнологий на основе 4-синаптических однородных нейронов сотовой структуры разработан каталог, включающий в себя 400 минимальных

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

Переименование переменных и замена переменной на ее отрицание называется преобразованиями Джевонса. Множество функций, получаемых друг из друга с помощью преобразований Джевонса, называется типом. Для распознавания однотипности заданной функции ЛХ) предложено 17-мерное признаковое пространство Рп, ^п = Ли х Рт * ^пз * Рт, где Рщ — четырехмерное пространство, каждая точка которого

{{Xj, Х:} / d(Xit Xi)= 1} \{{Xi,Xi}ld(Xi,X;)-2}\

\{{XhX,Md(XhXÙ = 3)\

d(Xj, Xj) — расстояния по Хеммингу между точками

х„хРлХ) =A*i) = h

очевидно, что

Z I{{X,Xj} / d(Xb Xj) = a}\ = C(r(j), 2),

a=l

r(J) — ранг функции Д^), C(r(/), 2) — число сочетаний из r(J) по 2; Pu 2 — пятимерное пространство, каждая

(35)

(36)

точка которого

|{v№)/5(V№)) = 0}| |{v№)/5(v«.))=l}| |{v№)/i(v«)) = 2}|

|{уда/ф№)) = з}| |М*,)/ф№)) = 4}|

х(у(^)) — степень вершины подгиперкуба с носителем М^) /

ЛХд= О.

очевидно, что

¿1М^Ф«)) = Р}| = К/); (38)

р=о

Рпз — четырехмерное пространство, векторы которого имеют вид:

|{v,{G (/))/Л(у.) = 3)1

|{V,(GM(/))/5(V,) = 5}|

|{v,{GM(/))/s(v,) = 4)|

I(v,(G (/)) /¿(v,) ~ б)|

(39)

5(у,(См(/))) — степень вершины мографа См(/), соответствующего функции/и рассматриваемого без его моделизации;

v(G') KX,Xi) KX„X,) l(X„Xk)

____________(40)

v(G') — цикломатическое число подгиперкуба, на носителе которого {v,№)} функция^) =1;

1(Ха, Ар), а, Р (а Ф р) = к— попарное расстояние между висячими вершинами, соответствующими векторам X,■, Хр Хь

С помощью признакового пространства Рш распознаются 146 типов (36,5%), с помощью Рщ х Рт — 207 типов (51,75%), Рщ х Рт х Рт — 41 тип (10,25%), Ли х Рт х Рпз х Рт — 6 типов (1,5%).

Предложенное признаковое пространство позволило при определении однотипности заменить труднорешаемую проблему определения изоморфизма мографов (гиперграфов) на менее трудоемкую - вычисления распознающих векторов длины 4, 9, 13 и 17 в зависимости от рассматриваемой функции ДА). • '

Разработанный каталог состоит из 400 таблиц (по числу типов в булевом четырехмерном пространстве, на считая константы 0 и 1). Каждая таблица включает в себя:

М{/г) — гарвардский номер типа (Айкен); /■¡{X) — функция типа Аг(/г)> единичная область которой содержит точку 0;

ЛГК/г ) — гарвардский номер инверсного типа; ¿тш — сложность нейронной реализации функции /т(Х), равная сумме весов синапсов;

(и»1, и>2, и>з, и>4) — веса синапсов; {Р,} — разрешенные квазипороги функции/-¡{Х)\ {7}} — запрещенные квазипороги функции/т(Х); А е РП1 х Р[12 х Рпз х Рш — вектор, распознающий однотипность.

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

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

Временным дебалансом с!, нейронной сети называется

dt 'max 'min 'min)> (41)

xk — время задержки сигнала ключа,

/тах — максимальная длина активизируемой цепи,

'min — минимальная длина активизируемой цепи.

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

тя=т к-La, (42)

тк - постоянная времени нейроключа, \к = 0,5 не.

Если дебаланс индексов вложения декомпозиции равен 0 и временные задержки нейронов постоянны, то временной дебаланс соответствующей нейронной сети равен 0.

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

Структура предложенного нейрона описывается с помощью кольца <{С7(лг,)}, х, +>, где носитель {G(x,)} представляет собой граф Кенига Д1, к), ребра которого взвешены значением переменной к-значной логики: 0, 1, 2, ..., к - 1, и соответствует ¿-фазному представлению переменной х,, х,- е Рь х — конкатенация, + — теоретико-графовое сложение.

Структура каскадного ¿-значного нейрона имеет вид:

т' т

Г№)+ П ад, (43)

(=1 _/'=ffi41

т — количество синапсов,

т' = [0,5от], [ ] — целое ближайшее большее число. Предложенный каскадный ¿-значный нейрон использовался в высокопроизводительных вычислительных системах и функционировал в субмикронном диапазоне, который определяет нулевое значение временного дебапанса нейронов.

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

= (44)

Условие возбужденияу-й фазы нейрона определяются как:

[О в противном случае,

5 е {0, 1.....к- 1},

Р\ — разрешенный квазипорог.

Показано, что минимальная сложность ¿т;„(к, т) каскадного нейрона ¿-значной логики с т синапсами равна:

Ашп(*, т) = Г+1 + #{к- 1)"' • (Гча3т1 + ¡¿°-5т] - 2). (46) Временная задержка т3 нейрона определяется как:

т, = (и1+1)-хь (47)

Информационная интерпретация.

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

Особенно эта проблема важна для случая небулярных данных ^О;},^, (48)

Я, — /-арное отношение, Л, с ({ Б!})',

— домен, определяющий свойство В] <-> Е>} = {Щ,ЩЪ •••> »*//}, т]а — атрибут,

т]а <Ща — обладает свойством 5, с индексом V»

у(т]а) - степень обладания т]а свойством Sj, \{т]а) = 0, 1,..., к- 1;

.С^ — домен, атрибуты которого имеют индексы обладания свойством 5), равные V.

Совокупность (48) определяет предметную среду, множество функций {/ХД, А, ..., А) / ДА. А,---, А) — запрос} —

функциональную среду. Функция ДА, А.....А) — функция к-

значной логики. При таком представлении все множество запросов разбивается на два класса: прямые и обратные запросы. Прямой запрос: «определить степень небулярности исследуемого значения отношения (ситуации)» сводится к вычислению значения функции ДАТ), УРО е РК при заданном значении X. Обратный запрос: «породить всю информацию, удовлетворяющую заданной степени небулярности V исследуемой ситуации» сводится к определению множества значений векторов {X, ¡ЛХ,) = v}.

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

Для успешного внедрения полученных научных результатов предложенная информационная технология доведена . до программной реализации в виде автоматизированной системы синтеза функциональной декомпозиции в А-значных логиках, состоящий из модулей РАЗЛОЖЕНИЕ, ПРОТИВОРЕЧИВОСТЬ, РАСКРАСКА-Н (Н — несовместная), РАСКРАСКА-С (С — совместная), РАСШИРЕНИЕ, ШТРИХОВКА, КОДИРОВАНИЕ, ДЕКОМПОЗИЦИЯ, РАСПОЗНАВАНИЕ, ИЗОМОРФИЗМ, ДЕБАЛАНС, УСКОРИТЕЛЬ. Разработанная автоматизированная система образует инструментальную среду в ПЭВМ 1ВМ РС и позволяет синтезировать функциональные декомпозиции в двух- и трехзначных логиках в пространстве размерности до 16, с учетом кластерных переменных до 64 - 80; проектировать сети из однородных нейронов сотовой структуры сложностью до 10б вентилей, нейронные сети из трехзначных каскадных нейронов сложностью до 108 вентилей, ускорять выполнение запросов в информационных системах в 8—10 раз по сравнению с существующей информационной технологий.

Разработанные информационные технологии и инструментальные средства успешно внедрены при нейронной и информационной предметных интерпретациях в практику реального автоматизированного проектирования нейронных сетей управления (НПО «Химсинтез»), нейронных ускорителей (НИИ Спецтехники и

связи МВД РФ; Ижевский государственный технический университет, Ноттингемский университет в рамках проекта INTAS) и информационных ускорителей (Администрация Президента РФ, Счетная палата РФ, Исполком Союзного государства Беларуси и России, ГИБДД РФ, Институт прикладной механики Уральского отделения РАН, ОАО «Концерн «Ижмаш», Информационно-аналитический центр при администрации Президента PCO - Алания, Министерство природных ресурсов и экологии PCO - Алания).

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

Автоматизированное проектирование нейронных сетей управления технологическими процессами.

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

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

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

• разогрев, плавление и вымешивание состава можно обеспечить при использовании только пара (в отличие от типового регламента, где использовался пар и вода);

• значительно повышается производительность оборудования (время приготовления состава уменьшается почти в 2 раза);

• повышается точность регулирования.

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

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

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

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

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

Управление осуществляется в реальном масштабе времени на основе использования блока реального времени.

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

Управление на обоих уровнях уровнях реализуется в виде сетей из двух- и трехзначных нейронов каскадной структуры, спроектированных с помощью разработанной в диссертации САПР функциональных декомпозиций. Контроллер системы теплорегулирования представляют собой нейронную сеть и стековую память, в которой хранятся векторы определяющие квазипороги. Каждый блок стековой памяти используется при последовательном управлении технологическим процессом, при реализации логического перехода в программе управления подключается соответствующий блок стековой памяти. Входной вектор X нейронной сети определяется технологическим срезом во времени, выходной вектор У определяет управление производственными аппаратами. Такое управление позволило обеспечить стабилизацию температурных режимов с использованием только одного теплоносителя - пара с точностью до ± 1,5°С при стабильном напряжении питания, и ± 2,5°С - при нестабильном (промышленная сеть: 220 В, колебания: -10%^- + 15 %).

Нейронные ускорители являются неотьемлимым компонентом высокопроизводительных информационно-вычислительных систем, начиная от суперкомпьютеров для обработки аэрокосмических фотоснимков (США, проект «Силиконовый мозг», производительность - 80 петафлоп) и кончая системами реального времени автоматизированного распознавания правдивой и ложной информации - системами оперативной оценки психофизиологического состояния человека с помощью полиграфа при борьбе с захлестнувшей общество преступностью. Разработанный программный инструментарий автоматизированного проектирования нейронных ускорителей был внедрен в НИИ Спецтехники и связи МВД РФ. Информация полиграмм включает четыре компонента: дыхание, сердечно-сосудистое,

электродермальное состояние и состояние мышечной активности. Компоненты определяются переменными - быстрая составляющая дыхания (собственно дыхание), медленная составляющая (базовая линия дыхания), изменения частоты и амплитуды пульса, размах амплитуды кожно-гальванической реакции, энергия тремора. Каждая переменная принимает значение из множества {0, 1, 2,..., к - 1}. Отсюда вычисление вероятности лжи определяется ¿-значной функцией на основе корреляционного анализа, что в процессе опроса позволяет идентифицировать ситуацию. Внедрение результатов диссертации при модификации компьютерного полиграфа «ЭПОС -5» увеличило его быстродействие в пять раз при уменьшении массогабаритных характеристик в два раза.

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

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

Автоматизированное проектирование информационных ускорителей в Счетной палате РФ.

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

- учредители, члены, их статус, взаимоотношение с ними;

- уставной капитал, фонды, страховка;

- технологии;

- финансовые и другие показатели деятельности;

- взаимоотношение с Госбюджетом;

- сведения о деятельности.

Предварительное представление функции запроса в виде функциональной декомпозиции запросов меньшей размерности повысило реактивность выполнения запросов в 8 т 10 раз по сравнению с применяемой ранее предварительной обработкой запросов на основе их факторизации.

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

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

Заключение.

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

Основные научные результаты, полученные лично соискателем:

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

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

2. На основе характеризационного подхода и связи между разложением Шеннона, матрицами Вейча (графами Кенига) и раскраской графов противоречивости доказан характеризационный критерий синтеза функциональной декомпозиции в £-значных логиках, позволивший эффективно проводить минимальное расширение исходного пространства при получении точного решения рассматриваемой проблемы.

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

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

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

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

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

7. Впервые разработанная характеризационная теория'синтеза функциональных декомпозиций в £-значных логиках признана научным открытием (РАЕН, регистр ИК - 16), является системной теорией и, следуя принципу «об изоморфизме законов" Л. фон Берталанфи,. должна иметь хотя бы две различные предметные интерпретации; в диссертации такими интерпретациями являются нейронная и информационная. Проектирование топологии многослойных нейронных сетей, проводимое в настоящее время методом проб и ошибок, предложено рассматривать как естественную интерпретацию проблемы синтеза функциональной декомпозиции заданной размерности, определяемой количеством синапсов нейрона. Ускорение выполнения запроса в информационных системах, использующих реляционные банки данных, предложено рассматривать как проблему декомпозиции соответствующей ¿-значной функции при обработке небулярных данных.

8. Показано, что проектирование средств Ьагё-нейротехнологии состоит из этапа синтеза топологии нейросети и настройки нейронов на функции синтезированной декомпозиции. Для вычисления весов синапсов был исследован подход, основанный на обучении с помощью известного интерактивного градиентного алгоритма обратного распространения, показана его малая эффективность при реализации отображения «точка — точка». Для реального проектирования средств Ьагс!-нейротехнологии на основе 4-синаптических однородных нейронов сотовой структуры были разработаны каталог минимальных 4-синаптических нейронов и 17-мерное признаковое пространство, позволившее эффективно распознавать однотипность реализуемой функции и по гарвардскому номеру типа и преобразованиям Джевонса определять минимальные веса синапсов нейрона. Для проектирования нейронных ускорителей, работающих в субмикронном диапазоне, с нулевым временным дебалансом предложен каскадный А-значный нейрон, на базе которого проектировались нейронные сети с помощью синтеза функциональных декомпозиций с нулевым дебалансом индексов вложения, однозначно определяющих нулевой временной дебаланс всей сети.

9. Для успешного внедрения полученных научных результатов разработанная информационная технология доведена до программной реализации в виде автоматизированной системы синтеза функциональных декомпозиций в ¿-значных логиках, образующей инструментальную среду в ПЭВМ 1ВМ РС и позволяющую синтезировать функциональные декомпозиции в двух-и трехзначных логиках в пространстве размерности до 16, с учетом кластерных переменных до 64 - 80; проектировать сети из однородных нейронов сотовой структуры сложностью до 106 вентилей, нейронные сети из каскадных нейронов сложностью до 108 вентилей.

10. Разработанные инструментальная среда и информационная технология внедрены при нейронной предметной интерпретации в практику реального автоматизированного проектирования нейронных сетей управления (НПО «Химсинтез»), нейронных ускорителей (НИИ Спецтехники и связи МВД РФ; Ижевский государственный технический университет, Ноттингемский университет в рамках проекта ШТАБ) и информационных ускорителей (Администрация Президента РФ, Счетная палата РФ,

Исполком Союзного государства Беларуси и России, ГИБДД РФ, Институт прикладной механики Уральского отделкения РАН, ОАО «Концерн «Ижмаш», Информационно-аналитический центр при администрации Президента РСО - Алания, Министерство природных ресурсов и экологии РСО - Алания). Внедрение показало, что трудоемкость проектирования нейронных ускорителей и сетей управления в 3—5 раз ниже, сложность проекта — в 1,5 - 2 раза меньше по сравнению с известными подходами; использование информационных ускорителей повышает реактивность выполнения запроса в 8 -ь 10 раз по сравнению с применяемой предварительной обработкой запросов на основе факторизации. Научные результаты так же успешно внедрены в учебный процесс при подготовке инженеров и магистров по направлению «Информатика и вычислительная техника» ряда ВУЗов: МГГУ, МИРЭА, ИжГГУ (Ижевск), ЧГТУ (Челябинск), СКГТУ (Владикавказ), РРТА (Рязань). По результатам внедрения получены соответствующие акты о внедрении.

По теме диссертации опубликованы следующие работы:

1. А. В. Горбатов «Характеризационная теория синтеза функциональных декомпозиций в ft-значных логиках», — М., Издательство физико-математической литературы, 2000,336 с.

2. А. V. Gorbatov Mographs isomorphism. / In «Control systems and computer science», vol. 1, BPI, Bucuresti, 1991, С. 118—120.

3. Горбатов А. В. Частотный алгоритм определения подобия матриц инцидентности. / В сб. АН СССР «Логическое управление с использованием ЭВМ», М., 1991, С. 39—42.

4. Горбатов А. В. Синтез цифрового нейрона. / В сб. IIA «Информационные коммуникации, сети, системы и технологии». М., 1993, С. 237—238.

5. Горбатов А. В. Решение проблемы синтеза повторной декомпозиции булевой функции и нейронная технология. / В сб. НА «Информационные процессы, технологии, системы, коммуникации и сети». М., 1995, С. 27—35.

6. Горбатов А. В. Автоматизированное логическое проектирование сотовых нейросетей. / В сб. «Информационные

процессы, технологии, системы, коммуникации и сети». Санкт-Петербург, Каравелла, 1995, С. 5—6.

7. Горбатов А. В., Горбатова М. В. Интеллектуальное проектирование и моделирование нейронных сетей, функционирующих в условиях субмикронной технологии. / В сб. IIA «Информатизация», посвященном памяти А. Нобеля. Ижевск, 1995, С. 111—121.

8. Горбатов А. В. Характеризация проектирования структур сотовой нейронной технологии. - М., Машиностроение, Информационные технологии № 0, 1995, С. 38—40.

9. Горбатов А. В. Характеризационно-декомпозиционный подход к проектированию нейронных сетей. / В сб. IIA «Информационная математика в информациологии». Ижевск, 1997, С. 3—7.

10 Горбатов А. В. Логическое проектировение нейронных сетей. / В сб. РАЕН «Проблемы характеризационного анализа и логического управления». М., 1999, С. 90—95.

11. Горбатов А. В. Характеризационное проектирование 4-синаптических нейронных сетей. / В сб. РАЕН «Проблемы характеризационного анализа и логического управления». М., 1999, С. 96—101.

12. Горбатов А. В. Характеризация функциональной декомпозируемости в ¿-значных логиках. / В сб. РАЕН «Проблемы характеризационного анализа и логического управления». М., 1999, С. 102—108.

13. Горбатов А. В., Валуева Н. В. Проектирование нейронных сетей управления горной автоматикой. / В сб. «Нейрокомпьютеры и их применение». М., Радио и связь, 1999, С. 191—194.

14. Горбатов А. В. Разложение Шеннона. Декомпозиция булевых функций. / В кн. «Фундаментальные основы дискретной математики. Информационная математика». М., Наука, Физматлит, 1999, С. 98—102.

15. Горбатов А. В. Семантический критерий декомпозируемости булевых функций при их нейронной реализации. / В сб. «Нейрокомпьютеры и их применение». М., Радио и связь, 1999, С. 402—404.'

16. Горбатов А. В. Синтез нейронных структур. / В кн. «Фундаментальные основы дискретной математики.

Информационная математика». М., Наука, Физматлит, 1999, С. 370— 373.

17. Горбатов А. В. Решение проблемы повторной функциональной декомпозиции в булевой логике. / В кн. «Фундаментальные основы дискретной математики. Информационная математика». М., Наука, Физматлит, 1999, С. 454— 466.

18. Горбатов А. В. Синтез функциональной декомпозиции в к-значной логике. / В кн. «Фундаментальные основы дискретной математики. Информационная математика». М., Наука, Физматлит, 1999, С. 467—473.

19. Горбатов А. В. Синтез функциональной декомпозиции заданной размерности. / В кн. «Фундаментальные основы дискретной математики. Информационная математика». М., Наука, Физматлит, 1999, С. 473—483.

20. Горбатов А. В. Семантическое проектирование нейронных сетей. / В кн. «Фундаментальные основы дискретной математики. Информационная математика». М., Наука, Физматлит, 1999, С. 483— 494.

21. Горбатов А. В. Оптимальная декомпозиция пространства по мультипликативной связке. — М., Машиностроение, Информационные технологии № 4, 2000, С. 7—11.

22. Горбатов А. В. Цифровой нейрон в ¿-значной логике и его минимальная сложность. / В сб. «Нейрокомпьютеры и их применение — 2000». М., Радиотехника, 2000, С. 550—555.,'

23. Горбатов А. В., Редкозубов С. А. Статистический подход при синтезе функциональных декомпозиций в ¿-значных логиках. — М., Издательство физико-математической литературы, Информационная математика № 0, 2000, С. 66—71.

24. Горбатов А. В. Семантическое кодирование красок вершин графов противоречивости в ¿-значных логиках. — М., Издательство физико-математической литературы, Информационная математика № 0, 2000, С. 82—86.

25. Горбатов. А. В. Эврикологический подход к синтезу

функциональных декомпозиций в ¿-значных логиках.---М.,

Издательство физико-математической литературы, Информационная математика JSfe о, 2,000, С, 61—65.

26. Горбатов А. В. Эврикокоалгебраический подход к синтезу функциональных декомпозиций. — М., Издательство физико-

математической литературы, Информационная математика № О, 2000, С. 72—81.

27. Горбатов А. В., Чечин И. В. Вероятностные методы настройки нейроструктур. — М., Издательство физико-математической литературы, Информационная математика № 0, 2000, С. 98—107.

28. Горбатов А. В. Признаковое пространство и распознавание однотипности функций по Джевонсу. — М., Издательство физико-математической литературы, Информационная математика № 0, 2000, С. 87—94.

29. Горбатов А. В., Карбачинский В. М., Леоненко И. В., Свертилова Н. В. Автоматизированное проектирование нейросетей логического управления обогащением полезных ископаемых. — М., Издательство физико-математической литературы, Информационная математика № 0,2000, С. 108—114.

30. Горбатов А. В. Автоматизированное проектирование нейронных и информационных ускорителей. — М., Издательство физико-математической литературы, Информационная математика № 0, 2000, С. 95—97.

31. Гольдфарб В. И., Горбатов А. В., Су Дж. Автоматизированное проектирование нейросредств логического управления микромехатронными системами. — М., Издательство физико-математической литературы, Информационная математика № 0,2000, С. 135—140.

32. Горбатов А. В. Интеллектуальная информационная технология синтеза функциональных декомпозиций в Аг-значных логиках. — М., Издательство физико-математической литературы, Информационная математика № 0, 2000, С. 122—125.