Введение к работе
Актуальность проблемы. При проектирований управляющих систем,то есть устройся в осуществляющих хранение, передачу и переработку информации .часто возникает задача реализация разбиений множеств булевых наборов - раз-деленкл ккожвства кэ непересекающиеся подмножестоа. Эт^ задача, например .встречается при разработке ,-.ешиф^аторов,то есть устройств,устанавливающих однозначное соответствие гнезду входным депкфрирускым сигналом и сигналом на соответствующем выходе. В ЭЕ.Ч дешифраторы преобразуют код опарений з увреышощий согнал,код адреса - в сигнал выборки соответствующей ячейки памяти. Зта задач* возникает также и при разработке систем распознавания образов. Пусть,например, смеется t образов и а признвкоз,харат<зрязтм2^іх дашок? образы. Тогда имеется некоторое множество го (n s 2П) булзвих наборов длил n - .-опустакит наборов значений признаков, и каждому образу соответствует некоторое подмножество данного кножества,прячем подмножества,соответствующие розним образом,?^ пересекаются.
Для контактных схем задача реализации систем элементарных конъюнкции гложет бить сведена я задаче реализацил разбиений булзвих наборов. Задачей реализация лроизвольных т элементарных конъюнкций одинакового ранга, зависящих от одних и тех га перемекннх , контактними схемами занимались в разно? время it. їйеннон , СВ. Яблонский , О.Б. Лупанов , Э.И.Нечипорук., Н.П.Редькин . Но все-таки для произвольного, достаточно больного "числа реализуемых конъюнкций задача не била рекена.
- A -
Цель работы. Целью работы является разработка асимптотически оптимальных методов синтеза схем, реализующих разбиения множеств булевах наборов, для основных модельных управляющих систем ( схемы лэ функциональных элементов, кон-тактнче схемы).
Методы исследований. В работе используются методы дискретной математики и математической кибернетики, члгебры, комбинаторного и математического анализа.
Научная новизна. Задача реализации произвольной с хтемы ш элементарных конъюнкций ранга п контактными схемами Очла впервые рассмотрена в 1949г. К.Шгнноном '. Для данное задачи им была построена схема в виде контактного дерева сложности 2 - 2 , где п - раиг конъюнкций. Долго время считалось , что понизить оценк" 2n+1 - 2 нельзя. Яблонский СВ. высказал предполо-жение о том что это не так. И уже в 1958г. О.Б.Лупанов ' предложил конструкцию, которая экономнее контактного дерева
асимптотически в два раза, где используется разбиение куба
*' Shannon СЕ. The synthesis of two-terminal switching circuits. - Bell Syst.Techr J., 1949, v.28,II 1, P.59-98 IPyc.nep.: Шеннон К. Работы по теории информации и кибернетике. - М.: ИЛ, 19R3. - С59-101J. ^' Лупанов О.Б. О синтезе контактных схем . Доклады АН СССР, 19!?0, т.119, N 1, Г..73-26.
їг па -~ попарно непересекающихся сфгр единичного рчд.гуса,
где г - некоторая степень двоглкіі. Пользуясь этой конструкцией , О.Б, Лупанов построил схему' с числом контактов г.ск.ли'огкчески ррвным 211. Задачз синтеза схемы для системы m пдзгмимсгеи яоїіьйшсцяй ранга п, где лі і 2? была впервые рассмотрена в 1954г. З.И.Нечшоруком '. При построении
схчіт, реализующей данную слстему, он использовал разбиение
куба Ь на і -^-} декартов'не произведений сфер единичного радиуса разиері.зсти 5. С почо^ью ju-ій конструкции Э.И.Нечл-порук показ8л 3 что при выполнения условия М б і п число
ЕОНТЗКТОН В Схеме ревизующей ИСДОИКВ ш конъюнкций КЗ
превосходит
ліп Ь + (М- 1/--,*» 1"| t l-^-j ЇМ ?>' + 2n r^+1).
Оче"идко,что ценный «летоц синїеза является асимптотически
оптимальний .тешь прз іа » ~ . Аналогичный результат
Е'ггекает непосредственно я га конструкции О.В.Лулпнова при
удалении неиспользуемых 2n - m шіодянх вершин схемы с
пнцядйптнлчи ан ребрами. ""
1' Не^морук Э.Н. 0 топологических прятгц.лах самокорректирования. - Доклады АН СЄСР,19бО,т.179,іі 4,СЛ66-7Ь9.... Нечиксрук Э.И. 0 топологических принципах самокор-пектирогаїша. - Проблема кибернетики,1S69,вып.21,С.5-102.
- б -
.Дальнейшее продвижение в решеши этой задачи бнло полу -
чено в 1975г. Н.П.Редькиным '. Им установлены следующие
Cjkth:
1 .Члсло контактов в схеме реализующей искомые иг конъюнкций
не превосходит
mln (2J-2-[ ( гг + го - 2)),
гр(1,...,п) л г і
2.Если = о(п) и log^n = o(log,m), то существует схема реализующая дашше m конъюнкций с аскютотически оптимальным числом контактов, а именно ^ .
Для реализации систем конъюнкций контактными схемзки Н П.Редькиным Сылз предложена следующая конструкция: сн&іала строи.ся двухполюсник.^еализумаий дизъюнкцию всех конъюнкций дайной системы как функцию с заданным числом единиц, и затем выходной полюс этого двухпо^аосники отождествляется с входным полюсом разделительной схвіа для кнсжсстьз булавіи н*оорсь, на которых конъюнкции дачной система обращаются а единицу. Таким образом задача реализации системы га произвольных элементарных конъюнкций ранга п может быть сведена :с задаче реализации разбиений булевых наборов. В настоящей работе приведено асимптотически оптимальное решение зздзчп реализации системы ш элементарных конъюнкций ранга п при условии -log„m ~ n .
В настоящей работе разработаны асимптотически оптимальные иетодн синтеза схем, реализующих разбиения, для схем ir*'
' Редькян Н.П. О реализация систем конъюнкций контактными схемами. - Проблемы кибернетики, 1975,вьш.ЗО,С.263-276.
.-7-
фуніщиональннх з^екентов и контактних схем. Многие результата, излученные для контактных схем,могу* быть перенесенч с незначительными изменениями п на бинарные программы , состояние только из команд передачи управления. Как частный ' случвй разбиения решается задача реализации проиэвольн "і системы пі злемєнтаріщх конъюнкций ранга п контактными
СХЄК2ЇЛІІ.
Рассмотрены также задачи реализации систем конъюнкций сакскорректирующиыися контактными схемами и синтеза самокорректирующихся і.онтактвіи разделительных схем. Показано, что соответствуйте асимптотически оптимальные самокорректирээ-щкеся схеш могут быть получены из асимптотически оптимальных некорректирующих схем с помощью тривиального дублиропания контактов. >
Методы, предлг^еіпше в цанной работе,опираются на теория A.L.Андреева ' декомпозиции частичных Нулевых функций.
' Андреев А.Е. О синтезе самокорректирующихся управ-^яв?5К систем. - Доклады АН CCCP,1984,T.277,N 3,С.521-525.
Андреев А.Е. Универсальный принцип самокорректирования. - Математический сборник,1985,т.127(169),N6,С.147-172.
Андреев А.Е. Метод бесповторкоа редукции синтеза самокорректирующихся схеа. - Доклады АН СХР, 1985, т.гВЗ, И 2,С.265-269.
Андреев А.Е. О синтезе топологических функциональных сетей. - Препринт 1..:59 ИШех АН СССР и МГУ им.М.В.Ломоносова, 1 «85,67 с.
-.-8-
Практичеекая ценность работы. Работь носит теоретический характер. Однако развитые ^. ней методы синтеза могут быть использованы при гтоектированш сл'жзшх управляющих систем. Они также могут быть попезни при созд ниті систем распознавания образов.
Апробация регулыатов работы. Результаты работы докладывались и обсуждались на Ill-ем gce-саозном семинире по дискретной математике а се приложениям (Москва,1990),на ІХ-й Всесогзной конференции "Проблемы теоретической кибернетики" (Волгоград, 1990), на ее.лшараг кафедры дкскргтной математики Волгоградского государственного университета под руководством д.ф.-м.н. А.Е.Андреева
Г (Волгиград,1989-1991).
Публикации, структура и объем работы. По теме диссертации автором опубликовано 3 работы, список которых приводится ь ггтхї ' артсрэфсрэта. Диссертация состоит из введеная, дві* глав к сгкскз литературы, содержит 5 рисунков. Библиогря^ид сллкча^т -32 наименования. Полный объем диссертации - 104 страницы клинописного текста.