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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА

Механнхо-математнчесхнк факультет

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

Зыков Константин Анатольевич

О СЛОЖНОСТИ ВЫЧИСЛЕНИЯ НЕКОТОРЫХ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ СХЕМАМИ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ

Специальность 01.01.09 — математическая кибернетика

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

Москва — 1994

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

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

профессор О. Б. Лупанов.

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

профессор М. М. Глухов, — кандидат физико-математических на-А. И. Рыбко.

Ведущая организация. — Институт математики

Сибирского отделения РАН.

Защита диссертации, состоится " ¿Р" НАЯ&РЗ 1994 в 16 час. 05 мин. на заседании Специализированного совета Д.01 05.05 по математике при МГУ им. М. В. Ломоносова по адрес 119899, ГСП, Москва, Ленинские горы, МГУ, механико-математ ческкй факультет, ауд. 14—08.

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

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

.Ученый секретарь Специализированного совета Д.053.05.05 при МГУ д. ф.-м. н., профессор ^ 1 В.. Н. Чубарнкс

Актуальность темы.

Данная работа относится к одному из важных разделов математической кибернетики — теории синтеза и сложности управляющих систем. Интерес к ней стимулируется все более широким . применением ЭВМ. Одной из самых глубоких и трудных проблем в этой области является проблема нижних оценок сложности. Внимание к этой проблеме во многом объясняется ее тесной связью с проблемой сравнения возможностей различных моделей вычислений. В диссертации проблема нетривиальных нижних оценок изучается в рамках одного из основных модельных классов вычислений —^ схем из функциональных элементов. Этот класс является удобной математической моделью дискретных преобразователей специального вида, занимающих важное место в современной технике управляющих и вычислительных устройств, так как наиболее точно отражает работу реальных вычислительных устройств.

Цель работы.

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

Методика исследования.

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

Научная новизна.

В диссертации получены следующие новые результаты:

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

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

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

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

Теорехическал и практическая ценность.

Работа ноокт теоретический характер: Полученные результаты могут быть использованы при проектировании вычислительных систем, а также при составлении и расшифровке генетических моделей.

Апробация работы.

Результаты диссертации докладывались и обсуждались на X международной конференции по проблемам теоретической кибернетики (Саратов, 1993), на III и IV школах семинарах по синтезу и сложности управляющих систем (Ташкент, 1991 и Нижний Новгород, 19Э2), па школе-семинаре по дискретным моделям в теории управляющих систем (Москва, 1993), на конференции молодых ученых ыоханико-математического факультета МГУ (1993), а также на семинарах и школис-семинарах п МГУ им. М. В. Ломоносова.

Публикации.

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

Структура работы.

Диссертация состоит из введения, двух глав, разбитых на девять параграфов и списка литературы, включающего 24 наименования. Общий объем работы составляет 71 страницу. Изложение материала проиллюстрировано 36 рисунками.

Содержание работы.

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

В первой главе даются основные определения и рассматривается задача о сложности реализации схемами из функциональных элементов в базисе из всех двуместных булевых функций систем булевых функций, удовлетворяющих специальному ограничению, накладываемому на взаимное расположение существенных переменных у функций, входящих в систему. Это расположение задается квадратной циклической булевой матрицей Мь, имеющей 2А: (к 6 строк. Первая половина первой строки матрицы Мк состоит сплошь из 1, а вторая — сплошь из 0. Каждая последующая . строка матрицы получается из предыдущей путем циклического сдвига на одну позицию вправо. Эта матрица введена в параграфе 1 главы 1. В этом же параграфе сформулирован основной результат первой главы:

Теорема 1. Пусть Д(г),..., /г»(5) — произвольна.г система булевых функций, удовлетворяющая следующему условию: для каждого г = 1,..., 2к функция существенно зависит от х^ (] = — 1,..., 2к) тогда, и только тогда, 'когда в матрице Мы элемент

vij; = l. Тогда при к > 2

£(/i(5), ...,/**(*))£ 4*-3.

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

Параграф 3 главы 1 посвящен основным определениям и вспомогательным утверждениям.

В параграфе 4 главы 1 проводится основная часть доказа- . тельства теоремы 1, с использованием лемм 9 и 10, доказательству которых посвящен параграф 5.

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

2 к

линейных булевых функций <у = VJ mijxi (mod2) доказана Теорема 2. При к > 2 сложность реализации системы функции gi,..., g2.k я базисе из одной функции — двоичного сложения равна 4к — 3.

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

Во второй главе диссертации исследуется вопрос о сравнении ¿ложности реализации схемами из функциональных элементов в базисе из единственной функции — Двуместного двоичного сложения— систем линейиьлх булевых функций (без свободного члена), задаваемых матрицами беа крямоугольников (то есть не содержащих подматриц размерь. 2 * 2 '..остоящюс 'л'л от:их единиц», со

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

Э. И. Нечипорук доказал*), что для схем из функциональных элементов в базисе' {&."\/} при реализации систем дизъюнкций, задаваемых матрицами без прямоугольников, невозможна реализация со сложностью меньшей, чем сложность тривиальной реализации. Там же был установлен аналогичный результат относительно реализации матриц без прямоугольников в классе вентильных схем. Однако для схем из функциональных элементов в базисе {©} аналогичное утверждение неверно. Это показывает простой пример, приведенный в параграфе 7 диссертации: система функций Д = XI ©22, /2 = 22®24, /3 = Х4@Х5, /4 = Zl©:E3©£4, /5 = 12 ® гз 8 2Г5 реализуется со сложностью 6. в то время как сложность тривиальной реализации равна 7.

Далее (параграф 8 главы 2) показывается, что приведенный выше пример является в некотором смысле простейшим, дающим уменьшение сложности по сравнению с тривиальной реализацией. Для величин L(B) — сложности реализации системы функций, задаваемых матрицей В — и Ьт{В) — сложности тривиальной реализации этой системы — устанавливаются следующие факты. Теорема 3. Пусть В — матрица без прямоугольников и L(B) <

< LT{B). Тогда Lt(B) ^ 7.

Следствие. Пусть В — матрица без прямоугольников и L(B) <

< Lt(B). Тогда матрица .В содержит не менее пяти строк, то есть система функции, 'задаваемая матрицей В, существенно зависит не менее, чем от пяти переменных.

В параграфе 9 главы 2 строится семейство матриц, для ко-

*) Нечипорук Э. И. Об одной булевской матрице // Проблемы кибернетики. —М.: Наука, 1969, — Вып. 21, — с. 237-240.

торого достигается уменьшение сложности асимптотически по крайней мере в два раза по сравнению с тривиальной реализацией.

В заключение автор пользуется возможностью выразить глубокую благодарность научному руководителю чл.-корр. РАН О. Б. Лупанову за постановку задачи, постоянное внимание к данной работе и ценные советы.

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

1. Зыков К. А. О сложности реализации систем линейных булевых функций // Методы и системы технической диагностики.

--Вып. 18. — Саратов, 1993. — с. 70-71.

2. Зыков К. А. Реализация некоторых систем булевых функций схемами из двувходовых элементов // Дискретная математика. — М.: 1993, — т. 5, вып. 3. — с. 125-149,- •