Введение в схемы, автоматы и алгоритмы



             

Основные определения - часть 2


Как и в случае БДР, УБДР реализует булеву функцию f(x1, …, xn), если для каждого набора значений переменных ?1, ?2, …, ?n путь в диаграмме, начинающийся в корне и соответствующий этому набору (из вершины xi идем по ребру, помеченному ?i), завершается стоком с меткой f(?1, ?2, …, ?n).

Из этого определения непосредственно следует, что каждая внутренняя вершина диаграммы v, помеченная переменной x

(k), является корнем поддиаграммы, которая включает все вершины диаграммы, достижимые из v, и реализует некоторую функцию fv( x
(k),x
(k+1), …, x
(n)) от (n -k +1) переменных x
(k),x
(k+1), …, x
(n). При этом ее 0-сын w0 является корнем поддиаграммы, реализующей функцию fw0(x
(k+1), …, x
(n)) =fv( 0, x
(k+1), …, x
(n)), а 1-сын w1 - корень поддиаграммы, реализующей функцию fw1(x
(k+1), …, x
(n)) =fv( 1, x
(k+1), …, x
(n)). Пусть диаграмма реализует функцию f(x1, … , xn) = f'(x
(1), …, x
(n)) и ?
(1),… , ?
(k-1) - это набор значений переменных x
(1), …, x
(k-1), который соответствует пути из корня в вершину v (таких наборов может быть несколько). Тогда fv( x
(k), …, x
(n))= f'(?
(1),… , ?
(k-1),x
(k), …, x
(n)).

Пример 3.2. Реализуем с помощью УБДР функцию f1(x,y,z), представленную выше в примере 3.1, с помощью БДР T1 и таблицы 3.1.

Вначале зафиксируем порядок переменных: x < y < z. Объединив листья с одинаковыми метками и две z- вершины с одинаковыми потомками, получим УБДР D1, приведенную на рис.3.2.


Рис. 3.2. 

Ясно, что реализация функции f1(x,y,z) с помощью УБДР D1 намного компактнее, чем с помощью БДР T1.

Под сложностью L(D) УБДР D будем понимать число внутренних вершин в D. Например, L(D1)=4. Может ли сложность диаграммы для некоторой функции зависеть от порядка переменных? Да! Рассмотрим порядок переменных y < x < z. Как показывает следующий рисунок, относительно этого порядка функцию f(x,y,z) можно реализовать УБДР D2 со сложностью L(D2)=3.


Рис. 3.3. 




Содержание  Назад  Вперед