Анализ строения и оценки сложности П-схем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

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

РЫНКОВ Константин Леонидович

АНАЛИЗ СТРОЕНИЯ И ОЦЕНКИ СЛОЖНОСТИ П-СХи

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

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

Новосибирск-1993

пв оа

.« г ' * 8 *

Работа выполнена в Институте' математики СО РАН

Научный руководитель: кандидат физико-математических наук Ю.Л.Васильев

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

Р.Е.Кричевския

кандидат физико-математических наук В.М. Храпченко

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

университет им. М. В Ломоносова

Защита состоится "28 " мая 1993 г. в 16-00 часов на заседании Специализированного совета д 1)02.23.03 в Институте математики СО РАН по адресу: 630090, Новосибирск. 90, Унивефситетскш проспект, 4, Институт математики.

С дисертациея можно ознакомиться в библиотеке Института математики СО РАН.

'/ ■ о

Автореферат разослан " 28" апреля 1993 г.

Ученый секретарь Специализированного совета

доктор физико-математических наук А-в-К°сточка

овт характеристика работы

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

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

Н?учная новизна результатов заключается в следующем. Во-первых, все известные . работы по сложности схем, как правило, содержат в себе либо оценки сложности схем. либо доказательство минимальности некоторых схем. В диссертации впервые описан класс всех, минимальных схем, реализующих конкретные функции, а именно, класс всех минимальных П-схем, реализующих лиреиные булевы функции от 2к переменных (А = 0,1,2,...). Во-вторых, получено обобщение метода В. М. Храпченко построения нижних оценок сложности П-схем. что позволило охватить квадратичными по числу переменных нижними оценками сложности ' в классе П-схем весьма широкий класс булевых функция - характеристических функция плотно упакованных кодов, в частности, таких кодов, строение которых до сих пор не выяснено.

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

Методическую основу работы составляют как известные ранее методы математической кибернетики, в частности, метод в.м.Храпченко получения нижних оценок сложности П-схем, так и новые методы, разработанные в диссертации.

1) Храпченко В.М. 06 одном нетоде получения нижних оценок сложности П-схем. - Мат.эакетки, ¡97!, 10, N 1, с.аэ-92.

Результаты настоящей диссертации докладывались на ¡1 Всесоюзной сеНинаре по дискретной математике (Москва. 1987), на 1П Всесоюзном семинаре по дискретной математике (Москва, 1990), на Всесоюзной школе-семинаре по нижним оценкам сложности управляющих систем (Казаць, 1990), на Всесоюзной школе-семинаре по-синтезу и сложности управляющих систем (Львов, 1988)/ на семинарах Института математики СО РАН.

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

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

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

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

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

- '^п5 = V' •••V = V1 (п Е '«2,3...),

и удовлетворявших следующим условиям.

1. Если при некоторых значениях переменных булева функция Их .... ,хп) равна 1, то в П-схене, реализующая найдется цепь длины п, замкнутая при этих значениях переменных.

2. Если при некот рых значениях переменных булева функция Их ,...,'х) равна 0, то в П-схем8, реализующей (, наидотся

тупиковое сечение (минимальное по включению сечение), состоящее из п контактов, разомкнутых при данных значениях переменных.

Этот класс П-схен обозначен через А. Класс П-схеи А можно назвать классом локально бесповторных Л-схем, реализующих линейные булевы функции. Локально бесповторных в том смысле, что в каждой цепи и в каждой тупиковом сечении, о которых идет речь в условиях 1,2, любые два контакта помечены разными пере-мэнншш.

Д.'лзе лз5тся некоторое обобщение метода С.В.Яблонского построен» П-схем реализующих линейные булеги функции'1. Класс П-схем, построенных этим обобщенным методом, назван классом П-схемЯблонского. Класс П-схем Яблонского вводится с помощью следующего индуктивного определения. Пусть п = 1, П-схени

X , , X .

где х - произвольная булева переменная, принадлежат классу П-схем Яблонского.

Пусть для и а 2* + р и для р = 2к + рг, где к, р^ рг

такие неотрицательные целые числа, что О * р1 * 2*. О ^ рг 2к.

П-сшш .реализующие соответственно линепные булевы

функции

>«Сх......V .....V 'У*««.....ХЛ+р> 'У*^. - • •

гдо >■• ■ »*и+р " произвольные попарно различные булевы вере-

кощщэ, принадлежат классу П-схем Яблонского. Гогда классу П-схем йблонского принадлежат следующие четыре П-схемы:

OQ

Si

£ 53

Легко видеть, что каждая из двух верхних П-схем реализует линеиную булеву функцию .....*га+р). каждая из двух ниж-

них - $ {х .... ,х ).

я+р 1* ' д+// ^

Чтобы закончить определение класса П-схем Ябл некого, введем понятие перестановки подсхем. Пусть s - некоторая

. ^ и

!) Яблонский C.B. Реализация л и ней и ой {ункции в [1

- Докл.ЛИ СССР, ИЧ4. - Т. 44, N <>. - Г. вэ( 6ЯЬ.

П-схема и - произвольная ее двухполюсная подсхема, инеющая ви&

г 5

2 3

Пусть П-схема 5' является результатом замены в П-схеме 5 подсхемы на подсхему имеющую вид

__з г

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

Продолжим определение класса П-схем- Яблонского. Пусть П-схема Я принадлежит классу П-схем Яблонского, тогда этому классу принадлежит любая П-схема в', получавшаяся из Э перестановкой подсхем. Других П-схем в классе П-схем Яблонского нет.

Далее в главе 1 доказаны следующие теоремы. ТЕОРЕМА 1. Класс всех П-схем, минимальных в классе А, совпадает с классом П-схем Яблонского.

ТЕОРЕМА 2. П-схема, реализующая линеиную булеву функцию

от 2* переменных (к = 0,1,2,...}, является минимальной тогда и только тогда, когда она принадлежит А и 'минимальна в классе л..

В главе 2 диссертации приведено некоторое обобщение метода В.М. Храпченко получения нижних оценок сложности.П-схем1'. В предлагаемой новой и более общей форме метод В,.М. Храпченко развит по двум взаимосвязанным направлениям. При сохранении основных идеи этого метода, во-первых, в более простои и общей форме представлено то, к чему сводится в нем оценка сложности П-схем. А именно, доказана следующая теорема.

Через ип обозначим минимальную сложность П-схемы,

реализующей булеву функцию Г с множеством единиц У'Ш и множеством нулей . Через ВС О обозначим матрицу

сьб.Л^°т,ае»'т- гДе (Ьб,<г> = (б'а>-

ТЕОРЕМА 3. Пусть .. ,хп) - булева функция, не равная

тождественно константе. Тогда ¿.(Г) * шгшп, где минимум

1) Хгапчдкко В.М. Об одной методе получения нижних оценен г.-о*ности П-схем. - Мат. замотки, 1971, 10, N 1, с. 63-92.

берется по всем разбиениям Г матрицы В(.И на непустые подматрицы е1.....ск, удовлетворяющие условиям:

1) = ВС О-,

2) VI £ I <] А) е1 п = 0;

3) уД1 ^ ] * к) 31С1 * I $11) за я О или 1

е CJ б{ = а, а{ = а."

Через 1П обозначено число подматриц в разбиении Г.

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

№(.П * НЧГ) до некоторого его специального поднноаества йСП. Прогресс заключается в обнаружении возможности варьировать это сужение с учетом специфики булевых функция и получать отсюда нетривиальные нижние оценки таких функции, для которых метод В.М.Храпченко в исходной форме давал лишь триаиальнкз оценки. В результате доказана следующая теорена.

Через обозначено множество (0-1)-пар булевой

.функции !, с расстоянием по Хэммингу неиду наборами, входящими в пару, не превышающем 1+1.

ТЕОРЕМА 4. Пусть гСх,.. ,хл) - характеристическая функция (п,21+1)-кода (здесь 2г+1 - кодовое расстояние). Тогда справедливо следующее неравенство

2.Ш *

: = 0 J

(,1 = 0

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

Список работ, в которых опубликованы основные результаты диссертации. *

1. Ричков K.J. Модификация метода В.Ц.Храпченко и применение ее к оценкам слоаности П-схек для кодовых функций //Дискретный анализ. - Новосибирск, 1985. - Вып. 42. - С.91-98.'

2. Рычков К.Л. Модификация метода В.И.Храпченко и применение ее к оценка« сдоености П-ехеи для кодовых функции //Труды семинара по дискретной математике и ее приловениян. -М.: ШТ 1988. - С. 288. •

3. Рычков K.J. О шшшальник П-схекак для линейных булевых функиип //Дискретный анализ - Новосибирск, 1991. -Вып.51. - С.84-104.

в

Надписано к печати ,04.1993

Формат бумаги 60 64 Объеи 0,ß п.л.

Тираж 100 экз. Заказ 38

Отпечатано аа ротапвинто Института математики СО РАН