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

• Автор: Шуткин, Юрий Сергеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 97 с.

Оглавление
Введение

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] рассматривал программную реализацию схем из функциональных элементов с помощью неветвящихся программ и доказал экспоненциальность функции Шеннона временной сложности схем из функциональных элементов. Тогда как для временной сложности реализации контактных схем с помощью информационных графов в настоящей работе получен точный линейный результат.
Актуальность исследования времени моделирования управляющих систем

Если а і — <ту, то в подграфе СД, мы удалим 2 ребра с пометками О, ведущих из вершины уа, затем ребра с пометками Х, х^. ведущие в вершину уа, а также удалим или стянем ребро с пометкой Х{, ведущее из корня (такое обязательно есть, так как у нас вершина уа типа (г, о)*). Суммарное изменение сложности будет равно 2 — |(3 + 2 • |) = — чего не может быть.
Если же а і ф сту, то в каждом из подграфов СХг и СХг будут стянуты или удалены по 3 ребра с предикатами Х{ и ж, (одно, выходящее из корня, и 2 других, выходящих из вершины у„). Суммарное изменение сложности составит 2 — |(2 • (1 + 2 • |)) = —чего также не может быть.
Осталось рассмотреть случай, когда все индексы 1, 2,3, г, і различны.
Разложим граф б по переменной :с*. Далее два подграфа Сх°і и Сха{ разложим по переменным х и Ху соответственно. Получим граф С, изображенный на рисунке 1.6Ь. По лемме 4 этот граф эквивалентен исходному, а также его сложность ровно на 4 больше сложности исходного графа (здесь мы применили лемму 4 трижды: сначала для графа Є и переменной ж;, потом для подграфа С°і и переменной Х, и наконец для подграфа Си переменной

Рассмотрим отдельно каждый из подграфов Сх"іХі , СХ°(Х1 , и
и преобразуем их.
Преобразование подграфа СХ^Х1 изображено на рисунке 1.7.1 и уменьшает сложность на | ■ 5. Здесь и далее мы будем объединять некоторые ветки графа, идущие из корня, чтобы не загромождать рисунок. Так, например, ветка, образованная при стягивании ребра с предикатом <7і, в случае, когда (Ті — 1, объединена с основной веткой, выходящей из корня.
Преобразование подграфа изображено на рисунке 1.7.2 и уменьшает сложность на | • 2.
Преобразование подграфа С я{ а3 изображено на рисунке 1.7.3 и уменьям X]
шает сложность на 4(4 + 2 • |).
Преобразование подграфа С <>{ °3 изображено на рисунке 1.7.4 и умень-
Хі *}
шает сложность на |(2 + 2 ■ |).
Сложность полученного графа С, тем самым, удовлетворяет соотношению
Т{С) < Г(О) + 4-^(5 + 2 + 4 + 2- Ц + 2 + 2-^) = Т((7).
Далее, аналогично случаю 3, получаем справедливость неравенства (1.1).
Случай 4.5.(1. Из вершины уа первого уровня ведет два ребра в вершину Уь- Пусть ребрам, входящим в вершину уа, приписаны предикаты Х и ж2, а ребрам, выходящим из вершины уа — предикаты х°ф и хаф. Описанный граф изображен на рисунке 1.8а.
Разложим граф С по переменной хг-. Сложность графа С увеличится на 2. Случай 4-5.Ь гарантирует, что г ф 1, г ф 2.