Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 66
Текст из файла (страница 66)
4.77, а) содержит граф Ни,, соответствуюший режиму В1. Выполняем и. 3, (з) 371 х, х, Сииепсы Квизипороги «~ -Сз- 1 Кхючи Х, х,хтхзхе х$ хзхзхе хг хтхь б Рис. 4.78 370 Гл.4. Теорие формальных грамматик и автоматов в результате получаем структуру, изображенную на рис. 4.77, 6. В оставшемся графе содержится граф, соответствующий режиму Нв. В результате получаем структуру, представленную на рис. 4.78, а, которую с помощью законов схемной алгебры приводим к виу у ду рис.4.78,6. Полученный граф Н(з)(у) соответствует режиму Нв.
Окончательно получаем логическую схему сложности 3 (см. рис. 4.71). Проектирование этим методом идет от входов к выходу, т. е. с помощью схемной алгебры строится композиция из базисных элементов. В силу того, что здесь используется прямой алгебраический подход, сложность схемы будет во многом зависеть от применяемой стратегии выбора последовательности законов при преобразовании структурного графа Нгз)(у). Это — недостаток всех методов прямого алгебраического подхода, он отсутствует только при коалгебраическом подходе. 3 4.10. Синтез нейронных структур Нейрон, модель которого была предложена У. Мак-Каллоком и У.
Питтсом (1943 г.), описывается булевой функцией вида 9о(хм хрп ( и ь 1, если ~,иЧ х;>Т, 1и1 0 в противном случае, где ю; — вес ь-го синапса, Т вЂ” порог возбуждения нейрона. Аналоговая реализация нейрона в виде композиции множительных устройств и сумматора при увеличении к обусловила повышенные требования к точности изготовления компонент. Этот факт определил необходимость цифровой реализации нейрона. 14.10. Синтез нейронных структур Первая реализация была предложена в виде гексагональной структуры (В.Л. Белявский, В.А.
Горбатов, 1970 г.; рис. 4.79), где вес синапса 1-й переменной то(ач) определяется числом горизонтальных целей, на вход которых подается переменная х;. Каждая горизонтальная цепь представляет собой последовательно включен- аксоиы Рис. 4.79. Гексвгонвпьнви структуре нейроне ные между собой ключи, при этом, если в рассматриваемой цепи нечетные ключи открываются переменной х;, а четные — пере- менной хб то в соседних горизонтальных цепях, наоборот, не- четные ключи открываются переменной х;, четные — переменной х;. Ключи, открывающиеся переменной х;, в дальнейшем будем называть неинверсны.ми, а открывающиеся переменной х; — ин- версными ключами. Нейрон гексагональной структуры описывается булевой функ- цией вида у(хм хз, ..., хь) = т ь 1, если ~,и>; х;=Т, ут1 0 в противном случае, где Т вЂ” разрешенный квазипорог, а множества разрешенных у квазипорогов (Туу моделирует порог Т в смысле У.
Мак-Каллока и У. Питтса. Настройка нейрона на заданную булеву функцию у(х1, хт, ... ..., х„) сводится к определению весов синапсов ии и множества разрешенных квазипорогов Т,. Единичные точки хо булевой функции у (хы хз, „х„), у (хо) = 1, соответствуют разрешенным квазипорогам Т, нулевые точки хр, у(хд) = О, — запрещенным квазипорогам х'е. Для определения (Тз ) и (Р,) составляем две системы урав- нений: систему для определения множества разрешенных квази- порогов и систему для определения множества запрещенных ква- зипорогов.
Системы решены, если любые два квазипорога Т и 372 Гл.4. Теория формальных грамматик и автоматов Р, не равны друг другу: (Чу, в)(Т, ~ Р,). Тривиальное решение получаем, если )О; ее 2~ ', в эхом случае значения Т, и Р, будут равны десятичному количественному эквиваленту соответствующего лвоичного набора. Очевидно, что каждый вес синапса равен 1, если функция У(21, х2,... ..., х„) янляется симметрической. Нетрудно показать, что функция у(21, х2, ..., х„) является симметрической, если в соответствующем гиперкубе не найдется яруса, который сопержит хотя бы лве точки, в которых эта функция принимает различные значения.
Обычно качество настройки нейрона определяют значением суммы весов синапсов, т. е. при настройке она минимизируется: пип 1) иц Для уменьшения трудоемкости настройки нейрона введем понятие графа неравенства с'и т (У , Ц, каждой вершине которого взаимно однозначно соответствует вес синапса и лве вершины соединены ребром тогда и только тогда, когда соответствующие веса синапсов представлены в виде одинаковых алгебраических сумм, ч3(ХР Хг, Х3) Х3 Хг х, Хг ХЗ Д 011 1$~Д3 ля бп Регмсср кввэниорогов в Рис. 4.80 входящих в различньге системы уравнений: один вес — в систему разрешенных квазипорогав, другой — в систему запрещенных квазипорогов. Используя введенное понятие, рассмотрим синтез (настройку) нейрона, реализующего булеву функцию у31(21, 22, хз)~ = Ч(2, 3, 4, 6).
Булева функция у)1(21, х2, хз) не является симметрической (рис. 4.80, а), так как нашелся ярус в гиперкубе, содержащий нули и единицы. Система лля разрешенных квазипорогов имеет вил и)2 = 71) и)2+ и)З = 32, и)1 = лэ, )О1+ и)2 = 34, 14.11. Моделирование автоматных систем сетлми Петри 373 для запрешенных— Ро се О, и)з = Р1, и)1 + и)з = Рэ и)1 + и)2 + и)з = Рз. Анализ уравнений показывает, что граф неравенстна весов является полным, слеловательно, песа синапсов попарно различны. Пусть )о1 — — 3, ю2 = 2, и)з = 1; тогда (2)] = (2з 3~ 5)з (Р)) = (1в 4~ 6). Решение найдено, нейрон имеет вил, представленный на рис.
4.80, б. На рис. 4.80, бв горизонтальной цепи перечеркнутый ключ соответствует инверсному ключу, обведенный кругом номер разряда регистра квазипорогов содержит 1, неабвеленный содержит О. Содержимое регистра квазипорогов имеет вил ...0011010... $4.11. Моделирование автоматных систем сетями Петри В связи со все более широким использонанием параллельных и распределенных вычислительных систем особую актуальность приобретают дискретные структуры, представляющие параллельные процессы. Аппаратом описания сложных систем взаимодействующих процессов янляются формальные системы типа сетей :Петри, молелируюшие динамические свойстна систем. Формализм сетей Петри общего вила основан на понятии ком'Плекта, являющегося в некотором роде обобщением понятия множества.
Как и множество, комплект — это набор элементов, но всякий элемент может входить в него более одного раза. Иначе 'говоря, отношение включения, связывающее элементы и множества, заменяются на функцию число экземпляров элемента в комплекте, которая обозначается 4~(2, В) (читается: число х в комплекте В). Множества — частный случай комплекта. Многие понятия теории множеств распространяются и на комплекты.
Так, пустой комплект аналогичен пустому множеству. Моиеность комплекта есть общее число экземпляров элементов в комплекте. Комплект А включен в комплект В (является полкамплектом), если пля всякого х рр(х, А) < 41(х, В). С помощью функции 44 легко определяются операции нал комплектами: обьсдинение комплектов А и В 44(х, А О В) = п)ах (41(х, А), ф(х, В)); пересечение комплектпов А и В 44(х, А г) В) = нйп (41(х, А), 44(х, В)); сумма комплектов А и В 44(х, А+ В) = -,ф(х, А) + 41(х, В); разность комплектов А и В 4~(х, А — В) = Щх, А) — 44(х, А Г) В). 374 Гл.4.
Теория формальных грамматик и автоматов Если М вЂ” множество, то М" — множество всех таких комплектов, построенных нз элементов М, что $1(х, В) < п, В б М"; М вЂ” множество всех комплектов, построенных из элементов М без ограничения на числе экземпляров элемента в комплекте. Сеть Петри — это четверка С = (Р, Т, 1, 0), где Р— конечное множество позиций, Т вЂ” конечное множество лсреходое, 1: Т -ь Р— входная функция, отображаюшая переходы в комплекты позиций, 0: Т -+ Р— выходная функция, отображающая переходы в комплекты позиций.
Графически сеть Петри Р ° з изображают в виде мулыиграфа с вершинами двух видов: кружки со- 2 й ответствуют позициям, планки— переходам. Функции 1 и 0 предр, р, ° „~ ставляются дугами (рис. 4.81). Позиции, дуги нз которых ведуг в переход 81, называются входными для 1", аналогично позиции, в которые ведут дуги из перехода Рис. 4.81 81, называются выходными для г .
Множество входных позиций обозначают 1(11), а выходных — 0(81). В сети Петри, изображенной на рис. 4.81, 1(81) = (р1, рг, р11, 0(11) = (рз, ре, ре). Функции 1 и 0 удобно обобшить и на отображение из позиции в комплекты переходов (Р ~ Т ), что позволяет обозначать множества входных и выходных переходов позиций р;, определяемые аналогично множествам входных и выходных позиций перехода, соответственно как 1(р;) и 0(р;).
В сети Петри, изображенной на рис. 4.81, 1(рз) = (88, 88), 0(рз) = (гт, ге). Введенные понятия относятся к статистической структуре сети Петри. Динамические свойства сети Петри определяются с помощью понятия маркировки. Маркировка уз сети Петри С = = (Р, Т, 1, 0) — это функция, отображающая множество позиций Р в множество неотрицательных целых чисел Ю. Маркировка изображается с помощью помещаемых внутрь позиций фишек (точек).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
