Московский государственный университет

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

На правах рукописи

Власов Никита Вадимович

О сложности мультиплексорных функций

в некоторых классах схем

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

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

Автореферат

диссертации на соискание ученой степени

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

Москва 2013

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

Научный руководитель: доктор физико-математических наук, профессор Ложкин Сергей Андреевич

Официальные оппоненты: доктор физико-математических наук, профессор кафедры дискретной математики механико-математического факультета МГУ имени М. В. Ломоносова Кочергин Вадим Васильевич кандидат физико-математических наук, ведущий инженер по разработке программного обеспечения в филиале компании Ментор Графикс Девелопмент Сервисез Лимитед (Ирландия) Шиганов Александр Евгеньевич

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

Защита диссертации состоится 20 декабря 2013 года в 11 часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М. В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМК, аудитория 685.

Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за 2 дня по тел. (495) 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ.

С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru/ в разделе Наука Работа диссертационных советов Д 501.001.44.

Автореферат разослан 20 ноября 2013 года.

Ученый секретарь диссертационного совета к. т. н, ведущий научный сотрудник В. А. Костенко

Общая характеристика работы

Актуальность темы. Теория синтеза управляющих систем является одним из основных разделов дискретной математики и математической кибернетики1,2,3. Она возникла в 30-40-х годах прошлого века в связи с необходимостью проектирования и логического описания дискретных вычислительных устройств различного типа. К. Шеннон4,5 дал строгую математическую постановку задачи синтеза управляющих систем, положив тем самым начало соответствующей теории, исследования в которой ведутся с тех пор непрерывно. В целом, в теории синтеза управляющих систем изучаются модели различных дискретных преобразователей сигналов, их сложность, надёжность и другие характеристики.

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

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

Задача синтеза ставится для определённого класса управляющих систем. Количество таких классов довольно велико, что вызвано потребностью в исследовании разных моделей и характеристик реальных схем. Для каждого класса управляющих систем задаётся определённая структура его схем (как правило, это графы определённого вида) и вводится их функционирование дискретного типа (в виде системы функций алгебры логики). Предполагается, что рассматриваемый класс является полным, то есть с помощью его схем можно реализовать любую функцию алгебры логики (ФАЛ) или систему таких функций. Предполагается также наличие функционала сложности, который каждой схеме ставит в соответствие некотоЛупанов О. Б. Асимптотические оценки сложности управляющих систем. М.:

Изд-во МГУ, 1984. 137 с.

2 Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. 384 с.

3 Ложкин С. А. Лекции по основам кибернетики. М.: Издательский отдел ф-та ВМиК МГУ, 2004. 251 с.

4 Shannon C. E. A symbolic analysis of relay and switching circuits. Trans. AIEE, 1938, v. 57, pp. 713–723.

5 Shannon C. E. The synthesis of two-terminal switching circuits. Bell Syst. Techn. J, 1949, v. 28, pp. 59–98.

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

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

Указанное значение считается сложностью данной системы ФАЛ в рассматриваемом классе схем относительно изучаемого функционала. В теории синтеза выделяют при этом два основных направления: массового и индивидуального синтеза.

Методы массового или, как его ещё называют, универсального синтеза позволяют единообразно строить схемы для произвольных ФАЛ. Критерием качества таких методов являются обычно получаемые с их помощью верхние оценки функции Шеннона, которая зависит от натурального аргумента n, равна сложности самой сложной ФАЛ от n булевых переменных (БП) и, как правило, при n = 1, 2,... асимптотически совпадает со сложностью почти всех ФАЛ от этих БП.

Методы массового синтеза применимы к любой ФАЛ и позволяют для почти всех ФАЛ получать схемы, сложность которых близка к оптимальной. При этом, однако, сложность схем, получаемых с их помощью для конкретных (индивидуальных) ФАЛ, может быть далека от оптимальной, в связи с чем и возникает необходимость решения соответствующей задачи индивидуального синтеза.

Одним из самых распространённых и широко используемых классов ФАЛ является класс управляющих ФАЛ, к числу которых относятся и так называемые мультиплексорные ФАЛ. Будем называть мультиплексорной (квазимультиплексорной) ФАЛ порядка n и ранга r ФАЛ от n адресных и r информационных БП, которая существенно зависит от всех этих БП, но на любом наборе значений адресных БП имеет только одну (соответственно, не более, чем одну) существенную информационную БП.

Наиболее распространённым вариантом мультиплексорной ФАЛ является мультиплексорная ФАЛ порядка n и ранга 2n, которая считается стандартной мультиплексорной ФАЛ порядка n (мультиплексором порядка n) и обозначается µn. При этом под стандартной квазимультиплексорной ФАЛ порядка n понимается квазимультиплексорная ФАЛ, которая получается из ФАЛ µn в результате подстановки констант вместо части её информационных БП.

Стандартная мультиплексорная ФАЛ, мультиплексорные ФАЛ общего вида и квазимультиплексорные ФАЛ часто применяются как в теоретических исследованиях, так и при синтезе интегральных схем. Данные ФАЛ обычно являются составной частью подсхем выбора из памяти и коммуникационных подсхем, что вызывает необходимость их оптимизации по различным параметрам: площади, задержке, энергопотреблению и т. д. Мультиплексорные ФАЛ используются как в теории индивидуального синтеза при синтезе оптимальных и близких к оптимальным схем, так и в теории массового синтеза при разработке универсальных методов построения схем и изучении поведения функции Шеннона. Кроме того, ФАЛ мультиплексорного типа находят применения в вопросах тестирования и исследования надёжности схем.

В иностранной литературе6,7 мультиплексорная ФАЛ µn обычно называется storage access function (т. е. функция доступа к памяти ) либо lookup function (т. е. функция поиска ), что подчёркивает сферу её применений.

Цель диссертации. Целью диссертации является разработка методов синтеза схем, которые реализуют ФАЛ мультиплексорного типа и глубина (сложность) которых либо оптимальна, либо близка к оптимальной, а также методов получения нижних оценок глубины и сложности указанных ФАЛ, позволяющих, в частности, обосновывать оптимальность построенных схем на уровне асимптотических оценок высокой степени точности (АОВСТ).

Научная новизна. Все полученные в диссертации результаты являютTardos G., Zwick U. The communication complexity of the universal relation.

Proceedings of the 12th Annual IEEE Conference on Computational Complexity (CCC), 1997, pp. 247–259.

7 Wegener I. The complexity of Boolean functions. Teubner, Stuttgart: John Wiley & Sons Ltd, and B. G, 1987, 458 pp.

ся новыми. В данной работе впервые установлено точное значение глубины стандартной мультиплексорной ФАЛ порядка n, n 20, а также получены АОВСТ для её сложности. Предложены новые методы синтеза схем для мультиплексорных ФАЛ, разработан новый подход к получению нижних оценок сложности ФАЛ мультиплексорного типа.

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

Разработанный подход к доказательству нижних оценок может, по мнению автора, быть использован при исследовании сложности реализации ФАЛ близких к ФАЛ мультиплексорного типа.

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

Публикации и апробирование. По теме диссертации опубликовано 7 печатных работ [1]–[7], из которых статьи [3, 5, 7] в изданиях, рекомендованных ВАК. Результаты диссертации докладывались на семинарах кафедры математической кибернетики факультета ВМК МГУ, а также докладывались и обсуждались на следующих конференциях и семинарах:

1. IX международный семинар Дискретная математика и её приложения (Москва, МГУ, 18–23 июня 2007 г.);

2. XV международная конференция Проблемы теоретической кибернетики (Казань, 2–7 июня 2008 г.);

3. XVI международная конференция Проблемы теоретической кибернетики (Нижний Новгород, 20–25 июня 2011 г.);

4. XI международный семинар Дискретная математика и её приложения (Москва, 18–23 июня 2012 г.) Структура и объём работы. Диссертация состоит из введения, двух глав и списка литературы. Текст изложен на 90 страницах. Список литературы включает 66 наименований.

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

Пусть B = {0, 1} булево множество, а X = {x1,..., xn,...} счётный упорядоченный алфавит (входных) булевых переменных (БП), принимающих значения из B. При этом будем считать, что любая ФАЛ f, f : B n B, зависит от набора БП x = (xi1,..., xin ), где B n единичный n-мерный куб, а xij, j [1, n], БП, которая связана с j-м разрядом указанного куба.

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

Пусть Б = {1,..., b } полный в P2 базис функциональных элементов (ФЭ), где i-й, i [1, b], ФЭ реализует базисную ФАЛ i (x1,..., xki ), а его сложность ( вес ) и глубина (задержка) равны 1. Далее будем рассматривать, в основном, стандартный базис Б0 = {x1 · x2, x1 x2, x1 } и так называемый унимодальный базис U2, состоящий из всех ФАЛ вида x1 ·x2 1 Схемой из функциональных элементов (СФЭ) над базисом Б будем называть ориентированный ациклический граф, в котором все истоки и только они помечены символами различных БП из множества X и считаются входами схемы, все остальные вершины помечены символами ФАЛ из базиса Б, а часть вершин схемы, кроме того, объявлена её выходами. При этом входящие в любую вершину v схемы дуги упорядочены, а их число, равное k, и порядок соответствуют количеству и порядку БП, от которых зависит связанная с v базисная ФАЛ (x1,..., xk ). Считается, что в указанной вершине v данной схемы реализуется ФАЛ (f1,..., fk ), где fi, i [1, k], ФАЛ, реализованная в той вершине, из которой в вершину v идёт дуга с номером i. Предполагается, что схема реализует систему ФАЛ, состоящую из тех ФАЛ, которые реализованы в её выходных вершинах.

Формулой над базисом Б будем называть СФЭ с 1 выходом, в которой из каждой вершины, отличной от входов и выхода, исходит одна дуга.

Формулу над базисом Б0, в которой все ФЭ ¬ расположены над БП, будем называть формулой с поднятыми отрицаниями. Для произвольной формулы F над базисом Б0 с поднятыми отрицаниями определим, как обычно, моделирующую её структурно и функционально -схему. При этом произвольной БП xi и её отрицанию xi, рассматриваемым как простейшие формулы, сопоставим -схему из одного контакта, помеченного xi и xi соответственно, а записи F = F1 &F2 (F = F1 F2 ) сопоставим -схему, которая представляет собой последовательное (соответственно параллельное) соединение -схем 1 и 2, сопоставленных формулам F1 и F2. Заметим, что любая -схема является моделью указанного вида для некоторой формулы с поднятыми отрицаниями.

Через L() (L( )) будем обозначать сложность СФЭ (соответственно сложность -схемы ), то есть число ФЭ в (соответственно контактов в ). Сложность формулы F, то есть сложность соответствующей ей СФЭ, будем также обозначать через L(F), а её ранг, то есть число символов БП в записи F, через R(F). Под глубиной D() одновыходной СФЭ или формулы будем понимать максимальную длину цепей от входов к её выходу. Заметим, что ранг формулы над базисом Б0 с поднятыми отрицаниями равен сложности моделирующей её -схемы.

Под схемной (формульной) сложностью ФАЛ f в базисе Б будем понимать величину LC (f ) (соответственно LФ (f )), равную минимальной сложБ Б ности тех СФЭ (соответственно формул) над базисом Б, которые реализуют ФАЛ f. Аналогичным образом определяется сложность L (f ) ФАЛ f в классе -схем, а также её глубина DБ (f ) в базисе Б, равная минимальной глубине реализующих ФАЛ f СФЭ над Б, которая, очевидно, всегда достигается на некоторой формуле.

В базисе Б0, кроме приведённых выше полных функционалов сложности, будем рассматривать также частичные функционалы сложности L&, () и D&, (), которые учитывают сложность и глубину только ФЭ & и схемы. При этом через LФ (f ), D&, (f ) и LС (f ) будем обозначать значения введённых частичных функционалов сложности для ФАЛ f в классе формул и СФЭ соответственно.

d 2, компонент. Тогда мультиплексорной ФАЛ разбиения называется ФАЛ характеристическая ФАЛ компоненты i, i [0, d 1], причём где i первые n переменных этой ФАЛ называются её адресными, а оставшиеся d её информационными БП. Мультиплексорную ФАЛ тривиального разбиения булева куба порядка n на 2n компонент мощности 1, упорядоченных в соответствии с лексикографическим порядком связанных с ними наборов, будем называть стандартной мультиплексорной ФАЛ µn порядка n или просто мультиплексором порядка n.

Любая мультиплексорная ФАЛ µ, где компонент, считается мультиплексорной ФАЛ порядка n и ранга d. Ту ФАЛ, которая получается из мультиплексорной ФАЛ f порядка n подстановкой констант вместо части (возможно, пустой) её информационных БП, будем называть связанной с f квазимультиплексорной ФАЛ порядка n и ранга r, где r число оставшихся информационных БП. При этом квазимультиплексорные ФАЛ, получающиеся в результате подстановки нулей, считаются нулевыми, а квазимультиплексорные ФАЛ порядка n и ранга r, связанные с ФАЛ µn, называются стандартными квазимультиплексорными ФАЛ порядка n и ранга r или, иначе, квазимультиплексорами порядка n и ранга r. Будем называть информационной областью квазимультиплексора множество тех наборов значений его адресных БП, на которых он равен одной из своих информационных БП.

Кроме того, во второй части введения формулируются в виде теорем 1-6 полученные в диссертации оценки сложности реализации стандартной мультиплексорной ФАЛ и квазимультиплексорных ФАЛ в рассматриваемых классах, а также оценки глубины реализации указанных ФАЛ.

Теорема 1. Для последовательности квазимультиплексорных ФАЛ µn порядка n, где n = 2, 3,... и ранга r, r = r(n), где 3 r(n) 2n, справедливы соотношения:

Теорема 2. При n = 2, 3,... для мультиплексорной ФАЛ µn справедливы неравенства:

Теорема 3. При n = 1, 2,... для мультиплексорной ФАЛ µn справедливы неравенства:

Теорема 4. При n = 1, 2,... для мультиплексорной ФАЛ µn справедливы неравенства:

Теорема 5. Для мультиплексорной ФАЛ µn, n = 1, 2,..., справедливы соотношения:

1. D&, (µ1 (x, y)) = DU2 (µ1 (x, y)) = 2;

Теорема 6. Пусть для n = 1, 2,... и натуральных последовательностей r = r(n) 2n, d = d(n) n выполнены условия Тогда для любой последовательности нулевых квазимультиплексоров µn, n = 1, 2,..., порядка n и ранга r(n) таких, что информационную область µn можно представить в виде объединения непересекающихся граней размерности не меньше, чем d(n), куба B n, выполняются соотношения Первая глава посвящена доказательству верхних оценок сложности и глубины реализации мультиплексорных ФАЛ.

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

Кроме того, в разделе 1.1 доказываются некоторые оценки глубины стандартной мультиплексорной ФАЛ µn при n = 1,..., 5.

В разделе 1.2 доказываются верхние оценки глубины мультиплексорной ФАЛ µn, n 6, в стандартном базисе Б0 и в унимодальном базисе U для функционалов сложности (глубины) D&, (f ), D(f ) и DU2 (f ). При этом построение оптимальных и близких к оптимальным по глубине схем производится следующим образом. Набор входных адресных БП x = (x1,..., xn ) делится на три части, и булев куб от БП первой части разбивается на непересекающиеся единичные сферы. Далее строится декартово произведение каждой компоненты такого разбиения и каждого набора куба от второй группы адресных БП. На каждой компоненте построенного разбиения булева куба от первых двух групп адресных БП мультиплексорная ФАЛ µn моделируется с помощью одной адресной БП либо её отрицания, что позволяет построить формулу в стандартном базисе, реализующую ФАЛ µn и имеющую глубину не более n + 3 для функционалов сложности D&, (f ) и DU2 (f ). Далее для значений n 20 часть построенных компонент отбрасывается, а затем группируется вместе так, чтобы итоговая формула имела глубину не более n + 2. Основным результатом раздела 1.2 является следующая лемма8.

Лемма 1 (6). Для мультиплексорной ФАЛ µn, где n > 5, справедливо:

D&, (µn (x, y)) = DU2 (µn (x, y)) n + 3, если 5 < n < 20, D&, (µn (x, y)) = DU2 (µn (x, y)) n + 2, если n 20.

В разделе 1.3 рассматриваются вопросы оптимальной по сложности реализации ФАЛ µn в классах -схем и формул с получением для этой сложности верхних АОВСТ в классе -схем и близких к АОВСТ верхних оценок в классе формул. В качестве основного метода синтеза в данном разделе используется техника так называемых m-регулярных разбиений булева куба9, которая позволяет моделировать системы ФАЛ от m БП на компоненте такого разбиения с помощью одной БП или её отрицания.

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

9 Ложкин С. А. О синтезе формул, сложность и глубина которых не превосходят асимптотически наилучших оценок высокой степени точности // Вестник Московского университета. Сер. 1, Математика, Механика. 2007. №3. С. 20–26.

При синтезе -схем в данном разделе набор адресных БП делится на несколько частей, а булев куб от первой группы БП разбивается на mрегулярные компоненты, на каждой из которых строится дополнительное подразбиение таким образом, чтобы на любой полученной компоненте ФАЛ µn совпадала либо с адресной БП, либо с её отрицанием. В классе формул, кроме того, используется дополнительное подразбиение для минимизации числа ФЭ ¬, входящих в формулу. Получаемые при этом -схемы и формулы имеют требуемую сложность.

Основными результатами раздела 1.3 являются утверждения, в которых устанавливаются верхние оценки сложности реализации ФАЛ µn в указанных классах схем.

Лемма 2 (8). В базисе Б0 имеется формула с поднятыми отрицаниями Fn (x, y), которая реализует ФАЛ µn (x, y) и для которой Следствие.

Лемма 3 (9). В базисе Б0 имеется формула Fn (x, y), которая реализует ФАЛ µn (x, y) и для которой Следствие.

В разделе 1.4 доказываются верхние оценки сложности мультиплексорных ФАЛ в классе СФЭ, для чего набор адресных БП ФАЛ µn делится на две части длины10 n и n соответственно, для каждой из которых строятся мультиплексоры соответствующего порядка, которые используют общие элементарные конъюнкции от адресных БП. Таким образом, устанавливается справедливость следующей леммы.

10 Через a ( a ) обозначается ближайшее к a сверху (соответственно, снизу) целое число.

Лемма 4 (12). В базисе Б0 имеется СФЭ n, которая реализует ФАЛ µn (x, y), n 2, и для которой Следствие.

Кроме того, в разделе 1.4 полученные в разделах 1.2 и 1.3, а также в данном разделе верхние оценки сложности и глубины стандартных мультиплексорных ФАЛ обобщаются на некоторый класс квазимультиплексорных ФАЛ.

Лемма 5 (13). Пусть для n = 1, 2,... и натуральных последовательностей r = r(n) 2n, d = d(n) n выполнены условия Тогда для любой последовательности нулевых квазимультиплексоров µn, n = 1, 2,..., порядка n и ранга r(n) таких, что информационную область µn можно представить в виде объединения непересекающихся граней размерности не меньше, чем d(n), куба B n, выполняются соотношения Вторая глава посвящена описанию нового подхода к доказательству нижних оценок сложности ФАЛ мультиплексорного типа. Также в ней устанавливаются нижние оценки глубины и сложности реализации стандартной мультиплексорной ФАЛ и квазимультиплексорных ФАЛ.

В разделе 2.1 вводятся такие понятия как незабиваемое множество БП и незабиваемая БП11. Для БП, входящих в такие множества, удаётся установить способ их вхождения в схему, который характеризуется тем, что ФАЛ, реализуемая данной схемой, сохраняет существенную зависимость от незабиваемой БП после любой подстановки констант вместо других БП из указанного множества. Информационные БП квазимультиплексорной ФАЛ образуют незабиваемое множество её переменных.

На основе свойств незабиваемости множества информационных БП доказывается следующие леммы, в которых устанавливаются нижние оценки глубины стандартной мультиплексорной ФАЛ и квазимультиплексорных ФАЛ.

Лемма 6 (15). Для любой формулы Fn в базисе Б0, реализующий мультиплексорную ФАЛ µn, n 2, справедливы соотношения:

Лемма 7 (16). Для квазимультиплексорной ФАЛ µn порядка n и ранга r, r 2, выполняется неравенство Из лемм 1 и 6 следует справедливость теоремы 5, а из леммы 7 нижняя оценка последнего из соотношений теоремы 1.

В разделе 2.2 приводится описание нового подхода к доказательству нижних оценок сложности ФАЛ мультиплексорного типа. Он заключается в разбиении входных БП схемы, реализующей заданную ФАЛ, на несколько специальных групп, определённых структурой схемы. Далее происходит подстановка констант вместо всех или почти всех БП в каждой из таких групп и последующее упрощение схемы. Затем производится анализ структуры полученной схемы и оценивается её сложность на основе 11 Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов. М.:

Издательский отдел ф-та ВМиК МГУ, 2000. 58 с.

невозможности устранения при этом части оставшихся переменных данной ФАЛ. При этом исследуются подсхемы определённого вида, которые являются характерными для получаемых квазимультиплексорных ФАЛ, и изучаются закономерности и ограничения в пределах таких подсхем, за счёт которых удаётся установить число дополнительных ФЭ, входящих в схему. В данном разделе формулируются и доказываются вспомогательные утверждения, позволяющие делать выводы о строении схем, реализующих квазимультиплексорные ФАЛ.

В разделе 2.3 разработанный подход применяется для доказательства нижних оценок сложности квазимультиплексорных ФАЛ в классах -схем и формул в стандартном базисе, приведённых в следующих утверждениях.

Лемма 8 (20). Для любой формулы Fn с поднятыми отрицаниями в базисе Б0, реализующей квазимультиплексорную ФАЛ µn порядка n и ранга r, где n 2 и 3 r 2n, справедливо неравенство Следствие. Для квазимультиплексорной ФАЛ µn порядка n и ранга r, n 2, r = r(n), 3 r(n) 2n, справедливы соотношения Лемма 9 (22). Для произвольной формулы Fn в базисе Б0, реализующей квазимультиплексорную ФАЛ µn порядка n и ранга r, где n = 2, 3,..., r = r(n), 1 r(n) 2n и 2 = o(r(n)), справедливо неравенство Следствие. Для квазимультиплексорной ФАЛ µn порядка n и ранга r, n 2, r = r(n), 1 r(n) 2n и 2 = o(r(n)), справедливо неравенство Следствия из лемм 2, 3, 8 и 9 доказывают справедливость теорем 2 и 3.

В разделе 2.4 на основе указанного подхода устанавливаются нижние оценки сложности квазимультиплексорных ФАЛ в классе СФЭ.

Лемма 10 (23). Для любой СФЭ n в базисе Б0, реализующей квазимультиплексорную ФАЛ µn порядка n и ранга r, n 2, r = r(n), 1 r(n) 2, справедливо:

Следствие. Для квазимультиплексорной ФАЛ µn порядка n и ранга r, n 2, r = r(n), 1 r(n) 2n, справедливо неравенство Справедливость теоремы 4 следует из лемм 4 и 10, а теоремы 1 из леммы 7 и из следствий из лемм 6, 8, 9 и 10.

Кроме того, из леммы 5 и теоремы 1 следует справедливость теоремы 6.

Основные результаты диссертации 1. Предложены новые методы синтеза схем для мультиплексорных и квазимультиплексорных функций алгебры логики (ФАЛ); с помощью этих методов получены новые, более точные верхние оценки сложности (глубины) указанных ФАЛ.

2. Разработаны новые методы получения нижних оценок сложности ФАЛ мультиплексорного типа; с помощью этих методов установлены новые, более точные оценки их сложности в классах -схем, формул и схем из функциональных элементов (СФЭ).

3. Установлены асимптотические оценки высокой степени точности (АОВСТ) для сложности реализации стандартной мультиплексорной функции в классе -схем и в классе формул в унимодальном базисе.

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

4. Получены близкие к АОВСТ оценки сложности реализации стандартной мультиплексорной функции в классах формул и СФЭ в стандартном и унимодальном базисах.

5. Установлено, что глубина стандартной мультиплексорной функции порядка n в унимодальном базисе равна n + 2, если n 20.

Публикации по теме диссертации [1] Ложкин С. А., Власов Н. В. О глубине мультиплексорной функции // Материалы IX Международного семинара Дискретная математика и её приложения (Москва, МГУ, 18–23 июня 2007 г.). 2007. С. 102– [2] Ложкин С. А., Власов Н. В. О сложности мультиплексорной функции в классе -схем // Проблемы теоретической кибернетики. Тезисы докладов XV международной конференции Проблемы теоретической кибернетики (Казань, 2–7 июня 2008 г.). 2008. С. 76.

[3] Ложкин C. А., Власов Н. В. О сложности мультиплексорной функции в классе -схем. // Ученые записки Казанского университета. Сер. Физ.матем. науки. 2009. Т. 151, кн. 2. С. 98–106.

[4] Власов Н. В. О сложности мультиплексорной функции в классе формул // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20–25 июня 2011 г.).

2011. С. 96–97.

[5] Ложкин C. А., Власов Н. В. О глубине мультиплексорной функции // Вестник Московского университета. Сер. 15, Вычислительная математика и кибернетика. 2011. №2. С. 40–46.

[6] Власов Н. В. О сложности мультиплексорной функции в классе схем из функциональных элементов // Материалы XI международного семинара Дискретная математика и её приложения (Москва, 18–23 июня 2012 г.). 2012. С. 100–101.

[7] Власов Н. В. О сложности мультиплексорной функции в классе формул // Вестник Нижегородского государственного университета им. Н.

И. Лобачевского. 2012. №5. C. 38–41.