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

• Данилов Борис Радиславович
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Данилов Борис Радиславович

Введение

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

Основные определения

Формулировка полученных результатов

Глава 1. Построение формул максимального ранга при ограниченной

глубине. Нижние оценки функций Шеннона для глубины и задержки

1.1 Простейшие асимптотические оценки ранговой функции базиса

1.2 Шаблоны подключений и их связь с ранговой функцией

1.3 Ранговая функция однородного шаблона подключений

1.4 Ранговая функция в базисах специального вида

1.5 Нижние мощно стные оценки функций Шеннона

Глава 2. Синтез схем для различных ФАЛ. Поведение функций Шеннона

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

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

2.2 Мультиплексорные ФАЛ и их обобщённое разложение

2.3 Реализация мультиплексорных ФАЛ

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

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

Заключение

Литература

Введение

Введение диссертации (часть автореферата) на тему «Асимптотически наилучшие оценки для некоторых функционалов глубины и задержки схем из функциональных элементов»

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

В диссертации изучается одна из задач синтеза дискретных управляющих систем. Проблема синтеза в общем виде состоит в построении для заданной дискретной функции её структурной реализации в заданном классе управляющих систем. Если дискретная функция может быть реализована в указанном классе, то обычно она может быть реализована в нём различными способами. В связи с этим возникает возможность выбора более предпочтительной реализации. Для того, чтобы оценить степень предпочтительности одной реализации относительно другой, вводят индекс «простоты», характеризующий «сложность» управляющих систем рассматриваемого класса. При этом под «сложностью» самой дискретной функции понимают «сложность» наиболее простой её реализации. Если класс дискретных функций достаточно велик, то задача синтеза наилучших по тому или иному критерию «сложности» управляющих систем для произвольных дискретных функций из этого класса имеет очень большую трудоёмкость, связанную с принципиальной невозможностью устранения перебора почти всех управляющих систем, реализующих данную функцию, — к такому выводу одним из первых пришёл С. В. Яблонский в своей работе [1], где он рассмотрел данную задачу в рамках реализации булевых функций в классе контактных схем. С тех пор эта точка зрения получила косвенные подтверждения своей справедливости и стала общепринятой.

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

Альтернатива заключается в том, чтобы значительно ослабить требования на степень оптимальности конструируемых управляющих систем. В этом ослабленном виде задача массового синтеза приобретает следующий вид: для произвольной функции из данного достаточно обширного класса дискретных функций построить такую её реализацию в заданном классе управляющих систем, чтобы значение индекса «простоты» построенной управляющей системы намного не превосходило значения индекса «простоты» самой «сложной» дискретной функции рассматриваемого класса. В такой постановке задача синтеза была впервые рассмотрена К. Э. Шенноном, который получил её первое решение [2,3]. Функцию натурального1 аргумента п, равную наибольшему значению «сложности» среди всех дискретных функций данного класса, зависящих от заданного количества п переменных, называют функцией Шеннона для рассматриваемого параметра «сложности».

При этом задача синтеза естественным образом распадается на две в определённой степени самостоятельные подзадачи: 1) задачу построения достаточно «простой» управляющей системы для произвольной дискретной функции; 2) задачу нахождения нижней оценки функции Шеннона, доказывающей оптимальность управляющей системы, построенной на первом этапе. Для решения второго вопроса обычно пользуются мощностными соображениями, в то время как первый из них решается построением конкретного алгоритма. Алгоритмы решения указанной задачи синтеза сравнивают по степени близости «сложности», получаемых с их помощью управляющих систем в худшем случае, к значению функции Шеннона. Так, метод, предложенный Шенноном [3] для синтеза булевых функций в некоторых моделях управляющих систем для интегральных и логических схем, позволил получать схемы, не превосходящие по так называемой структурной «сложности» значения функции Шеннона больше, чем в конечное число раз. Решения двух указанных выше задач устанавливают соответственно верхнюю и нижнюю асимптотические оценки функции Шеннона, при этом более точные алгоритмы синтеза позволяют получать более точные асимптотические оценки этой величины. Другими словами, можно говорить о том, что Шенноном установлен порядок роста функции Шеннона для структурной «сложности» булевых функций при их реализации в некоторых классах схем.

Позднее О. Б. Лупанов предложил [4-7] более точный метод синтеза, позволивший установить асимптотику роста функции Шеннона для этого и некоторых

1Для исключения возможной неоднозначности следует отметить, что число ноль не включается во множество натуральных чисел.

других параметров «сложности» булевых функций в целом ряде классов управляющих систем (контактные схемы, п-схемы, схемы из функциональных элементов, формулы). Работы Лупанова позволили установить в этих классах управляющих систем так называемый эффект Шеннона, гипотеза о котором была высказана [3] Шенноном в 1949 году: почти все функции от п аргументов имеют почти одинаковую «сложность», асимптотически равную «сложности» самой «сложной» функции от п аргументов. В некоторых случаях, например, для дизъюнктивных нормальных форм, имеет место ослабленный эффект Шеннона, когда почти все функции от п аргументов имеют почти одинаковую «сложность», однако, меньшую, чем «сложность» самой «сложной» функции [8-10].

Основным предметом нашего рассмотрения являются дискретные функции из класса Р2(п) — класса функций алгебры логики (ФАЛ), принимающих значения из множества {0,1} и зависящих от заданных п булевых переменных х\,..., хп, а также их представление в классе схем из функциональных элементов (СФЭ) над конечным полным базисом р. Класс СФЭ [4], известных также под названием комбинационных схем [11], представляет собой достаточно точную модель электронных логических схем без обратной связи, одним из основных параметров которых является скорость срабатывания, определяемая, в частности, временем «прохождения» сигналов, подаваемых на входы схемы, к её выходам. Эта характеристика быстродействия схем в общем случае представляет собой довольно сложный параметр, зависящий от целого ряда свойств составляющих схему элементов, способа их соединения, значений сигналов, подаваемых на входы схемы, и последовательности, в которой подаются эти значения, первоначального состояния схемы и других факторов. Поэтому в рамках математической постановки задачи для класса СФЭ возможны различные варианты формализации как процесса распространения сигналов в схеме, так и понятия её быстродействия, которые приводит нас к различным критериям временной «сложности». Среди иных рассматриваемых характеристик «сложности» СФЭ отметим структурную «сложность», понимаемую, например, в смысле количества элементов в схеме и традиционно называемую просто сложностью, а также «сложность» энергопотребления или мощность, определяемую как наибольшее число элементов, находящихся в единичном состоянии, которое образуется при подаче всевозможных комбинаций сигналов на входы схемы.

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

рые называют цепями), соединяющих входы схемы с её выходами (такие цепи традиционно называют главными). Функция Шеннона др(п) для такой классической глубины произвольной ФАЛ из Р2(п) при её реализации в базисе Р для базисов определённого вида была подробно исследована рядом авторов [12-16]. Из тривиальных соображений для дизъюнктивных и конъюнктивных нормальных форм вытекает следующая верхняя оценка этой функции в так называемом стандартном базисе Р0 = {&, V, —}: &р0(п) ^ п + log2 п. В работах [12-14] сначала было показано, что глубина п + 1 является достаточной для реализации любой ФАЛ из Р2(п) в базисе из двухвходовых элементов, реализующих все ФАЛ двух переменных. Затем в работе С. Б. Гашкова [15] с использованием техники [17] были получены асимптотические оценки для &р0 (п) вида2:

п - ^ ^ п - о(1) ^ &Ро (п) ^ п - ^ log2 п + 2 + о(1),

которые были улучшены в работе С. А. Ложкина [16] и распространены им на некоторые другие базисы, состоящие из двухвходовых элементов. Из работы [16], в частности, следует, что величина (п) в точности равна3 | п — п ± о(1)].

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

2На протяжении работы мы пользуемся рядом обозначений из математического анализа, так запись д(п) = o(f(п)) (д(п) = (п))) означает, что для любого е > 0 найдётся такое число п0 > 0, что 0 ^ д(п) ^ еf (п) (соответственно 0 ^ еf (п) ^ д(п)) при всех п ^ п0. Тем самым, во-первых, предполагается неотрицательность функций д, f при всех достаточно больших п, и, во-вторых, рассматривается их поведение на бесконечности. Мы также неформально употребляем асимптотические соотношения внутри формул, например, Н(п) < ¿(п) + о(1) надо понимать так, что найдётся функция д(п) = о(1), для которой Н(п) < ¿(п) + д(п). Аналогичным образом понимаются и другие подобные соотношения.

3Запись вида Н(п) = ¿(п) ± о(д(п)) означает, что |Л,(п) — ¿(п)| = о(д(п)).

может быть построена правильная схема её реализующая, то есть имеется в виду «полнота во втором смысле» в терминологии В. Б. Кудрявцева [19]. Асимптотика функции Шеннона Дрин.(п) для задержки синхронных СФЭ при их реализации в произвольном полном базисе р равна трп, где константа тр определяется исключительно свойствами базиса р. Оказалось, что в зависимости от соизмеримости задержек элементов базиса упомянутый выше эффект Шеннона, вообще говоря, может не иметь места для задержки синхронных СФЭ. Это связано с тем, что в любом полном базисе задержка «почти половины» ФАЛ из Р2(п) асимптотически совпадает с трп, тогда как асимптотика задержки другой «почти половины» ФАЛ равна Тфп и определяется другой зависящей от базиса р и не превосходящей тр константой тр'.

В дальнейшем исследование модели синхронной задержки СФЭ, в которой дополнительно допускается нулевая величина задержки элементов базиса, продолжил Ложкин в работе [20]. Оказалось, что тип асимптотического поведения функции Шеннона Др^п) для задержки синхронных СФЭ в этом случае определяется множеством тех элементов базиса, которые имеют нулевую задержку, и может принимать три различные формы: 1) асимптотически линейную трп; 2) асимптотически логарифмическую о^ п; 3) асимптотически постоянную, когда Др^п) при п ^ п'р становится равна константе С^, названной им критической задержкой базиса р . Аналогично [18] в каждом из этих случаев задержка «почти половины» ФАЛ из Р2(п) асимптотически совпадает с функцией Шеннона, тогда как задержка другой «почти половины» ФАЛ асимптотически равна тр'п, а^ п и С^ при п ^ прр. При этом константы т^, тр, а^, а^ в [18,21] находятся по базису р достаточно просто, а для констант Ср, Ср, п^, п^ установлен только факт их существования.

В работе Ложкина [21] была предложена упрощённая модель задержки, в которой не требуется правильности рассматриваемых СФЭ и где задержка (обобщённая структурная глубина) схемы определяется «комбинаторным» образом как наибольшая из задержек её главных цепей. Для указанной модели из результатов [18, 21] вытекает, что для любого полного (в обычном смысле) базиса р функция Шеннона Др (п) для задержки (обобщённой структурной глубины) ФАЛ из Р2(п) аналогично [20] асимптотически равна либо тр п, либо ар п, либо Ср (при п ^ пр), где константы тр, ар, Ср, пр зависят от базиса р и, в том случае когда он полон «во втором смысле», совпадают с константами тр, а^, Ср, пр соответственно. При этом имеет место эффект Шеннона и аналогично [18,20]

константы тр, ар вычисляются по базису р достаточно просто. Более сложному способу определения констант Ср, пр по характеристикам элементов базиса посвящена работа [21]. К этим результатам близко примыкают работы, в которых исследуется глубина ФАЛ в бесконечных базисах произвольного вида [22-24] и глубина функций алгебры к-значной логики в различных базисах [25-27].

В работе [28] на основе методов [18] и специальной техники, применённой её автором в связи с синтезом контактных схем [29], доказывается верхняя асимптотическая оценка функции Др(п), позволяющая для этой величины установить более точное асимптотическое поведение вида4 тр(п — п)±0(1) (см. также [30]).

Такого рода асимптотические оценки функции Шеннона для глубины и задержки, устанавливающие её поведение с точностью до слагаемого 0(1), стали называться асимптотическими оценками высокой степени точности.

Результаты В.М. Храпченко [31-33] выявляют интересную особенность скорости срабатывания вычислительных устройств: в некоторых случаях возможно значительное расхождение интуитивного понятия быстродействия с понятием структурной глубины и рассмотренными до сих пор вариантами обобщения последней. Так, для СФЭ был предложен [31] вариант модели распространения сигнала по схеме, и на его основе сформулировано понятие скорости срабатывания схемы, также названное задержкой. Это новое понятие задержки, в отличие от рассмотренной выше задержки в смысле обобщения структурной глубины, учитывает не только структурные, но и логические особенности функционирования схемы, а именно: при определении задержки фактически выводится из рассмотрения глубина цепей, не влияющих на результат работы схемы, за счёт чего задержка некоторых схем становится существенно меньше их глубины. Примечательно, что указанное различие оказывается справедливо для некоторых неизбыточных по количеству элементов схем: построен [33] пример бесконечной последовательности ФАЛ / неограниченно растущей глубины, такой что задержка Т(Е&) любой минимальной (по количеству элементов) для / схемы в стандартном базисе р0 с единичной глубиной базисных элементов не превосходит log2 ) + 14; кроме того в работе [32] установлено, что задержка Т(2) любой минимальной схемы 2 в базисе р0 не меньше £(£). Тем не менее, различия между глубиной и за-

4Запись д(п) = 0(/(п)) (д(п) = П(/(п))) означает, что найдётся такая константа с > 0 и такое число п0 > 0, что 0 ^ д(п) ^ с/(п) (соответственно 0 ^ с/ (п) ^ д(п)) для всех п ^ п0. Функции /, д по-прежнему предполагаются неотрицательными для достаточно больших п. Запись вида

Л-(п) = ¿(п) ± 0(д(п)) означает, что |Л,(п) — ¿(п)| = 0(д(п)).

держкой исчезают [31] при оптимизации схем непосредственно по глубине (или задержке): для любой ФАЛ f её минимальная задержка Тр(/) и глубина ) в произвольном полном конечном базисе Р достигаются на одной и той же схеме. Учитывая обсуждаемые результаты, следует признать за термином задержка это новое понятие задержки в смысле Храпченко, как более подходящее, оставляя за предыдущим его значением термин обобщённой глубины.

Обнаруженное разграничение понятия задержки и глубины позволяет для некоторых содержательных примеров функций [31,34] ослаблять ограничения на параметр быстродействия искомых схем, накладывая их на задержку вместо глубины, что делает возможным построение схем более оптимальных по количеству элементов. В этой связи! мы подходим близко к соотношениям между временными и структурными характеристиками управляющих систем. Для задачи синтеза ФАЛ формулами над конечным полным базисом Р Храпченко в 1967 году установил [35] для некоторых констант к и г соотношение 5р(/) ^ к £р(/) + г между классической глубиной 5р(/) и сложностью £р(/) (в смысле количества операций) произвольной ФАЛ f. Поскольку аналогичная нижняя оценка для 5р(/) (с другими константами) получается тривиально, то этим было установлено наилучшее по порядку соотношение5 &р(/) = £р(/)). В связи с этим результатом воз-

ник вопрос об уточнении константы к для конкретных базисов.

Рассматривая формулы над базисом Р0, для которого нижняя тривиальная оценка этой константы имеет вид к ^ 1, П. М. Спира [36] независимо от Храпченко установил это соотношение с константой к < 3,42, за ним Р. П. Брент с соавторами [37] —с константой к < 2,47, после чего оценка константы последовательно улучшалась6 рядом авторов [38-40], и в 1978 году Храпченко установил [41] оценку к ^ 1,73. Аналогичная задача для неполного арифметического базиса {0, &} привела к оценкам 1,16 ^ к ^ 2,09, нижняя из которых получена в [42], верхняя —в [43]. В работе [44] рассматривается пример базиса, в котором константа к оценивается точнее 1 ^ к ^ 1,45. Во всех этих случаях верхняя оценка глубины устанавливается путём выполнения некоторого преобразования, которое любую формулу сложности I переводит в эквивалентную ей формулу (над тем же базисом) глубины не более к log2 I + г. Сложность формулы при этом может

5Запись д(п) = 0(f (п)) означает, что одновременно д(п) = O(f (п)) и д(п) = Q(f (п)). Когда это не приводит к неоднозначности, мы опускаем основание логарифмов в асимптотических соотношениях.

6Результаты [37, 38] справедливы не только для булевых формул, но и для формул над коммутативным кольцом с единицей.

возрастать. В работах [45,46] рассматриваются приёмы уменьшения сложности получаемых формул за счёт незначительного увеличения их глубины.

Эти результаты, однако, не переносятся на схемы из функциональных элементов: для глубины 5p0 (f) и сложности £p0 (f) реализации ФАЛ f в классе СФЭ над стандартным базисом p0 при несложно доказываемой нижней оценке 5p0 (f) = ft (log £p0 (f)) до сих пор известна лишь верхняя асимптотическая оценка вида 5p0(f) = O(£p0(f)/log£p0(f)), впервые доказанная М.С.Патерсоном и Л. Г. Валиантом в [47] и позже установленная П. Даймондом и М. Томпа в [48] с использованием другого метода.

Схемы и формулы, на которых достигаются значения рассмотренных функционалов «сложности», вообще говоря, различны. Для задачи массового синтеза была обнаружена [18] возможность построения для любой ФАЛ из P2(n) такой реализующей её СФЭ в произвольном полном конечном базисе P, сложность и глубина которой асимптотически не превосходят значений соответствующих функций Шеннона, а с использованием методов [18,28,30] аналогичные результаты могут быть получены и для формул. Кроме того, в стандартном базисе p0 возможна [49] одновременная оптимизация параметров сложности и глубины формул на уровне асимптотических оценок высокой степени точности: для любой ФАЛ f из P2(n) существует реализующая её формула F над p0, для которой одновременно выполняются неравенства

£(F) ^ (2n/log2n) • (1 + O(1/logn)), 5(F) ^ n - log2log2n + O(1).

Коснёмся вкратце индивидуальной постановки задачи синтеза в связи с одним классом ФАЛ, играющим важную роль при разработке универсальных методов синтеза, — классом так называемых мультиплексорных ФАЛ, наиболее распространённым вариантом которого является класс стандартных мультиплексорных ФАЛ дп порядка n. Функция дп, также иногда называемая в иностранной литературе [50,51] функцией доступа к памяти (storage access function) или функцией поиска (lookup function), имеет n «адресных», 2n «информационных» переменных и совпадает с той своей информационной переменной, номер которой в двоичной системе счисления задаётся набором значений её адресных переменных. Для произвольного полного базиса P из работы [18], где ФАЛ дп возникает в качестве одной из основных частей разложения произвольной ФАЛ, следует асимптотическая оценка обобщённой глубины Dp(jin) в классе произвольных СФЭ без

нулевых глубин функциональных элементов вида Tpn ± O(log n). В работе [52] установлена асимптотическая оценка высокой степени точности для указанной величины Dp(^n), которая имеет вид Tpn + O(1). Для стандартного базиса p0 в работе [49] установлено, что классическая (структурная) глубина £p0 (дп) не превосходит величины n + 4, когда все элементы базиса имеют единичную глубину, и не превосходит n + 3, когда элемент отрицания имеет нулевую глубину, а элементы конъюнкции и дизъюнкции —единичную. Затем в работе [53] было найдено точное значение структурной глубины мультиплексорной ФАЛ в стандартном базисе с нулевой глубиной отрицания для почти всех значений n, которое оказалось равным n + 2 при n ^ 20 и 3 ^ n ^ 5; в работе также показано, что эта величина находится в пределах между n + 2 и n + 3, когда 5 < n < 20. Из результатов [53] также вытекают аналогичные соотношения для базиса, состоящего из всех элементарных конъюнкций и элементарных дизъюнкций от двух переменных.

В диссертации в рамках задачи синтеза СФЭ для ФАЛ из P2(n) в произвольном полном базисе P предложено [54,55] несколько дальнейших возможных вариантов обобщения глубины СФЭ в смысле работы [28], для которых получены оценки соответствующей функции Шеннона Dp (n) на уровне асимптотики, а при некоторых ограничениях — и на уровне асимптотических оценок высокой степени точности.

Предложен [56] вариант модели задержки СФЭ в смысле работы Храп-ченко [31], который основан на анализе «функционирования» цепей схемы на различных наборах значений её входных переменных и учитывает возможную зависимость задержки функционального элемента по выбранному входу от значений на других его входах. Для данной модели задержки сохраняются те же самые расхождения между задержкой и глубиной, которые были выявлены в работах [31-33]. В рамках указанной модели для соответствующей функции Шеннона Tp(n) получена асимптотическая оценка вида Tpn ± O(log n).

Во всех предложенных моделях [54-56] имеет место эффект Шеннона и возможна одновременная оптимизация схем из различных классов по обобщённой глубине (задержке) и сложности на уровне асимптотически наилучших оценок, что продемонстрировано [57] на примере формул. В некоторых рассматриваемых моделях получены [54-56] асимптотические оценки для задержки Tp(^n) и обобщённой глубины Dp(^n) мультиплексорной ФАЛ вида Tpn±O(logn) и Tpn±O(1) соответственно.

Основные определения

Напомним, что основным предметом исследования в данной работе являются СФЭ над конечным полным базисом Р, состоящим из функциональных элементов различных типов Е1,... , При этом элемент7 типа Е{, 1 ^ г ^ Ь, имеет к^ к ^ 1, входов и реализует ФАЛ ^ (х\,... ), которая в случае к ^ 2 существенным образом зависит8 от всех своих булевых переменных, определённых на множестве В = {0,1}. Понятие СФЭ фактически совпадает с понятием схемы вычисления, которую обычно определяют как последовательность равенств:

у1 Х1 , ... , Уп ХП1 Уп+1 = ^ (и1,1 ,...,П1М1), (1)

Уп+8 = (Щ,Ъ . . . ^^ ),

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

Если исходить из того, что в схеме вычисления все операции , 1 ^ ] ^ в, выполняются функциональными элементами, то мы приходим к схеме из функциональных элементов, состоящей из п входов, которым сопоставлены соответственно переменные9 х1,..., хп, и в функциональных элементов, причём ] -й по счёту функ-

7Иногда для краткости мы опускаем слово «функциональный» в словосочетании «функциональный элемент», а вместо словосочетания «схема из функциональных элементов» и его сокращения СФЭ используем в качестве синонима слово «схема».

8По поводу существенных и фиктивных переменных, а также равенства ФАЛ см. [58, с. 11-12]. Функцию алгебры логики, которая существенно зависит от всех своих переменных, называют существенной.

9Подчеркнём, что переменные х\,... ,хп различны, то есть различным входам СФЭ сопоставлены различные переменные.

циональный элемент имеет к^. перенумерованных входов и один выход, которому сопоставлена переменная yn+j и на котором реализуется ФАЛ ^ (и^д,..., ), а соединения осуществляются так, как это диктуется равенствами (1). В схеме из функциональных элементов ещё указывают её выходы, которыми могут быть выходы элементов или входы схемы. Выходы схемы имеют кратность, выражающуюся натуральным числом, и получают пометки выходными переменными г1,..., гто, отличными от всех входных и внутренних переменных. Каждый выход получает ровно столько пометок, какова его кратность. Суммарная кратность всех выходов равна т, а все выходные пометки в схеме различны. Считается, что СФЭ реализует упорядоченный (в соответствии с упорядочением выходных переменных) набор из т ФАЛ, каждая из которых задаётся либо формулой-развёрткой внутренней переменной, сопоставленной соответствующему выходу, либо входной переменной, если выход является входом схемы. Такой набор из т функций называется (п, т)-функцией или вектор-функцией. В случае т =1 вектор-функция является ФАЛ в обычном смысле. Схемы называют эквивалентными, если они реализуют равные вектор-функции.

Список литературы диссертационного исследования кандидат наук Данилов Борис Радиславович, 2016 год

Литература

1. Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики. — Вып. 2. — М: Физматгиз, 1959.— С. 75-121.

2. Shannon C. E. A symbolic analysis of relay and switching circuits // Trans. Amer. Inst. Electrical Engineers. — Vol. 57. — 1938. — P. 713-723. (Русский перевод: Шеннон К. Символический анализ релейных и переключательных схем // Работы по теории информации и кибернетике. — М: ИЛ, 1963. — С. 9-45.)

3. Shannon C.E. The synthesis of two-terminal switching circuits // Bell System Technical Journal.—Vol. 28, No. 1. — 1949.— P. 59-98. (Русский перевод: Шеннон К. Синтез двухполюсных переключательных схем // Работы по теории информации и кибернетике. — М: ИЛ, 1963. — С. 59-105.)

4. Лупанов О. Б. Об одном методе синтеза схем // Известия высших учебных заведений. Радиофизика. — № 1. — 1958. — С. 120-140.

5. Лупанов О. Б. О синтезе контактных схем // Доклады Академии наук СССР. — Т. 119, №1. —1958. —С. 23-26.

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

7. Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. — Вып. 10. — М: Физматгиз, 1963. — С. 63-97.

8. Глаголев В. В. Некоторые оценки дизъюнкитвных нормальных форм функций алгебры логики // Проблемы кибернетики. — Вып. 19. — М: Наука, 1967. — С. 75-94.

9. Макаров С. В. Верхняя оценка средней длины дизъюнктивной нормальной формы // Дискретный анализ (сб. трудов ИМ СО АН СССР).— Вып. 14.— М: Наука, 1964. — С. 78-80.

10. Нигматуллин Р. Г. Вариационный принцип в алгебре логики // Дискретный анализ (сб. трудов ИМ СО АН СССР). — Вып. 10. — М: Наука, 1967. — С. 69-89.

11. MullerD.E. Complexity in electronic switching circuits // IRE, Trans. Electron. Comput.—Vol.5, No. 1. —1956. —P. 15-19.

12. Mc Coll W.F., Paterson M. S. The depth of all Boolean functions // SIAM Journ. on Computing. — 1977. — Vol. 6, No. 2. — P. 373-380.

13. Preparata F. P., Muller D.E. On the delay required to realize Boolean functions // IEEE Trans. Computers. — 1971. — Vol. C-20, No. 1. — P. 459-461.

14. SpiraP.M. On the time necessary to compute switching functions // IEEE Trans. Computers. — 1971. — Vol. C-20, No. 1. — P. 104-105.

15. ГашковС.Б. О глубине булевых функций // Проблемы кибернетики.— Вып.34.—М: Наука, 1978. — С.265-268.

16. Ложкин С. А. О глубине функций алгебры логики в некоторых базисах // Ann. Univ. Sci. Budapest. Sec. Comput. — 1983. — Vol. IV. — С. 113-125.

17. Лупанов О.Б. О сложности универсальной параллельно-последовательной сети глубины 3 // Труды математического института АН СССР.—№133.— М: Наука, 1973. —С. 127-131.

18. Лупанов О. Б. О схемах функциональных элементов с задержками // Проблемы кибернетики. — Вып. 23 — М: Наука, 1970. — С. 43-82.

19. Кудрявцев В. Б. Теорема полноты для одного класса автоматов без обратных связей // Проблемы кибернетики. — Вып. 8. — М: Физматгиз, 1962. — С. 91-115.

20. Ложкин С. А. Асимптотическое поведение функции Шеннона для задержек схем из функциональных элементов // Математические заметки. — 1976. — Т. 19, №6. —С. 939-951.

21. Ложкин С. А. О критической задержке схем из функциональных элементов с задержками // Проблемы кибернетики. — 1980. — № 37. — С. 43-82.

22. Касим-Заде О. М. О глубине булевых функций при реализации схемами над произвольным базисом // Вестник Московского университета. Серия 1. Математика. Механика. — 2007. — № 1. — С. 18-21. (Английский перевод: Kasim-Zade O. M. The depth of boolean functions realized by circuits over an arbitrary basis // Moscow University Mathematics Bulletin. — 2007. — Vol. 62, No. 1. — P. 1821.)

23. Касим-Заде О.М. О глубине булевых функций над произвольным бесконечным базисом // Дискретный анализ и исследование операций. Серия 1. — 2007. — Т. 14, № 1. — С. 45-69. (Английский перевод: Kasim-Zade O. M. Depth of boolean functions over an arbitrary infinite basis // Journal of Applied and Industrial Mathematics.—2008. —Vol.2, No.2. —P. 196-210.)

24. Касим-Заде О. М. О глубине булевых функций при реализации схемами над произвольным бесконечным базисом // Вестник Московского университета. Серия 1. Математика и механика. —2012. — № 6. — С. 55-57. (Английский перевод: Kasim-Zade O. M. Depth of boolean functions realized by circuits over an arbitrary infinite basis // Moscow University Mathematics Bulletin.—2013. — Vol.68, No. 1. —P. 69-70.)

25. КочергинА.В. О глубине функций k-значной логики в бесконечных базисах // Вестник Московского университета. Серия 1. Математика и механика. — 2011. —№1. —С. 22-26.

26. Кочергин А. В. О глубине функций k-значной логики в конечных базисах // Вестник Московского университета. Серия 1. Математика и механика. — 2013.—№1. —С. 56-59.

27. Кочергин А. В. О глубине функций многозначной логики при реализации схемами над произвольным бесконечным базисом // Матераилы IX молодежной научной школы по дискретной математике и ее приложениям (Москва, 16-21 сентября 2013 г.). — М: Изд-во ИПМ РАН, 2013. — С. 61-65.

28. Ложкин С. А. О глубине функций алгебры логики в произвольном полном базисе // Вестник Московского университета. Серия 1. Математика. Механика. — 1996. —№2. —С. 80-82.

29. Ложкин С. А. О синтезе ориентарованных контактных схем // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика.— 1995. —№2. —С. 36-42.

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

31. Храпченко В. М. Различие и сходство между задержкой и глубиной // Проблемы кибернетики. — 1979. — № 35. — С. 141-148.

32. Храпченко В. М. Новые соотношения между глубиной и задержкой // Дискретная математика. — 1995. — Т. 7, № 4. — С. 77-85.

33. Храпченко В. М. Принципиальное расхождение между глубиной и задержкой // Дискретная математика. — 2008. — Т. 20, № 3. — С. 51-72.

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

35. Яблонский С. В., Козырев В. П. Математические вопросы кибернетики. — «Информационные материалы» Научного совета по комплексной проблеме «Кибернетика» АН СССР. — М, 1968. — Вып. 19а. — С. 3-15.

36. SpiraP.M. On time-hardware complexity tradeoffs for boolean functions // Proceedings of 4th Hawaii Symposium on System Sciences — North Hollywood: Western Periodicals, 1971. — P. 525-527.

37. Brent R. P., KuckD.J., Maruyama K. The parallel evaluation of arithmetic expressions without divisions // IEEE Trans. Computers. — 1973.—Vol. C-22. — P. 532-534.

38. Preparata F. P., Muller D. E. The time required to evaluate division-free arithmetic expressions // Inf. Proc. Lett. — 1975.—Vol. 3, No. 5. — P. 144-146.

39. Barak A., Shamir E. On the parallel evaluation of boolean expressions // SIAM J. Computers. — 1976.—Vol. 5, No. 4. — P. 678-681.

40. Preparata F. P., Muller D. E. Efficient parallel evaluation of boolean expressions // IEEE Trans. Computers. — 1976. — Vol. C-25, No. 5. — P. 548-549.

41. Храпченко В.М. О соотношении между сложностью и глубиной формул // Методы дискретного анализа в синтезе управляющих систем. — Новосибирск: Инт математики СО АН СССР, 1978. — Вып. 32. — С. 76-94.

42. Shamir E., Snir M. On the depth complexity of formulas // Math. Syst. Theory.— 1980. — Vol. 13, No. 4. — P. 301-322.

43. Muller D. E., Preparata F. P. Restructuring of arithmetic expressions for parallel evaluation // J. ACM. — 1979.—Vol. 23, No. 3.— P. 534-543. (Русский перевод: Кибернетический сборник, новая серия. — 1979. — Вып. 16. — С. 5-22.)

44. Храпченко В. М. О соотношении между сложностью и глубиной формул в базисе, содержащем медиану // Методы дискретного анализа в изучении булевых функций и графов.— Новосибирск: Ин-т математики СО АН СССР, 1981.— Вып. 37. — С. 77-84.

45. Bshouty N.H., Cleve R., Eberly W. Size-depth tradeoffs for algebraic formulas // SIAM J. Comput. — 1991. — Vol. 24, No. 4. — P. 682-705.

46. Bonet M. L., Buss S. R. Size-depth tradeoffs for Boolean formulae // Inf. Proc. Lett. — 1994.—Vol.48.—P. 151-155.

47. Paterson M. S., Valiant L. G. Circuit size is nonlinear in depth // Theor. Comput. Sci. — 1976. — Vol. 2, No. 3. — P. 397-400.

48. Dymond P., Tompa M. Speedups of deterministic machines by synchronous parallel machines // J. Comput. Syst. Sci. — 1985. — Vol. 30, No. 2. — P. 149-161.

49. Ложкин С. А. О синтезе формул, сложность и глубина которых не превосходят асимптотически наилучших оценок высокой степени точности // Вестник Московского университета. Серия 1. Математика. Механика. — 2007. — № 3 — С. 19-25. (Английский перевод: Lozhkin S. A. Synthesis of formulas whose depth and complexity do not exceed asymptotically the best estimates of high accuracy // Moscow Univ. Math. Bull. — 2007. — Vol. 62, No. 3. — P. 101-107.)

50. Tardos G., Zwick U. The communication complexity of the universal relation // Proceedings of the 12th Annual IEEE Conference on Computational Complexity (CCC). — 1997. — P. 247-259.

51. Wegener I. The complexity of Boolean functions // Teubner, Stuttgart: John Wiley & Sons Ltd, and B. G. — 1987. —458 P.

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

53. Ложкин С. А., Власов Н. В. О глубине мультиплексорной функции в классе схем из функциональных элементов // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2011. — №2. — С. 40-46. (Английский перевод: Lozhkin S. A., Vlasov N. V. On the depth of the storage access function // Moscow University Computational Mathematics and Cybernetics. — 2011. — Vol. 35, No. 2. — P. 97-104.)

54. Lozhkin S. A., Danilov B. R. Delay in networks of functional elements in a model with an arbitrary distribution of basis element input delays // Computational Mathematics and Modeling. — 2012. — Vol. 23, No. 4. — P. 487-506. (Перевод с русского: Ложкин С. А., Данилов Б. Р. О задержке схем из функциональных элементов в модели с произвольным распределением задержек элементов базиса по входам // Прикладная математика и информатика. № 39. — М: МАКС Пресс, 2011. —С. 107-129.)

55. Данилов Б. Р. О поведении функции Шеннона для задержки схем в модели, где задержка соединений определяется типами соединяемых элементов // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2014. — Т. 3, № 31. — С. 78-100.

56. Ложкин С. А., Данилов Б. Р. О задержке схем из функциональных элементов в модели с произвольным распределением задержек элементов базиса по входам и входным наборам // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2013. — №4. — С. 25-33. (Английский перевод: Lozhkin S. A., Danilov B. R. Network delay in a model with inputs of functional elements // Moscow University Computational Mathematics and Cybernetics. — 2013.— Vol.37, No.4. —P. 180-188.)

57. Данилов Б. Р. Об одновременной оптимизации формул по сложности и задержке на наборах в модели с задержками соединений между элементами //

Известия высших учебных заведений. Поволжский регион. Физико-математические науки. -2015. - Т. 4, № 36. - С. 58-77.

58. Яблонский С. В. Введение в дискретную математику: Учеб. пособие для вузов / Под ред. В. А. Садовничего. — 4-е изд., стер. — М: Высш. шк., 2003. — 384 С.

59. Ложкин С. А. Основы кибернетики. — М: Издательский отдел Факультета ВМиК МГУ им. М. В. Ломоносова, 2004. — 256 С.

60. Захарова Е. Ю., Яблонский С. В. Некоторые свойства невырожденных суперпозиций в Pk // Математические заметки. — 1972. — Т. 12, № 1. — С. 3-12.

61. Гохберг И. Ц., Фельдман И. А. Уравнения в свертках и проекционные методы их решения / М: Наука, 1971. — 352 С.

62. Гантмахер Ф. Р. Теория матриц / М: ФИЗМАТЛИТ, 2010. — 560 С.

63. Ланкастер П. Теория матриц / М: Наука, 1978. —280 С.

64. Ложкин С. А., Данилов Б. Р. Поведение функции Шеннона для задержки в одной модели схем из функциональных элементов // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.). — Нижний Новгород: Изд-во Нижегородского гос. ун-та, 2011. —С. 277-280.

65. Ложкин С. А., Данилов Б. Р. Поведение функции Шеннона для глубины в модели схем допускающей различие задержек функциональных элементов по входам // Материалы VIII молодежной научной школы по дискретной математике и ее приложениям (Москва, 24-29 октября 2011 г.). —Т. 1. — М: Изд-во ИПМ РАН, 2011. —С. 51-54.

66. Островский А. М. Решение уравнений и систем уравнений / М: Изд-во Иностранной литературы, 1963. —220 С.

67. Шилов Г. Е. Математический анализ (функции нескольких вещественных переменных). Части 1-2 / М: Наука, 1972. —624 С.

68. Vere-Jones D. Ergodic properties of non-negative matrices —I / Pacific J. Math.— 1967. —Vol. 22. —P. 361-386.

69. Гаврилов Г.П., Сапоженко А. А. Задачи и упражнения по дискретной математике: Учеб. пособие / Под ред. Е. Ю. Ходан. — 3-е изд., перераб. — М: ФИЗМАТ-ЛИТ, 2005.—416С.