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

• Коноводов, Владимир Александрович
• кандидат наук
• 2015

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

Содержание

Введение

1 Синтез формул с ограниченной глубиной альтернирования и схем

из функциональных элементов ограниченной ширины

1.1 Формулы с ограниченной глубиной альтернирования

1.1.1 Вспомогательные определения и утверждения

1.1.2 Верхняя оценка функции Шеннона

1.1.3 Нижняя мощностная оценка функции Шеннона

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

1.3 Схемы с ограниченной памятью

2 Синтез формул в базисах с прямыми и итеративными переменными

2.1 Некоторые особенности задачи и порядок функции Шеннона

2.2 Сложность формул в базисах, итеративное замыкание которых содержит все монотонные функции

2.3 Асимптотические оценки высокой степени точности для некоторых базисов

Заключение

Литература

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

Введение

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

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

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

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

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

Первый результат о поведении функции Шеннона для сложности схем в конечных полных базисах был получен Мюллером в [5] с использованием метода Шеннона [6]. Было показано, что порядок роста указанной функции при стремлении натурального аргумента п к бесконечности равен 2п/п.

Затем О. Б. Лупановым [41] был предложен оптимальный метод синтеза схем в произвольных полных конечных базисах. Им же был получен первый результат об асимптотическом поведении функции Шеннона для сложности формул в таких базисах. А именно, была установлена асимптотика функции Шеннона вида

Г)П

Р ■ —,

п

для сложности схем из функциональных элементов, и асимптотика для случая булевых формул [42] вида1

2п

Р- i-,

iOg 71

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

В дальнейшем в работах С. А. Ложкина [31] уточнялись оценки остаточного члена асимптотического разложения для некоторых функций Шеннона и устанавливались асимптотические оценки высокой степени точности, в которых указывалась асимптотика второго члена этого разложения. Такие оценки были получены для сложности некоторых основных классов схем.

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

'Здесь и далее все логарифмы двоичные

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

О. Б. Лупановым одним из первых были исследованы некоторые классы схем из функциональных элементов с ограничениями.

В работе [43] была получена асимптотика функции Шеннона, связанной со сложностью схем, в которых выход любого элемента может быть подсоединен не более чем к заданному числу входов других элементов. Число присоединенных к элементу входов других элементов схемы называется ветвлением выхода. Ограничение этой величины означает ограничение на число использований функций на выходах функциональных элементов схемы как промежуточного результата вычислений. В указанной работе схемы с ограничением на ветвление выходов элементов назывались формулами с частичной памятью. Они занимают промежуточное положение между схемами с произвольным ветвлением и формулами, являющимися схемами без ветвлений. В этой работе было показано, что при допущении ветвлений хотя бы у одного базисного элемента функция Шеннона сложности соответствующих схем имеет такой же порядок роста, как и для схем без ограничений, однако, асимптотика может быть значительно выше.

В работе [44] рассматривались формулы ограниченной глубины в стандартном базисе {V, ->}. Глубина формулы в этой работе определялась индуктивно. Формулы глубины 0 составляли символы переменных и их отрицаний, а формулы глубины 1, делились на два типа по внешней операции. Формулы глубины 1) с внешней дизъюнкцией представляли собой дизъюнкцию формул глубины (I с внешней конъюнкцией. Формулы глубины (с1 + 1) с внешней конъюнкцией определялись двойственным образом. Установлено, что функция Шеннона для сложности формул, имеющих глубину не большую, чем и реализующих функции от п переменных, при всех в, ^ 3 асимптотически ведет себя как 2п/\о^п. При этом для с1 = 2 сложность самой трудной функции в этом классе составляет 3 ■ п ■ 2п~2 — 1.

Аналогичный результат для СФЭ был получен в работе [45].

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

В настоящей работе глубина формулы в смысле [44] называется глубиной альтернирования данной формулы. Следует отметить, что в работе [32] величина (с1 — 1) называлась альтернированием формулы.

Другой тип ограничения, связанный с числом регистров, т. е. ячеек памяти, необходимых для осуществляемых схемой вычислений, был рассмотрен в работах Н. А. Карповой [13, 14]. В [14] изучались схемы с 1 регистром — линейные суперпозиции, и возможность реализации ими булевых функций. Было показано существование функции от трех переменных, которая не может быть представлена линейной суперпозицией в базисе из всех двухместных функций. При переходе к схемам с двумя регистрами такой эффект не имеет места. В [13] получено, что функция Шеннона для класса схем с t регистрами в базисе из всех

р-местных функций при фиксированных I ^ 3 и р ^ 2 асимптотически ведет себя как

2п

(р — 1) \ogri'

В работах Н. А. Карповой схемы с £ регистрами назывались схемами толщины I.

Задача синтеза управляющих систем с ограничениями активно изучалась и в классе контактных схем. В этой модели реализация булевых функций осуществляется в терминах проводимости контактов, которой управляют внешние булевы переменные. Сложностью таких схем называется число контактов в них. Шенноном [6] был установлен порядок роста соответствующей функции Шеннона, а О. Б. Лупанов в [47] разработал асимптотически оптимальный метод синтеза контактных схем и показал, что функция Шеннона для их сложности асимптотически ведёт себя как 2п/п.

Одной из первых моделей контактных схем с ограничениями была модель, в которой степени вершин схемы ограничены некоторой константой. Такие схемы рассматривались в работе А. Д. Коршунова [23], где был описан асимптотически оптимальный метод их синтеза. В работе X. А. Мадатяна [48] получены асимптотические оценки сложности реализации булевых функций с помощью контатных схем ограниченной ширины.

А. Е. Шиганов [55,56] рассматривал контактные' схемы и итеративные контактные схемы с различными типами ограничений на смежные контакты. В работе [56] были разработаны методы синтеза ориентированных контактных схем с ограничением на полустепени исхода вершин, и установлена асимптотика первого остаточного члена асимптотического разложения функции Шеннона, зависящая от параметров ограничений.

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

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

9 п

3 п

для сложности таких программ получил О. М. Касим-Заде в [15]. В [25] показано, что программы, состоящие только из вычислительных команд, эквивалентны классу схем из функциональных элементов, поэтому для соответствующей функции Шеннона справедлива асимптотика 271/п. В [25] также указано, что бинарные программы, где все ячейки памяти в вычислительных командах, в которые происходит запись результата вычисления, различны, эквивалентны одному из специальных видов контактных схем, и установлена асимптотика 2п~1/п функции Шеннона для такого класса программ. Класс бинарных программ, состоящих только из переадресующих команд, был впервые предложен Ли в [4]. Такие программы также называются BDD (Binary Decision Diagrams), и имеют огромное значение в прикладных задачах. Подходы к созданию алгоритмов для синтеза и верификации схем, основанных на представлении булевых функций специальными упорядоченными BDD, были исследованы в работе Брайанта [1]. Наряду с обычными BDD рассматриваются также различные их модификации, имеющие приложения в теории квантовых вычислений. В работе Ф. М. Аблае-ва [7] рассматривались синтаксические квантовые ветвящиеся программы, вычисляющие булевы функции с большой надежностью.

Асимптотику 211 ¡п функции Шеннона для сложности двоичных решающих диаграмм установил В. А. Кузьмин в [25]. Такие программы представимы в виде контактных схем из ориентированных контактов без циклов с одним истоком, являющимся входом схемы, и двумя стоками, являющимися её выходами. При этом выходы помечены символами 0 и 1, а из каждой невыходной вершины ис-

ходит ровно два контакта, один из которых помечен символом переменной, а другой — символом её отрицания. Для некоторых классов ЕШБ С. А. Ложкиным [35] и А. Е. Шигановым [57,58] были получены асимптотические оценки высокой степени точности для соответствующих функций Шеннона.

Ещё одно обобщение бинарных программ было введено С. В. Грибком в работе [11]. Вычисляющая программа представлялась в виде набора подпрограмм, каждой из которых соответствовало отдельное множество ячеек памяти, и была введена команда вызова подпрограммы. Исследована задача синтеза для таких классов программ со специальными весовыми характеристиками и получены асимптотические оценки для соответствующих функций Шеннона. Кроме того, для некоторых классов были установлены оценки высокой степени точности, в которых асимптотика второго члена разложения зависела от весовых характеристик — параметров ограничений.

Отметим следующую связь между вычислительными программами и схемами с регистрами. Если под шириной вычисляющей программы понимать минимальное число ячеек памяти, необходимых для хранения её внутренних переменных, то вычисляющие программы ширины £ представляют собой схемы с £ регистрами, определенные в указанных выше работах Н. А. Карповой.

Другим направлением задачи синтеза является исследование реализации булевых функций в схемах с ограничениями на типы соединяемых элементов и номера присоединяемых входов. При этом предполагается, что базисные элементы имеют входы двух видов — прямые и итеративные. Прямые входы могут являться только входами схемы, а на итеративные входы должны подаваться выходы других элементов. Возможность итеративных входов являться входами схемы может оговариваться отдельно. Впервые задача синтеза в такой модели была предложена и рассмотрена С. А. Ложкиным в работах [37,38]. В [37] был установлен критерий полноты относительно всех функций прямых переменных

при наличии в базисе элементов, реализующих функции-константы, и описаны некоторые особенности решетки вложения замкнутых классов функций с прямыми и итеративными переменными. В [38] было исследовано поведение функции Шеннона на уровне асимптотических оценок высокой степени точности для класса всех схем из функциональных элементов над произвольным полным базисом с прямыми и итеративными переменными и некоторых его подклассов. Эта функция имеет «стандартный» порядок роста 271 /п. В [38] указано также, что функция Шеннона для формул в таких базисах имеет порядок роста не более, чем 2", и не менее, чем 2п/\о%п.

К этому направлению задачи синтеза относится также задача реализации функций алгебры логики а-формулами, которые определяются индуктивно следующим образом. Пусть X — некоторое множество переменных. Если <р — а-формула или символ переменной из множества X, а / — функция из некоторого множества А, то выражение вида /(<р, ..., Х{н), где х^,..., Х{3 Е X, является а-формулой над множеством функций А. Нетрудно видеть, что су-формулы над множеством А можно рассматривать как формулы в базисе А', состоящем из констант и функций множества А, в каждой из которых первая переменная является итеративной. Формулы такого вида были введены в работе М. М. Глу-хова [10] и рассматривались над множествами функций /с-значных логик, к ^ 2. В [10] было показано существование при к ^ 7 конечных а-полных систем, т. е. таких систем, что любую функцию /с-значной логики можно реализовать а-формулой над этой системой. А. Л. Чернышевым в работе [54] был доказан критерий а-полноты функций многозначной логики и показано отсутствие конечных а-полных систем в случае булевых функций. Оценки функции Шеннона для глубины а-формул были получены в работах Д. В. Трущина [50,51].

Модель схем из функциональных элементов в базисах с прямыми и итеративными переменными обладает рядом сходств с другими моделями, использу-

ющими память. Так, в случае базиса, в котором каждый элемент имеет не более одного итеративного входа, соответствующие схемы представимы как схемы с одним регистром памяти. Другой базис, приводящий к связи с моделью вычисляющих программ, — базис, состоящий из функции /¿1 = х\у\ V Х\у2, в которой переменные у\ и у2 итеративные, а х\ — прямая. Класс схем в этом базисе, в которых итеративные входы функции ц\ могут быть константными, изоморфно соответствует классу бинарных адресующих программ.

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

В ряде работ задача синтеза управляющих систем решалась для специальных классов функций, в частности для функций, связанных с языками. В [39] оценки высокой степени точности установлены для сложности реализации функций из таких классов схемами из функциональных элементов с ограниченной глубиной ветвления и ориентированными контактными схемами, в [17] — для сложности реализации таких функций в специальном классе схем из функционально-проводящих элементов.

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

Пусть X = {.Т1,..., хп,...} — счетный алфавит булевых переменных, каждая из которых может принимать значения из множества В = {0,1}. Пусть, далее, В11, п = 1,2,..., — единичный п-мерный куб, то есть множество всех упоря-

доченных наборов длины п из элементов В; а р2(п) - множество всех функций / = /0е ь • • •; хп) '■ Вп —> В. Элементы т-й декартовой степени множества Р2{п), т.е. множества (Р2{п))т = Р2т(п)> будем, как обычно, считать системами функций и записывать их в виде вектора (/1,...,/7Н), где 6 А^) при любом г, г е [1, т].

Будем рассматривать схемы из функциональных элементов (в дальнейшем будем называть их просто схемы) и формулы в различных полных базисах, состоящих из функциональных элементов (далее — элементов). Базис Б0, состоящий из элементов &;, V и -1 веса 1, которые реализуют функции алгебры логики Х\-Х2- Х\\/Х2 и х\ соответственно, будем называть стандартным. Под формулами будем понимать те одновыходные схемы, в которых выход любого элемента либо поступает на вход ровно одного (другого) элемента, либо является выходом схемы. Полнота базиса означает возможность реализации всех функций алгебры логики схемами в этом базисе. Каждый элемент базиса если не оговорено иное, имеет вес р(£) = 1.

Под сложностью £(£) схемы Е понимается, как обычно, сумма весов её элементов. При этом, если веса всех элементов равны 1, то сложность схемы совпадает с числом элементов в ней, и для указанной величины будет использоваться обозначение £(£), а для соответствующей функции Шеннона — обозначение Ь(п). В случае существования элементов неединичного веса функция Шеннона будет обозначена как С{п).

Рангом формулы Т будем называть число переменных, встречающихся в её записи, т. е. число листьев в соответствующем ей дереве.

Определим понятие глубины альтернирования схемы в стандартном базисе Б0. Формулу С, которая состоит из г, г ^ 1, элементов

, и в которой

выход элемента г = 1,..., г — 1, является входом элемента будем на-

зывать нетривиальной цепью, а число г - её длиной или глубиной. Если при этом

последовательность ..., где (р(г\ tp^ € Бо, - тип базисного элемента г — 1,..., г, имеет вид (ри ..., tpi, ip2, -. -, <^2, • • •, фа, • • •, W гДе <Pj <Pj+i при всех j, j = 1,..., a — 1, а число с равно 1 в случае = и равно 0 в остальных случаях, то разность (а — с) будем называть глубиной альтернирования указанной цепи С. Формулу, которая состоит из единственной вершины, являющейся как её входом, так и её выходом, будем считать тривиальной цепью, а глубину и глубину альтернирования такой цепи положим равными 0.

Для схемы Е её глубина D(E) (глубина альтернирования -4(E)) определяется как максимальная глубина (соответственно глубина альтернирования) цепей, являющихся подсхемами Е.

Таким образом, схема Е имеет глубину альтернирования а в том и только том случае, когда максимальное число изменений типов элементов в последовательностях, которые являются цепями схемы Е и не содержат отрицаний, присоединённых к её входам, равно (а — 1). Так, любая элементарная конъюнкция или дизъюнкция переменных и их отрицаний имеет глубину альтернирования 1, а любая отличная от них дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ) имеют глубину альтернирования 2.

Для любого а, а ^ 2, определим сложность L^a\f) функции / как минимальную из сложностей тех реализующих её формул, глубина альтернирования которых не больше, чем а. Введем далее функцию Шеннона L^a\n) как максимальную из сложностей где максимум берется по всем функциям / от булевых переменных хп.

При любом a, a ^ 3, из результатов О. Б. Лупанова [44] следуют оценки2

logn ^ (logn)) ^ ^ (n) \ (п) ^ iogn logn ) '

2Для числовых функций (]{п) и h(n) натурального аргумента п запись h(n) = 0(g(ii)) означает, как обычно, что отношение \h(n)/д(п)\ ограничено сверху. Эта запись равносильна загшеп д{п) = Г2(/г(п)). Запись h(n) = Q(g(n)) означает, что h(n) = 0(д(п)) и д(п) = 0(/г(п)).

которые устанавливают поведение функции Шеннона L^a\n) с относительной погрешностью вида О —) . Положим log^ х = log.. .loga:, если указан-

а раз

ный повторный логарифм определен и неотрицателен, и log^ х = 0 в остальных случаях. При этом будем считать, что X = 1 при любом X.

В настоящей работе при а ^ 3 указанные выше оценки величины

уточняются и устанавливается её поведение с относительной погрешностью ви-

Теорема 1 ( [26]). Для любого натурального числа а, а ^ 3, при растущем значении натурального аргумента п, п ^ 2, выполняется соотношение

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

В работе [2] введено понятие грамматики с конечным числом состояний. Модифицируем это понятие следующим образом. Пусть грамматика Г задается множеством внутренних состояний ..., 5р и множеством грамматических правил. Каждое грамматическое правило определяется упорядоченной парой (<т, /с), с7 Е {0,1}, 1 ^ к ^ р. Если такое правило (ст, к) сопоставляется состоянию 5г-, 1 ^ г < р, то это означает, что, когда грамматика находится в состоянии может быть произведен символ сг, причем грамматика переходит в состояние Б/;. Выделим в Г два произвольных (возможно, совпадающих) состояния 5г и 1 ^ ЬЗ ^ Р- Грамматика Г, отправляясь от состояния ¿>г-, пробегает в соответствии с грамматическими правилами последовательность состояний ¿>г1..... где 1 < ¿1,..., ц ^ р, ч = г, ц — 3-, и переходит в состояние Sj, при этом она производит слово, состоящее из цепочки символов в том порядке, в котором они выбирались при последовательных переходах. Пусть Т^ — множество

таких слов. Языком грамматики Г без выделенного начального состояния будем называть язык

Тг= U % 1

Пусть Tr(s), s ^ 1. — множество слов языка Тг, длина которых равна s. Тогда, как следует из работы [2], мощность 7r(s) либо ограничена, либо с ростом s растет линейно, либо экспоненциально. В последнем случае существует такая константа сгр G (0,1], что при s —У оо справедливо [17] соотношение

|Tr(s)| = 2ars+0(1). (1)

Величину <тг будем называть мощностной константой грамматики Г.

Пусть Qr{ri)— класс булевых функций от n, п ^ 1, переменных, множество столбцов значений которых совпадает с Тр(2п). Положим

Qy = U Qr(n).

71^1

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

LT(n) = max

feQr(n)

Теорема 2 ( [27]). Пусть Г — грамматика с конечным числом состояний, для которой мощность множества Tr(s) растет экспоненциально с ростом s, а ay . o~r G (0,1],—её мощностная константа. Тогда при растущем значении натурального аргумента п, п ^ 2, справедливо соотношение

2п Л loglogn±0(l)'\

Lr(n) = <7г • ;- 1 +-;- •

iogn \ logn /

Эта теорема устанавливает поведение функции Шеннона Ь^{п) с относительной погрешностью О 5 и? тем самым, приведённая в ней оценка является оценкой высокой степени точности.

В качестве примера рассмотрим грамматику Го с двумя состояниями и ¿2; в которой состоянию приписаны правила (0,1), (1,2), а состоянию — правило (0,1). Схематично она изображена на рис. 1.

Рисунок 1: Грамматика Г0.

Этой грамматике соответствует класс Qr0 всех булевых функций, столбцы значений которых не содержат двух подряд идущих единиц. По индукции легко доказать, что |Тг0(п)| = Fn+2 для всех n, п = 1,2,..., где Fn-n-ое число Фибоначчи. Так как (см., например, [9])

, 1 + л/5

то для данной грамматики мощностная константа сгГо — log—--, поэто-

¿л

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

2п ( log log n ± 0(1)\

Lr0(n) = (log(l + V5) - l) ■ — 1 +

log те \ logn J

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

Будем говорить, что схема S является схемой с t регистрами, если все её функциональные элементы занумерованы числами 1, 2,..., L, где L = L{Е), и каждому из них приписан регистр из множества R — {7*1,..., г^} так, что для произвольного элемента £ схемы Е выполняются условия:

1. номер £ больше номера любого элемента, выход которого подается на один из его входов;

2. если на вход элемента £ с номером ^ Е [2, Ь], подается выход элемента £' с номером г, г Е [1,3 — 1], и приписанным ему регистром г, г Е Я, то другим элементам с номерами из интервала (г, регистр г не приписан.

Кроме того, будем считать, что значения входных переменных схемы записаны в отдельных входных регистрах гХ1,.. . , гХп, не лежащих во множестве И. При этом предполагается, что функциональный элемент с номером = 1,. .., Ь, указанной схемы «срабатывает» в момент времени 7, выбирая значение каждого своего входа либо из регистра, приписанного выходу соответствующего элемента Е, либо из некоторого входного регистра, и занося вычисленное значение своей базисной функции в приписанный ему регистр.

Входные регистры, таким образом, не используются схемой в процессе описанного вычисления для записи результатов. Регистры из множества Я, наоборот, служат ячейками памяти для вычисления, производимого схемой. Формальное определение вычисления дано в работе [13].

Для схемы Е с £, £ Е {1, 2,...}. регистрами число £ будем называть её шириной. Для произвольной функции алгебры логики / и для любого ¿, Ь Е {1,2,...}, определим сложность функции / как минимальную из сложностей тех

реализующих её схем в базисе Б, ширина которых не превосходит причем в случае стандартного базиса {&, V, -1} индекс Бо будем опускать.

Пусть — функция Шеннона для класса схем в базисе Б, ширина ко-

торых не превосходит 1 Как следует из работы [13], при любом натуральном I ^ 3, функция асимптотически равна сб^т^, где Сб — константа, зави-

сящая от базиса. В частности, в случае стандартного базиса- L^(n) ~ для t ^ 3.

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

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

Литература

1. Bryant R. Е. Graph-based algorithms for Boolean function manipulation // IEEE Trans. Comput. - 1986. - Vol. 35, no. 8. - P. 677-691.

2. Chomsky N., Miller G. A. Finite state languages // Information and Control — 1958. - Vol. 1. - P. 91-112.

3. Cooper J. N., Ellis R. В., Kahng A. B. Asymmetric binary covering codes // Journal of Combinatorial Theory, Series A. — 2002. — Vol. 100, no. 2. — P. 232249.

4. Lee C. Y. Representation of switching circuits by binary-decision programs //Bell Labs Technical Journal. - 1959. - Vol. 38, no. 4. - P. 958-999.

5. Muller D. E. Complexity in electronic switching circuits //Electronic Computers, IRE Transactions on - 1956. - Vol. 5, no. 1. - P. 15-19.

6. Shannon C.E. The synthesis of two-terminal switching circuits //Bell System Technical Journal. - 1949. - Vol. 28, no. 1. - P. 59-98.

7. Аблаев Ф. M. К вопросу о сложности классического моделирования квантовых ветвящихся программ // Учёные записки Казанского государственного университета. Серия Физико-математические науки. — 2009. — Т. 151, № 2. - С. 7-15.

8. Алексеев В. Б., Ложкин С. А. Элементы теории графов, схем и автоматов. — М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М. В. Ломоносова, 2000. — 58 с.

9. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по курсу дискретной математики. - М.: ФИЗМАТЛИТ, 2005. - 416 с.

10. Глухов М. М. Об cv-замкнутых классах и а-полных системах функций к-значной логики // Дискретная математика. — 1989. — Т. 1, вып. 1. — С. 16-21.

11. Грибок С. В. Оценка высокой степени точности для сложности обобщенных бинарных программ // Проблемы теоретической кибернетики. Материалы XIII международной конференции (Казань, 27-31 мая 2002 г.), Часть I. — М.: Изд-во центра прикладных исследований при мех.-мат. ф-те МГУ, 2002. - С. 47.

12. Гринчук М. И. О монотонной сложности пороговых функций // Дискретный анализ. - Вып. 52. - Новосибирск: ИМ СО АН СССР, 1992. - С. 41-48.

13. Карпова H.A. О вычислениях с ограниченной памятью // Математические вопросы кибернетики. — Вып. 2. — М.: Наука, 1989. — С. 131-144.

14. Карпова H.A. О сложности представлений функций алгебры логики линейными суперпозициями // Дискретный анализ. — Вып. 43. — Новосибирск: ИМ СО АН СССР, 1986. - С. 40^16.

15. Касим-Заде О. М. О сложности реализации функций в одном классе алгоритмов// Материалы IX межгосударственной школы-семинара «Синтез и сложность управляющих систем» (Нижний Новгород, 16-19 декабря 1998 г.). — М.: Издательство механико-математического факультета МГУ, 1999. — С. 2530.

16. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций // Дискретная математика. — 2005. — Т. 17, вып. 3. — С. 80-88.

17. Кондратов A.B. Асимптотические оценки высокой степени точности для сложности реализации функций, связанных с автоматными языками, в неко-

торых классах схем // Математические вопросы кибернетики. — Вып. 13. — М.: Наука, 2004. - С. 279-288.

18. Коноводов В. А. Некоторые особенности задачи синтеза булевых формул в полных базисах с прямыми и итеративными входами // Учёные записки Казанского университета. Серия Физико-математические науки. — 2014. — Т. 156, № 3. - С. 76-83.

19. Коноводов В. А. О синтезе схем ограниченной ширины // Материалы VIII молодежной научной школы по дискретной математике и ее приложениям (г. Москва, 24—29 октября 2011 г.). — М.: Издательство механико-математического факультета МГУ им. М. В. Ломоносова, 2011. — Ч. 1. — С. 37—41.

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

21. Коноводов В. А. Некоторые особенности задачи синтеза булевых формул в полных базисах с прямыми и итеративными переменными // Проблемы теоретической кибернетики. Материалы XVII международной конференции (Казань, 16-20 июня 2014 г.). - Казань: Отечество, 2014. - С. 138—140.

22. Коноводов В. А. Асимптотические оценки высокой степени точности для сложности булевых формул в некоторых базисах, состоящих из элементов с прямыми и итеративными входами // Дискретные модели в теории управляющих систем: IX Международная конференция, Москва и Подмосковье, 20-22 мая 2015 г.-М.:МАКС Пресс, 2015. - С. 110—113.

23. Коршунов А. Д. Об асимптотических оценках сложности контактных схем заданной степени // Дискретный анализ. — Вып. 5. — Новосибирск: ИМ СО АН СССР, 1965. - С. 35-63.

24. Кричевский Р. Е. Минимальная схема из замыкающих контактов для одной булевой функции от п аргументов // Дискретный анализ. — Вып. 5. — Новосибирск: ИМ СО АН СССР, 1965. - С. 89-92.

25. Кузьмин В. А. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ // Дискретный анализ. — Вып. 29. — Новосибирск: ИМ СО АН СССР, 1976. - С. 11-39.

26. Ложкин С. А., Коноводов В. А. О синтезе и сложности формул с ограниченной глубиной альтернирования // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2012. — № 2. — С. 28-36.

27. Ложкин С. А., Коноводов В. А. О сложности реализации булевых функций из некоторых классов, связанных с конечными грамматиками, формулами глубины альтернирования 3 // Вестник Московского университета. Серия 1. Математика. Механика. — 2014. — № 3. — С. 14-19.

28. Ложкин С. А., Коноводов В. А. О сложности формул алгебры логики в некоторых полных базисах, состоящих из элементов с прямыми и итеративными входами // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2015. — № 1. — С. 55-68.

29. Ложкин С. А., Коноводов В. А. Оценки высокой степени точности для сложности булевых формул в некоторых базисах из элементов с прямыми и итеративными входами // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2015. — № 2. — С. 16-30.

30. Ложкин С. А., Коноводов В. А. О синтезе и сложности формул с ограниченной глубиной альтернирования // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.). — Нижний Новгород: Издательство Нижегородского университета, 2011. - С. 281-284.

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

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

33. Ложкин С. А. Реализация функций алгебры логики схемами из функциональных элементов с задержками // Диссертация на соискание ученой степени кандидата физико-математических наук. — МГУ им. М. В. Ломоносова, 1979.

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

35. Ложкин С. А. О сложности реализации произвольных булевых функций в некоторых классах // Труды Международной школы-семинара «Дискретная математика и математическая кибернетика» (Ратмино, 31 мая — 1 июня 2001 г.). - М.: МАКС Пресс ИПМ РАН, 2001. - С. 18-19.

36. Ложкин С. А. Асимптотические оценки высокой степени точности для сложности управляющих систем // Диссертация на соискание ученой степени доктора физико-математических наук. МГУ им. М. В. Ломоносова, 1998.

37. Ложкин С. А. О полноте и замкнутых классах функций алгебры логики с прямыми и итеративными переменными // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 1999. — № 3. -С. 35—41.

38. Ложкин С. А. О сложности реализации функций алгебры логики схемами и формулами, построенными из функциональных элементов с прямыми и итеративными переменными // Труды III Международной конференции «Дис-

кретные модели в теории управляющих систем» (Красновидово, 1998 г.). — М.: Диалог-МГУ, 1998. - С. 72-73.

39. Ложкин С. А. Асимптотические оценки высокой степени точности для сложности функций, связанных с автоматными языками // Проблемы теоретической кибернетики. Тезисы докладов XII международной конференции (Нижний Новгород, 17-22 мая 1999 г.), Часть II. — М.: Издательство механико-математического факультета МГУ, 1999. — С. 138.

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

41. Лупанов О. Б. Об одном методе синтеза схем // Известия вузов. Радиофизика.

- 1958. - Т. 1, № 1. - С. 120-140.

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

43. Лупанов О. Б. Об одном классе схем из функциональных элементов (формулы с частичной памятью) // Проблемы кибернетики — 1962. — Вып. 7. — С. 61-114.

44. Лупанов О. Б. О реализации функций алгебры логики формулами из конечных классов (формулами ограниченной глубины) в базисе V, // Проблемы кибернетики — 1961. — Вып. 6. — С. 5-14.

45. Лупанов О. Б. О реализации функций алгебры логики схемами из функциональных элементов «ограниченной глубины» в базисе &;, V, // Сборник работ по математической кибернетике — 1977. — Вып. 2. — С. 3-8.

46. Лупанов О. Б. О влиянии глубины формул на их сложность // Кибернетика

- 1970. - Вып. 2. - С. 46-49.

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

48. Мадатян X. А. Синтез контактных схем ограниченной ширины // Проблемы кибернетики - 1965. - Вып. 14. - С. 301-307.

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

50. Трущин Д. В. О глубине «-пополнений систем булевых функций // Вестник Московского университета. Серия 1. Математика. Механика. — 2009. —№ 2. - С. 72-75.

51. Трущин Д. В. О сложности реализации функци многозначной логики формулами специального вида // Материалы XI Международного семинара «Дискретная математика и ее приложения»(Москва, 18-23 июня 2012 г.). — М.: Издательство механико-математического факультета МГУ. — С. 174-176.

52. Холл М. Комбинаторика. — М.: Мир, 1970. — 424 с.

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

54. Чернышов А. Л. Условия а-полноты систем функций многозначной логики // Дискретная математика. — 1992. — Т. 4, вып. 4. — С. 117-130.

55. Шиганов А. Е. О синтезе ориентированных контактных схем с некоторыми ограничениями на смежные контакты // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2009. — № 3. — С. 46-52.

56. Шиганов А. Е. Некоторые особенности задачи синтеза булевых формул в полных базисах с прямыми и итеративными входами // Учёные записки Ка-

занского государственного университета. Серия Физико-математические науки. - 2009. - Т. 151, № 2. - С. 164-172.

57. Шиганов А. Е. Синтез схем контактного типа с ограничением на смежные контакты // Диссертация на соискание ученой степени кандидата физико-математических наук. — МГУ им. М. В. Ломоносова, 2010.

58. Шиганов А. Е. Некоторые оценки сложности двоичных решающих диаграмм // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.). — Нижний Новгород: Издательство Нижегородского университета, 2011. — С. 568-570.

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

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