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



             

Задачи


Задача 3.1. Докажите, что совершенная, сокращенная и минимальная ДНФ функции odd(X1,X2,…, Xn) совпадают и состоят из 2n-1 элементарных конъюнкций длины n.

Задача 3.2. Докажите лемму 3.2 возвратной индукцией по i.

Задача 3.3. Используя лемму 3.2, докажите утверждение 2 теоремы 3.2.

Задача 3.4. Постройте минимальные УБДР для двуместных функций: x

y, x
y, x + y, x
y, x|y.

Задача 3.5. Постройте минимальные УБДР для функции

f(x_1, x_2, x_3, x_4, x_5, x_6)= (x_1\wedge x_2) +( x_3\wedge x_4) +( x_5\wedge x_6)

относительно двух упорядочений переменных:

  • x1 < x2 < x3 < x4 < x5 < x6 и
  • x1 < x3 < x5 < x2 < x4 < x6.

Задача 3.6. Пороговая функция Tnk от n переменных с порогом k выдает 1, если во входном наборе имеется не менее k единиц: Tnk(x1,x2, …, xn) = 1

x1 + x2 + … + xn
k.

  • Постройте минимальные УБДР для пороговых функций T32, T42, T53.
  • Зависит ли сложность минимальной УБДР для пороговых функций от порядка переменных?
  • Оцените сложность минимальной УБДР для пороговой функции Tnk.

Задача 3.7. Выберите подходящий порядок переменных и постройте для него минимальные УБДР, реализующие функции из задач 12.5 и 12.6.

Задача 3.8. Как мы видели, логические схемы естественным образом реализуются в виде неветвящихся программ. Наоборот, для деревьев решений и УБДР естественным программным представлением являются ветвящиеся программы, включающие лишь условные операторы вида if ... then ... else ... с тестами вида "x = 0?" и "x = 1?" (они соответствуют внутренним вершинам диаграмм) и операторы присвоения значения 0 или 1 результату (они соответствуют вершинам-стокам).

Напишите ветвящиеся программы, вычисляющие функции, представляемые УБДР D2 на рис. 3.3 и Df на рис.3.6.




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