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

• Калачев, Глеб Вячеславович
• кандидат наук
• 2017

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

Оглавление

Введение

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

§2 Краткое содержание работы

§2.1 Плоские схемы

§2.2 Меры мощности схем

§2.3 Общие обозначения

§2.4 Результаты

1 Общие оценки мощности плоских схем

§1 Связь переключательной мощности и потенциала

§2 Связь между мощностью и площадью плоских схем

§3 Универсальная нижняя оценка средней мощности плоских схем

§4 Общие вспомогательные утверждения

2 Оценки мощности частичных булевых операторов

§1 Нижние оценки

§1.1 Идея и схема доказательства для случая большого числа выходов

§1.2 Метод расслоения

§1.3 Общие оценки для частичных операторов

§1.4 Нижние оценки для всюду определенных операторов

§2 Верхние оценки

§2.1 План доказательства

§2.2 Вспомогательные блоки

§2.3 Реализация всюду определённой булевой функции

§2.4 Построение схемы частичной булевой функции

§2.5 Реализация частичного булева оператора

3 Оценки мощности для различных классов булевых функций

§1 Оценки для функций с малым числом единиц

§1.1 Нижние оценки

§1.2 Верхняя оценка

§2 Оценки мощности для замкнутых классов булевых функций

§2.1 Построение схемы, реализующей монотонную функцию

§3 Мощность схем, реализующих функции из остальных замкнутых классов

Заключение

Список литературы

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

Введение

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

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

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

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

Актуальность темы и степень ее разработанности

Исторически первой моделью устройств, вычисляющих булевы функции, были контактные схемы1 (далее — КС), введённые К. Шенноном [3] в 1938 году ещё до появления электронно-вычислительных устройств.

С 1950-х годов популярной моделью стали схемы из функциональных элементов (далее — СФЭ). Д. Мюллер в работе [4] 1956 года определил сложность СФЭ, как количество её элементов и показал, что для класса всех булевых функций от п переменных в худшем случае сложность имеет порядок 2п/п. Под сложностью булевой функции понимается минимальная сложность среди схем, реализующих эту функцию. Вскоре О. Б. Лупанов в работе [5] доказал, что в стандартном базисе ({V, &, —}) сложность почти всех булевых функций асимптотически равна 2п/п. Более того, он исследовал взвешенную сложность и нашёл асимптотическую формулу сложности для почти всех функций в произвольном конечном базисе с заданными положительными весами всех базисных функций. Л. А. Шоломов в работе [6] предложил асимптотически оптимальный метод синтеза СФЭ для класса частичных операторов, разбивающих область определения на части заданного размера, однако в теореме накладываются существенные ограничения на размеры этих частей и область определения. В работе [7] Шоломов нашёл асимптотику функции Шеннона сложности СФЭ, реализующих частичные булевы функции в произвольном конечном базисе. Из его теоремы, в частности, следует, что при некоторых ограничениях сложность почти всех частичных булевых функций в стандартном базисе асимптотически равна б/ 1с^2 б, где б — число наборов, на которых значение функции определено. А. Е. Андреев в работе [8] усилил результат Шоломова, найдя асимптотику функции Шеннона уже без ограничений на размер области определения.

В работе [9] А. Е. Андреев и И. А. Вихлянцев рассмотрели другую меру сложности СФЭ — длину кода схемы, которая кроме числа элементов отражает и топологию их соединения. Каждой СФЭ ставится в соответствие двоичный код программы, позволяющей последовательно вычислить функцию в соответствии с данной СФЭ. Фактически, кодирование СФЭ можно рассматривать, как топологическую сортировку её графа с последующей укладкой на целочисленную решётку на прямой так, чтобы все рёбра были направлены вправо. При такой интерпретации длина кода СФЭ в основном определяется суммой логарифмов длин рёбер графа при заданной укладке. В [9] предложен метод, позволяющий по произвольной СФЭ строить асимптотически оптимальный код, а также показано, что функция Шеннона длины кода СФЭ для функций от п переменных асимптотически равна 2п. Кроме этого, показано, что для сумматора двух двоичных чисел длина кода СФЭ растёт линейно от числа переменных, а для умножителя - нелинейно.

Другую меру сложности — мощность СФЭ — определил М. Н. Вайнцвайг в работе [10]. Мощность(активность) СФЭ равна максимальному количеству элементов схемы, выдающих на выходе единицу, где максимум берётся по всем возможным входным наборам. Мощность СФЭ отражает электрическую мощность устройства, вычисляющего булеву функцию. При таком определении мощности СФЭ предполагается, что функциональный элемент потребля-

Определения терминов, используемых во введении, можно найти, например, в учебнике [1] и обзоре [2]

ет энергию, только когда значение на его выходе равно 1. Вайнцвайг исследовал мощность СФЭ в зависимости от базиса и показал, что её порядок может быть как линейным (например, в базисе {V, &, —}), так и экспоненциальным (например, в базисе {X V у}). Более детально зависимость мощности СФЭ О. М. Касим-Заде. В работе [11] он предложил метод синтеза СФЭ в базисе {V, &, —}, одновременно асимптотически оптимальных по сложности с линейной мощностью. В работе [12] Касим-Заде исследовал мощность в различных базисах и установил порядок функции Шеннона мощности СФЭ для произвольного полного конечного базиса, а также привёл пример базиса, в котором для почти всех функций не существует схем с асимптотически оптимальной сложностью и мощностью, оптимальной по порядку.

В работе [13] Касим-Заде ввёл ещё одну меру мощности СФЭ — Р-активность: на каждом входном наборе рассматривается количество элементов, на вход которых подаётся единица, или сам элемент выдаёт единицу, после этого берётся максимум по всем наборам. Фактически, Р-активность, в отличие от обычной активности, учитывает степень ветвления на выходах элементов СФЭ. Как и для обычной активности, для Р-активности Касим-Заде исследовал зависимость от базиса и, в частности, показал, что в базисе {V, &, —} любую функцию от п переменных можно реализовать при помощи СФЭ с Р-активностью 0(п2).

С. А. Ложкин и М. С. Шуплецов в работе [14] ввели понятие динамической активности СФЭ — максимальное количество выходов элементов, изменяющих своё значение при изменении входных наборов схемы. Такая мера сложности обусловлена тем, что большая часть энергии микросхемы выделяется именно при изменении значений на её входах и, соответственно, в узлах схемы. В работе [14] было показано, в любом полном базисе можно реализовать булеву функцию от п переменных с линейной динамической активностью, а также был предложен метод синтеза СФЭ в базисе {V, &, —} для функций от п переменных с асимптотической сложностью 2п/п и линейной динамической активностью. Важно отметить, что, в отличие от обычной(статической) активности, порядок динамической активности не зависит от базиса.

Ещё одной важной мерой сложности СФЭ является её глубина. Если сложность моделирует размер устройства, мощность — энергопотребление, то глубина определяет задержку между подачей входного набора на вход устройства и получением вычисленного значения на выходе. В работе [15] С. Б. Гашков показал, что функция Шеннона для глубины СФЭ, реализующих функции от п переменных, с точностью до константы равна п — 1с^21с^2 п.

СФЭ является далеко не единственной моделью, позволяющей определять меры сложности булевых функций. Другой такой моделью являются контактные схемы (далее КС). Сложностью КС является количество её контактов. Лупанов показал [16], что асимптотическая сложность КС, реализующих булевы функции от п переменных, равна 2п/п, как и для СФЭ. Ю. С. Шуткин в работе [17] ввёл понятие временной сложности КС — в определённом смысле аналог мощности СФЭ. Шуткин показал, что функция Шеннона временной сложности КС растёт линейно от числа переменных.

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

последовательность вычисления значений этих переменных в виде программы, в которой каждая строчка имеет вид хг = /г(xji х, ...,Xji „.), где / — функция, вычисляемая г-м функциональным элементом, Xji х, ...,xj•i п. — переменные, приписанные входам этого элемента, хг — переменная, приписанная его выходу. В неветвящейся программе с условной остановкой левые части команд могут повторяться, и кроме обычных команд могут также быть команды вида з£ор(хг). Если хг = 1, то выполнение программы на этом шаге завершается. Таким образом, среднее время выполнения программы с условной остановкой может быть существенно меньше, чем длина программы. Среднее время оптимальной программы с условной остановкой называется средней сложностью булевой функции. В работе [18] были получены порядки функции Шеннона средней сложности для классов всюду определённых булевых функций, частичных булевых функций и функций с малым числом единиц. В частности, было показано, что для почти всех булевых функций средняя сложность по порядку совпадает со сложностью СФЭ, а для класса функций с малым числом единиц от п переменных средняя сложность по порядку в п раз меньше сложности СФЭ.

Применительно к моделированию микросхем, реализующих булевы функции, из перечисленных моделей ближе всего СФЭ. Недостатком модели СФЭ является то, что в ней не учитывается разводка проводов на плоскости, хотя при проектировании чипа размещение проводов является не менее важной задачей, чем построение самой логической схемы. В работе [19] С. С. Кравцов предложил модель плоских (клеточных) схем2, которая включает в себя как логическую часть (СФЭ), так и размещение её элементов на плоскости. Фактически, плоская схема является укладкой СФЭ на целочисленную решётку на плоскости таким образом, что соединены могут быть лишь элементы, находящиеся с соседних точках решётки; при этом длинные провода моделируются цепью элементов, реализующих тождественные функции. В работе [19] было показано, что прядок функции Шеннона площади плоских схем, реализующих функции от п переменных, равен 2п. А. Альбрехт в работе [20] показал, что асимптотика функции Шеннона имеет вид а2п, однако доказательство неконструктивное, и конкретное значение константы а неизвестно. Кроме того, эта константа может зависеть от базиса.

Н.А. Шкаликова в работе [21] исследовала площадь плоских схем для некоторых конкретных семейств булевых операторов, а также для класса симметрических булевых функций. Кроме того, в этой работе исследуется связь между площадью плоских схем и объёмом трёхмерных схем, реализующих булевы операторы. В [21] показано, что если оператор реализуется трёхмерной схемой с объёмом V, то его можно реализовать плоской схемой с площадью 0(У3/2) , причём порядок этой оценки нельзя понизить. Д. А. Жуков в работах [22], [23], [24] для различных семейств булевых операторов и функций предложил методы синтеза плоских схем, оптимизирующий одновременно площадь и глубину. В частности, в работе [24] Жуков показал, что произвольную частичную булеву функцию можно реализовать плоской схемой

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

с площадью O(d) и глубиной O(log d), где d — размер области определения.

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

Теоретическая и практическая ценность работы

Диссертация носит теоретический характер. Результаты работы могут применяться при проектировании СБИС для уменьшения энергопотребления различных электронных устройств.

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

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

Апробация работы и публикации автора

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

• Международная конференция студентов, аспирантов и молодых учёных «Ломоносов» (2013, 2014, Москва)

• Ломоносовские чтения (2013, 2014)

• XII Международный семинар «Дискретная математика и ее приложения» имени академика О. Б. Лупанова (2016, Москва).

• XI Международная конференция «Интеллектуальные системы и компьютерные науки» (2016, Москва)

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

• Семинаре «Теория автоматов» под руководством академика, проф., д.ф-м.н. В. Б. Кудрявцева (2013 г., 2016 г., 2017 г.).

• Семинаре «Вопросы сложности алгоритмов поиска» под руководством проф., д.ф-м.н. Э. Э. Гасанова (2013 - 2016 гг.).

• Спецсеминар для преподавателей, научных сотрудников, аспирантов и студентов «Дискретная математика и математическая кибернетика» (2016 г.).

Основные результаты диссертации опубликованы в статьях [29-34] в рецензируемых научных изданиях, определённых положением о присуждении учёных степеней в МГУ имени М. В. Ломоносова, а также в тезисах конференций [35-37].

Структура и объем работы

Диссертация состоит из введения и трёх глав. Объем диссертации 164 страницы. Список литературы содержит 37 наименований.

Благодарности

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

§2 Краткое содержание работы §2.1 Плоские схемы

Клеточным элементом будем называть булев оператор, у которого в сумме не более четырёх входов и выходов, причём каждому его входу и каждому выходу сопоставлена некоторая метка из множества {/, г, Ь, Ь}, причём метки не повторяются. Метки будем также называть сторонами элемента:

• I — левая сторона;

• г — правая сторона;

• Ь — верхняя сторона;

• Ь — нижняя сторона.

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

Метки, присвоенные входам (выходам) оператора будем называть входами (выходами) элемента. Метки, не присвоенные ни входам, ни выходам, будем называть изоляторами. Множество входов (выходов) элемента е будем обозначать гп(е) (оиЬ(е)). Входы и выходы элемента будем называть его контактами.

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

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

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

Описывать элемент будем уравнениями, которые задают его оператор, заменяя все переменные в них на сопоставленные им метки (1,г,Ь или Ь). Тогда в левой части каждого уравнения будет стоять выходная метка, а в правую будут входить только входные метки.

(а) логические элементы

(Ъ) коммутационные элементы Рис. 1: Примеры клеточных элементов.

На рисунке 1 приведены примеры клеточных элементов.

Для удобства введем пустой клеточный элемент — изолирующий (будем обозначать Л).

Всюду далее значок := будет обозначать «по определению равно».

Через Е обозначим множество всех клеточных элементов, Не := |Е|.

Сетью из клеточных элементов на множестве М С 1? над базисом Е С Е будем называть отображение К : М ^ Е'.

Элемент К(х,у) будем называть элементом схемы К с координатами (х,у). Элемент с приписанными ему координатами будем называть элементом схемы.

Левой, правой, верхней и нижней сторонами элемента е с координатами (х,у) будем называть точки с координатами (х — |,у), (х + |,у), (х,у — 2) и (х,у + 2) соответственно (на рисунках ось у будет направлена вниз).

Будем говорить, что сеть К из клеточных элементов корректна, если для любых двух элементов х и у схемы К верно, что если сторона а элемента х совпадает со стороной Ь элемента у, то выполнено одно из условий:

• один из элементов х, у — изолирующий,

• стороны а и Ь являются изоляторами,

• Среди сторон а и Ь одна является входом, другая — выходом, например, а — выход, а Ь — вход, в таком случае будем говорить, что выход а подключен к входу Ь;

Множество М будем называть носителем сети К.

Введём понятие графа корректной сети из клеточных элементов К (будем обозначать О к). О к — ориентированный граф, вершинами которого являются входы и выходы элементов схемы. Если выход одного элемента подключён ко входу другого, то им будет соответствовать одна и та же вершина графа (будем говорить, что эта вершина является выходом первого элемента и входом второго). Из вершины а в вершину Ь ведёт ребро в том и толь-

ко том случае, когда существует элемент е такой, что а является его входом, Ь — выходом, причём функция, реализуемая на выходе Ь, существенно зависит от входа а.

Плоской схемой или схемой из клеточных элементов на множестве М С Ъ2 над базисом Е' С Е будем называть корректную сеть из клеточных элементов, в графе которой нет ориентированных циклов. Множество М будем называть носителем схемы К.

Список литературы диссертационного исследования кандидат наук Калачев, Глеб Вячеславович, 2017 год

Список литературы

[1] Чашкин А. В. Дискретная математика. — Академия Москва, 2012. — С. 352. — ISBN: 9785-7695-7949-3.

[2] Коршунов А. Д. Сложность вычислений булевых функций // Успехи математических наук.—2012. —Т. 67, № 1. —С. 97-168.

[3] Shannon C. E. A symbolic analysis of relay and switching circuits // Transactions of the American Institute of Electrical Engineers. — 1938. —Vol. 57, no. 12. — P. 713-723.

[4] Muller D. E. Complexity in Electronic Switching Circuits // IRE Transactions on Electronic Computers. —1956.—Vol. EC-5, no. 1.—P. 15-19.

[5] Лупанов О. Б. Об одном подходе к синтезу управляющих систем - принципе локального кодирования // Проблемы кибернетики. Вып 14. — Наука, М., 1965. — С. 31-110.

[6] Шоломов Л. А. О функционалах сложности систем недоопределённых функций // Проблемы кибернетики. Вып 19. — Наука, М., 1967. — С. 123-139.

[7] Шоломов Л. А. О реализации недоопределенных булевых функций схемами из функциональных элементов // Проблемы кибернетики. Вып 21. — Наука, М., 1969. — С. 215-226.

[8] Андреев А. Е. О сложности реализации частичных булевых функций схемами из функциональных элементов // Дискретная математика. — 1989. — Т. 1, № 4. — С. 36-45. — Режим доступа: http://mi.mathnet.ru/dm939.

[9] Андреев А. Е., Вихлянцев И. А. Оценки длины кода для схем из функциональных элементов // Дискретная математика. — 1994. — Т. 6, № 4. — С. 10-20. — Режим доступа: http://mi.mathnet.ru/dm651.

[10] Вайнцвайг М. Н. О мощности схем из функциональных элементов // Докл. АН СССР. — 1961. —Т. 139, № 2. —С. 320-323.

[11] Касим-Заде О. М. Об одновременной минимизации сложности и мощности схем из функциональных элементов. // Проблемы кибернетики. Вып. 33. — М.: Наука, 1978. — С. 215220.

[12] Касим-Заде О. М. Об одной мере сложности схем из функциональных элементов // Проблемы кибернетики. Вып. 38. — М.: Наука, 1981. — С. 117-179.

[13] Касим-Заде О. М. Об одной мере активности схем из функциональных элементов. // Математические вопросы кибернетики. Вып 4. — М.: Наука, 1992. — С. 218-228.

[14] Ложкин С. А., Шуплецов М. С. О динамической активности схем из функциональных элементов и построении асимптотически оптимальных по сложности схем с линейной динамической активностью // Ученые записки Казанского университета. Серия Физико-математические науки. — 2014. — Т. 156, № 3. — С. 84-97.

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

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

[17] Шуткин Ю. С. Об одновременной минимизации объемной и временной сложности контактных и вентильных схем // Интеллектуальные системы. Теория и приложения. — 2010. —Т. 14, № 1-4.— С. 595-615.

[18] Чашкин А. В. О среднем времени вычисления значений булевых функций // Дискретный анализ и исследование операций. — 1997. — Т. 4, № 1. — С. 60-78.

[19] Кравцов С.С. О реализации функций алгебры логики в одном классе схем из функциональных и коммутационных элементов // Проблемы кибернетики. Вып 19. —М.: Наука, 1967. —С. 285-293.

[20] Альбрехт А. О схемах из клеточных элементов // Проблемы кибернетики. Вып 33. — М.: Наука, 1977.— С. 209-214.

[21] Шкаликова Н. А. О реализации булевых функций схемами из клеточных элементов // Математические вопросы кибернетики. Вып 2. — М.: Наука, 1989. — С. 177-197.

[22] Жуков Д. А. О времени параллельного сложения нескольких чисел // Вестник Московского университета. Серия 1, Математика. Механика. — 2001. — № 6. — С. 52-54.

[23] Жуков Д. А. Быстрые клеточные схемы для умножения // Дискретный анализ и исследование операций. Серия 1. — 2002. — Т. 9, № 3. — С. 40-47.

[24] Жуков Д. А. О вычислении частичных булевых функций клеточными схемами // Дискретный анализ и исследование операций. Серия 1. — 2004. — Т. 11, № 2. — С. 32-40.

[25] Черемисин О. В. Об активности схем из клеточных элементов, реализующих систему всех конъюнкций // Дискретная математика. — 2003. — Т. 15, № 2. — С. 113-122.

[26] Зорич В. А. Математический анализ. Часть I. — МЦНМО Москва, 2017. — С. 576. — ISBN: 978-5-4439-0693-5.

[27] Угольников А.Б. Классы Поста. Учебное пособие. — М.: Изд-во ЦПИ при механико-математическом факультете МГУ имени М.В. Ломоносова, 2008. — С. 64.

[28] Klarner D. A., Rivest R. L. A procedure for improving the upper bound for the number of n-ominoes // Canadian Journal of Mathematics. — 1973. —Vol. 25. —P. 585-602.

Публикации автора Статьи

[29] Калачев Г. В. Порядок мощности плоских схем, реализующих булевы функции // Дискретная математика. — 2014. — Т. 26, № 1. — С. 49-74. — (перевод: Kalachev G. V. Order of power of planar circuits implementing Boolean functions // Discrete Mathematics and Applications. — 2014. — Vol. 24, no. 4. — P. 185-205.).

[30] Калачев Г. В. Нижние оценки мощности плоских схем, реализующих частичные булевы операторы // Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460). — 2014. — Т. 18, № 2. — С. 279-322.

[31] Калачев Г. В. Об одновременной минимизации площади, мощности и глубины плоских схем, реализующих частичные булевы операторы // Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460). — 2016. —Т. 20, № 2. —С. 203-266.

[32] Калачев Г. В. Об оценках мощности плоских схем для замкнутых классов булевых функций // Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460). — 2016. — Т. 20, № 3. — С. 52-57.

[33] Калачев Г. В. Оценки мощности плоских схем, реализующих функции с ограниченным числом единиц // Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460). — 2017. — Т. 21, № 1. — С. 28-96.

[34] Калачев Г. В. Оценки мощности плоских схем, реализующих монотонные функции // Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460).— 2017.— Т. 21, № 2. —С. 163-192.

Тезисы конференций

[35] Калачев Г. В. Порядок мощности плоских схем, реализующих булевы функции // Тезисы докладов XX Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2013» / Секция «Математика и механика» / 2013г. / тезисы. — Москва, 2013.

[36] Калачев Г. В. Оценки мощности плоских схем, реализующих булевы операторы // Тезисы докладов XX Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2014». Секция «Математика и механика:». — 2014.

[37] Калачев Г. В. О порядке роста мощности плоских схем для замкнутых классов булевых функций // Материалы XII Международного семинара «Дискретная математика и ее приложения» имени академика О. Б. Лупанова (Москва, МГУ, 20-25 июня 2016 г.). — Изд-во механико-математического факультета МГУ Москва, 2016. — С. 132-133.