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

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

Коноводов Владимир Александрович

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

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

221''0Л 2015

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

005570855

Москва — 2015

005570855

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики федерального государственного бюджетного образовательного учреждения высшего образования «Московский государственный университет имени М. В. Ломоносова».

Научный руководитель: Ложкин Сергей Андреевич,

доктор физико-математических наук, профессор кафедры математической кибернетики факультета вычислительной математики и кибернетики федерального государственного бюджетного образовательного учреждения высшего образования «Московский государственный университет имени М. В. Ломоносова»

Официальные оппоненты: Аблаев Фарнд Мансурович,

доктор физико-математических наук, профессор, член-корреспондент Академии Наук Республики Татарстан, заведующий кафедрой теоретической кибернетики Казанского федерального университета Шиганов Александр Евгеньевич, кандидат физико-математических наук, ведущий инженер по разработке программного обеспечения в филиале компании «Ментор Графике Девелопмент Сервисез Лимитед» (Ирландия)

Ведущая организация: «Федеральный исследовательский центр «Информатика и управление» Российской Академии Наук

Защита состоится 25 сентября 2015 г. в 11 час. 00 мин. на заседании диссертационного совета 501.001.44 при Московском государственном университете имени М. В. Ломоносова по адресу: 119991, г. Москва, ГСП-1, Ленинские горы, д. 1, стр. 52, 2-й учебный корпус, аудитория 685.

С диссертацией можно ознакомиться в Научной библиотеке Московского государственного университета имени М. В. Ломоносова по адресу: 119192, г. Москва, Ломоносовский проспект, д. 27 — а также на официальном сайте факультета ВМК МГУ http://cmc.msu.ru в разделе «Диссертации».

Автореферат разослан « 8 » 2015 года.

Ученый секретарь

диссертационного совета 501.001.44, доктор физико-математических наук, доцент

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

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

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

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

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

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

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

'MullerD. Е. Complexity in electronic switching circuits // Electronic Computers, IRE Transactions on. 1956. Vol. 5. no. 1. P. 15-19.

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

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

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

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

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

О. Б. Лупановым одним из первых были исследованы некоторые классы схем из функциональных элементов с ограничениями. Им была получена асимптотика функции Шеннона, связанной со сложностью схем, в которых выход любого элемента может быть подсоединен не более чем к заданному числу входов других элементов5. Также О.Б.Лупанов 6'7 рассматривал формулы и схемы ограниченной глубины в стандартном базисе {V, -1}, у которых отрицания стояли только над переменными. Под глубиной схемы понимается уменьшенное на единицу максимальное число изменений типов элементов в последовательностях, которые являются цепями этой схемы без учета отрицаний, присоединённых к её входам. В диссертации эта величина называется глубиной альтернирования схемы. Установлено, что функция Шеннона для сложности формул, имеющих

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

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

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

'Лупанов О. Б. О влиянии гаубины формул на их сложность // Кибернетика. — 1970. — № 2. — С. 46-49.

глубину альтернирования не большую, чем d, и реализующих функции от п переменных, при всех d > 3 асимптотически ведет себя так же, как и в случае без ограничений — 2П/ log п. Аналогичный результат был получен и для схем из функциональных элементов8.

Другой тип ограничения, связанный с числом регистров, т. е. ячеек памяти, необходимых для осуществляемых схемой вычислений, был рассмотрен в работах Н. А. Карповой 9,1°, которая, в частности, показала, что функция Шеннона для класса схем с t регистрами в базисе из всех уместных функций при фиксированных t ^ 3 и р ^ 2 асимптотически ведет себя как в диссертации схемы с t регистрами называются схемами ширины t.

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

Одной из первых моделей контактных схем с ограничениями была модель, в которой степени вершин схемы "ограничены некоторой константой. А.Д.Коршунов описал13 асимптотически оптимальный метод их синтеза, а Х.А.Мадатян получил14 асимптотические оценки сложности реализации булевых функций с помощью контатных схем ограниченной ширины. А. Е. Шигано-вым 15,16 рассматр ивалис ь контактные схемы и итеративные контактные схемы с различными типами ограниченййТГасмё5Кные контакты. В частности, были раз-

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

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

10КарповаН. А. О сложности представлений функций алгебры логики линейными суперпозициями // Дискретный анализ. - 1986. - Вып. 43. - С. 40-46.

11 Shannon С. Е. The synthesis of two-terminal switching circuits // Bell System Technical Journal, 1949. Vol. 28,

по. 1. P. 59-98.

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

''Коршунов А. Д. Об асимптотических оценках сложности контактных схем заданной степени // Дискретный

анализ. - 1965. - Вып. 5. - С. 35-63.

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

- С. 301-307.

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

16Шиганов А. Е. О сложности ориентированных контактных схем с ограниченной полустепенью исхода // Учён. зап. Казан, гос. ун-та. Сер. Физ.-матем. науки. — 2009. - Т. 151. — № 2. — С. 164-172.

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

Другой моделью, изучаемой в математической кибернетике, являются вычисляющие программы. Класс бинарных программ был введён В. А. Кузьминым17, который рассматривал два основных типа команд — вычислительные и переадресующие команды, и получил асимптотику функции Шеннона сложности таких программ из некоторых классов. Асимптотику вида 2"/(3п) для сложности бинарных программ общего вида получил О. М.Касим-Заде18. Класс бинарных программ, состоящих только из переадресующих команд, был впервые предложен Ли19, такие программы также называются BDD (Binary Decision Diagrams), и имеют огромное значение в прикладных задачах20,21. Асимптотику 2п/п функции Шеннона для сложности двоичных решающих диаграмм установил В.А.Кузьмин17. Для некоторых классов BDD С.А.Ложкиным22, А. Е. Шигановым23 и С. В. Грибком 24 были получены асимптотические оценки высокой степени точности для соответствующих функций Шеннона.

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

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

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

|8Касим-ЗадеО.М. О сложности реализации функций в одном классе алгоритмов // Материалы IX межгосударственной школы-семинара «Синтез и сложность управляющих систем». Изд. мех.-мат. ф-та МГУ. — 1999. — С. 25-30.

"LeeC. Y. Representation of switching circuits by binary-decision programs // Bell Labs Tech. J., 1959. Vol. 38, по. 4. Р. 958-999.

^BiyantR-E. Graph-based algorithms for Boolean function manipulation // IEEE TYansactions on Computers. 1986. Vol. 35, no. 8. P. 677-691.

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

22 Ложкин С. А. О сложности реализации произвольных булевых функций в некоторых классах BDD // Труды международной школы-семинара «Дискретная математика и математическая кибернетика». М.: МАКС Пресс, 2001. С. 18-19.

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

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

номера присоединяемых входов. При этом предполагается, что базисные элементы имеют входы двух видов — прямые и итеративные. Прямые входы могут являться только входами схемы, а на итеративные входы должны подаваться выходы других элементов. Впервые задача синтеза в такой модели была предложена и рассмотрена С. А. Ложкиным25'2б. Им был установлен критерий полноты относительно всех функций прямых переменных при наличии в базисе элементов, реализующих функции-константы, и описаны некоторые особенности решетки вложения замкнутых классов функций с прямыми и итеративными переменными. При этом все базисы специальным образом классифицировались для определения их полноты. Для оператора, с помощью которого проводилась эта классификация, в настоящей диссертации получено более наглядное представление. Это представление определяет результат применения этого оператора к некоторому базису А как множество тех функций, зависящих только от итеративных переменных, которые можно получить рассматриваемыми суперпозициями функций из А. В диссертации указанный оператор назван оператором итеративного замыкания.

Также С. А. Ложкиным было исследовано поведение функции Шеннона на уровне асимптотических оценок высокой степени точности для класса всех схем из функциональных элементов над произвольным полным базисом с прямыми и итеративными переменными и некоторых его подклассов. Эта функция имеет «стандартный» для схем порядок роста 2п/п. Известно также26, что функция Шеннона для формул в таких базисах имеет порядок роста не более, чем 2™, и не менее, чем 2П/ log п.

К этому направлению задачи синтеза относится также задача реализации функций алгебры логики а-формулами, т. е. формулами, в которых каждая подформула содержит не более одной нетривиальной главной подформулы. Эту задачу впервые рассматривал М. М. Глухов27, он показал существование при k ^ 7 конечных а-полных систем, т. е. таких систем, что любую функцию fc-значной логики можно реализовать а-формулой над этой системой. А. Л. Чернышевым28 был доказан критерий ct-полноты функций многозначной логики и показано от-

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

26Ложкин С. А. О сложности реализации функций алгебры логики схемами и формулами, построенными из функциональных элементов с прямыми и итеративными переменными // Т^руды Ш Международной конференции «Дискретные модели в теории управляющих систем» (Красновидово, 1998 г.) Диалог-МГУ, Москва. - 1998. -С. 72-73.

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

28Чернышов А. Л. Условия а-полноты систем функций многозначной логики // Дискретная математика. -

1992. _ Т. 4. - Вып. 4.-С. 117-130.

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

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

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

Основные результаты работы:

1. Получены оценки высокой степени точности функции Шеннона для сложности формул в базисе {&, V, ~i} с ограниченной глубиной альтернирования.

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

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

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

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

6

Научная новизна. Все результаты диссертации являются новыми.

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

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

Апробация работы. Результаты работы докладывались на следующих конференциях.

• XVI Международная конференция «Проблемы теоретической кибернетики» (Нижний Новгород, 2011),

• VIII Молодежная научная школа по дискретной математике и ее приложениям (Москва, 2011),

• IX Молодежная научная школа по дискретной математике и ее приложениям (Москва, 2013),

• XVII Международная конференция «Проблемы теоретической кибернетики» (Казань, 2014),

• IX Международная конференция «Дискретные модели в теории управляющих систем» (Москва и Подмосковье, 2015).

Также результаты обсуждались на научных семинарах кафедры математической кибернетики факультета ВМК МГУ и кафедры дискретной математики механико-математического факультета МГУ.

Личный вклад. Все результаты получены автором самостоятельно.

Публикации. Результаты диссертации изложены в 10 печатных изданиях [1-Ю], из которых [1-5] — в журналах из перечня рецензируемых научных изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученой степени кандидата наук. В работах [1,2,4-6] Коноводову В. А. принадлежат все результаты, а Ложкину С. А. — постановка задачи.

Структура и объем работы. Диссертация состоит из введения, двух глав, заключения и списка литературы. Общий объем диссертации составляет 109 страниц. Принята сквозная нумерация лемм и теорем. Список литературы содержит 60 наименований.

Содержание работы

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

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

Вводится модифицированное понятие грамматики с конечным числом состояний30. Пусть грамматика Г задается множеством внутренних состояний Si,. ■ •, Sp и множеством грамматических правил. Каждое грамматическое правило определяется упорядоченной парой (сг, fe), а £ {0,1}, 1 < к ^ р. Если такое правило (а, к) сопоставляется состоянию Si, 1 < i ^ р, то это означает, что, когда грамматика находится в состоянии S¿, может быть произведен символ а, причем грамматика переходит в состояние S*. Выделим в Г два произвольных (возможно, совпадающих) состояния Sj и Sj, 1 < i,j < р. Грамматика Г, отправлясь от состояния Si, пробегает в соответствии с грамматическими правилами последовательность состояний S^,..., Sit, где 1 < ¿i,...,it < р, ¿i = г, it = j, и переходит в состояние Sj, при этом она производит слово, состоящее из цепочки символов в том порядке, в котором они выбирались при последовательных переходах. Пусть Ту—множество таких слов. Языком грамматики Г без выделенного начального состояния называется язык Тг = U Ту.

Пусть Тг(з), s ^ I,—множество слов языка 7г, длина которых равна s. Н. Хомский и Дж. Миллер показали30, что мощность 7г(з) либо ограничена, либо с ростом s растет линейно, либо экспоненциально. В последнем случае существует такая константа сгг € (0,1], что при s —оо справедливо соотношение |7r(s)| = 2"T'a+0^l\ Величина от называется мощностной константой грамматики Г. Класс булевых функций от п, п > 1, переменных, множество столбцов значений которых совпадает с 7г(2п), обозначается как Qr(n).

30ChomskyN„ Miller G. A. Finite slate languages // Information and Control. 1958. Vol. 1. P. 91-112

8

Далее определяется понятие схемы ограниченной ширины. Схема Е является схемой с t регистрами, если все её функциональные элементы занумерованы числами 1,2,..., Ь, где Ь = ДЕ), и каждому из них приписан регистр из множества К = {г1,...,^} так, что для произвольного элемента £ схемы Е номер £ больше номера любого элемента, выход которого подается на один из его входов; и если на вход элемента £ с номером j е [2, Ь], подается выход элемента £' с номером г, г € [1,^' — 1], и приписанным ему регистром г, г £ Я, то другим элементам с номерами из интервала (г,з) регистр г не приписан. Кроме того, считается, что значения входных переменных схемы записаны в отдельных входных регистрах гХ1,..., гХп, не лежащих во множестве Л. При этом предполагается, что функциональный элемент с номером j, ] = 1,..., Ь, указанной схемы «срабатывает» в момент времени выбирая значение каждого своего входа либо из регистра, приписанного выходу соответствующего элемента Е, либо из некоторого входного регистра, и занося вычисленное значение своей базисной функции в приписанный ему регистр. Входные регистры, таким образом, не используются схемой в процессе описанного вычисления для записи результатов. Регистры из множества Я, наоборот, служат ячейками памяти для вычисления, производимого схемой. Для схемы Е с Ь е {1,2,...}, регистрами число t называется её шириной.

Схема с ¿, 4 ^ 1, регистрами реализует систему из т, т > 1, функций Р1, если в схеме выделены т элементов £\,..., £т, являющихся выходными, и имеются т дополнительных выходных.регистров г[,... ,г'т К при всех

г, г = 1, ...,т) таких, что после срабатывания £{ (г = 1,...,т) в регистр г- записывается значение из регистра, приписанного элементу Кроме того, значения в выходных регистрах не могут подаваться на входы элементов схемы.

Пусть X = {хх, х2,. • •} и У = {ух, у2, • • •} — счетные множества булевых переменных, переменные из множества X (из 10 называются прямыми (соответственно, итеративными). Для каждого множества переменных 2 через Рг(2) обозначается множество всех функций алгебры логики, зависящих от переменных из

На множестве Р2(ХиУ), определяются следующие операции суперпозиции:

1. переименование (с отождествлением) прямых переменных,

2. подстановка констант 0, 1 вместо переменных,

3. переименование (без отождествления) итеративных переменных,

4. подстановка одной из двух функций, не имеющих общих существенных переменных, вместо итеративной переменной другой функции,

5. замена итеративных переменных прямыми переменными,

9

6. отождествление итеративных переменных.

Пусть А С Р2(Х и У) — некоторое конечное множество базисных функций. В соответствии с введенными операциями суперпозиции в диссертации рассматриваются одновыходные схемы из функциональных элементов и формулы над базисом А, в которых прямые входы любого элемента либо присоединяются к входам схемы, либо являются константными входами (вход называется константным, если вместо него в базисный элемент подставлена константа 0 или 1); итеративные входы любого элемента либо присоединяются к выходам других элементов, либо присоединяются к входам схемы, либо являются константными входами; неконстантным входам схемы сопоставлены некоторые переменные из множества X.

Система функций А, А С Р2(Х и У), называется полной, если для любой функции /, / е РорО, существует формула над А указанного вида, реализующая функцию /.

Далее вводятся некоторые понятия, необходимые для формулировки результата о поведении функции Шеннона в таких базисах. Приведенным весом элемента с к входами (прямыми и итеративными), имеющего вес Ь, называется величина Ь/(к—1). Макроблоком в базисе А, А С Р2(ХиУ), называется схема из функциональных элементов в этом базисе, состоящая из элемента £, имеющего более одного итеративного входа, и элементов, имеющих только прямые входы, выходы которых подаются на итеративные входы элемента £, причем количество элементов с прямыми входами на единицу меньше числа итеративных входов элемента £. Итеративным входом макроблока считается его свободный (т. е. тот, на который не подаются выходы других элементов макроблока) входов элемента £, остальные входы макроблока считаются прямыми. Приведенным весом макроблока указанного вида называется величина, равная отношению суммарной сложности макроблока к числу его прямых входов.

Приведенным весом рл базиса А называется минимальный приведенный вес среди всех элементов с хотя бы одним итеративным входом и всех макроблоков в этом базисе.

Для рассматриваемых в диссертации моделей с ограничениями используются следующие обозначения:

• Для любого а, а ^ 2, функция Шеннона для сложности формул, глубина альтернирования которых не больше чем а, обозначается как

• Функция Шеннона для сложности формул с глубиной альтернирования не более 3, реализующих функции из класса С^г = и <2г(п)> обозначается

как Ьг(п).

• Сложность функции алгебры логики / в классе схем в базисе {&, V, ->}, ширина которых не превосходит t, определяется как минимальная сложность схемы из этого класса, реализующей функцию /. За L^(n) обозначается соответствующая функция Шеннона. Сложностью системы функций F называется минимальная сложность схем с \F\ выходами, реализующих систему F. Соответствующая сложность в классе схем с t регистрами в стандартном базисе обозначается L^ (F).

• Если А — базис, состоящий из элементов с прямыми и итеративными входами, то са(п) — функция Шеннона для сложности формул в этом базисе, определенной как сумма весов элементов этих формул.

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

• sn(:ci,..., хп) — V xixj- ' монотонная симметрическая функция с по-

1 <i<j<n

рогом 2.

• 1п = х\ ® ... ® хп, п > 2. —линейная функция порядка п, здесь символом ф обозначается сумма по модулю 2.

• Система функций = {х\ ■ ■ ■ xn-ixn, х\ ■ • • хп-\хп, ..., Х\ • • • xn-ix„}, состоящая из всех элементарных конъюнкций ранга тг от п переменных, называется дешифратором порядка п.

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

Для функции Шеннона L(o)(n) сложности формул с ограниченной глубиной альтернирования устанавливаются следующие оценки высокой степени точности, имеющие относительную погрешность вида О :

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

4 ' log72 у iOgn J

где log^z = log.. .logs, если указанный повторный логарифм определен и

а раз

неотрицателен, и log'0' х = 0 в остальных случаях.

В следующей теореме получена оценка высокой степени точности для величины Lr(n).

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

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

М. И. Гринчук доказал31, что сложность реализации функции 5П в классе схем из функциональных элементов в базисе {&,\/} без ограничений асимптотически равна 2п. Кроме того, Р. Е. Кричевским установлено32, что в классе 7г-схем (а, следовательно, и в классе формул в стандартном базисе, у которых отрицания стоят только над переменными) сложность этой функции равна • 2^™-! + ([к^тг] + 2) • (п - ~ пк^п. С. А. Ложкиным этот

результат был обобщён33 для случая 7Г-схем, в которых контакты различных переменных могут иметь различные веса.

Н. П. Редькин показал34, что сложность реализации линейной функции 1п, п ^ 2, в классе схем из функциональных элементов без ограничений равна 4п — 4. Из результатов В. М. Храпченко35 и С. В. Яблонского36 следует, что сложность этой функции в классе 7г-схем (а, следовательно, и в классе формул в {&, V, -1}, у которых отрицания стоят только над переменными) равна &(п2) . Реализовать линейную функцию порядка п при п > 2 схемой ширины 1 в базисе {&, V, -1} невозможно. Следующая теорема, в частности, показывает, что в классе схем с двумя регистрами данная функция допускает оптимальную реализацию.

Теорема 3. Для любого натурального 2, справедливы следующие соотно-

шения:

31 ГринчукМ. И. О монотонной сложности пороговых функций // Дискретный анализ. — 1992. — Вып. 52. —

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

33 Ложкин С. А. О минимальных !г-схемах для монотонных симметрических функций с порогом 2 // Дискретная математика. - 2005. - Вып. 17.4. - С. 108-110.

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

35ХрапченкоВ.М. О сложности реализации линейной функции в классе П-схем // Математические заметки.

- 1971.-Т. 9.-Й1.-С. 21-23.

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

L™(ln) = L™(ln) = 4n - 4; £{3}(sn) < 3n - 5.

С. 41-48.

При п —>■ со справедлива оценка:

L{2](sn)<n\ogn.

Следует отметить, что, как следует из результатов С. А. Ложкииа33, каждая минимальная формула для функции sn имеет глубину альтернирования 3 и сложность, асимптотически равную п log п, и, следовательно, может быть представлена схемой с 3 регистрами. Приведенная теорема устанавливает возможность реализации этой функции схемой линейной сложности с тремя регистрами, а также схемой с двумя регистрами со сложностью, асимптотически минимальной для случая формул — n log п.

Далее приводится результат о сложности реализации дешифратора в схемах ширины 2 и 3.

Теорема 4. При п —> оо справедливы следующие оценки:

£{3}Й„) ~ 2", ЬЮ($п)=в( 2").

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

Вторая глава посвящена формулам в базисах из элементов с прямыми и итеративными входами.

Пусть А С Р2(Х U Y). Множество тех функций, которые можно получить из функций системы А в результате применения операций суперпозиции с номерами из множества Т',Т С Т = {1,2,3,4,5,6}, обозначим через [Л]х', и пусть [А)т — [Л]. В работе С. А. Ложкина25 введено обозначение ¿(А) = [[А](2} П • В диссертации это множество называется ите-

ративным замыканием множества А. Множество <5(Л) является «обычным» замкнутым классом в P2{Y), содержащим все константы, и поэтому совпадает с одним из классов системы Д = {B,I,0,D,K,L,M,P2(Y)}, где В = {0,1}, I = YU В, О = IU {у : у 6 Y}, класс D (класс К) содержит константы и дизъюнкции (соответственно, конъюнкции) переменных Y, а классы L и М состоят из линейных и монотонных функций от переменных Y соответственно. В первой теореме второй главы для оператора 6 приводится более наглядное представление:

Теорема 5. Для любой системы функций А, А С P2(XUY), справедливо равенство

5(A) = [А] П P2{Y).

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

Теорема 6. Для любой системы функций А, А С Р2(ХиУ), такой, что 6(А) € {М, Р2(У)}, при п —> оо справедливо соотношение

2 п

£а(п) ~ ра • ;-•

Для каждого 6, 8 е {/, О, Д К, Ь}, существует базис А такой, что 5(А) = 6 и при этом

£л(тг) = 9(2").

В некоторых базисах А, таких, что 5(А) = Г> и ЬЛ(п) = 6(2"), самой сложной функцией является линейная функция 1п = Х\ © ... 0 хп, однако, как показывает следующий результат, при переходе от базиса к базису сложность функции 1п может кардинально изменяться в рамках одного и того же семейства.

Теорема 7. В базисе Ах = {(ях ф х2)уи {Х1 © х2 © 1)2/1,2/1 V 2/2} сложность линейной функции 1п удовлетворяет соотношению

ЬМ{1П) = в(2"/2),

а в базисах А2 = {(ях 0 х2)уиУ1 V у2} и А3 = {(жх 0 х2 © 1)уъУг V 2/2 } -соотношению

Сх • 2"/2 < ЬА,(1п) < с2 ■ 3ПЛ г'— 1,2,

где Сх, с2 — некоторые положительные константы.

Итеративное замыкание каждого из указанных в теореме базисов образует класс

В теореме 6 получена асимптотика функции Шеннона для случая тех базисов А, для которых ¿(Л) Э М. Для некоторых классов таких базисов в следующих теоремах установлены асимптотические оценки высокой степени точности. Для каждого базиса А, А С Р2(ХиУ), через А обозначается множество тех элементов базиса А с итеративными входами, которые либо имеют приведенный вес, равный ра, либо входят в макроблоки этого базиса с приведенным весом рл-

Теорема 8. Пусть А, А С Р2(Х и У), — конечный полный базис, такой, что 5{А) Э М. Пусть, далее, справедливо хотя бы одно из следующих утверждений:

1. 5{А) Э М;

2. базис А является полным базисом;

3. О (А) е {Ь, Д К}, множество [А]{1д4} содержит функцию / вида

/ = (<Л ° 2/1) о • • • о (</>к 0 Ук) о Уо,

гдец>о,ч>1,...,ч>к € Р2(Х), (о,о) е V), (V,&), (&,9)}, для которой найдутся такие индексы 32 € {1, • • •, 31 ф п, и наборы а, /3 значений прямых переменных, что

ыа) = ч>ь{р) = = =

Тогда при растущем значении натурального аргумента п, п > 2, справедливо соотношение „ „ л/-иЧЧ

г ( \ п 2 Л 4-0

= Ра ■ \- 1 ± ч-i •

4 ' к^тг \ 1о g7г/

Заключительная теорема демонстр1фует другое поведение остаточного члена в оценках высокой степени точности для функции Шеннона сложности формул рассматриваемого класса. Итеративное замыкание приведённых в ней базисов равно Р2(У).

Теорема 9. Пусть

Бх = {ш •.. ■ • уь,ъ V... V хк2,т}; Б2 = {У1 V ... V УЬ, XI ■... ■ хк2, т};

где ки к2 > 2. Тогда для г = 1, 2 имеют место следующие неравенства:

2™ / ^^тг±0(1)

2" / ¿1о§1о8п±0(1)\ 2"

^ + Ь8п.-) < £*(П) < I1 ' 1о8»

Если при этом минимальный приведенный вес базиса Б¡, г € {1,2}, достигается на макроблоке, отличном от элемента, то справедливо соотношение:

( ¿1о8Ь8п±0(1)\

£«(п) ='«ЙЕ^1 +-¡5^-

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

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

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

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

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

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

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

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

Напечатано с готового оригинал-макета

Подписано в печать 29.06.2015 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 65 экз. Заказ 142.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.