Главная Промышленная автоматика.

которые входят в один л-членный кортеж, содержащий a. Пусть

л п. (=1 /=1

Рассмотрите изменение / по мере выполнения шагов вычисления.

**12.21. Наложим следующее ограничение на вид шагов вычисления: в а -<-66с операция 6 состоит в выборе п12 формальных переменных из циклического сдвига л-членного кортежа b и л/2 формальных переменных из дополнительных позиций в с. Найдите вычисление для множества л-членных кортежей из упр. 12.20, состоящее из 0(л log л) шагов.

**12.22. Пусть G - ориентированный ациклический граф с л выделенными истоками (узлами, в которые не входят никакие ребра) и л выделенными выходами (узлами, из которых не выходят никакие ребра). Пусть X и F - подмножества истоков и выходов соответственно, а Ь{Х, Y) - подграф, состоящий из всех ориентированных ребер, лежащих на путях из узлов множества X в узлы множества Y. Пропускной способностью графа G(X, Y) называется наименьшее число узлов, удаление которых (вместе с входящими и выходящими ребрами) отделяет каждый узел из X от каждого узла из Y. Допустим, что для любых X vlY граф G{X, Y) обладает пропускной способностью MIN (Х, 1F). Покажите, что для каждого л существует такой граф G с сп log л ребрами, где с - некоторая постоянная.

**12.23. Сдвигающей схемой называется такой ориентированный граф с л истоками, занумерованными числами от О до л-1, и л выходами, занумерованными числами от О до л-1, что для каждого S, 0<5<л-1, найдется множество путей, непересекающихся по узлам, которое для каждого i содержит путь из истока i в выход [i+s) по модулю л.

(а) Покажите, что для каждого л существует сдвигающая схема с 2л log л ребрами.

(б) Покажите, что для сдвигающей схемы асимптотически требуется л log л ребер.

(в) Покажите, что с помощью сдвигающей схемы можно вычислить транспонированную матрицу.

Определение. Пусть F - поле и JCi, . . . , л;„-формальные переменные. Линейньш вычислением называются последовательность шагов вида а -Хф+Хс, где а - переменная, b к с - переменные или формальные переменные, а и - элементы из F (называемые постоянными).

**12.24. Пусть F - поле комплексных чисел, А - матрица с элементами из f и х=[л;1, . . . , XnV. Покажите, что любое линейное вычисление для Ах требует log [det(i4)]/log(2c) шагов, где с - наи-



) Модуль числа а+Ы равен }а+Ь\

больший ИЗ модулей постоянных, входящих в шаги этого вычисления.

*12.25. Покажите, что для преобразования Фурье вектора [xi,. .. ... , Хп] линейное вычисление с постоянными, по модулю не превосходящими 1, требует Va« log rt шагов.

Следующие 6 упражнений касаются минимального числа логических элементов с двумя входами, необходимых для реализации булевой функции.

*12.26. Покажите, что каждую булеву функцию от п переменных можно реализовать с помощью не более rt2" логических элементов с двумя входами.

*12.27. Покажите, что для каждого п существует булева функция от rt переменных, наименьшая реализация которой требует примерно 2"/rt логических элементов с двумя входами.

**12.28. О сложности реализации конкретных булевых функций известно мало. Однако, если ограничиться реализациями на схемах, являющихся деревьями, то можно показать, что для некоторых функций требуется rtVlog п логических элементов. Докажите, что следующее условие достаточно для того, чтобы булева функция от rt переменных требовала для своей реализации не менее rtVlog rt логических элементов.

Условие. Пусть f{xi,... , х„) - булева функция от п переменных. Разобьем множество переменных Xi на 6=rt/log п блоков по log п переменных в каждом. Присвоим значения (О или 1) всем переменным в 6-1 блоках. Это можно сделать 2"/rt способами. Результатом будет функция от log п переменных, совпадающая с одной из 2" функций от log rt переменных. Функция, получаемая в действительности, зависит от значений, присвоенных переменным в b-1 блоках. Пусть Bt - блок переменных, которым значения не присвоены. Если присваивание подходящих значений переменным не из Bt дает порядка 2"/п различных функций от переменных из Bt, причем это выполняется для каждого i, l<t<log п, то любая древовидная схема для f должна содержать rt/log п логических элементов.

**12.29. Пусть rtz=2+log п и {tij\\in/m, 1</</п} - такое множество лг-мерных векторов из О и 1, что каждый вектор Ui имеет среди своих компонент не менее двух единиц. Пусть



/ (-11, 12, • • • , Хп/т,т} - Ф i/

i<i<n/m

© п

1<Л<л/2 1</<т t</<m L Tt такие, что

где t-j - это 1-я компонента вектора tij. Докажите, что в любой реализации функции / с помощью древовидной схемы не менее «Vlog п логических элементов.

*12.30. Постройте другие булевы функции, для реализации которых с помощью древовидных схем требуется (а) п/ и (б) «Vlog п логических элементов.

12.31. Пусть Sj(Xi, ... , Хп) - симметрическая булева функция, принимающая значение 1 тогда и только тогда, когда в точности i переменных Xj имеют значение 1.

(а) Найдите реализацию функции 5з(л;,, ... , х) с минимально возможным числом логических элементов.

(б) Найдите древовидную реализацию для Saixi.....Хп) с минимально возможным числом логических элементов.

**12.32. В примере 12.9 мы доказали, что любая схема, пригодная для вычисления значений произвольного полинома п-й степени, требует п умножений. Постройте конкретный полином п-й степени с вещественными коэффициентами, для вычисления значений которого требуется п умножений.

**12.33. Докажите, что умножение матриц в полукольце положительных целых чисел с операциями MIN и -f требует сп операций, где с - постоянная, 0<с<1.

**12.34. Докажите, что умножение булевых матриц с операциями И и ИЛИ требует операций.

Упр. 12.35 и 12.36 касаются такого представления полинома, при котором значение полинома в точке можно вычислить примерно за л/2 умножений.

**12.35. Пусть р(х) -полином л-й степени, где л - нечетное целое число, большее 1. Запишем его в виде

p{x) = {x-a)q{x)+bx+c.

(а) Покажите, что при подходящем а можно взять Ь=0.

(б) Покажите, что существуют такие и Р;, что р{х) можно представить в виде

р(х) = (х-а,)[{х--а,)[ ... +

и, значит, полином р{х), представленный этими а,- и р,-, можно вычислить за п/2 J +2 умножений.





0 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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 [162] 163 164 165 166 167 168 169 170 171 172 173 174

0.002