4551
правка
Бинарный граф решений: различия между версиями
Материал из WEGA
нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 4: | Строка 4: | ||
'''Булевы функции''' | '''Булевы функции''' | ||
Понятие булевой функции – функции с областью определения {0,1}n и областью значений {0,1} – является одним из базовых понятий для любых вычислений. Булевы функции используются в основополагающих работах по вычислительной сложности [7, 9], а также при проектировании и анализе логических схем [4, 13]. Булева функция может быть представлена в виде таблицы истинности – перечисления значений, принимаемых функцией на каждом элементе {0,1}n. Поскольку для представления в виде таблицы истинности требуется экспоненциальный относительно n объем памяти, для большинства приложений оно оказывается непрактичным. Следовательно, существует потребность в структурах данных и соответствующих алгоритмах для эффективного представления и обработки булевых функций. | Понятие [[булева функция|булевой функции]] – функции с областью определения {0,1}<math>^n</math> и областью значений {0,1} – является одним из базовых понятий для любых вычислений. Булевы функции используются в основополагающих работах по вычислительной сложности [7, 9], а также при проектировании и анализе логических схем [4, 13]. Булева функция может быть представлена в виде таблицы истинности – перечисления значений, принимаемых функцией на каждом элементе {0,1}^n</math>. Поскольку для представления в виде таблицы истинности требуется экспоненциальный относительно n объем памяти, для большинства приложений оно оказывается непрактичным. Следовательно, существует потребность в структурах данных и соответствующих алгоритмах для эффективного представления и обработки булевых функций. | ||
'''Булевы схемы''' | '''Булевы схемы''' | ||
Булевы функции могут быть представлены различными способами. Одним из естественных представлений является схема булевых комбинаций, или просто булева схема [6, глава 34]. Схема состоит из булевых комбинационных элементов, соединенных проводами. Булевыми комбинационными элементами являются вентили и первичные входы. Существуют три типа вентилей: NOT, AND и OR. Вентильная функция NOT работает следующим образом: она принимает одно булево значение-вход и вычисляет одно булево значение-выход, которое принимает значение 0, если вход равен 1, и 1 – если вход равен 0. Вентиль AND принимает два булевых значения-входа и вычисляет одно значение-выход, равное 1, если оба входа имеют значение 1, и 0 в противном случае. Вентиль OR похож на AND, за тем исключением, что выходное значение равно 1 в случае, если одно или оба входных значения равны 1, и 0 в противном случае. | Булевы функции могут быть представлены различными способами. Одним из естественных представлений является схема булевых комбинаций, или просто булева схема [6, глава 34]. Схема состоит из булевых комбинационных элементов, соединенных проводами. Булевыми комбинационными элементами являются вентили и первичные входы. Существуют три типа вентилей: NOT, AND и OR. Вентильная функция NOT работает следующим образом: она принимает одно булево значение-вход и вычисляет одно булево значение-выход, которое принимает значение 0, если вход равен 1, и 1 – если вход равен 0. Вентиль AND принимает два булевых значения-входа и вычисляет одно значение-выход, равное 1, если оба входа имеют значение 1, и 0 в противном случае. Вентиль OR похож на AND, за тем исключением, что выходное значение равно 1 в случае, если одно или оба входных значения равны 1, и 0 в противном случае. | ||
Схемы должны быть бесконтурными; отсутствие контуров обеспечивает возможность однозначным образом протягивать булево присваивание первичным входам по вентилям в топологическом порядке. Из этого следует, что схема на n упорядоченных первичных входах с выделенным вентилем, называемым первичным выходом, соответствует булевой функции на {0,1}n. Каждая булева функция может быть представлена схемой – например, путем построения схемы, воспроизводящей таблицу истинности. | Схемы должны быть бесконтурными; отсутствие контуров обеспечивает возможность однозначным образом протягивать булево присваивание первичным входам по вентилям в топологическом порядке. Из этого следует, что схема на n упорядоченных первичных входах с выделенным вентилем, называемым первичным выходом, соответствует булевой функции на {0,1}^n</math>. Каждая булева функция может быть представлена схемой – например, путем построения схемы, воспроизводящей таблицу истинности. | ||
Представление в виде схемы имеет слишком общий вид: любая проблема разрешимости, вычислимая на машине Тьюринга за полиномиальное время, может быть вычислена при помощи схем полиномиальной относительно размера экземпляра величины, причем схемы могут быть эффективно построены из программы машины Тьюринга [15]. Однако главные задачи анализа на схемах, называемые проблемой выполнимости и проблемой эквивалентности, являются NP-полными [7]. | Представление в виде схемы имеет слишком общий вид: любая проблема разрешимости, вычислимая на машине Тьюринга за полиномиальное время, может быть вычислена при помощи схем полиномиальной относительно размера экземпляра величины, причем схемы могут быть эффективно построены из программы машины Тьюринга [15]. Однако главные задачи анализа на схемах, называемые проблемой выполнимости и проблемой эквивалентности, являются NP-полными [7]. | ||
'''Булевы формулы''' | '''Булевы формулы''' | ||
Булева формула определяется рекурсивным образом: булева переменная xi является булевой формулой, а если φ и ψ являются булевыми формулами, то ими являются также (φ), (φ ψ), (φ ψ), (φ → ψ) и (φ ↔ ψ). Операторы , , , →, ↔ называются логическими операциями; ради удобства записи скобки часто опускаются. Булевы формулы могут использоваться для представления произвольных булевых функций; однако проблемы выполнимости и эквивалентности формул также являются NP-полными. Булевы формулы являются менее краткими и сжатыми, чем булевы схемы: к примеру, функция четности имеет схемы линейного размера, тогда как представления в виде формул являются сверхполиномиальными. Точнее говоря, XORn: {0, 1}n (стрелка вправо с коротким «упором» слева) {0; 1} определена следующим образом: она принимает значение 1 в точности на тех элементах {0, 1}n, которые содержат нечетное число единиц. Определим размер формулы, равный количеству встречающихся в ней логических операций. Тогда для любой последовательности формул θ1, θ2, … , такой, что θk представляет XORk, размер θk равен Ω(kc) для всех c Z+ [14 , главы 11 и 12]. | Булева формула определяется рекурсивным образом: булева переменная xi является булевой формулой, а если φ и ψ являются булевыми формулами, то ими являются также (φ), (φ ψ), (φ ψ), (φ → ψ) и (φ ↔ ψ). Операторы , , , →, ↔ называются логическими операциями; ради удобства записи скобки часто опускаются. Булевы формулы могут использоваться для представления произвольных булевых функций; однако проблемы выполнимости и эквивалентности формул также являются NP-полными. Булевы формулы являются менее краткими и сжатыми, чем булевы схемы: к примеру, функция четности имеет схемы линейного размера, тогда как представления в виде формул являются сверхполиномиальными. Точнее говоря, XORn: {0, 1}^n</math> (стрелка вправо с коротким «упором» слева) {0; 1} определена следующим образом: она принимает значение 1 в точности на тех элементах {0, 1}^n</math>, которые содержат нечетное число единиц. Определим размер формулы, равный количеству встречающихся в ней логических операций. Тогда для любой последовательности формул θ1, θ2, … , такой, что θk представляет XORk, размер θk равен Ω(kc) для всех c Z+ [14 , главы 11 и 12]. | ||
Дизъюнкция представляет собой булеву формулу, содержащую только логические операции и , причем применяется только к переменным; к примеру, x1 x3 x5 является дизъюнкцией. Булева формула находится в дизъюнктивной нормальной форме (ДНФ), если она имеет вид D0 D1 … Dk-1, где каждый член Di является дизъюнкцией. ДНФ-формулы могут представлять произвольные булевы функции, например, путем определения каждого входа, на котором формула принимает значение 1, как дизъюнкции. ДНФ-формулы применяются в проектировании логических схем, поскольку могут быть непосредственно переведены в ПЛМ [4]. Однако если проблема выполнимости ДНФ-формул решается тривиально, то проблема эквивалентности является NP-полной. Кроме того, если φ и ψ являются ДНФ-формулами, то φ и φ ψ таковыми не являются, а перевод их в ДНФ, представляющие ту же функцию, может привести к экспоненциальному росту размера формулы. | Дизъюнкция представляет собой булеву формулу, содержащую только логические операции и , причем применяется только к переменным; к примеру, x1 x3 x5 является дизъюнкцией. Булева формула находится в дизъюнктивной нормальной форме (ДНФ), если она имеет вид D0 D1 … Dk-1, где каждый член Di является дизъюнкцией. ДНФ-формулы могут представлять произвольные булевы функции, например, путем определения каждого входа, на котором формула принимает значение 1, как дизъюнкции. ДНФ-формулы применяются в проектировании логических схем, поскольку могут быть непосредственно переведены в ПЛМ [4]. Однако если проблема выполнимости ДНФ-формул решается тривиально, то проблема эквивалентности является NP-полной. Кроме того, если φ и ψ являются ДНФ-формулами, то φ и φ ψ таковыми не являются, а перевод их в ДНФ, представляющие ту же функцию, может привести к экспоненциальному росту размера формулы. | ||
'''Деревья Шеннона''' | '''Деревья Шеннона''' | ||
Пусть f – булева функция на области определения {0,1}n. Ассоциируем n размерностей с переменными x0, | Пусть f – булева функция на области определения {0,1}^n</math>. Ассоциируем n размерностей с переменными x0, ..., xn-1. Тогда положительным сомножителем f относительно xi, обозначаемым fxi, является функция на области определения {0,1}^n</math>, которая задается следующим образом | ||
fxi(α0, ... ,αi-1, ai, αi+1, …, αn-1) = f(α0, ... ,αi-1, 1, αi+1, …, αn-1). | fxi(α0, ... ,αi-1, ai, αi+1, …, αn-1) = f(α0, ... ,αi-1, 1, αi+1, …, αn-1). | ||
| Строка 29: | Строка 29: | ||
f(x1, ... , xn) = xi • fxi + x'i fx’i | f(x1, ... , xn) = xi • fxi + x'i fx’i | ||
Это наблюдение можно использовать для представления f в виде дерева Шеннона – полного бинарного дерева [6, приложение B.5] высоты n, в котором каждый путь в вершину-лист определяет полное присваивание n переменным, над которыми определена функция f; а вершина-лист содержит значение 0 или 1 в зависимости от значения, которое f принимает при присваивании. | Это наблюдение можно использовать для представления f в виде дерева Шеннона – полного бинарного дерева [6, приложение B.5] высоты n, в котором каждый путь в вершину-лист определяет полное присваивание n переменным, над которыми определена функция f; а вершина-лист содержит значение 0 или 1 в зависимости от значения, которое f принимает при присваивании. | ||
Дерево Шеннона нельзя назвать достаточно удобным представлением, поскольку высота дерева, представляющего любую булеву функцию на {0,1}n, равна n, так что дерево имеет 2n листьев. Дерево Шеннона можно уменьшить при помощи слияния изоморфных поддеревьев и пренебрежения вершинами, имеющими идентичных потомков. На первый взгляд, использование сокращенного дерева Шеннона тоже не особенно практично, поскольку оно включает создание на первом этапе полного бинарного дерева. Более того, пока неясно, как можно на сокращенном дереве Шеннона эффективно производить такие операции, как проверка эквивалентности или вычисление конъюнкции функций, представленных в виде сокращенных деревьев Шеннона. | Дерево Шеннона нельзя назвать достаточно удобным представлением, поскольку высота дерева, представляющего любую булеву функцию на {0,1}^n</math>, равна n, так что дерево имеет 2n листьев. Дерево Шеннона можно уменьшить при помощи слияния изоморфных поддеревьев и пренебрежения вершинами, имеющими идентичных потомков. На первый взгляд, использование сокращенного дерева Шеннона тоже не особенно практично, поскольку оно включает создание на первом этапе полного бинарного дерева. Более того, пока неясно, как можно на сокращенном дереве Шеннона эффективно производить такие операции, как проверка эквивалентности или вычисление конъюнкции функций, представленных в виде сокращенных деревьев Шеннона. | ||
Брайант [5] пришел к выводу, что накладывание ограничения, согласно которому переменные появляются в фиксированном порядке от корня к листьям, значительно снижает сложность обработки сокращенных деревьев Шеннона. Это представление он назвал бинарной диаграммой решений (БДР). | Брайант [5] пришел к выводу, что накладывание ограничения, согласно которому переменные появляются в фиксированном порядке от корня к листьям, значительно снижает сложность обработки сокращенных деревьев Шеннона. Это представление он назвал бинарной диаграммой решений (БДР). | ||
| Строка 36: | Строка 36: | ||
Бинарная диаграмма решений (БДР) представляет собой бесконтурный орграф с выдеренной вершиной и не более чем двумя стоками, один из которых имеет метку 0, а другой – метку 1. Вершины, не являющиеся стоками, помечены переменными. Каждая вершина, не являющаяся стоком, имеет две исходящих дуги; одна из них имеет метку 1 и ведет к 1-потомку, другая имеет метку 0 и ведет к 0-потомку. Переменные должны быть упорядочены; иначе говоря, если переменная-метка xi появляется раньше метки xj на некотором пути из вершины к стоку, тогда метка xj не может встречаться до xi ни на одном пути из вершины к стоку. Две вершины являются изоморфными, если обе являются стоками с одинаковой меткой либо представляют собой вершины, не являющиеся стоками, с одной и той же переменной-меткой, причем их 0-потомки и 1-потомки изоморфны. Чтобы бесконтурный орграф был допустимой БДР, необходимо, чтобы в нем не было изоморфных вершин и чтобы никакие вершины не имели одинаковых 0-потомков и 1-потомков. | Бинарная диаграмма решений (БДР) представляет собой бесконтурный орграф с выдеренной вершиной и не более чем двумя стоками, один из которых имеет метку 0, а другой – метку 1. Вершины, не являющиеся стоками, помечены переменными. Каждая вершина, не являющаяся стоком, имеет две исходящих дуги; одна из них имеет метку 1 и ведет к 1-потомку, другая имеет метку 0 и ведет к 0-потомку. Переменные должны быть упорядочены; иначе говоря, если переменная-метка xi появляется раньше метки xj на некотором пути из вершины к стоку, тогда метка xj не может встречаться до xi ни на одном пути из вершины к стоку. Две вершины являются изоморфными, если обе являются стоками с одинаковой меткой либо представляют собой вершины, не являющиеся стоками, с одной и той же переменной-меткой, причем их 0-потомки и 1-потомки изоморфны. Чтобы бесконтурный орграф был допустимой БДР, необходимо, чтобы в нем не было изоморфных вершин и чтобы никакие вершины не имели одинаковых 0-потомков и 1-потомков. | ||
Основной результат теории БДР заключается в следующем: если дано фиксированное упорядочение переменных, то представление является уникальным с точностью до изоморфизма. Иначе говоря, если F и G являются БДР, представляющими f: {0, 1}n (стрелка вправо с коротким «упором» слева) {0, 1} с порядком переменных x1 (круглый символ «меньше») x2 (круглый символ «меньше») … xn, то F и G являются изоформными. | Основной результат теории БДР заключается в следующем: если дано фиксированное упорядочение переменных, то представление является уникальным с точностью до изоморфизма. Иначе говоря, если F и G являются БДР, представляющими f: {0, 1}^n</math> (стрелка вправо с коротким «упором» слева) {0, 1} с порядком переменных x1 (круглый символ «меньше») x2 (круглый символ «меньше») … xn, то F и G являются изоформными. | ||
Определение изоморфизма напрямую дает нам рекурсивный алгоритм проверки на изоморфизм. Однако он имеет экспоненциальную по отношению к числу узлов сложность; это можно проиллюстрировать, в частности, при помощи проверки изоморфизма БДР для функции четности относительно ее самой. Экспоненциальная сложность связана с постоянно возникающими проверками на изоморфизм между парами вершин; решение может быть найдено в динамическом программировании. Кэширование проверок на изоморфизм снижает сложность этих проверок до O(|F| • |G|), где |B| обозначает количество вершин в БДР B. | Определение изоморфизма напрямую дает нам рекурсивный алгоритм проверки на изоморфизм. Однако он имеет экспоненциальную по отношению к числу узлов сложность; это можно проиллюстрировать, в частности, при помощи проверки изоморфизма БДР для функции четности относительно ее самой. Экспоненциальная сложность связана с постоянно возникающими проверками на изоморфизм между парами вершин; решение может быть найдено в динамическом программировании. Кэширование проверок на изоморфизм снижает сложность этих проверок до O(|F| • |G|), где |B| обозначает количество вершин в БДР B. | ||
| Строка 47: | Строка 47: | ||
'''Упорядочение переменных''' | '''Упорядочение переменных''' | ||
Все симметричные функции на {0,1}n имеют БДР полиномиального относительно n размера, независимо от порядка переменных. Однако другие полезные функции (например, компараторы, мультиплексоры, сумматоры и вычитатели) могут быть представлены более эффективно, если правильно выбран порядок переменных. Эвристики для выбора упорядочения представлены, например, в [1, 2, 11]. Существуют функции, не имеющие полиномиальных БДР при любом порядке переменных – например, функция, представляющая n-й бит выходного значения мультиплексора, принимающего на вход два n-битных целых числа без знака [5]. Вегенер [17] приводит и другие примеры, доказывающие важность правильного выбора порядка переменных. | Все симметричные функции на {0,1}^n</math> имеют БДР полиномиального относительно n размера, независимо от порядка переменных. Однако другие полезные функции (например, компараторы, мультиплексоры, сумматоры и вычитатели) могут быть представлены более эффективно, если правильно выбран порядок переменных. Эвристики для выбора упорядочения представлены, например, в [1, 2, 11]. Существуют функции, не имеющие полиномиальных БДР при любом порядке переменных – например, функция, представляющая n-й бит выходного значения мультиплексора, принимающего на вход два n-битных целых числа без знака [5]. Вегенер [17] приводит и другие примеры, доказывающие важность правильного выбора порядка переменных. | ||
== Применение == | == Применение == | ||
