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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им.М.В.ЛОМОНОСОВА механико - математический факультет

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

ТАРАЗЕВИЧ Юрий Георгиевич

О СЛОЖНОСТИ РЕАЛИЗАЦИИ ФУНКЦИЙ В НЕКОТОРЫХ КЛАССАХ . ПЛОСКИХ К07ГГАКТНЫХ СХЕМ

01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

Москва 1994

Работа выполнена на кафедре дискретной математики механико - математического факультета Московского государственного университета им.М.В.Ломоносова

Научный руководитель: член - корреспондент РАН

О.Б.Лупанов

Официальные оппоненты: доктор физико-математических наук

16 час.05 мин.на заседании специализированного совета .053.05.05 при МГУ им.М.п.Ломоносова по адресу: 119899,Москва, эробьёвы горы, МГУ, мехг.;п;ко - математический факультет, /дитория 1408.

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

Автореферат разослан " 1994 г.

Учёный секретарь специализированного звета Д. 053. 05. 05 при МГУ

зктор физико - математических наук В.Н.Чубариков

A.А.Сапоженко,

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

B.А.Стеценко

Ведущая организация: Институт математики СО РАН

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

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

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

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

Научная новизна результатов заключается в .следующем. Во -первых, получена асшеттотика для функции Шеннона п классе схем на плоской целочисленной решётке ( 1г - схем ). Тек самым показано, -что:все три вышеупомянутых класса ( р - схем, .г- схем к ЗС-схем ) обладают равными возможностями с точки зрения асимптотики сложности реализации в них почти всех функций алгебры логики. Во -вторых, для линейной функции + ... + Хп ( 2 ) построена плоская контактная схема ( р - схема ) сложности 8 п. - 20(«?5) и схема сложности У1, Тем самым показано, что

класс р - схем .. сильнее " класса - схем с точки зрения

сложности реализации функций, и что существует ( эффективно заданная ) последовательность функций, реализуемая в классе Г - схем существенно проще, чем в классе - схем. В - третьих, построен многополюсник, имеющий линейную сложность в классе р - схем и квадратичную сложность в классе V - схем. Таким образом, показано, что класс р - схем сильнее " класса - схем с точки зрения реализации многополюсников.

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

Методическую основу работы составляют как ранее- известные методы математической кибернетики, в частности, метод О.Б.Лупано-ва реализации функций формулами, метол каскадов для контактных схем, так и некоторые'новые приёмы и методы, разработанные в диссертации.

Результаты диссертации докладывались на Республиканской научной конференции, посвященной 70-летию Белгосунизерситета ( Минск, апрель 1991 г'.), Межреспубликанских школах-семинарах •< Синтез и сложность управляющих систем " ( Н.Новгород, сентябрь 1992 г.; Минск, ноябрь 1993 г.).

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

Диссертация состоит из введения, четырёх глав и списка литературы ( II наименований ). Объём работы - 41 страница машинописного текста.

ОБЗОР СОДЕР^-НИЯ ДИССЕРТАЦИИ

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

В главе I определяются основные понятия и формулируются некоторые известные*результаты.

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

Определение 2. К - полюсной г- сетью называется всякий прямоугольный подграф ( см.рисунок ) плоской целочисленной решётки, некоторые К вершин на границе ( периметре ) которого выделены в качестве полюсов.

: "1- 1 -н

Высота Г - сети <5 обозначается через Н (& ) .ширина—через ),площадь—через ( С5 ).

Под сложностью [_, ( С5 ) сети с5 понимается число рёбер в ней.

Определение 3. р - схемой ( - схемой ) называется произвольная р - сеть ( ^ - сеть ), каждому ребру которой поставлен в соответствие контакт какой-либо переменной, проводник или изолятор.

Сложность, высота,ширина,площадь схемы определяются сложность! высотой, шириной, площадью соответствующей сети.

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

В главе 2 доказывается асимптотическая оценка для функции Шеи

нона в классе У* - схем: и

л'

При этом используется конструкция -О.БЛупанова-для реализации функций формулели.* ^

О.Б.Лупановым была получена асимптотика для функции Шеннона

рК-

в классе формул в произвольном конечном базисе Ф= { , Фч} ,

каждой функции ' (|> [ которого приписан некоторый неотрицательный индекс простоты ( вес ) р! ( 1= 4,___)»а каждой формуле над Ф приписан вес ( сложность ),равный сумме весов всех вхоздений базисных функций.Через р обозначается минимальный из приведённых весов базисных функций,существенно зависящих не менее чем от двух аргументов ( 2).

I) Лупанов О.Б. О сложности реализации функций алгебры логик!' формулами. - В сб.: Проблемы кибернетики.М.,1960, вып.3,с.61 - 80.

/

Для доказательства верхней оценки L О1) ~ Р {¡ск^г^

О.Б.Лупановым выбиралась базисная функция, имеющая минимальный приведённый вес р , и строилось зависящее от этой функции специальное регулярное разбиение

множества Ик всех двоичных наборов длины на непере-

секающиеся подмножества (YL € // ) .

Краткое изложение метода О.Б.Лупанова даётся в § 2.1 диссертации.

Следует отметить , что требование конечности базиса Ф можно заменить более ,» слабым " требованием существования базисной функции с минимальным приведённым весом.

С учётом последнего замечания в § 2.2 диссертации метод О.Б. Лупанова модифицируется применительно к классу f - схем. При этом в качестве базиса Ф выбирается бесконечный базис, каждой функции которого, существенно зависшей от К ^ 2 аргументов, приписан индекс простоты К - I { следует заметить, что определённое выше понятие индекса простоты и все связанные с ним понятия в настоящей диссертации нигде существенно не используются ). А для построения регулярного разбиения множеств ^ уь б k( )

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

Таким образом, строится универсальная f* - сеть , реализующая произвольную функцию h- аргументов со сложностью аснмптотичес-

кк27%л.

Тем самым, с учётом известной нижней оценю! Lp(n) -^ >

г £оа2.'ъ

доказывается следующая теорема.

I 2

Теорема I. /_, ^ '

В главе 3 реализуется линейная функция в классах р - схем и, Г - схем.

Рассматривается пара лкнейкык функций И аргументов:

• х4 + ...ч- X* (пи><12-) , 1^-=. +1 (коЛг) .

В § 3.1 доказывается следующая теорема. Теорема 2. Для любого К^Ъ

Зп-20.

При этом методом каскадов строится четырёхполюсная р - схема , реализующая пару функций Я и Р со сложностью

16 • построения схемы ясен из ри -

сунка.

В § 3.2 предыдущая конструкция существенно модифицируется применительно к классу V ~ схем. Доказывается следующая теорема.

Теорема 3. 1Г (\) + .

В главе 4 строится многополюсник функций У1 аргументов, имеющий линейную ( относительно И-) сложность в классе р - схем и квадратичную сложность в классе Г - схем. ^

Многополюсник Г^ задаётся бесповторной Ю " полюс-

ной р - схемой • сеть Х^.оторой строится следующим образом.

Строится + 1 ) - полюсная р - сеть <31ь слох-

кости 3 ( см.рисунок ). Сеть к строится из пята одинако-

вых сетей ¿^так как показано на рисунке.

I) Ветухковский Ф.Я. Об оценках числа плоских градов. - ДАН СССР, 1962, т.142, )Ы, с.50-53.

Lt n-,

U ( p.) ~ ^ •

СПИСОК РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Таразевич Ю.Г.Реализация функций контактными схемами на целочисленных решётках. - В сб.: Актуальные проблемы социально -гуманитарных и естественных наук. Тезисы научной конференции. Минск, 1991, с.193 - 194.

2. Таразевич Ю.Г. Реализация линейной функции плоскими контактными схемами и схемами на плоской целочисленной решётке. -Дискретная математика, 1992, т.4, вып.1, с. III - 116.

3. Таразевич Ю.Г. О сложности реализации многополюсников плоскими контактными схемами. - Вестн.Мос, уп-та. СерЛ.матем., мех., 1992, £ 6, с.59 - 61.