О синтезе разделительных схем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАЛЯВЕНШЯ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА ЖХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

Ча правах рукописи УДК 519.7

йшшвцев Игорь Анатольевич

О СИНТЕЗЕ РАЗДЕЛИТЕЛЬНЫХ СХЕМ

01.С:.09 - математическая кибернетика •

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата фиэшсо-матенатпчесгага; „пауте

МОСКВА-1992

/7 /> / / / < * .«

( ч < . / / 1

Работа выполнена в Волгоградском государственном унивеосигете.на кафедре дискретной математики.

Ьаучный руководитель: доктор фиэчко-мэтеааткгаескш.

наук - А.Е.Андреев

Официальные оппоненты: доктор Физико-ыатемэтичеокыХ

наук,профессор " Н.П.Редькпн

кандидат физкко-метенатиче-

«их наук

Н.А.Карпова

Ведущая организация: Московский институт

энергетический

Залита диссертации состоится

75.

1992г.

в 16.05 часов на зе-едания специализированного совет-д.053.05.05 при МГУ по адресу:119899, Москва, Ленинские горы МГУ, механико-математический факультет, аудитория 14-Ой.

С диссертацией можно ознзкс'иться в библиотеке иехачико-иатешатического факультета МГУ (14 этаж)-

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

» ^ **

1992г.

Ученый' секретаре специализированного совета Д.053.05.05 доктор фиэико-иатематических наук

В.Н.Чубариков

1. ОБЩАЯ ХАРАКТЕРИСТИКА Р A F О Т Ы

Актуальность проблемы. При проектирований управляющих систем,то есть устройсяв,осуществляющих хранение,передачу и переработку информации,часто возникает задача реализация разбиений множеств булевых наборов - разделения множества ::э неперэсекакяетеся подмножества. Этч задача,например,встречается при разработке ;'.зшиС>^&торо1:,то есть устройств,устанавливающих однозначное соответствие •зезду • входам декорируемым сигналом и сигналом на соответствующее выходе. В ЭВМ дешифратора преобразуют код опарсция в управляющий сигнал,код адреса - в сигнал выборки соответствующей ячейки пеняти. Зта задач* возникает также и при разработке систем распознавания образов. Пусть,например, смеется t оСпязов и а признаков,харатеряэущих цашпле образы. Тогда имеется некоторое- множество го (m s 2П) булзв'лх наборов длирч п - .-опусташг наборов значений признаков, и каждому образу соответствует некоторое подмножество данного кножества,причем подмножества,соответствуйте розним обра-зпм,гэ пересекается.

Для коитактшх схем задача реализации систем элементарных конъюнкций может бить сведена я задаче реализации разбиений булззцз наборов. Задачей реализации лроизвольных m элементарных конъюнкций одинакового ранга, зависящих от одних и тех га перемекняг , кентаетшчл схемами занимались в разно? время 1С. ¡"еннон , C.B. Яблонский , О.Б. Лупанов , Э.И.Нечкпорук., Н.П.Редькин . Но все-таки для произвольного, достаточно больного "числа реализуемых конъюнкций задача не била регсена.

- А -

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

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

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

К.Шгннонои1'. Для данной задачи им была построена схема

п ■ 1

в виде контактного дерева сложности 2 - 2 , где п - раиг конъюнкций. Долго™ время счйталось , что понизить оценк" 2n+1 - 2 нельзя. Яблонский C.B. высказал предположение о том что это не так. И уже в 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-101). ^ Лупанов О.Б. О синтезе контактных схем . Доклады АН СССР, 1'J!?0, т. 119, N 1,

г ,г

1г аз попарно непвресеквияахся сфер единичного рэдхуса,

где г - некоторая степень двойки. Пользуясь этой конструкцией , О.Б, Лупанов построил схему' с числом контактов г.си..л1тотически ррвнын 211, Задачз синтеза схемы для системы т ялвмягаркхх хонъюшсцяй ранга п, где т & 21} была впервые рассмотрена в 1954г. З.И.Не^ипорунш * ^. При построена

охч1т, реализующей дянауи систему, он использовал разбиение

■ ?б и

гсуба Е на »-3-} декартов1 ис произведений сфор единичного радиуса размерьапти 5. С помощью эи.нЧ конструкции Э.И.Нечл-порук показ8л 3 что при выполнения условия М б ^ п число контактов в схеме ревизующей искомме га конъюнкций ко превосходит

лйп 1ч + (М + (-§-)М 1М ?>г + 2п-М,+1>.

Оче-идко,что ценный метод синтеза является асимптотически

оптимальные .тешь при т » д - Аналогичный результат Ечтекает непосредственно й га конструкции О.В.Луппнова при удалении неиспользуемых 2П - ш шюдянх вершил схемы с шщиднктннчи ан ребрами. ""

'' Нечнлорук Э.Н. О топологических прштп.лаг самокорректирования. - Дглслады АН СССР,15бО,т.179,Н 4,СЛ8б~7ЬЭ....

Нечиксрук Э.И. О топологических принципах сгмокор-ректирогаша. - Проблема кибернетики,1369,вып.21 .С.5-Ю2.

.Дальнейшее продвижение в решении этой задачи было полу -чено в 1975г. Н.П.Редькиным Км установлены следящие 4jkth:

1 .Члсло контактов в схеме реализующей искомые ш конъюнкций не превосходит •

min (21—1 ( 2Г + ¡п - 2)],

ГР(1,...,П) л . г J

2.Если log.ro = о(п) и l'og^n = oU.og,m), то существует схема реализующая данные m конъюнкций с всгслгготическв оптимальным числом контактов, о именно зог>Пт .

Для реализации систем конъюнкций контактными схеиаш Н П.Редькиньгм была предложена следующая конструкция: ск-, ja л а строк.ся дцухполюсник,Реализующий дизъюнкцйш всех конъюнкций, дайной системы как функцию с заданным числом единиц, а затем выходной полюс этого двухполюсник, отождествляется с. входным полюсом разделительной cxeia для кнсжсстьз булсжи н?»0орсь, на которых конъюнкции дачной система сбращахпгоя а единицу. Таким образом задача реализации системы ю произвольных элементарных конъюнкций ранга п может быть сведена :с задаче реализации разбиений Судовых наборов. В настоящей работе приведено асимптотически оптимальное решение задэчи реализации системы ш элементарных конъюнкций ранга п при условии -log„m ~ п .

В настоящей работе разработаны асимптотически оптимальные методы синтеза схем, реализующих разбиения, дли схем ¡г*'

1) Редькпн Н.П. О реализации систем конъюнкций контактными схемами. - Проблемы кибернетики,1975,вьш.ЗО,С.263-276.

функциональных з^екентов и контактннх схем. Многие результата, излученные для контактных елем,могу! быть перенесена с незначительными изменениями п на бинарные программы , состоял?« только из команд передачи управления. Как частный ' случпй разбиения решается задача реализации проиэвольн 1 системы т элементар}щх кош.шкцкй ранга п контактными схекагля.

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

Методы, предлг-тапгнв в ранней работе,опираются на теория А.Ь.Андреева 1^ декомпозиции частичных Нулевых функций.

^ Андреев Á.E. 0 синтезе самокорректирующихся управ-систем. - Доклады АН СССР,1984,т.277,N 3,С.521-525.

Андреев А.Е. Универсальный принцип самокорректирования. - Математический сборник,1985,т.127(169),N6,С.147-172.

Андреев А.Е. Метод бесповторной редукции синтеза самокорректирующихся exea. - Доклады АН Г"ХР, 1985, т.гВЗ, И 2,С.265-269.

Андреев А.Е. О синтезе топологических функциональных сетей. - Препринт 1:59 ИЕИех АН СССР и МГУ им.М.В.Ломоносова, 1У 85,67 с.

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

Апробация регультатов работы. Результаты работы докладывались и обсуждались на Ш-ен §се-сш'зноы о скин и ре по дискретной математике н се приложениям (Москва,1990)¡на 1Х-Й Всесогзной конференции "Проблемы теоретической кибернетики" (Волгоград, 1990), на ее.лшаг-аг кафедры д^скрг^иой математики Волгоградского государственного университета под руководством д.ф.-м.н. А.Е.Андреева

Г

(Волгоград,1989-1991>.

Публикации, структура и объем работы. По теме диссертации автором опубликовано 3 работы, список которых приводится ь угшдг ' аэтсрзфера-га. Диссертация состоит из введения, ДВ1Х глав V сгкс.кг» литературы, содержит 5 рисунков. Библиогрвфад екякчаот -32 наименования. Полный объём диссертации - 104 страницы клинописного текста.

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

Во введении указывается тс направление иате-катической кибернетики,к котором/ - относится растсвцзн работа,ус.тянаапг^сстся ее актуальность. Форкулирусся цель работы к основные р«гз?льтвти,указывается сфера иг воз»озг::ого примж-1г>н0Я. Нряз'.'датся краткое излсхекке содер*«Ч"!« . рг^-уш.

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

■^разбиением множества назовем рвзбяснав дш'гтого множества на t подмножеств- (среди которых допускается пустые), а (т?,п?,...,п+)-раэОиенкем - разбиение данного' множества на 1 -^яю^есгв с заданными неотрицательными гхщ~ НОСТЯЖ1 ш1, ш2,.. •, ^.

Обозначим через п(т,п) • - класс ь-ех множеств из пт Оулегах наборов длингс п, через ( ,..-

класс всех ^разбиений (соответственно, (ш1,...я^)-разбиений) множества д.

Будем говорить,что схема рсзл;:з/пг разбиение (Л,,,... гшогьствз Л ч и(т,п},есят. она реализует частичккй (п, ^-оператор (м^ ,?<ч,.. (то есть некоторое его

.доопределение) такей, что

И, (5) =

1, если ■"> с и , 0. есла 6 <-: А. \ А ,

*, если 6 V А," 1 = 1,2....^, 5 е Е

Схему, реалпзувЕстю т-разб':ение множествами булевых наборов .назовем разделительной.

ОСозКаЧим через ЗСЦГ'(А,!г) - ктхас'с вгег сим. реалиэув-Вйх рззСпе а!в 2 «ножествн Л. Через Ьт(5> будем обозначать сложность схемы Б упргвлшг.ей сгетегл г. Введем следувдве функционала слатаоста: . ^'(Л/Л = -Шп С.г ^З),

Г,т(п,п,г) = ¡г.зх ялх Г." (А,Т),

л. : <;т;,п> т. (I)

1.т(ш,п,ш ) - шах шах Ьх(к,2).

1 1 Ае51(га,п) 1ейд(10 ....П^}

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

21о£3п

Теорема 1.1. Если ш а 2 ,то .

Ь*(т,п,т) ~ т".

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

Контактная схема,реализующая некоторую булеву функцию (систему булевых функций) корректирует замыкание Ь (размыкание а ) контактов,если эта схема реализует ту яе сылую функцию(систему функций) при короткой эвмыкакии/размыкаяии в вей на более чем Ь(соответственно а) произвольных контактов.

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

Получен следуш'чий результат

Лемма 1.2.4.

1*>ь(ш,п) а: (а+1)(Ь+1 )ш. Отсзда^в силу теоремы 1.1,следует вывод, что асимшготическа

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

Теорема 1.2. Если л г 2 2 •, то

L*:b0n,n) ~ (а+1)(Ъ-И)гп.

Третий параграф поспкцен вопросу реализации систый поньмещий контактны,™ схемаии и сйкокорректируюп^кися контактными схемами. • •

.Ir

Обозначил через I. (п,п) - нзим~ны2ь>г число контактов, достаточное для реализации произвольной систекы m элеиелтар-ннг копъепкцж! ранга п с neperгнными >с ,... , а через vm.г») наименьшее число контактов, достаточное длк

* и ' , •

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

"остроин схему, реализутцуя m зл-эиентаргах конъюнкции ранга п следующем образом : сначала построим двухполюсник, . р&элизукщяй дизъюнкции все'г кснъучткщ-Г; дзнлой система как функции с заданна« число?,! единиц, з затем отождествим выходной долгое этого двугиигденика с входным пэлкезм разделитель1- . коп схем* для гавгестзэ булевых наборов , на ютрых ктшегата! данной пстеиьг обращаются в единицу. Поэтом/ из теорекн 1, 7 е силу того, что диз^'тнкция всех m конъюнкция мотет Сть реализована, при log я ~ п со сложность» о(ш) ,

следует

Теорема 1.3. Если log. ni ~ п , то

ьЧт.п) ~ го.

йа леммы 1.2.4 а творилы 1.2 следует Теорема 1.4. Если 1обгт ~ ,п , то

1д|Ь(ш,п) ~ (а + 1)(Ь + 1) ш

Такза доказан и следующий р-зэу^ьтат

Теорема 1.5. Если га г 2 " а ЩП?, = о(аЬ)- то

Ь^ь(и.ц) ~ (а + 1)(Ь + 1) т .

Основным результатом четвертого параграфа гшдастса

'/еореаа 1.С. Еслч 4 1о£,т * п, то

~ щ. при

Ь^Оп.пД)* ш при ~ б, где б е (0,1),

к ш 1о§ 1 '

~ —Зо§-1г "Р" 1о§7ш " 0(1 > И ^г* * ^бг"-

Теорема 1.7. Если 1о>».,1о|;,|Кд(т ,...,т )| г 1°огп п 1ог2г = о(^21ое2|Пд(т1,;..,П1)|), то

тЬ(т П Р, „ V - ^УУ —»VI Ь^т.п.п,,...^) iogгlogг |Нд (га1,... ,т1) | *

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

В перс!см параграфе рассматривается вопрос реализации разделительных схем(систем конъюнкций) для кнэжестч булевых наборов в поллых конечных базисах из , где .Р* - множество всех двукесткыг булевых функций. Полсп™ хг = х в г в 1 . где г р (0,1). Основном результатом ьтого "араграфа яьляптсп

Теорема 2.1. Если п 1оз_п = о( ш ) и в полной конечном

базисе В из Р*. не существует ни одной функции типа

т г ^

х.1 & у ' ,где * е <0,1 >, то

Теорема 2.2. Если пЛо^п = о( п ) и л полном конечно» базисе 3 из Р; существует функция типа

Т I

х 1 8» у , где г <0,1), то

^(ш.п.ш) ~ ш.

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

( iogJMro,.....га.)| "

г logJR^tm,,...,^)! ч г = °l ioggiog2|KüiBl,...;BtnJ • то

где р(Б) - минимум приведенных весов элементов базиса Б.

Теорема 2.4. Если п 1ое;.,п = о(ш) и t = o(m> , то

R гп log t

I>,o.t> " PtBJ-Tsg-- .

где р(Б) - минимум приведенных весов элементов базиса Б.

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

1. Вихлянцев И.Л. О реализации систем конъюнкций контактными . схемами. - Дискретная математика, 1989, т.1, вып.4,с.3-11.

2. Вихлянцев И.А. О самокорректировании контактных разделительных схем. - дискретная математика, 1 ПО,т.2, вып.1, С.80-86.