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

• Власов, Никита Вадимович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Власов, Никита Вадимович

Оглавление

Введение

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

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

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

1.1. Некоторые понятия и конструкции, связанные с реализацией

мультиплексорных ФАЛ

1.2. Реализация мультиплексоров формулами с оптимизацией их глубины

1.3. Реализация мультиплексоров 7г-схемами и формулами с опти-

мизацией их сложности

1.4. Реализация мультиплексоров схемами из функциональных эле-

ментов. Обобщение полученных ранее результатов на некоторый класс квазимультиплексоров

Глава 2. Нижние оценки сложности (глубины) мультиплексорных функций в некоторых классах схем. 54 2.1. Операция стандартной подстановки констант. Нижние оценки

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

2.2. Канонические квазимультиплексорные схемы и формулы, осо-

бенности их структуры

2.3. Нижние оценки сложности реализации квазимультиплексор-

ных функций 7Г-схемами и формулами

2.4. Нижние оценки сложности реализации квазимультиплексор-

ных функций схемами из функциональных элементов

Литература

Введение диссертации (часть автореферата) на тему «О сложности мультиплексорных функций в некоторых классах схем»

Введение.

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

Теория синтеза управляющих систем является одним из основных разделов дискретной математики и математической кибернетики ([14, 24, 45]). Она возникла в 30-40-х годах прошлого века в связи с необходимостью проектирования и логического описания дискретных вычислительных устройств различного типа. К. Шеннон в работах [62, 63] дал строгую математическую постановку задачи синтеза управляющих систем, положив тем самым начало соответствующей теории, исследования в которой ведутся с тех пор непрерывно. В целом, в теории синтеза управляющих систем изучаются модели различных дискретных преобразователей сигналов, их сложность, надёжность и другие характеристики.

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

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

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

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

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

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

предложенных Шенноном ([24, 63]). Эти соображения основаны на том, что число ФАЛ, которые зависят от п БП и имеют сложность не более, чем Ь, не может быть меньше числа попарно не эквивалентных схем от этих БП сложности не больше, чем Ь.

Среди подходов к решению задач массового синтеза стоит выделить широко известный метод Шеннона (см. [24, 63]), который основан на разложении реализуемой ФАЛ по части переменных и получении искомой схемы в виде суперпозиции двух «стандартных» схем. Метод Шеннона позволяет установить порядок функции Шеннона для сложности КС и СФЭ.

Другим известным методом синтеза является метод каскадов, предложенный Г. Н. Поваровым [29]. Как и метод Шеннона, он позволяет установить порядок сложности реализации почти всех ФАЛ в классах КС и СФЭ, хотя является технически более простым и удобным. Кроме того, метод каскадов позволяет получать хорошие схемы для ФАЛ с небольшим числом переменных и целого ряда последовательностей конкретных ФАЛ. Так, для линейной ФАЛ от п (п ^ 2) БП с помощью метода каскадов строится оптимальная контактная схема сложности (4п — 4).

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

В частности, О. Б. Лупанов разработал метод (см. [25, 26] и, например, [24]), который позволил установить асимптотическое поведение функции Шеннона и наличие эффекта Шеннона для сложности СФЭ, КС и целого ряда других классов схем. В основе метода ЛуПанова лежит представление каждой из тех ФАЛ, которые являются результатом разложения исходной ФАЛ по части переменных, в виде дизъюнкции вспомогатель-

ных ФАЛ определённого вида.

В дальнейшем множество указанных вспомогательных ФАЛ было названо С. А. Ложкиным (см. [14]) дизъюнктивно-универсальным множеством (ДУМ) функций. Обобщение ДУМ — так называемые ^-универсальные множества ФАЛ — позволило разработать метод синтеза, с помощью которого для ряда классов оказалось возможным строить такие схемы, сложность которых для почти всех ФАЛ не превосходит асимптотически оптимальных значений на уровне так называемых асимптотических оценок высокой степени точности (см. [16, 17]).

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

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

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

часто используется приём «забивающих» констант, связанный с подстановкой различных констант вместо части входных БП в схему, реализующую данную ФАЛ, и последующим устранением из неё определённого числа элементов.

Так, Б. М. Клосс и В. А. Малышев доказали указанным способом первую нижнюю оценку вида (2п — 0(1)) для сложности ФАЛ из некоторого класса в классе СФЭ над базисом из всех двуместных ФАЛ ([10]). К. Шнорр в работе [59] доказал нижнюю оценку (2п — 3) для сложности такой ФАЛ, из которой при подстановке констант вместо любых двух её переменных можно получить по крайней мере 3 различных ФАЛ, в классе СФЭ над базисом из всех двуместных ФАЛ. В. Поль ([58]) и Л. Стокмай-ер ([61]) получили нижние оценки, асимптотически равные 2, 5п, для некоторых ФАЛ от п БП в классе СФЭ над базисом из всех двуместных ФАЛ, что стало качественным улучшением нижних оценок, асимптотически равных 2гг. Их методы были использованы К. Шнорром ([60]) и Л. Блюм ([47]) для получения нижних оценок, асимптотически равных 3п.

Оценки более высокого порядка позволяет установить, например, метод Б. А. Субботовской ([36]), в котором нижняя оценка сложности исследуемой функции получается на основе сложности некоторых её подфункций. Этот метод заключается в последовательной подстановке констант О и 1 вместо БП исходной ФАЛ до получения ФАЛ, сложность которой легко может быть оценена снизу. Для сложности линейной ФАЛ в классе формул в стандартном базисе = {&, V, -•} с помощью этого метода удаётся получить нижнюю оценку порядка п3/2. В работах [37, 38] метод Субботовской применяется к другим похожим базисам.

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

Так, Андреев предложил пример ФАЛ, построенной с использованием универсальной функции Э. И. Нечипорука (см. [28]), для сложности которой в классе формул в стандартном базисе Eq с помощью указанного метода можно доказать нижнюю оценку, по порядку равную1

5

П 2

(log п)1 log log п

Позже И. Хастад ([54]) для функции Андреева доказал наивысшую известную на данный момент нижнюю оценку сложности в классе формул в стандартном базисе, которая по порядку равна

п3

7 о •

(log n)2 (log log п)

В. М. Храпченко в работе [44] предложил метод получения высоких нижних оценок в классе 7г-схем. Оценки получаются тем выше, чем чаще ФАЛ меняет своё значение при переходе к соседней точке булева куба.

Метод Нечипорука (см. [28]) позволяет получить нижние оценки вида (iogn) для контактных схем и вида для формул в произвольном конечном базисе. Эти оценки являются самыми высокими из известных для этих классов схем. Для класса формул в базисе, состоящем из всех двухместных ФАЛ, нижние оценки вида (nlogn) даёт метод Фишера-Майера-Патерсо-на ([50, 51]). А. А. Разборов в работах [30, 31] привёл метод получения экспоненциальных нижних оценок сложности ФАЛ в классе схем в базисе {&;, V} вида 2n(log2n). Андреев в работе [3] привёл пример последовательности ФАЛ, для которых указанная сложность имеет вид 2п3 °(1) и является максимальной в настоящее время.

Заметим, что некоторые из приведённых выше нижних оценок сложности связаны с реализацией достаточно «искусственных» ФАЛ. Вместе с тем, одним из основных направлений индивидуального синтеза являет-

:Все логарифмы в данной работе берутся по основанию 2.

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

Для сложности целого ряда «естественных» ФАЛ известны точные или близкие к ним оценки сложности. Среди них стоит выделить оценки сложности линейной ФАЛ 1°п порядка п, а £ {0,1}, где 1°п = Х\®.. .®хп®сг. Как в классе СФЭ в стандартном базисе Д) = так и в клас-

се контактных схем сложность линейной ФАЛ 1°п порядка п, п ^ 2, равна (4п — 4) (см. [33]). Метод Храпченко позволяет установить нижнюю оценку сложности линейной ФАЛ порядка п в классе 7г-схем, равную п2 (см. [41]). С. В. Яблонский ([46]) доказал верхнюю оценку указанной сложности, равную |п2 в общем случае, и равную п2, если п = 2к, к = 1,2,.. то есть для указанных п известно точное значение сложности линейной ФАЛ.

В ряде работ рассматривалась ФАЛ зп{хь ..., хп) — монотонная симметрическая ФАЛ с порогом 2, которая равна 1, если число единиц среди значений БП х\,...,хп больше одной, и равна 0 в противном случае. Р. Е. Кричевский в работе [12] доказал, что сложность ФАЛ 5П в классе 7г-схем равна2

[_1о§п\ • 2^ + ([1оётг] - 2)(п - 2^).

Аналогичный результат устанавливается в работе [15] для случая, когда контакты разных БП могут иметь различные веса.

Большая часть работ, относящихся к теории индивидуального синтеза, тесно связана с одним из направлений теории сложности — иссле-

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

дованием сложности реализации ФАЛ и систем ФАЛ, задающих арифметические операции. Н. П. Редькин в работе [32] доказал, что сложность сумматора порядка п, то есть системы ФАЛ, задающей сложение двух п-разрядных двоичных чисел, в классе СФЭ в базисе {&, V, 0, -i} в точности равна (5п — 3). Однако, глубина построенной при этом схемы указанной сложности оказалась равной (2п — 1), что значительно превосходит нижнюю оценку этого параметра, равную [log п]. Известно, что в стандартном базисе Бо существуют СФЭ, реализующие сложение и вычитание двух п-разрядных чисел со сложностью (9п — 5) и (lin — 5) соответственно (см., например, [1]). Храпченко в работе [42] привёл метод построения СФЭ в произвольном базисе, реализующих сумматор порядка п с линейной относительно п сложностью и асимптотически оптимальной глубиной, которая имеет логарифмический порядок роста. Позже в работе [43] он доказал нижнюю оценку глубины реализации сумматора порядка п в стандартном базисе, равную logn + (1 — о(1)) log log log п.

Известным методом умножения двух n-разрядных двоичных чисел является метод Карацубы ([9]), позволяющий реализовать с его помощью СФЭ сложности О (nlog3). Обобщением метода Карацубы является алгоритм Тоома-Кука, предложенный А. Л. Тоомом в [39] и усовершенствованный С. Куком в его кандидатской диссертации [48]. Алгоритм Тоома-Кука позволяет строить СФЭ, реализующую умножение двух n-разрядных чисел со сложностью О (п1+е) для любого наперёд заданного положительного е. Ещё более эффективным методом реализации умножения является метод Шёнхаге-Штрассена, предложенный в 1971 году (см. [64]), который позволяет получать СФЭ для умножения двух n-разрядных чисел сложности О (п log п log log п). Только спустя 35 лет указанная верхняя оценка была улучшена в работе [52] до величины3 О (nlogn 2°(log п)). Однако, послед-

3Через log* п обозначается величина гтп{г ^ 0 : log'-1'' п ^ 1}, где log'0' п — п, а

ние три подхода реально применимы только для очень больших значений параметра п.

Наряду с исследованием сложности «арифметических» систем ФАЛ широко изучалась также сложность реализации «управляющих» ФАЛ и сложность (совместной) реализации систем таких ФАЛ. Доказано, в частности, что сложность реализации так называемого универсального многополюсника порядка п, то есть системы всех ФАЛ от п БП, в классе СФЭ в произвольном базисе с единичными весами элементов равна 22"—п (см. [1]). В работе [63] Шеннон построил универсальный контактный многополюсник с 1 входом и 22" выходами, имеющий сложность асимптотически равную 2 ■ 22" , и только много позднее С. А. Ложкиным и М. А. Кошкиным в работе [23] было доказано, что он является асимптотически оптимальным.

На основе предложенного в работе [23] подхода её авторами был развит достаточно общий метод получения нижних и верхних оценок сложности реализации «больших» систем ФАЛ контактными и обобщёнными контактными схемами, имеющими линейную относительно мощности системы асимптотику роста с коэффициентом большим единицы. С помощью этого метода в [22] была установлена асимптотика для контактной сложности дизъюнктивного дешифратора порядка п от п БП, то есть системы всех элементарных дизъюнкций (ЭД) ранга п, для системы всех ФАЛ от п БП из произвольного ненулевого инвариантного класса, класса самодвойственных ФАЛ и др.

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

к^(г+1)п = гг.

базисе, которая получается с помощью разбиения набора переменных на две части, равна 2п + О (го • 2^) и является асимптотически точной (см., например, [1]).

Сложность контактного дешифратора порядка п, то есть сложность реализации этого дешифратора в классе контактных схем с 1 входом и 2п выходами, асимптотически равна 2п (см. [24]). В работе [13] поведение сложности дешифратора порядка го = 1,2,... в классе контактных схем было установлено с точностью до второго члена разложения, и оказалось равным величине вида

о п / о п \

2п + — ± О

п \rologro)

Неполными дешифраторами порядка го являются системы из т, т < 2П, ЭК ранга го от го БП, реализацию которых в классе КС с 1 входом и т выходами впервые рассмотрел Нечипорук в работе [27]. Он показал, что для величины L(m,ro), которая равна сложности реализации самой сложной из указанных систем ФАЛ в данном классе КС, при Ма ^ го справедливо неравенство

L(m, го) ^ min jm + (М - 1)^, Mm j + (^j (Ма2 + 2n~M<J+1) ,

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

В работе [34] Редькин получил следующую верхнюю оценку введённой величины:

L(m, го) ^ min f 2 Г-1 (2r + т - 2)) ,

re{i,...,n} V г 4 Ч

с помощью которой доказал, что для последовательности чисел тп, го = 1, 2,..., удовлетворяющей условиям

logn fe^o^

log тп го

имеет место асимптотическое равенство:

птг

L{mn, п)

log тп

Так как нижняя оценка в последнем равенстве устанавливается на основе мощностных соображений, то полученный в [34] результат следует, скорее, отнести к теории массового синтеза. Что же касается задачи «индивидуального» синтеза контактных дешифраторов, то в работе [4] доказывается, что сложность реализации произвольной системы из m ЭК ранга п от п БП асимптотически равна т, если т = 2п~°(п\

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

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

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

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

В иностранной литературе (см., например, [65, 66]) мультиплексорная ФАЛ \хп обычно называется storage access function (т. е. «функция доступа к памяти») либо lookup function (т. е. «функция поиска»), что подчёркивает сферу её применений.

Сложность мультиплексорной ФАЛ цп изучалась в ряде работ. В работе [58] устанавливается нижняя оценка сложности реализации стандартного мультиплексора порядка п в классе СФЭ в так называемом унимодальном базисе [/2, состоящем из всех двухместных элементарных конъюнкций и дизъюнкций, равная 2n+1 — 2. В работе [56] приводится реализация стандартного мультиплексора порядка п с помощью СФЭ в этом же базисе со сложностью 2n+1+0 (2f ) и глубиной n+ [logп\ +1. Также известно (см., например, [11]), что сложность реализации ФАЛ /¿n, п = 1,2,..., как формулами, так и СФЭ в стандартном базисе £>о, асимптотически равна 2n+1. В работе [35] получена нижняя оценка вида

2n+1 + Cl(n)-2?-0(2?) (1)

и верхняя оценка вида

2n+1-fc2(n)-2?+0(2*), (2)

для сложности реализации мультиплексора fin в классе СФЭ над базисом Д), где ci(n) = С2(п) = 2, если п чётно, и ci(n) = 0,32, 02(11) = если п нечётно.

Что касается глубины мультиплексорной ФАЛ дп, то в работе [65] была доказана её верхняя оценка (п + 3) в базисе U2 при п = 1, 2,.... В

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

В работе [16] также было доказано, что глубина ФАЛ как в классе СФЭ, так и в классе формул в базисе U2 не превосходит величины (n + З) и что она не превосходит (п+4) в стандартном базисе Указанные верхние оценки были получены при этом с помощью явного построения формул, реализующих мультиплексорные ФАЛ.

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

Таким образом, из приведённых выше оценок сложности дешифраторов в различных классах схем могут быть получены некоторые оценки сложности соответствующих мультиплексорных ФАЛ. В частности, из [4] следует, что контактная сложность указанного выше стандартного квазимультиплексора порядка п и ранга г асимптотически не превосходит 2г при г — 2п~°(п\ Заметим, что построенные при этом КС являются 7г-схемами, и

поэтому такие же асимптотические верхние оценки будут справедливы для сложности реализации данного мультиплексора в классах формул и СФЭ в базисе £/2, а также в классе СФЭ в базисе Бо, причём с учётом нижних оценок [58] все эти оценки являются асимптотически точными.

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

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

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

в классе 7г-схем и в классе формул в унимодальном базисе, оценки вида

в классе формул в стандартном базисе, если — = о(г), и оценки вида

ФАЛ.

(4)

в классе СФЭ в обоих указанных базисах. Заметим, что оценки (3)-(5) тем выше, чем больше ранг квазимультиплексорной ФАЛ.

В работе предложены новые методы синтеза схем для мультиплек-сорных ФАЛ и получения верхних оценок их сложности, основанные на известных методах Ложкина ([16, 17]) построения специальных разбиений булева куба и моделирования ФАЛ переменными или их отрицаниями на компонентах построенных разбиений. При этом использовались как разбиения булева куба на так называемые т-регулярные компоненты, так и его разбиение на единичные сферы. Каждая компонента таких разбиений, в свою очередь, делилась на достаточно «простые» по сложности характеристических ФАЛ подкомпоненты, допускающие «простое» моделирование соответствующих квазимультиплексорных ФАЛ. При построении оптимальных по глубине формул, реализующих мультиплексорные ФАЛ, использовался также специальный приём, согласно которому часть построенных компонент отбрасывается, а затем группируется вместе так, чтобы итоговая формула получилась оптимальной по глубине. Все схемы и формулы из доказательств верхних оценок могут быть построены явным образом.

С помощью описанных выше методов и приёмов для ФАЛ а также некоторых квазимультиплексорных ФАЛ были получены новые более точные верхние оценки сложности их реализации во всех рассматриваемых классах схем. В ряде случаев при ть = 1, 2,... и г = г(п) полученные верхние оценки с точностью до слагаемого вида о совпали с нижними оценками (3) для соответствующих классов схем. По аналогии с [17] в этих случаях можно говорить об установлении значений исследуемой сложности на уровне асимптотических оценок высокой степени точности (АОВСТ).

Так, для сложности стандартной мультиплексорной ФАЛ порядка п

в классе 7г-схем были получены АОВСТ вида

\ 2п \nlogn) )

Такие же АОВСТ справедливы для сложности реализации ФАЛ /¿п в классе формул над базисом U2 и в классе формул в стандартном базисе для функционала сложности, который учитывает только функциональные элементы (ФЭ) «&» и «V». Кроме того, аналогичные оценки справедливы для некоторых квазимультиплексорных ФАЛ.

Список литературы диссертационного исследования кандидат наук Власов, Никита Вадимович, 2013 год

Литература

[1] Алексеев В. В., Ложкин С. А. Элементы теории графов, схем и автоматов. — М.: Издательский отдел ф-та ВМиК МГУ, 2000. — 58 с.

[2] Андреев А. Е. Об одном методе получения более чем квадратичных эффективных нижних оценок сложности 7г-схем // Вестник Московского университета. Сер. 1, Математика, Механика. — 1987. — №1. — С. 70-73.

[3] Андреев А. Е. Об одном методе получения эффективных нижних оценок монотонной сложности // Алгебра и логика. — 1987. — №1. — С. 3-26.

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

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

[6] Власов Н. В. О сложности мультиплексорной функции в классе формул // Вестник Нижегородского государственного университета им. Н. И. Лобачевского. - 2012. - №5. - С. 38-41.

[7] Власов Н. В. О сложности мультиплексорной функции в классе формул // Проблемы теоретической кибернетики. Материалы XVI Меж-

дународной конференции (Нижний Новгород, 20-25 июня 2011 г.). — 2011. - С. 96-97.

[8] Дискретная математика и математические вопросы кибернетики. Том 1. / Ю. Л. Васильев, Ф. Я. Ветухновский и др.; под ред. С. В. Яблонского и О. Б. Лупанова. — М.: Наука, 1974. — 311 с.

[9] Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР. - 1962. - Т. 145, №2. - С. 293294.

[10] Клосс Б. М., Малышев В. А. Оценки сложности некоторых классов функций // Вестник Московского университета. Сер. 1, Математика, Механика. - 1965. - №4. - С. 44-51.

[11] Коровин В. В. О сложности реализации универсальной функции схемами из функциональных элементов // Дискретная математика. — 1995. Т. 7, вып. 2. - С. 95-102.

[12] Кричевский Р. Е. Минимальная схема из замыкающих контактов для одной булевой функции от п аргументов // Дисретный анализ. — 1965. Вып. 5. - С. 89-52.

[13] Липатова А. Е. Об одном покрытии множества двоичных наборов и реализации конъюнкций контактными схемами // Математические вопросы кибернетики. — 1989. — Вып. 2. — С. 161-173.

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

[15] Ложкин С. А. О минимальных 7Г-схемах для монотонных симметрических функций с порогом 2 // Дискретная математика. — 2005. — Т. 17, вып. 4. - С. 108-110.

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

[17] Ложкин С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов // Математические вопросы кибернетики. - 1996. - Вып. 6. - С. 189-214.

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

[19] Ложкин С. А., Власов Н. В. О глубине мультиплексорной функции // Материалы IX Международного семинара «Дискретная математика и её приложения» (Москва, МГУ, 18-23 июня 2007 г.). — 2007. — С. 102105.

[20] Ложкин С. А., Власов Н. В. О сложности мультиплексорной функции в классе 7г-схем // Проблемы теоретической кибернетики. Тезисы докладов XV международной конференции (Казань, 2-7 июня 2008 г.). — 2008. - С. 76.

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

[22] Ложкин С. А, Кошкин М. А. О сложности реализации некоторых систем функций алгебры логики контактными и обобщёнными контактными схемами // Математические вопросы кибернетики. — 1991. — Вып. 3. - С. 257-285.

[23] Ложкин С. А, Кошкин М. А. О сложности реализации некоторых систем функций алгебры логики контактными многополюсниками // Доклады Академии Наук СССР. - 1988. - Т. 298, №4. - С. 807-811.

[24] Лупанов О. Б. Асимптотические оценки сложности управляющих систем. - М.: Изд-во МГУ, 1984. - 137 с.

[25] Лупанов О. Б. О синтезе КС // Доклады Академии Наук СССР. — 1958. - Т. 119, т. - С. 23-26.

[26] Лупанов О. Б. Об одном методе синтеза схем // Известия вузов, Радиофизика. - 1958. - Т. 1, т. - С. 120-140.

[27] Нечипорук Э. И. О топологических принципах самокорректирования // Проблемы кибернетики. — 1969. — Вып. 21. — С. 5-102.

[28] Нечипорук Э. И. Об одной булевской функции // Доклады Академии Наук СССР. - 1966. - Т. 169, №4. - С. 765-766.

[29] Поваров Г. Н. Математическая теория синтеза контактных (1 ,к)~ полюсников // Доклады Академии Наук СССР. — 1955. — Т. 100, №5. - С. 909-912.

[30] Разборов А. А. Нижние оценки монотонной сложности логического перманента // Математические заметки. — 1985. — Т. 37, №6. — С. 887900.

[31] Разборов А. А. Нижние оценки монотонной сложности некоторых булевых функций // Доклады Академии Наук СССР. — 1985. — Т. 281, №4. - С. 798-801.

[32] Редькин Н. П. О минимальной реализации двоичного сумматора // Проблемы кибернетики. — 1981. — Вып. 38. — С. 181-216.

[33] Редькин Н. П. Доказательство минимальности некоторых схем из функциональных элементов // Проблемы кибернетики. — 1970. — Вып. 23. - С. 83-102.

[34] Редькин Н. П. О реализации систем конъюнкций контактными схемами // Проблемы кибернетики. — 1975. — Вып. 30. — С. 263-276.

[35] Румянцев П. В. О сложности реализации мультиплексорной функции схемами из функциональных элементов // Проблемы теоретической кибернетики. Тезисы докладов XIV международной конференции (Пенза, 23-28 мая 2005 г.). - 2005. - С. 133.

[36] Субботовская Б. А. О реализации линейных функций формулами в базисе V, // Доклады Академии Наук СССР. — 1961. — Т. 136, №3. - С. 553-555.

[37] Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами // Доклады Академии Наук СССР. — 1963. - Т. 149, Ш. - С. 784-787.

[38] Субботовская Б. А., Мучник Б. А. Оценка сложности реализации линейной функции формулами в некоторых базисах // Кибернетика. — 1970. - №4. - С. 29-38.

[39] Тоом А. Л. О сложности схемы из функциональных элементов, реализующей умножение целых чисел // Доклады Академии Наук СССР. — 1963. - Т. 150, №3. - С. 496-498.

[40] Храпченко В. М. Нижние оценки сложности схем из функциональных элементов (обзор) // Кибернетический сборник. Новая серия. — 1984. - Вып. 21. - С. 3-54.

[41] Храпченко В. М. О сложности реализации линейной функции в классе схем // Математические заметки. — 1971. — Т. 9, №1. — С. 35-40.

[42] Храпченко В. М. Об асимптотической оценке времени сложения параллельного сумматора // Проблемы кибернетики. — 1967. — Вып. 19. - С. 107-122.

[43] Храпченко В. М. Об одной из возможностей уточнения оценок для задержки параллельного сумматора // Дискретный анализ и исследование операций. Сер. 1. - 2007. - Т. 14, №1. — С. 87-93.

[44] Храпченко В. М. Об одном методе получения нижних оценок сложности 7г-схем // Математические заметки. — 1971. — Т. 10, №1. — С. 83-92.

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

[46] Яблонский С. В. Реализация линейной функции в классе 7г-схем // Доклады Академии Наук СССР. - 1954. - Т. 94, №5. - С. 805-806.

[47] Blum L. A Boolean function requiring 3n network size. Theoretical Computer Science, 1984, v. 28, pp. 337-345.

[48] Cook S. A.. On the minimum computation time of functions. Ph.D. thesis, Harvard University Department of Mathematics, Cambridge, MA. 1966.

[49] Feller W. An introduction to probability theory and its application. New York, Wiley, 1950, 704 pp.

[50] Fischer M., Meyer A., Paterson M. Lower bounds on the size of Boolean formulas, preliminary report. Proc. 7th Annual ACM Symposium on Theory of Computing. Albuquerque, 1975, pp. 37-44.

[51] Fischer M., Meyer A., Paterson M. Q(nlogn) lower bounds on length of Boolean formulas. SIAM J. Comput, 1962. 11(3). P. 416-427.

[52] Fürer M. Faster integer multiplication. STOC 2007 Proceedings, 2007, pp. 57-66.

[53] Hamming R. W. Coding and information theory, 2nd edn. New York: Prentice-Hall, Englewood Cliffs, 1986, 272 pp.

[54] Hästad J. The Shrinkage Exponent is 2. SIAM Journal on Computing, 1998, v. 27, pp. 48-64.

[55] Karchmer M., Wigderson A. Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 1990, v. 3, pp. 255-265.

[56] Klein P., Paterson M. S. Asymptotically optimal circuit for a storage access function. IEEE Trans, on Computers, IEEE Computer Society, 1980, v. 29, N-8, pp. 737-738.

[57] Lamagna E. A., Savage J. E. On the logical complexity of symmetric switching functions in monotone and complete bases. Tech. rep. Rhode Island: Brown University, 1973.

[58] Paul W. J. A 2, 5n lower bound on the combinational complexity of Boolean functions. SIAM, Philadelphia: SIAM Journal on Computing, 1977, v. 6, pp. 427-443.

[59] Schnorr C. Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen. Computing 13, 1973, pp. 155-171.

[60] Schnorr C. A 3n-lower bound on the network complexity of Boolean functions. Theoretical Computer Science 10, 1980, pp. 83-92.

- [61] Stockmeyer L. On the combinational complexity of certain symmetric Boolean functions. Mathematical Systems Theory, 1970, v. 10, pp. 323336.

[62] Shannon C. E. A symbolic analysis of relay and switching circuits. Trans. AIEE, 1938, v. 57, pp. 713-723.

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

[64] Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen. Computing, 1971, v. 7, pp. 281-292.

[65] 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.

[66] Wegener I. The complexity of Boolean functions. Teubner, Stuttgart: John Wiley k Sons Ltd, and B. G, 1987, 458 pp.

(J