close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
управление, вычислительная техника и информатика
Крайнюков Н.И. Пивнева С.В.
ВЫЧИСЛЕНИЕ АВТОМАТНОЙ СЛОЖНОСТИ...
УДК 004.421, 004.912
ВЫЧИСЛЕНИЕ АВТОМАТНОЙ СЛОЖНОСТИ БУЛЕВЫХ ФУНКЦИЙ
КАК ЗАДАЧА ДИСКРЕТНОЙ ОПТИМИЗАЦИИ
© 2012
Н.И. Крайнюков, кандидат технических наук, доцент кафедры
«Прикладная математика и информатика»
С.В. Пивнева, кандидат педагогических наук, доцент, доцент кафедры
«Высшая математика и математическое моделирование»
Тольяттинский государственный университет, г. Тольятти (Россия)
Ключевые слова: булевы функции; недетерминированные конечные автоматы; конечно-автоматная
сложность; дизъюнктивная нормальная форма.
ɋɅɈɀɇɈɋɌɖ
ȻɍɅȿȼɕɏ
ɎɍɇɄɐɂɃ ɂ ɋɅɈɀɇɈɋɌɖ ɄɈɇȿɑɇɕɏ
Аннотация:
Рассматривается
задача
вычисления
сложности
описания булевых функций с помощью
ɋɅɈɀɇɈɋɌɖ
ȻɍɅȿȼɕɏ
ɎɍɇɄɐɂɃ
ɂ
ɋɅɈɀɇɈɋɌɖ
ɄɈɇȿɑɇɕɏ
ȺȼɌɈɆȺɌɈȼ
дизъюнктивных нормальных форм, детерминированных конечных автоматов и упорядоченных
ȺȼɌɈɆȺɌɈȼ
ɋɥɨɠɧɨɫɬɶпримеры
ɛɭɥɟɜɵɯреализации
ɮɭɧɤɰɢɣ функций
– ɱɢɫɥɨɜɚɹ
ɯɚɪɚɤɬɟɪɢɫɬɢɤɚ
ɛɭɥɟɜɵɯ
двоичныхɛɭɥɟɜɵɯ
разрешающих
диаграмм.
Рассмотрены
тремя
способами,
ɋɥɨɠɧɨɫɬɶ
ɮɭɧɤɰɢɣ
– ɱɢɫɥɨɜɚɹ
ɯɚɪɚɤɬɟɪɢɫɬɢɤɚ ɛɭɥɟɜɵɯ
проанализирована их сложность. ɮɭɧɤɰɢɣ, ɜɵɪɚɠɚɸɳɚɹ ɬɪɭɞɧɨɫɬɶ ɢɯ ɜɵɱɢɫɥɟɧɢɹ. ȼ ɱɚɫɬɧɨɫɬɢ, ɬɚɤɨɣ
ɮɭɧɤɰɢɣ, ɜɵɪɚɠɚɸɳɚɹ ɬɪɭɞɧɨɫɬɶ ɢɯ ɜɵɱɢɫɥɟɧɢɹ.
ȼ ɱɚɫɬɧɨɫɬɢ,
ɬɚɤɨɣ
ɯɚɪɚɤɬɟɪɢɫɬɢɤɨɣ
(ɦɟɪɨɣ ɫɥɨɠɧɨɫɬɢ)
ɦɨɠɟɬ ɛɵɬɶ ɧɚɢɦɟɧɶɲɟɟ ɱɢɫɥɨ ɲɚɝɨɜ
статочное
для
вычисления данной функции в некотором
ВВЕДЕНИЕ
ɯɚɪɚɤɬɟɪɢɫɬɢɤɨɣ
(ɦɟɪɨɣ ɫɥɨɠɧɨɫɬɢ) ɦɨɠɟɬɞɨɫɬɚɬɨɱɧɨɟ
ɛɵɬɶ ɧɚɢɦɟɧɶɲɟɟ
ɱɢɫɥɨ
ɲɚɝɨɜ,
ɞɥɹ
ɜɵɱɢɫɥɟɧɢɹ
ɞɚɧɧɨɣ
ɮɭɧɤɰɢɢ
ɜ ɧɟɤɨɬɨɪɨɦ
ɤɥɚɫɫɟ ɚɥɝɨɪɢɬɦɨɜ
классе
алгоритмов,
число
функциональных
элементов,
функции применяются
во многих
областях ɤɥɚɫɫɟ ɚɥɝɨɪɢɬɦɨɜ,
ɞɨɫɬɚɬɨɱɧɨɟБулевы
ɞɥɹ ɜɵɱɢɫɥɟɧɢɹ
ɞɚɧɧɨɣ ɮɭɧɤɰɢɢ
ɜ ɧɟɤɨɬɨɪɨɦ
ɱɢɫɥɨ
ɮɭɧɤɰɢɨɧɚɥɶɧɵɯ
ɞɨɫɬɚɬɨɱɧɨɟ
ɞɥɹ ɩɨɫɬɪɨɟɧɢɹ
ɫɯɟɦɵ
достаточноеɷɥɟɦɟɧɬɨɜ,
для построения
схемы, реализующей
эту
анализа дискретных систем, информатики.
Компьютеры
ɱɢɫɥɨ ɮɭɧɤɰɢɨɧɚɥɶɧɵɯ
ɷɥɟɦɟɧɬɨɜ,
ɞɨɫɬɚɬɨɱɧɨɟ
ɞɥɹ ɷɬɭ
ɩɨɫɬɪɨɟɧɢɹ
ɫɯɟɦɵ,
функцию,
количество
переменных
в ее конъюнктивных
строятся на аппаратном
обеспечении,
в основе
которого
ɪɟɚɥɢɡɭɸɳɟɣ
ɮɭɧɤɰɢɸ,
ɤɨɥɢɱɟɫɬɜɨ
ɩɟɪɟɦɟɧɧɵɯ
ɜ ɟɟ ɤɨɧɴɸɧɤɬɢɜɧɵɯ ɢɥɢ
ɪɟɚɥɢɡɭɸɳɟɣ
ɮɭɧɤɰɢɸ,
ɤɨɥɢɱɟɫɬɜɨ
ɩɟɪɟɦɟɧɧɵɯ
ɜ ɟɟ
ɢɥɢ членах, количество
илиɱɥɟɧɚɯ,
дизъюнктивных
элементарных
лежит ɷɬɭ
булева
алгебра –
тип алгебры,
в которой
все
пе-ɤɨɧɴɸɧɤɬɢɜɧɵɯ
ɞɢɡɴɸɧɤɬɢɜɧɵɯ
ɤɨɥɢɱɟɫɬɜɨ
ɷɥɟɦɟɧɬɚɪɧɵɯ
ɤɨɧɴɸɧɤɰɢɣ
в дизъюнктивной
нормальной форме.
ременные могут
принимать
только два значения:
0 и 1. конъюнкций
ɞɢɡɴɸɧɤɬɢɜɧɵɯ
ɱɥɟɧɚɯ,
ɤɨɥɢɱɟɫɬɜɨ
ɷɥɟɦɟɧɬɚɪɧɵɯ
ɤɨɧɴɸɧɤɰɢɣ
ɜ
ɞɢɡɴɸɧɤɬɢɜɧɨɣ ɧɨɪɦɚɥɶɧɨɣ ɮɨɪɦɟ.
Наш подход, к определению сложности булевой фунБулева алгебра
широкоɮɨɪɦɟ.
применяется в релейно-контактɞɢɡɴɸɧɤɬɢɜɧɨɣ
ɧɨɪɦɚɥɶɧɨɣ
ɇɚɲ
ɩɨɞɯɨɞ,
ɤ Bɨɩɪɟɞɟɥɟɧɢɸ
ɛɭɥɟɜɨɣ ɮɭɧɤɰɢɢ B( X ) ɨ
= {x1 , xɫɥɨɠɧɨɫɬɢ
кции
от) Xɨɬ
( XB) ( X
ных
схемах,
транзисторах,
цифровых
вентилях
и
т.п.
2 ,... xn } n - переменных, состоит
ɇɚɲ ɩɨɞɯɨɞ, ɤ ɨɩɪɟɞɟɥɟɧɢɸ ɫɥɨɠɧɨɫɬɢ ɛɭɥɟɜɨɣ ɮɭɧɤɰɢɢ
следующем: ɫɨɫɬɨɢɬ ɜ ɫɥɟɞɭɸɳɟɦ:
Задача минимизации булевых функций
{x1 , x2 ,...быть
X = может
xn } n -вɩɟɪɟɦɟɧɧɵɯ,
ɫɨɫɬɨɢɬ
ɜ ɫɥɟɞɭɸɳɟɦ:
X = {x1 , x2 сформулирована
,... xn } n - ɩɟɪɟɦɟɧɧɵɯ,
1.Выделяем ~те наборы a~ = (a 1 ,a 2 ,...a n )∈ {0,1} для коследующим
образом:
найти представ1. ȼɵɞɟɥɹɟɦ ɬɟ
ɧɚɛɨɪɵ α = (α1 ,α 2 ,...α n ) ∈ {0,1} ɞɥɹ ɤɨɬɨɪɵɯ B( x1 , x2 ,... xn ) = 1
~
торых
ление
заданной
булевой
функции
в
форме,
содержащей
1. ȼɵɞɟɥɹɟɦ ɬɟ ɧɚɛɨɪɵ α = (α1 ,α 2 ,...α n ) ∈ {0,1} ɞɥɹ ɤɨɬɨɪɵɯ B( x1B, x( 2x,...
) =xn1), = 1 , множество этих наборов будем
1 , xx2n,...
ɦɧɨɠɟɫɬɜɨ
ɷɬɢɯ
ɧɚɛɨɪɨɜ
ɛɭɞɟɦ
ɨɩɪɟɞɟɥɹɬɶ
ɹɡɵɤ LB .
определять
конечный
язык Lɤɨɧɟɱɧɵɣ
минимально возможное число букв, в каком-то смысле
B.
ɦɧɨɠɟɫɬɜɨ
ɷɬɢɯ ɧɚɛɨɪɨɜ
ɛɭɞɟɦпостановке
ɨɩɪɟɞɟɥɹɬɶданная
ɤɨɧɟɱɧɵɣ
ɹɡɵɤ
LB .
2.Затем
строим
минимальный
конечный
минимальное.
В общей
задача
пока
2. Ɂɚɬɟɦ ɫɬɪɨɢɦ ɦɢɧɢɦɚɥɶɧɵɣ ɤɨɧɟɱɧɵɣ ɚɜɬɨɦɚɬ автомат
A = (Q , Σ, δ , i, F ) ,
решена,
однако
достаточно хорошо
исследована
2. не
Ɂɚɬɟɦ
ɫɬɪɨɢɦ
ɦɢɧɢɦɚɥɶɧɵɣ
ɤɨɧɟɱɧɵɣ
ɚɜɬɨɦɚɬ A = (Q, Σ, δ , i, F ) ,, сɫ алфавитом Σ = {0,1} допускающий
n
{
}
ɚɥɮɚɜɢɬɨɦ
Σ
=
0
,
1
ɞɨɩɭɫɤɚɸɳɢɣ
ɹɡɵɤ
n LA , ɬɚɤɨɣ, ɱɬɨ LB = Σ ∩ LA , ɝɞɟ Q
в классе
нормальных
ɚɥɮɚɜɢɬɨɦ
ɞɨɩɭɫɤɚɸɳɢɣ ɹɡɵɤ LA , ɬɚɤɨɣ,
ɱɬɨ LB = язык
ɝɞɟ Qчто– LB = Σ ∩ LA , где Q –Qконечное мноΣ = {0,1}дизъюнктивно-конъюнктивных
Σ n ∩ LLAA,, такой,
ɤɨɧɟɱɧɨɟ
ɫɨɫɬɨɹɧɢɣ,
ɚɜɬɨɦɚɬɚ, i
переходов авсостояний,ɮɭɧɤɰɢɹ
функция δ : Q × Σ → 2 ɩɟɪɟɯɨɞɨɜ
форм. Известно, что любая булева формула
можетQ ɦɧɨɠɟɫɬɜɨ
быть жество
ɤɨɧɟɱɧɨɟприведена
ɦɧɨɠɟɫɬɜɨ
ɫɨɫɬɨɹɧɢɣ, ɮɭɧɤɰɢɹ
i –
δ : Qформе
× Σ → (ДНФ).
2 ɩɟɪɟɯɨɞɨɜ
ɚɜɬɨɦɚɬɚ,
F
i
томата,
–
множество
начальных
состояний,
–
мнок дизъюнктивно
нормальной
ɦɧɨɠɟɫɬɜɨ ɧɚɱɚɥɶɧɵɯ ɫɨɫɬɨɹɧɢɣ, F – ɦɧɨɠɟɫɬɜɨ ɡɚɤɥɸɱɢɬɟɥɶɧɵɯ ɫɨɫɬɨɹɧɢɣ.
жество
заключительных состояний.
Дляɧɚɱɚɥɶɧɵɯ
этого можно
использовать
двойного
ɦɧɨɠɟɫɬɜɨ
ɡɚɤɥɸɱɢɬɟɥɶɧɵɯ
ɫɨɫɬɨɹɧɢɣ.
F –закон
ɦɧɨɠɟɫɬɜɨ
ɫɨɫɬɨɹɧɢɣ,
LB ɫɬɚɜɢɬɫɹ ɜ ɫɨɨɬɜɟɬɫɬɜɢɟ ɦɢɧɢɦɚɥɶɧɨ ɧɟɨɛɯɨɞɢɦɨ
3.отрицаɄɚɠɞɨɦɭ ɹɡɵɤɭ
3.Каждому
языку LB ставится в соответствие мининия,
закон
де
Моргана,
закон
дистрибутивности.
3. Ʉɚɠɞɨɦɭ ɹɡɵɤɭ LB ɫɬɚɜɢɬɫɹ ɜ ɫɨɨɬɜɟɬɫɬɜɢɟ ɦɢɧɢɦɚɥɶɧɨ ɧɟɨɛɯɨɞɢɦɨɟ
ɤɨɥɢɱɟɫɬɜɨ
ɫɨɫɬɨɹɧɢɣ,
ɧɚ
ɤɨɬɨɪɵɯ
ɦɨɠɧɨ состояний,
ɩɨɫɬɪɨɢɬɶнаɤɨɧɟɱɧɵɣ
ɚɜɬɨɦɚɬ
мально
необходимое
количество
которых
Используя законы булевой алгебры, можно получить
ɤɨɥɢɱɟɫɬɜɨ
ɫɨɫɬɨɹɧɢɣ,
ɤɨɬɨɪɵɯфункции
ɦɨɠɧɨɪɚɫɩɨɡɧɚɸɳɢɣ
ɩɨɫɬɪɨɢɬɶ
ɚɜɬɨɦɚɬ,
можно
построить
автомат, распознающий
для одной
и той жеɧɚ
логической
множество
эк- ɤɨɧɟɱɧɵɣ
ɷɬɨɬ
ɹɡɵɤ.
Ⱦɥɹ конечный
ɞɟɬɟɪɦɢɧɢɪɨɜɚɧɧɨɝɨ
ɚɜɬɨɦɚɬɚэтот
(ȾɄȺ), ɬɚɤɨɣ
ɪɚɫɩɨɡɧɚɸɳɢɣ
ɷɬɨɬ представлений.
ɹɡɵɤ. Ⱦɥɹ ɞɟɬɟɪɦɢɧɢɪɨɜɚɧɧɨɝɨ
ɚɜɬɨɦɚɬɚ
(ȾɄȺ),
ɬɚɤɨɣ
язык.
Для
автомата (ДКА),
такой
вивалентных
Чем прощеɚɜɬɨɦɚɬ
аналитическое
ɟɞɢɧɫɬɜɟɧɧɵɣ,
ɧɨ детерминированного
ɞɥɹ
ɧɟɞɟɬɟɪɦɢɧɢɪɨɜɚɧɧɨɝɨ
ɚɜɬɨɦɚɬɚ
(ɇȾȺ), ɦɨɠɟ
автомат
единственный,
но для недетерминированного
функции,
тем экономичнее
и проще ее пракɚɜɬɨɦɚɬ выражение
ɟɞɢɧɫɬɜɟɧɧɵɣ,
ɧɨ ɞɥɹ
ɧɟɞɟɬɟɪɦɢɧɢɪɨɜɚɧɧɨɝɨ
ɚɜɬɨɦɚɬɚ
(ɇȾȺ),
ɦɨɠɟɬ
ɫɭɳɟɫɬɜɨɜɚɬɶ
ɧɟɫɤɨɥɶɤɨ
ɪɚɡɥɢɱɧɵɯ
ɇɄȺ
ɫ
ɦɢɧɢɦɚɥɶɧɨ
ɜɨɡɦɨɠɧɵɦ
автомата
(НДА), может существовать несколько различтическаяɧɟɫɤɨɥɶɤɨ
реализация на
интегральныхɇɄȺ
микросхемах.
ɫɭɳɟɫɬɜɨɜɚɬɶ
ɪɚɡɥɢɱɧɵɯ
ɫ ɦɢɧɢɦɚɥɶɧɨ
ɜɨɡɦɨɠɧɵɦ
ɤɨɥɢɱɟɫɬɜɨɦ
ɫɨɫɬɨɹɧɢɣ,
ɧɨ
ɫɚɦɨ
ɷɬɨ
ɤɨɥɢɱɟɫɬɜɨ
ɞɥɹ
ɞɚɧɧɨɝɨ
ɪɟɝɭɥɹɪɧɨɝɨ
ɹɡɵɤ
из возможных способов задания булевых функ- ных НКА с минимально возможным количеством состоɤɨɥɢɱɟɫɬɜɨɦОдин
ɫɨɫɬɨɹɧɢɣ,
ɧɨ ɫɚɦɨ ɷɬɨ ɤɨɥɢɱɟɫɬɜɨ
ɞɥɹ ɞɚɧɧɨɝɨ
ɪɟɝɭɥɹɪɧɨɝɨ ɹɡɵɤɚ
ɨɩɪɟɞɟɥɹɟɬɫɹ
ɨɞɧɨɡɧɚɱɧɨ.
яний,
но
само
это
количество
для
данного
регулярного
ций – с помощью конечных автоматов. Конечные автоɨɩɪɟɞɟɥɹɟɬɫɹ
однозначно.
маты ɨɞɧɨɡɧɚɱɧɨ.
являются моделью для многих компонентов
аппа- языка определяется
B ( x1 , x 2 ,...x n ) ɧɚɡɵɜɚɟɬɫɹ ɤɨɥɢɱɟɫɬɜ
4. ɋɥɨɠɧɨɫɬɶɸ
ɛɭɥɟɜɨɣ ɮɭɧɤɰɢɢ
ɧɚɡɵɜɚɟɬɫɹ
ɤɨɥɢɱɟɫɬɜɨбулевой функции B( x1 , x 2 ,...x n ) назы4. ратного
ɋɥɨɠɧɨɫɬɶɸ
ɛɭɥɟɜɨɣобеспечения.
ɮɭɧɤɰɢɢ Наиболее
B ( x1 , x 2 ,...xважные
4.Сложностью
и программного
n)
ɧɚɡɵɜɚɬɶ
ɷɬɭA . Будем
ɜɟɥɢɱɢɧɭ
ɚɜɬɨɦɚɬɧɨɣ
A . Ȼɭɞɟɦ
ɫɨɫɬɨɹɧɢɣ
ɚɜɬɨɦɚɬɚ
вается
количество
состояний
автомата
называть
из них
– это программное
используемое
ɫɨɫɬɨɹɧɢɣ
ɚɜɬɨɦɚɬɚ
A . Ȼɭɞɟɦобеспечение,
ɧɚɡɵɜɚɬɶ
ɷɬɭ ɜɟɥɢɱɢɧɭ
ɚɜɬɨɦɚɬɧɨɣ
(
)
DBCom
B
ɫɥɨɠɧɨɫɬɶɸ
ɛɭɥɟɜɨɣ
ɮɭɧɤɰɢɢ
ɢ
ɨɛɨɡɧɚɱɚɬɶ
(deterministic
Boolea
эту
величину
автоматной
сложностью
булевой
функции
для разработки и проверки цифровых схем, программное
( B ) (deterministic Boolean
ɫɥɨɠɧɨɫɬɶɸ
ɛɭɥɟɜɨɣ ɮɭɧɤɰɢɢ ɢ ɨɛɨɡɧɚɱɚɬɶ DBCom
и обозначать DBCom(B
) (deterministic
обеспечение для поиска в больших текстовых
массивах,
complexity)
ɞɥɹ ɞɟɬɟɪɦɢɧɢɪɨɜɚɧɧɨɝɨ
ɚɜɬɨɦɚɬɚ
( B ) (nondeterministi
A ɢ Boolean
NDBComcomplexity)
A ɢ NDBCom
complexity)
ɞɟɬɟɪɦɢɧɢɪɨɜɚɧɧɨɝɨ
(nondeterministic
детерминированного автомата A и NDBCom(B )
дляɞɥɹ
проверки
различного родаɚɜɬɨɦɚɬɚ
систем, которые
могут( B )для
Boolean complexity)
ɞɥɹ
ɧɟɞɟɬɟɪɦɢɧɢɪɨɜɚɧɧɨɝɨ ɚɜɬɨɦɚɬɚ A .
(nondeterministic
Boolean complexity) для недетерминиронаходиться
в
конечном
числе
различных
состояний,
расA.
Boolean complexity) ɞɥɹ ɧɟɞɟɬɟɪɦɢɧɢɪɨɜɚɧɧɨɝɨ ɚɜɬɨɦɚɬɚ
Ɋɚɫɫɦɨɬɪɢɦ
ɧɟɫɤɨɥɶɤɨ
ɩɪɢɦɟɪɨɜ
ɪɟɚɥɢɡɚɰɢɢ ɛɭɥɟɜɵɯ ɮɭɧɤɰɢɣ
ванного
автомата
познавание
цепочек
символов
и
т.п.
Ɋɚɫɫɦɨɬɪɢɦ ɧɟɫɤɨɥɶɤɨ ɩɪɢɦɟɪɨɜ ɪɟɚɥɢɡɚɰɢɢ
ɛɭɥɟɜɵɯ
ɮɭɧɤɰɢɣ A
ɫ . ɝɪɚɮɨɜ ɢ ɤɨɧɟɱɧɵɯ ɚɜɬɨɦɚɬɨɜ ɢ ɫɪɚɜɧɢɦ
ɩɨɦɨɳɶɸ
ȾɇɎ,
ɢɧɮɨɪɦɚɰɢɨɧɧɵɯ
Рассмотрим
несколько
примеров
реализации булевых
СЛОЖНОСТЬ
БУЛЕВЫХ ɝɪɚɮɨɜ
ФУНКЦИЙ
И СЛОЖɩɨɦɨɳɶɸ ȾɇɎ,
ɢɧɮɨɪɦɚɰɢɨɧɧɵɯ
ɢɫɥɨɠɧɨɫɬɢ
ɤɨɧɟɱɧɵɯ
ɚɜɬɨɦɚɬɨɜ
функцийɢ с ɫɪɚɜɧɢɦ
помощью ДНФ, информационных графов и коɢɯ
ɨɩɢɫɚɧɢɹ.
НОСТЬ
КОНЕЧНЫХ АВТОМАТОВ
ɫɥɨɠɧɨɫɬɢ
ɢɯ ɨɩɢɫɚɧɢɹ.
автоматов и
сравним сложности
их описания.
ɉɪɢɦɟɪ 1.нечных
Ɋɚɫɫɦɨɬɪɢɦ
ɮɭɧɤɰɢɸ,
ɡɚɞɚɧɧɭɸ
ɩɨɥɢɧɨɦɨɦ ɀɟɝɚɥɤɢɧ
Сложность булевых функций – числовая характерисПример
1. Рассмотрим функцию, заданную полиɉɪɢɦɟɪ
1.
Ɋɚɫɫɦɨɬɪɢɦ
ɮɭɧɤɰɢɸ,
ɡɚɞɚɧɧɭɸ
ɩɨɥɢɧɨɦɨɦ
ɀɟɝɚɥɤɢɧɚ
тика булевых функций, выражающая трудность
, x5 , x6 ) = x6 . ɗɬɨ ɮɭɧɤɰɢɹ ɩɪɢɧɢɦɚɟɬ ɡɧɚɱɟɧɢɟ 1 ɩɪɢ x6 = 1 . ɉɪɢ n=
f ( x1 , x 2 , xих
3 , x 4выномом
, x 4 , x5 , x6 ) =Вxчастности,
ɡɧɚɱɟɧɢɟ
1 ɩɪɢ
. ɉɪɢ n=6 f (x1 , x 2 , x3 , x 4 , x5 , x6 ) = x6 . Это фунf ( x1 , x 2 , x3числения.
x = 1Жегалкина
такой ɩɪɢɧɢɦɚɟɬ
характеристикой
(мерой
6 . ɗɬɨ ɮɭɧɤɰɢɹ
ɬɚɤɢɯ ɧɚɛɨɪɨɜ
32.кция6 принимает значение 1 при x6 = 1 . При n=6 таких
сложности)
доɬɚɤɢɯ ɧɚɛɨɪɨɜ
32. может быть наименьшее число шагов,
наборов 32.
ȼ ȾɇɎ-ɩɪɟɞɫɬɚɜɥɟɧɢɢ
ɷɬɚ ɮɭɧɤɰɢɹ ɢɦɟɟɬ ɫɥɨɠɧɨɫɬɶ, ɪɚɜɧɭɸ 1. ɗɬ
ȼ ȾɇɎ-ɩɪɟɞɫɬɚɜɥɟɧɢɢ ɷɬɚ ɮɭɧɤɰɢɹ ɦɨɠɧɨ
ɢɦɟɟɬ ɫɥɨɠɧɨɫɬɶ,
ɪɚɜɧɭɸ
1.ɋȾɇɎ
ɗɬɨ ɢ ɫɨɤɪɚɬɢɜ ɟɟ. Ɂɚɞɚɜ ɜ ɫɢɫɬɟɦɟ GAP ɷɬ
ɩɪɨɜɟɪɢɬɶ,
ɫɨɫɬɚɜɢɜ
Вектор науки
ТГУ. № 4ɋȾɇɎ
(22), 2012
59
ɦɨɠɧɨ ɩɪɨɜɟɪɢɬɶ,
ɫɨɫɬɚɜɢɜ
ɢ ɫɨɤɪɚɬɢɜ
ɟɟ. Ɂɚɞɚɜ
ɜ ɫɢɫɬɟɦɟɜɵɪɚɠɟɧɢɟ
GAP ɷɬɭ a_l:=ListOfWordsToAutomaton(),
ɮɭɧɤɰɢɸ,
ɢɫɩɨɥɶɡɭɹ
ɩɨɥɭɱɚɟɦ
ɮɭɧɤɰɢɸ, ɢɫɩɨɥɶɡɭɹ ɜɵɪɚɠɟɧɢɟ a_l:=ListOfWordsToAutomaton(),
ɩɨɥɭɱɚɟɦ
ɞɟɬɟɪɦɢɧɢɪɨɜɚɧɧɵɣ ɤɨɧɟɱɧɵɣ ɚɜɬɨɦɚɬ, ɫɨɫɬɨɹɳɢɣ ɢɡ 8ɦɢ ɫɨɫɬɨɹɧɢɣ:
ɞɟɬɟɪɦɢɧɢɪɨɜɚɧɧɵɣ ɤɨɧɟɱɧɵɣ ɚɜɬɨɦɚɬ, ɫɨɫɬɨɹɳɢɣ
ɢɡ 8ɦɢ ɫɨɫɬɨɹɧɢɣ:
a_l:=ListOfWordsToAutomaton("01",["000001","000011","000101","000111","001
a_l:=ListOfWordsToAutomaton("01",["000001","000011","000101","000111","001
0
Крайнюков Н.И. Пивнева С.В.
ВЫЧИСЛЕНИЕ АВТОМАТНОЙ СЛОЖНОСТИ...
1
2 3
4
5
6
7 8
2
2 2
3
4
5
6 7
управление, вычислительная техника и информатика
1
2
2 1
3
4
5
6 7
В ДНФ-представлении эта функция имеет сложность, равную 1. Это можно проверить, составив СДНФ
и сократив ее. Задав в системе GAP эту функцию, используя выражение a_l:=ListOfWordsToAutomaton(), получаем детерминированный конечный автомат, состоящий
из 8-ми состояний:
a_l:=ListOfWordsToAutomaton(“01”,[“000001”,”000
011”,”000101”,”000111”,”001001”,”001011”,”001101”,
”001111”,”010001”,”010011”,”010101”,”010111”,”011001
”,”011011”,”011101”,”011111”,”100001”,”100011”,”10010
1”,”100111”,”101001”,”101011”,”101101”,”101111”,”1100
01”,”110011”,”110101”,”110111”,”111001”,”111011”,”111
101”,”111111”]);
< deterministic automaton on 2 letters with 8 states >
gap> Display(a_l);
| 1 2 3 4 5 6 7 8
----------------------------0 | 2 2 2 3 4 5 6 7
1 | 2 2 1 3 4 5 6 7
Initial state: [ 8 ]
Рис. 1. Представление автомата функции
Accepting state: [ 1 ]
Ɋɢɫ. 1. ɉɪɟɞɫɬɚɜɥɟɧɢɟ
ɚɜɬɨɦɚɬɚ
ɮɭɧɤɰɢɢ f x1 , x 2 , x3 , x 4 , x5 , x6 = x6
f (x1 , x 2 , x3 , x 4 , x5 , x6 ) = x6
5
5
1 2 3 4 5 6 7 8
выражение для этого автомата.
(–0Ιɪɟɝɭɥɹɪɧɨɟ
1 1) – регулярноеɜɵɪɚɠɟɧɢɟ
ɞɥɹ ɷɬɨɝɨ ɚɜɬɨɦɚɬɚ.
Данный автомат является минимальным, значит, в авто0 2 2 2 3 4 5 6 7
матном
представлении
сложность
этой
функции
8.
Ⱦɚɧɧɵɣ ɚɜɬɨɦɚɬ ɹɜɥɹɟɬɫɹ ɦɢɧɢɦɚɥɶɧɵɦ, равна
ɡɧɚɱɢɬ,
ɜ ɚɜɬɨ
Построим
упорядоченную
двоичную
разрешающую
1 2 2 1 3 4 5 6 7
ɩɪɟɞɫɬɚɜɥɟɧɢɢ ɫɥɨɠɧɨɫɬɶ
ɷɬɨɣ
ɮɭɧɤɰɢɢ
диаграмму
для этой
функции.ɪɚɜɧɚ 8.
(
({0Ι1} 1) { }
)
ɉɨɫɬɪɨɢɦ ɭɩɨɪɹɞɨɱɟɧɧɭɸ ɞɜɨɢɱɧɭɸ ɪɚɡɪɟɲɚɸɳɭɸ ɞɢɚɝɪɚɦɦɭ ɞ
ɮɭɧɤɰɢɢ.
Упорядоченная двоичнаяɞɜɨɢɱɧɚɹ
разрешающая диаграмма
для функции ɞɢɚɝɪɚɦɦɚ
.
f (x , x , x , x , x ,ɞɥɹ
x ) = xɮɭɧɤɰɢɢ
Ɋɢɫ.Рис.
2. 2.ɍɩɨɪɹɞɨɱɟɧɧɚɹ
ɪɚɡɪɟɲɚɸɳɚɹ
Минимизировав эту диаграмму, получим:
f ( x1 , x 2 , x3 , x 4 ,a_l:=ListOfWordsToAutomaton(“01”,[“000001”,”000010”,
x5 , x6 ) = x6 .
1
2
3
4
5
6
6
”000101”,”000110”,”001001”,”001010”,”001101”,”0011
10”,”010001”,”010010”,”010101”,”010110”,”011001”,
”011010”,”011101”,”011110”,”100001”,”100010”,”100101
Ɇɢɧɢɦɢɡɢɪɨɜɚɜ ɷɬɭ ɞɢɚɝɪɚɦɦɭ, ɩɨɥɭɱɢɦ:”,”100110”,”101001”,”101010”,”101101”,”101110”,”11000
1”,”110010”,”110101”,”110110”,”111001”,”111010”,”1111
01”,”111110”]);
< deterministic automaton on 2 letters with 9 states >
gap> Display(a_l);
| 1 2 3 4 5 6 7 8 9
-------------------------------0 | 9 9 1 2 4 5 6 7 9
1 | 9 1 9 3 4 5 6 7 9
Д Н Ф - Автоматное Представление
Initial state: [ 8 ]
представ- представле- в виде упорядоAccepting state: [ 1 ]
ление ȾɇɎ-ɩɪɟɞɫɬɚɜɥɟɧɢɟ
ние
ченной двоич- Ⱥɜɬɨɦɚɬɧɨɟ
ɉɪɟɞɫɬɚɜɥɟɧɢɟ ɜ ɜɢɞɟ
ной диаграммы
1 2 3 4ɭɩɨɪɹɞɨɱɟɧɧɨɣ
5 6 7 8 9
ɩɪɟɞɫɬɚɜɥɟɧɢɟ
Слож1
8
1
0 9 9 1ɞɜɨɢɱɧɨɣ
2 4 5 ɞɢɚɝɪɚɦɦɵ
6 7 9
ность
Рис. 3. Минимизированная
ɋɥɨɠɧɨɫɬɶ
1 диаграмма.
8
1
Пример 2. f = x5 ⊕ x6
Минимизируя СДНФ получаем сложность функции
Ɋɢɫ.
3. Ɇɢɧɢɦɢɡɢɪɨɜɚɧɧɚɹ
в ДНФ-представлении равную
2. Автомат
для этой функции будет иметь 9 состояний:
9
1
9
2
3
5
16
7
9
ɞɢɚɝɪɚɦɦɚ.
ɉɪɢɦɟɪ 2. f = x5 ⊕ x6
Ɇɢɧɢɦɢɡɢɪɭɹ ɋȾɇɎ ɩɨɥɭɱɚɟɦ ɫɥɨɠɧɨɫɬɶ ɮɭɧɤɰɢɢ ɜ ȾɇɎ-ɩɪɟɞɫɬɚɜɥɟɧɢɢ
60
Вектор науки ТГУ. № 4 (22), 2012
управление, вычислительная техника и информатика
Крайнюков Н.И. Пивнева С.В.
ВЫЧИСЛЕНИЕ АВТОМАТНОЙ СЛОЖНОСТИ...
Построим упорядоченную двоичную разрешающую
диаграмму для этой функции:
Рис. 4. Представление автомата функции
f = x5 ⊕ x 6 .
Рис. 5. Упорядоченная двоичная разрешающая диаграмма для функции
Минимальная OBDD:
Сложность
f = x5 ⊕ x 6 .
ДНФпредставление
Автоматное
представление
Представление
в виде упорядоченной двоичной
разрешающей
диаграммы
2
9
11
Рис. 6. Минимизированная диаграмма.
Пример 3. В этом примере сгенерируем в GAPе произвольные наборы, на которых функция принимает значение 1.
Для начала с помощью функции Random зададим
произвольное количество наборов, на которых функция
принимает значение 1.
gap> kol_ed:=Random([1..64]);
44
Мы получили произвольное число 44.
gap> zn_ar:=[];
[]
Сгенерируем произвольные наборы.
gap> for i in [1..kol_ed] do Add(zn_ar, b6_
L[Random([1..64])]); od;
gap> zn_ar;
[[0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0], [1, 0, 1,
1, 0, 0], [1, 0, 1, 0, 0, 1],
[1, 1, 0, 0, 0, 1], [0, 1, 1, 0, 1, 1], [0, 0, 1, 0, 1, 1], [1, 0, 1,
0, 1, 0], [0, 0, 1, 1, 1, 1],
Вектор науки ТГУ. № 4 (22), 2012
61
Крайнюков Н.И. Пивнева С.В.
управление, вычислительная техника и информатика
ВЫЧИСЛЕНИЕ АВТОМАТНОЙ СЛОЖНОСТИ...
[1, 1, 1, 1, 0, 1], [1, 1, 0, 0, 1, 0], [0, 0, 1, 0, 0, 0], [1, 1, 1,
1, 1, 1], [1, 0, 1, 1, 0, 1],
[1, 0, 0, 1, 1, 1], [0, 1, 0, 1, 0, 0], [0, 1, 1, 0, 0, 1], [0, 1, 1,
1, 0, 1], [1, 1, 1, 0, 0, 1],
[1, 0, 0, 1, 1, 0], [1, 0, 0, 0, 1, 1], [1, 1, 0, 1, 0, 0], [1, 0, 1,
0, 0, 0], [0, 1, 0, 0, 1, 1],
[0, 0, 0, 1, 0, 0], [1, 1, 0, 1, 1, 1], [1, 0, 0, 0, 0, 1], [1, 1, 1,
0, 1, 1], [1, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0], [0, 1, 1, 1, 0, 0], [1, 0, 0,
1, 0, 0], [0, 0, 0, 0, 1, 0],
[1, 0, 0, 1, 0, 1], [1, 0, 1, 0, 1, 1], [0, 0, 1, 0, 0, 1], [1, 1, 1,
0, 0, 0], [1, 1, 0, 1, 0, 1],
[0, 0, 1, 1, 0, 1], [1, 0, 1, 1, 1, 0], [1, 0, 1, 1, 1, 1], [0, 0,
1, 1, 0, 0]]
Составим СДНФ:
( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 )
Приведем СДНФ к ДНФ:
( x1 x2 x3 ) ∪ ( x1 x2 x3 x6 ) ∪ ( x1 x2 x3 x4 ) ∪ ( x1 x2 x3 x4 ) ∪ ( x1 x2 x3 x4 ) ∪ ( x1 x2 x3 x5 )
∪ ( x1 x2 x3 x4 x5 ) ∪ ( x1 x2 x3 x4 x5 ) ∪ ( x1 x2 x3 x4 x5 ) ∪ ( x1 x2 x3 x4 x6 )
∪ ( x1 x2 x3 x5 x6 ) ∪ ( x1 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
∪ ( x1 x2 x3 x4 x5 x6 ) ∪ ( x1 x2 x3 x4 x5 x6 )
В ДНФ-представлении сложность будет равна 16.
62
Напишем полином Жегалкина по этой таблице истинности:
Вектор науки ТГУ. № 4 (22), 2012
управление, вычислительная техника и информатика
Крайнюков Н.И. Пивнева С.В.
ВЫЧИСЛЕНИЕ АВТОМАТНОЙ СЛОЖНОСТИ...
По сгенерированным наборам в системе GAP получим ДКА:
gap>
a_l:=ListOfWordsToAutomaton(“01”,[“000001”,”100
010”,”110110”,”101100”,”101001”,”110001”,”011011”,
”001011”,”101010”,”001111”,”111101”,”110010”,”0010
00”,”111111”,”101101”,”100111”,”010100”,”011001”,
”011101”,”111001”,”100110”,”100011”,”110100”,”1010
00”,”010011”, ”000100”,”110111”,”100001”,”111011”,”10
0000”,”110011”,”110000”,”011100”,”100100”,”000010”,
”100101”,”101011”,”001001”,”111000”,”110101”,”0011
01”,”101110”,”101111”,”001100”]);
< deterministic automaton on 2 letters with 25 states >
gap> MinimalizedAut(a_l);
< deterministic automaton on 2 letters with 25 states >
Этот автомат задается таблицей переходов:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
0
25
25
1
3
16
5
6
10
18
9
19
4
23
5
2
3
4
15
2
1
20
25
22
3
25
1
25
25
1
2
16
5
14
7
17
13
24
19
11
12
20
3
4
21
2
25
25
2
21
25
25
Сложность автомата равна 25.
Рис. 7. Упорядоченная двоичная разрешающая диаграмма.
Минимальная упорядоченная двоичная разрешающая диаграмма:
Сложность
ДНФпредставление
Автоматное представление
Представление
в виде упорядоченной двоичной разрешающей диаграммы
16
25
19
Рис. 8. Минимизированная диаграмма.
Вектор науки ТГУ. № 4 (22), 2012
Примеры показывают, что определение сложности
булевой функции многоплановое понятие, в различных
прикладных областях можно использовать различные
подходы для этого.
Для вычисления автоматной сложности булевой
функции приходится решать сложные задачи минимизации ДКА и НДА, последняя задача является (PSPACEполной) и для булевых функций от большого количества
63
математика
Кузичкина Е.И.
ПЕРЕБОРНЫЕ АЛГОРИТМЫ ПОДСЧЁТА ЧИСЛА...
переменных необходимо применение эвристических алгоритмов, например описанных в [7].
ЗАКЛЮЧЕНИЕ
Итак, в статье проанализирована сложность описания
булевых функций с помощью ДНФ, конечных автоматов
и упорядоченных двоичных разрешающих диаграмм. Показано, что понятие сложности различных представлений
булевых функций взаимосвязаны и дополняют друг друга.
СПИСОК ЛИТЕРАТУРЫ
1. Мельников Б.Ф. Эвристики в программировании
недетерминированных игр. – «Программирование»
(Известия РАН), 2001, №5, С.63–80.
2. Пивнева С.В. Моделирование задач дискретной оптимизации / С. В. Пивнева, М. А. Трифонов // Вектор науки. –
№ 3 (13). – Тольятти : Тольят. гос. ун-т, 2010. – С. 31–34.
3. Пивнева С.В. Программная реализация задач дискретной оптимизации / С. В. Пивнева, М. А. Трифонов // Некоторые вопросы математического моделирования дискретных систем : сб. науч. тр. – Тольятти :
ТГУ, 2011. – С. 210–219.
4. Поваров Г. Конечные трансдьюсеры и недетерминированная сложность регулярного языка. Известия вузов. Математика. 2010, № 6, С. 23–31.
5. Хопкрофт Дж., Мотвани Р., Ульман Дж.. Введение
в теорию автоматов, языков и вычислений. 2-е изд.:
Пер. с англ. – М. : Издательский дом «Вильямс»,
2002. – 528 с. : ил. – Парал. тит. англ.
6. Шуткин Ю. Асимптотически оптимальная реализация булевых функций информационными графами.
Дискрет. матем., 2011, 23:4, С.80–102.
7. Мельников Б. Мультиэвристический подход к задачам дискретной оптимизации. Кибернетика
и системный анализ (НАН Украины), 2006, № 3,
С. 32–42.
Работа частично поддержана программой Министерства образования и науки РФ в рамках Госзадания Тольяттинского государственного университета на 2012 год
(шифр 6.3072.2011) и реализации гранта федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009–2013 годы (Соглашение
№ 14.В37.21.1934)
CALCULATION OF AUTOMATON COMPLEXITY OF BOOLEAN
FUNCTIONS AS DISCRETE OPTIMIZATION PROBLEMS
© 2012
N.I. Kraynyukov, candidate of pedagogical sciences, associated professor of the chair «Applied
mathematics and informatics
S.V. Pivneva, candidate of pedagogical sciences, associated professor, associated professor of the chair
«Higher mathematics and mathematical modeling»
Togliatti State University, Togliatti (Russia)
Keywords: Boolean functions; certainly-automatic complexity; final automatic devices.
Annotation: The problem of calculation of complexity of the description булевых functions by means of the disjunctive normal forms, the determined final automatic devices and the ordered binary diagrams is considered.
Examples of realization of functions are considered by three ways, their complexity is analysed.
УДК 512.531.2
ПЕРЕБОРНЫЕ АЛГОРИТМЫ ПОДСЧЁТА ЧИСЛА КОНЕЧНЫХ
ПОЛУГРУПП – ПОСТАНОВКА ЗАДАЧИ И ПРОСТЕЙШИЕ ЭВРИСТИКИ
© 2012
Е.И. Кузичкина, аспирант
Тольяттинский государственный университет, Тольятти (Россия)
Ключевые слова: конечная полугруппа; алгоритмы перебора; эвристические алгоритмы.
Аннотация: Рассмотрены простые эвристические переборные алгоритмы для подсчёта числа конеч-
ных полугрупп.
64
Вектор науки ТГУ. № 4 (22), 2012
Документ
Категория
Без категории
Просмотров
4
Размер файла
696 Кб
Теги
вычисления, оптимизация, булевых, дискретное, функции, автоматные, сложности, задачи
1/--страниц
Пожаловаться на содержимое документа