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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

01.Q1.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертаций на соискание учёной степени кандидата физико-математических наук

МОСКВА - 2011

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

Научйый руководитель доктор физико-математических наук,

профессор

Гасгжов Зль&р Эльд&ровкч

Официальные оишжешък доктор физико-математических каух,

профессор

Гапжов Сергей Борисович

кандидат физико-математических наук Зайцев Денис Владзшшгровзгч

Ведущан организация РГГУ, Российский государственный

гуманитарный университет

Защита диссертации состоится 8 апреля 2011 г. в 16 ч. 45 м. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете им. М. В .Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ имени М.В. Ломоносова (Глазное здание, 14 зта>:<).

Автореферат разослан 4 марта 2011 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор

А.О.Иванов

РОССИЙСКАЯ ГОСУДАРСТВЕННАЯ БИБЛИОТЕКА 2011

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

Хронологически первой и наиболее исследованной мерой сложности схем является количество базисных элементов схемы. Зта мера сложности (будем называть ее объемной) характеризует размеры схемы при физическом синтезе, или на объем памяти, необходимый для хранения алгоритма или программы на компьютере. Для объемной сложности О. Б. Лупанс-вым1 получены асимптотически окончательные результаты для различных классов схем и базисов.

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

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

'Лу паков О. Б. О синтезе некоторых хлесгоз управляющих систем // Проблемы кибернетика. — 1863. - Т. 10

аЛупакоз 0.3. О схзмах из функциональных элэмгктоэ с задержками // Проблемы ккбгрнзтикй. — 1070. - Т. 23. - С. 73-97

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

С целью исследования мощностных свойств схем вводится мощностная мера сложности схемы, которая характеризуется количеством активизированных базисных элементов при вычислении значения функции. Исследования мощностной меры сложности также проводились, однако значительно уже, чем исследования объемной сложности. Для схем из функциональных элементов основные результаты были получены М. Н. Вайнцвайгом3 и О. М. Касим-Заде4. В частности, ими для некоторых базисов получен линейный порядок функции Шеннона мощностной сложности схем из функциональных элементов.

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

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

Заметим, что вопрос эффективности моделирования для схем из функциональных элементов также рассматривался в литературе. А. В. Чаш-кин0 рассматривал программную реализацию схем из функциональных

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

4Кваш-Заде О. М. Об одаой маре сложности схем из функциональных элементов // Проблемы

кибернетики. - 1981. - Т. 38. - С. 117-179

6ГЬсанозз Э. 3., Кудрявцев В. Б. Теория хранения к поиске информации. — Физметлкт, 2002 вЧашкин А. В. О среднем времени вычислений значений булззых функций // Дкскрзтн. анализ я

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

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

Теперь более подробно остановимся на существующих результатах в области сложности управляющих систем. Начнем с объемной сложности.

Для схем из функциональных элементов б полном базисе О. Б. Лупановым получено асимптотически оптимальное решение, найдена асимптотика функции Шеннона Ь$(п) ~ п —со.

Для контактных и контактно-вентильных схем также получено асимптотически оптимальное решение Ьв(п) ~ Ьк(п) ^ п со.

Для параллельно-последовательных схем, а также для формул над базисом V, —»}• получена асимптотическая оценка сложности Ь^п) ~

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

Для взвешенных схем из функциональных элементов также получен асимптотически точный результат (га) ~ где рв — наименьший

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

Для схем из функциональных элементов В&йкцвайгом и Касим-Заде

исслзд. опер. — 1997. — Т. 4, И» 1. — С. 60-78

7Лупаяов О. В. Об одном метода синтеза схем // Известия ВУЗов. Радиофизика. — 1858. — Т. 1, № 1. - С. 120-140

рассматривалась такая мера сложности, как мощность схемы Е(8), которая характеризует среднее число элементов с единицей на выходе, что в каком-то смысле соответствует степени нагревания физической схемы.

М. Н. Вайкцвайгом были получены оценки мощности схем из функциональных элементов для различных базисов, а именно, для базиса В\ = {&, V,-»} получен порядок функции Шеннона Евх(п) х п, для базиса 32 = {'} также получен порядок функции Шеннона Ев3{п) ж а для базиса Дз = {V, -1} получена оценка 2а < Ев3{п) <

О. М. Касим-Заде получил более полную картину зависимости роста функции Шеннона от свойств базиса, а также построил метод синтеза, одновременно асимптотически оптимальный по объему и оптимальный по порядку по мощности схем, для которого £(5) < а Е(3) < 4п8.

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

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

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

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

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

Для задержки схемы получен асимптотически точный результат Т®(п) ~ гп, где т — наименьшая приведенная задержка базисного элемента.

8Квгаш-Звде О. М. Об одновременной мипкмкзацки сложности и мощности схем нз функциональных элементов // Проблемы ки&зркетики. — 1978. — Т. 33. — С. 215-220

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

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

Что касается класса контактных схем, для них нестандартные меры сложности рассматривались лишь в некоторых частных случаях. Был разработан такой класс управляющих систем как класс бинарных диаграмм решений (BDD, Binary Decision Diagrams) или ветвящихся программ (BP, Branching Programs), который изначально предназначался для реализации булевых функций ка компьютере, а не для физического синтеза. Этот способ реализации булевых функций получил большее распространение на западе, нежели в России. Впервые BBD были введены С. Ли®, но стали широко известны позже с работой С. Акерса10.

И. Брейтбарт с соавторами11 получили асимптотическую оценку для объемной сложности бинарных диаграмм решений Lbdd&) ~ ti —> со. Также было введено понятие времени отклика бинарной диаграммы решений Tqdd{D), которое задается максимальным количеством шагов, необходимых для получения значения булевой функции на произвольном входном наборе с помощью этой диаграммы, и для описанной меры сложности была получена асимптотика Tbdd{w) ~ п со.

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

В диссертации исследуется способ моделирования контактных и

"Leo С. Y. Rapriasntatiaa of switching circuits by binary-decision programa // Вг11 Systems Technical Journal. — 1959. — Vol. 38. — Pp. 886-9SB

10Aksrs S. B. Binary decision diagrams // I3EE Transactions on Computéis. — 1978. — Vol. C-27, no. 6. - Pp. 503-516

"Breitbart Y., Kuat H., Rosoakrants D. Oa ths sizs of blnaay decision diagrams repr&aaniiss boclsaa functions // Theoretical Computer Scisnca. — 1895. — Vol. 145, no. 1-2. — Pp. 45 - S3

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

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

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

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

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

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

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

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

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

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

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

Для получения отдельных результатов используются следующие методы.

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

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

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

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

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

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

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

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

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

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

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

Конференция «Интеллектуальные системы и компьютерные науки» (2006, Москва).

Конференция студентов, аспирантов и молодых ученых мех-мат. ф-та МГУ (2007, 2008, Москва).

Девятый международный семинар «Дискретная математика и ее приложения», посвященный 75-летию со дня рождения академика О. Б. Лупа-нова (2007, Москва).

Конференция «Ломоносовские чтения» (2007, 2009, 2010, Москва).

Пятая Всемирная конференция «Интеллектуальные системы для индустриальной автоматизации» (>УС18-2008, Ташкент, Узбекистан).

Международная конференция «Современные проблемы математики, механики и их приложений», посвященная 70-летию академика В.А.Садовничего (2009, Москва).

Международная конференция студентов, аспирантов и молодых ученых «Ломоносов-2009» (2С09, Москва). Доклад отмечен грамотой.

Международный семинар «Дискретная математикаг-2010» (2010, Москва).

Международная конференция студентов, аспирантов и молодых ученых «Ломоносов-2010» (2010, Москва). Победитель конференции.

Шестая международная конференция «Интеллектуальные системы для промышленной автоматизации» (ШС18-2010, Ташкент, Узбекистан).

Также результаты докладывались на семинарах механико-математического факультета МГУ им. М.В.Ломокосоза: на семинаре «Теория автоматов» под руководством академика, проф., д.ф-м.и. В.В. Кудрявцева (2008-2010 г.), на семинаре «Вопросы сложности алгоритмов поиска» под руководством проф., д.ф-м.н. Э.Э.Гасанова (2006-2010 гг.).

ПублЕзкащии. По теме диссертации опубликованы 4 печатных работ в

научных журналах, а также несколько коротких докладов в тезисах конференций.

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

Основные понятия

Ниже приводятся основные понятия, используемые в работе.

Булевыми функциями (б. ф.) будем называть функции вида / {0,1}п —> {О, I}, и будем рассматривать их с точностью до несущественных переменных.

Контактной (вентильной) схемой называется неориентированная (ориентированная) сеть (т. е. связный неориентированный (ориентированный) граф с выделенными вершинами — полюсами), каждому ребру которой приписана некоторая булева переменная с отрицанием или без него. Ребро вместе с приписанной ему переменкой называется контактом (вентилем) переменной х, а точнее, замыкающим контактом (вентилем)^ если а = 1, и размыкающим контактом (вентилем), если (7 — 0. Контакт (вентиль) ха считается зоилшутым, когда х° — 1, и разо-мкнутшл, когда ха — 0. Если контакт (вентиль) х\ замкнут на наборе а = (й1, ..., ап), т. е. а? = 1, то говорим, что он проводит набор а.

Путем в вентильной схеме называем ориентированную цепь. Путем в контактной схеме называем цепь.

По определению, путь контактной (вентильной) схемы проводит набор а тогда и только тогда, когда все его контакты (вентили) проводят этот набор.

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

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

Один из полюсов схемы выделяется как входной полюс, остальные полюса считаются выходными.

Говорим, что схема реализует функцию, равную дизъюнкции проводк-мостей между входным и всеми выходными полюсами. Эта функция назы-

вается проводимостью схемы.

Схема, имеющая структуру (ориентированного) дерева, в котором входной полюс является корнем, а все выходные полюса — листовыми вершинами дерева, называется древовидной схемой.

Объемной сложностью контактной (вентильной) схемы 3 называется число контактов (вентилей) в этой схеме. Обозначаем Ь{8).

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

Заметим, что если вентильная схема 3 реализует некоторую функцию /, то контактная схема К(8) реализует функцию д) которая, возможно, отличается от /.

Пусть контактная (вентильная) схема 3 реализует булеву функцию /. Моделью схемы 3 будем называть алгоритм, вычисляющий значение функции / на произвольном входном наборе а из области определения функции /•

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

Объемной сложностью б. ф. / (или сложностью реализации б. ф. / вентильными схемами) назовем следующую величину.

где Н(/) — множество всех вентильных схем, реализующих функцию /.

Функцией Шеннона сложности реализации булевых функций вентильными схемами назовем величину

Ь(п) = шах £/(/).

/6-Рз

Информационным графом для вентильной схемы 3 (обозначаем 0(3)) будем называть модель схемы 3} определенную на структуре схемы следующим образом.

Входной полюс вентильной схемы будем называть корнем информационного графа. Выходные полюса будем называть концевыми вершинами информационного графа.

Вершины и ребра вентильной схемы 3 будем называть соответственно вершинами и ребрами информационного графа 0(3).

Определим функционирование информационного графа 0(3) для некоторой схемы 5.

Пусть дан некоторый набор а.

Сначала корень информационного графа добавляется в множество активных вершин А.

Далее, для каждой вершины v из множества А, для каждого ребра е, выходящего из вершины v, вычисляется значение переменной, приписанной ребру е, на наборе а. Если значение переменной равно 1 на этом наборе, и вершина, в которую ведет ребро е, не помечена как посещенная, то эта вершина добавляется в множество А. Когда для всех исходящих из v ребер процедура выполнена, вершина v помечается как посещенная.

Если после завершения работы алгоритма хотя бы одна концевая вершина информационного графа оказалась посещенной, то считаем, что информационный граф выдает значение 1. Иначе считаем, что он выдает значение 0.

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

Очевидно, что информационных граф G(S) выдает значение 1 в точности на тех наборах, на которых функция /, реализуемая вентильной схемой S, равна 1. Говорим, что информационный граф G(S) реализует функцию /•

Пусть F = {/i, /2,...} — некоторое (возможно, бесконечное) множество булевых функций.

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

Базовое множество F называется ИГ-полным в классе булевых функций А, если для любой булевой функции / € А существует информационный граф с базовым множеством i7, реализующий функцию /.

Функции, приписанные ребрам информационного графа, будем также называть предикатами.

Считается, что ребро графа проводит набор а, если значение функции, приписанной этому ребру, на наборе а равно 1.

Таким образом, информационный граф для вентильной или контактной схемы — это информационный граф с базовым множеством {х1,Ё1,Х2,Х2г' • • }• Такое базовое множество будем обозначать Fq е называть простым базовым множеством.

Очевидно, что оно является полным в классе всех булевых функций.

Древовидный информационный граф будем называть также информационным деревом.

Понятия проводимости и достижимости в информационном графе аналогичны соответствующим понятиям для схем.

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

Вершину У2 называем достижимой кз вершины если существует проводимый путь, соединяющий вершины У\ и г^. Вершина V называется достижимой, если она сильно достижима из корня г>о-

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

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

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

Количество элементарных функций из множества Е, вычисленных на наборе а в информационном графе О обозначим через Т(0,а).

Легко проверить, что

Т(С1а)= ]Г

геб„0(а)

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

Величина Т(£?, а) называется сложностью информационного графа С на наборе а. Здесь и далее, если не сказано обратное, под сложностью информационного графа понимаем временную сложность, а под сложностью контактной или вентильной схемы понимаем объемную сложность.

Пусть на множестве наборов введено вероятностное пространство ({0,1}п,с,Р), где <7 — множество всех подмножеств булева куба {О,!}71, а Р — вероятностная мера на этом множестве. Сложностью информационного графа назовем величину

т(0)= ]Г Т(0, а)Р(о),

ае{0,1}"

где Р(а) — вероятность набора а в данном вероятностном пространстве.

Вероятностью ребра назовем вероятность прохождения набора в вершину, из которой это ребро выходит. Это есть вероятность, с которой это

ребро вычисляется. Эту величину также будем называть сложностью ребра.

Далее будем по умолчанию считать, что распределение наборов равномерное, то есть вероятности появления всех наборов равны.

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

T(S) = T(G(S)).

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

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

Пусть V{K) — множество вентильных схем S € О (К), которые реализуют ту же самую булеву функцию, что и К.

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

Т(К) = mm T(S),

причем считаем, что Т(К) = со, если V{K) = 0.

Сложностью реализации б. ф. / информационными графами с базовым множеством F (временной сложностью) называется следующая величина.

Т(/, F) = in£ T(G),

где Q(f, F) — множество информационных графов с базовым множеством F, реализующих функцию /.

В работе показано, что нижняя грань в определении сложности достигается, то есть для любого F в £?(/, F) существует информационный граф, сложность которого в точности равна временной сложности функции /. Такие графы будем называть оптимальными для функции / и говорить, что они реализуют функцию / оптимально.

Для произвольного класса булевых функций А через Л^ будем обозначать класс функций / € Л, зависящих от п переменных. Так, Р^ будет обозначать класс всех n-местных булевых функций.

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

T(n,F)= m exT(ftF).

feP¡n)

Если не сказано обратное, через Т(/) и Т(п) будем обозначать соответственно величины Г(/, и Т(п,Р\Ь).

Под объемной сложностью информационного графа будем понимать количество его ребер.

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

где 2>(/, Р) — множество всех древовидных информационных графов с базовым множеством F

Аналогично информационным графам вводятся величины ТЬ(?г, Р),

тыл, гь(п).

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

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

Теорема 1. Для любого п выполнено

Т(п) = 2п - 1.

Теорема 2. Для почти всех б. ф. f(xi,..., 6 Рг выполнено

T(f) ~ 2n, п со.

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

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

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

Теорема 3. Существует метод синтеза, который каждой б. ф. f ставит в соответствие вентильную и контактную схемы 3(f) и К(3(f)),

реализующие эту функцию, причем для почти всех /(sj,..., хп) € Рг выполнено

2

L{S(f)) г--, пн> со,

71

Т(5(/)) ~ те -)> оо.

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

В главе 3 приводятся оценки временной сложности для различных классов Поста12.

Теорема 4. При п оо выполнено

класс С функция Шеннона П. 8. f{xl,...,Xn) I

Т{С, п) ~ 271 T{f) ~ 2п

А\, Ä2, Аз, A4, Dz п<Т{С,п)<2п Ц<Т(Л<2п i

Ff.Ff.F^Ff Т(С,п)~п Т(/) ~ п |

Ff, Ff, Fp,Fg° %<Т{С,п)<п §^Г(/)<п !

п<Т{С,п)<2п %<T{f)<2n

Fi, Fl Ff, Fi %<Т{С,п)<2п %<T{f)<2n

F^F^F^F^ M = 2,3,... \n<T{C)n)<2n T{f) ~ n

F£,F£,Ff,F£, ix = 2,3,... |f <T(C,n)<2n i<TU)<n 1

класс ö точная оценка сложности б. ф. / 6 С

Irl, L2,1/3, £4, L5 Т(/) = 2п — 1, п > 1 — число сущ. переменных /

PhPz,P5,PQ Т(/) = 2 — п — число сущ. переменных /

SuSbSbSs Т(/) = 4 — 2~"+а, тг > 2 — число сущ. переменных /

O* Т(/) — п, п — число сущ. переменных 1(0 либо 1)

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

Пусть = ...} — монотонный базис. Информационный граф

с базовым множеством называется монотонным информационным графом.

:аО5о0ыьчэния хлвссоэ прявздены согласно реботз: Яблексхий С. В., Гаврняоз Г. Н., Кудрявцев В. В. ©уккции алгебры логика и классы Поста. — М.: Науке., 19*53

Теорема 5. При га —* со выполнено

1оё2Т(п,^м)~(Ьё23-!)п. Теорема 6. Для почти всех /(^ь..., хп) £ М при п со выполнено

2»,

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

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

п

8Т = {Д /л(а1,... ,ап) = 1 -фф ^а* > Л}. Для функций из этого класса

1=1

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

Теорема 7. Для любой /л(я1,... ,гп) е ЭТ при к < п -л со выполнено

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

В главе 5 рассматривается проблема самокорректирования информационных графов.

Через Т(а, 6, /) обозначаем сложность реализации б. ф. / с помощью информационных графов с простым базовым множеством, исправляющих не более а замыканий и Ь размыканий.

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

Т(с, 6, п) = тах Т(а, Ъ, /). /6р2{п)

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

Теорема 8. Для любого п выполнено

^(а + 1)(Ь 4- < Т{а, Ь, п) < 2{а + 1)(Ь + 1)п.

А

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

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

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

Публикации автора по теме диссертации в научных журналах (в хронологическом порядке):

1. Шуткин Ю. С. Синтез информационных графов для предполных классов булевых функций // Интеллектуальные системы. - 2007. - Т. 11, № 1-4. - С. 733 - 746.

2. Шуткин Ю. С. О реализации булевых функций информационными графами // Дискретная математика. - 2008. - Т. 20, № 4. - С. 31 - 41.

3. Шуткин Ю. С. Реализация монотонных булевых функций монотонными информационными графами // Интеллектуальные системы. - 2003. - Т. 13, № 1-4. - С. 491 - 522.

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

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

5. Шуткин Ю.С. Реализация булевых функций с помощью информационных графов. Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, 23-27 октября 2006 г.), том 1, часть 1, с. 323-326.

6. Шуткин Ю.С. О реализации булевых функций информационными графами. Материалы IX Международного семинара «Дискретная матемаг тика и ее приложения», посвященного 75-летию со дня рождения академика О.Б.Лупанова (Москва, 18-23 июня 2007 г.), с. 147-149.

7. Шуткин Ю.С. Временная сложность реализации булевых функций // Международная конференция «Современные проблемы математики, механики и их приложений», посвященная 70-летию ректора МГУ академика В.А.Садовничего (30 марта - 2 апреля 2009 г., Москва). Материалы конференции. С. 381.

8. Шуткин Ю.С. Сложность реализации некоторых классов Поста информационными графами с монотонным базовым множеством // Сборник тезисов XVI Международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2009», секция «Математика и механика» (Москва, 13-18 апреля 2009). С. 74.

9. Шуткин Ю.С. Оценки временной сложности самокорректирующихся информационных графов. Материалы Международного семинара «Дискретная математика» (Москва, 1-5 февраля 2010 г.). 465-467.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж 10@ экз. Заказ № /X"

2010198668

2010198668

Введение

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

2 Основные понятия.

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

1 Асимптотика сложности реализации булевых функций информационными графами

1.1 Общие утверждения.

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

1.3 Нижняя оценка.

2 Одновременная минимизация объемной и временной сложности

2.1 Верхняя оценка.

3 Классы Поста

3.1 Общие утверждения.^.

3.2 Предполные классы.

3.3 Замкнутые классы Поста.

4 Монотонный базис

4.1 Нижние оценки сложности.

4.2 Реализация пороговых функций.

4.3 Реализация произвольной монотонной булевой функции

4.4 Оценки сложности для почти всех монотонных булевых функций

5 Синтез самокорректирующихся информационных графов

Введение

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

Актуальность темы. Понятие управляющей системы является одним из центральных понятий в кибернетике [19]. Наиболее исследованными классами управляющих систем являются схемы из функциональных элементов, контактные и контактно-вентильные схемы, формулы, автоматы и др. Одной из основных задач теории управляющих систем является задача синтеза. Она состоит в следующем. Дан набор некоторых базисных элементов (например, контактов, вентилей, функциональных элементов, подпрограмм, формул и т.д.), также заданы правила построения из данных элементов более сложных систем (схем) и способ определения по схеме реализуемой функции. Далее вводится понятие сложности схемы. Задача состоит в получении для каждой функции схемы, реализующей эту функцию, причем имеющую по возможности наименьшую сложность. Чтобы оценить эффективность построенной схемы вводится понятие функции Шеннона [18], характеризующей минимальную сложность схемы, необходимую для реализации произвольной функции, зависящей от заданного числа переменных. Одними из основных задач синтеза управляющих систем являются задача построения эффективного метода синтеза, позволяющего для произвольной функции построить схему, по сложности меньшую или близкую к функции Шеннона, а также задача получения по возможности наиболее точных оценок функции Шеннона.

Хронологически первой и наиболее исследованной мерой сложности схем является количество базисных элементов схемы. Эта мера сложности (будем называть ее объемной) характеризует размеры схемы при физическом синтезе, или на объем памяти, необходимый для хранения алгоритма или программы на компьютере. Для объемной сложности О. Б. Лупановым [12] получены асимптотически окончательные результаты для различных классов схем и базисов.

Наряду с объемом также рассматривались другие характеристики схем, такие как глубина схем из функциональных элементов [4,13] и задержка [13, 16].

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

С целью исследования мощностных свойств схем вводится мощностная мера сложности схемы, которая характеризуется количеством активизированных базисных элементов при вычислении значения функции. Исследования мощностной меры сложности также проводились, однако значительно уже, чем исследования объемной сложности. Для схем из функциональных элементов основные результаты были получены М. Н. Вайнцвайгом [2] и О. М. Касим-Заде [6]. В частности, ими для некоторых базисов получен линейный порядок функции Шеннона мощностной сложности схем из функциональных элементов.

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

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

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

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

Теперь более подробно остановимся на существующих результатах в области сложности управляющих систем. Начнем с объемной сложности.

Для схем из функциональных элементов в полном базисе {&, V, ->} О. Б. Лупановым получено асимптотически оптимальное решение, найдена асимптотика функции Шеннона Ьф(п) ~ п —оо.

Для контактных и контактно-вентильных схем также получено асимптотически оптимальное решение Ьв(п) ~ Ьк(п) ~ п —> со.

Для параллельно-последовательных схем, а также для формул над базисом получена асимптотическая оценка сложности Ьж(п) ~

Все вышеописанные результаты приведены в [12].

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

Для взвешенных схем из функциональных элементов также получен асимптотически точный результат Щ{п) ~ рвгде рв — наименьший приведенный вес базисного элемента в конечном базисе В [11]. Заметим, что если положить вес каждого элемента в базисе равным 1, то приведенны результат дает также оценку функции Шеннона объемной сложности для произвольного конечного полного базиса.

Для схем из функциональных элементов была рассмотрена такая мера сложности, как мощность схемы E(S) [2,6], которая характеризует среднее число элементов с единицей на выходе, что в каком-то смысле соответствует степени нагревания физической схемы.

М. Н. Вайнцвайгом в работе [2] были получены оценки мощности схем из функциональных элементов для различных базисов, а именно, для базиса {&, V, -■} получен порядок функции Шеннона Ев^п) х п, для базиса В2 = {'} также получен порядок функции Шеннона Ев2{п) х а для базиса В3 = {V, -«} получена оценка 2f < Ев3(п) < \/п2%.

О. М. Касим-Заде получил более полную картину зависимости роста функции Шеннона от свойств базиса в [6], а также построил метод синтеза, одновременно асимптотически оптимальный по объему и оптимальный по порядку по мощности схем, для которого Ь(Б) < а Е^Б) < 4п [5].

Также для управляющих схем вводились и другие меры сложности, основанные на их физических особенностях (глубина, задержка и т. д.) [4,13,16].

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

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

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

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

Для задержки схемы получен асимптотически точный результат Тф(п) ~ тп, где т — наименьшая приведенная задержка базисного элемента [13].

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

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

Что касается класса контактных схем, для них нестандартные меры сложности рассматривались лишь в некоторых частных случаях. Был разработан такой класс управляющих систем как класс бинарных диаграмм решений (BDD, Binary Decision Diagrams) или ветвящихся программ (BP, Branching Programs), который изначально предназначался для реализации булевых функций на компьютере, а не для физического синтеза. Этот способ реализации булевых функций получил большее распространение на западе, нежели в России. Впервые BBD были введены С. Ли в [23], но стали широко известны позже с работой С. Акерса [21].

И. Брейтбарт с соавторами в [22] получили асимптотическую оценку для объемной сложности бинарных диаграмм решений lbdd(p) ~ п ~<► Также было введено понятие времени отклика бинарной диаграммы решений Tbdd{D), которое задается максимальным количеством шагов, необходимых для получения значения булевой функции на произвольном входном наборе с помощью этой диаграммы, и для описанной меры сложности была получена асимптотика tbdd{^) ~ п, п -> оо.

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

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

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

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

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

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

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

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

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

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

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

Для получения отдельных результатов используются следующие методы.

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

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

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

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

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

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

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

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

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

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

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

Конференция «Интеллектуальные системы и компьютерные науки» (2006, Москва).

Конференция студентов, аспирантов и молодых ученых мех-мат. ф-та МГУ (2007, 2008, Москва).

Девятый международный семинар «Дискретная математика и ее приложения», посвященный 75-летию со дня рождения академика О. Б. Лупанова (2007, Москва).

Конференция «Ломоносовские чтения» (2007, 2009, 2010, Москва).

Пятая Всемирная конференция «Интеллектуальные системы для индустриальной автоматизации» (\УС18-2008, Ташкент, Узбекистан).

Международная конференция «Современные проблемы математики, механики и их приложений», посвященная 70-летию академика В.А.Садовничего (2009, Москва).

Международная конференция студентов, аспирантов и молодых ученых «Ломоносов-2009» (2009, Москва). Доклад отмечен грамотой.

Международный семинар «Дискретная математика-2010» (2010, Москва).

Международная конференция студентов, аспирантов и молодых ученых «Ломоносов-2010» (2010, Москва). Победитель конференции.

Шестая международная конференция «Интеллектуальные системы для промышленной автоматизации» (\¥С18-2010, Ташкент, Узбекистан).

Также результаты докладывались на семинарах механико-математического факультета МГУ им. М.В.Ломоносова: на семинаре «Теория автоматов» под руководством академика, проф., д.ф-м.н. В.Б. Кудрявцева (2008-2010 г.), на семинаре «Вопросы сложности алгоритмов поиска» под руководством проф., д.ф-м.н. Э.Э.Гасанова (2006-2010 гг.).

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

Структура и объем работы. Диссертация состоит из введения и пяти глав. Объем диссертации 97 стр. Список литературы содержит 24 наименования.

1. Андреев А. Е. Универсальным принцип самокорректирования // Математический сборник. — 1985. — Т. 127(169), № 2. — С. 147-172.

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

3. Ратное Э. Э., Кудрявцев В. Б. Теория хранения и поиска информации. — Физматлит, 2002.

4. Гашков С. Б. О глубине булевых функций // Проблемы кибернетики. — 1978. Т. 34. - С. 265-268.

5. Касим-Заде О. М. Об одновременной минимизации сложности и мощности схем из функциональных элементов // Проблемы кибернетики. — 1978. Т. 33. - С. 215-220.

6. Касим-Заде О. М. Об одной мере сложности схем из функциональных элементов // Проблемы кибернетики. — 1981. — Т. 38. — С. 117-179.

7. Коршунов А. Д. О числе монотонных булевых функций // Проблемы кибернетики. — 1981. — Т. 38.

8. Коршунов А. Д. О мощности и структуре некоторых замкнутых классов поста // ДАН СССР. 1987. - Т. 295, № 3. - С. 533-537.

9. Кудрявцев В. Б., Гасанов Э. Э. Теория тестирования логических устройств. — Физматлит, 2006.

10. Лупанов О. Б. О вентильных и контактно-вентильных схемах // ДАН СССР. 1956. - Т. 111, № 6. - С. 1171-1174.

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

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

13. Лупанов О. Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики. — 1970. — Т. 23. — С. 73-97.

14. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. — МГУ, 1984.

15. Потапов Ю. Г., Яблонский С. В. О синтезе самокорректирующихся контактных схем // ДАН СССР. 1960. - Т. 134, № 3. - С. 544-547.

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

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

18. Шеннон К. Работы по теории информации и кибернетике. — ИЛ, 1963.

19. Яблонский С. В. Основные понятия кибернетики // Проблемы кибернетики. — 1959. — Т. 2. — С. 7-38.

20. Яблонский С. В., Гаврилов Г. Н., Кудрявцев В. Б. Функции алгебры логики и классы Поста. — М.: Наука, 1966.

21. Akers S. В. Binary decision diagrams // IEEE Transactions on Computers. — 1978. Vol. C-27, no. 6. — Pp. 509-516.

22. Breitbart Y., Hunt H., Rosenkrantz D. On the size of binary decision diagrams representing boolean functions // Theoretical Computer Science.— 1995. Vol. 145, no. 1-2. - Pp. 45 - 69.

23. Lee C. Y. Representation of switching circuits by binary-decision programs // Bell Systems Technical Journal — 1959. — Vol. 38. — Pp. 985-999.

24. Post E. Two-valued iterative systems of mathematical logic.— Princeton, 1941.Публикации автора по теме диссертацииПубликации автора по теме диссертации в научных журналах (в хронологическом порядке):

25. Шуткин Ю. С. Синтез информационных графов для предполных классов булевых функций // Интеллектуальные системы. 2007. - Т. 11, № 1-4. - С. 733 - 746.

26. Шуткин Ю. С. О реализации булевых функций информационными графами // Дискретная математика. 2008. - Т. 20, № 4. - С. 31 - 41.

27. Шуткин Ю. С. Реализация монотонных булевых функций монотонными информационными графами // Интеллектуальные системы. 2009. -Т. 13, № 1-4. - С. 491 - 522.

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

29. Шуткин Ю.С. Реализация булевых функций с помощью информационных графов. Материалы IX Международной конференции «Интеллектуальные системы и компьютерные науки» (Москва, 23-27 октября 2006 г.), том 1, часть 1, с. 323-326.

30. Шуткин Ю.С. О реализации булевых функций информационными графами. Материалы IX Международного семинара «Дискретная математика и ее приложения», посвященного 75-летию со дня рождения академика О.Б.Лупанова (Москва, 18-23 июня 2007 г.), с. 147-149.

31. Шуткин Ю.С. Оценки временной сложности самокорректирующихся информационных графов. Материалы Международного семинара «Дискретная математика» (Москва, 1-5 февраля 2010 г.). 465-467.