1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 101
Текст из файла (страница 101)
Покажите, что для вычисления значе- г-ъ г-о ния этого полинома с предварительной обработкой коэффициентов необходимо и достаточно (и+1)(и+2)!2 — 1 умножений. гл. ис нижнив оцвнки числА хриэматичвских опзрлция 12.5. Покажите, что умножение теплицевой (2 х 2)-матрицы (см. упражнения к гл. 6) иа вектор, т. е. требует трех умножений. 12.6. Обобщите упр. 12.5, показав, что для умножения теплицевой (л'кл)-матрицы на вектор необходимо 2л — 1 умножений. Как близко к втой границе вы можете подойти при л=З? "12.7. Можно обобщить алгоритм умножении из равд.
2.6, разбивая каждый из сомножителей на три части и затем вычисляя произведение матрицы на вектор аОО за минимально возможное число умножений. Сколько умножений требуется для решения этой задачи? Приводит ли этот подход к улучшению алгоритма из разд. 2.6? ""12.8. Пусть Р— поле и ап..., а и х„..., хр — непересекающиеся множества формальных переменных. Пусть х=(хь... ..., хр)г, а М вЂ” (гХР)-матРица с элементами из Р(а„..., а„), у которой а столбцов линейно независимы по модулю Р'.
Покажите, что при предварительной обработке вектора х, т. е. когда не учитываются произведения, включающие только х„..., х, вычисление произведения Мх все же требует с/2 умножений. **12.0. Пусть ровно А выражений из множества Р, никакая нетривиальная линейная комбинация элементов которого не равна постоянной, представляют собой одиночные умножения (например, они имеют вид аэЬ, где а и Ь вЂ” формальные переменные); допустим, что а умножений достаточно, чтобы вычислить все выражения из Р.
Покажите, что существует вычисление для Р с а умножениями, А из которых совпадают с теми выражениями из Р, которые можно вычислить с помощью одного умножения. *12.10. Покажите, что для вычисления выражений ас и Ьс+аг( требуется не менее трех умножений. Указание: Воспользуйтесь упр. 12.9. *12.11. Покажите, что для вычисления множества из 2А выражений а,с~ и Ь|с,+а~4, !(!(й, требуется не менее Зй умножений. аэ4 УПРАЖНЕНИЯ которые входят в один л-члеииый кортеж, содержащий ам.
Пусть и и 1=ЕЕ!паз;/. 1=1 1=1 Рассмотрите изменение / по мере выполнения шагов вычисления. *"12,21. Наложим следующее ограничение на видшагов вычисления: в а -Ьйс операция 6 состоит в выборе л/2 формальных переменных нз циклического сдвига л-члеиного кортежа Ь и л/2 формальных переменных из дополнительных позиций в с. Найдите вычисление для множества л-членных кортежей из упр. 12.20, состоящее из 0(л 1оя л) шагов. **12.22. Пусть б — ориентированный ациклический граф с л выделенными истоками (узлами, в которые не входят никакие ребра) и л выделенными выходами (узлами, из которых не выходят никакие ребра). Пусть Х и У' — подмножества истоков и выходов соответственно, а б(Х, У) — подграф, состоящий из всех ориентированных ребер, лежащих на путях из узлов множества Х в узлы множества У.
Пропускной способностью графа 6(Х, У) называется наименьшее число узлов, удаление которых (вместе с входящими и выходящими ребрами) отделяет каждый узел из Х от каждого узла из У, Допустим, что для любых Х и У граф 6(Х, У) обладает пропускной способностью М1 1Ч (!!Х!!, !! У!!). Покажите, что для каждого л существует такой граф б с сп!оп л ребрами, где с — некоторая постоянная.
*"12.23. Сдвига1ои!ей схемой называется такой ориентированный граф с л истоками, занумерованными числами от 0 до л — 1, и л выходами, занумерованными числами от 0 до л — 1, что для каждого з, 0(~л — 1, найдется множество путей, непересекающихся по узлам, которое для каждого 1 содержит путь из истока 1 в выход (1+з) по модулю л. (а) Покажите, что для каждого л существует сдвигающая схема с 2п!оя л ребрами. (б) Покажите, что для сдвигающей схемы асимптотически требуется л !ой л ребер. (в) Покажите, что с помощью сдвигающей схемы можно вычислить транспонированную матрицу. Определение.
Пусть г' — поле и х„ ..., х †формальн переменные. Линейным вычислением называются последовательность шагов вида а и-),Ь+Х,с, где а — переменная, Ь и с — переменные или формальные переменные, а )11 и ), — элементы из г" (называемые постоянными). "*12.24. Пусть г — поле комплексных чисел, А — матрица с элементами из г и х=!х„..., х„!т. Покажите, что любое линейное вычисление для Ах требует 1ой !йе1(А))/!оя(2с) шагов, где с — наи- ГЛ. ПА НИЖНИЕ ОЦЕНКИ ЧИСЛА АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ (б) Покажите, что существует вычисление, минимальное по числу умножений, в котором каждое умножение производится между линейной функцией от а„а„...
и линейной функцией от Ьн Ь„.... (Заметьте, что зто утверждение не верно, если ограничиться случаем, когда основное кольцо коммутативно.) (в) Пусть разрешаются более общие вычисления, а именно вычисления с делениями. Покажите, что существует вычисление, минимальное по числу мультипликативных операций, которое не использует делений. *" 12.18. Пусть )т — некоммутативиое кольцо и а, Ь, х — векторы- столбцы из формальных переменных (ан..., а )Г, (ьн..., ь„!Г, (хн..., хрР' соответственно. Пусть Х вЂ” матрица, элементами которой служат линейные суммы нз х,,..., хр.
Из упр. !2.17 следует, что вычисление множества билинейных форм (агХ)Г можно представить в виде М(Р 'Ех), где М, Р и Я вЂ” матрицы с элементами из Р. Определим левое двойственное множество в2яражений для (а Х)г как (Ь Х )Г и определим вычисление, Р-двойственное к вычислению М(Ра.ЯХ), как РГ(МГЬ 9х). Докажите, что вычисление, Р-двойственное к любому вычислению для (аГХ)т, вычисляет левое двойственное множество выражений для (а"Х)Г. "12.19. Докажите, что минимальное число умножений, необходимое для умножения (тХН)-матрицы на (пхр)-матрицу над некоммутативным кольцом, то же, что и для умножения (ПХт)-матрицы на (т х р)-матрицу. Укозанае: Воспользуйтесь упр.
12.18. До сих пор в упражнениях содержался материал, относящийся к нижним границам для числа арифметических операций. В последующих упражнениях содержится материал более общего характера. Упр. 12.20 — 12.23 касаются транспонирования матриц. Для 1(1, 1(а пусть аы — формальные переменные. Рассмотрим модель вычислений, в которой каждая переменная представляет собой нчленный кортеж формальных переменных. Шаг а — Ьйс такого вычисления присваивает и-членному кортежу а формальные переменные, выбранные из Ь или с.
Эти и-членные кортежи Ь и с не меняются. "12.20. Докажите, что любое вычисление множества а-членных кортежей ((а2и ..., а„,)11<1<а) по множеству входов ((ан,..., а, )~1к (е-.п) требует не менее и 1од и шагов. Указание: Для каждых 1 и 1 пусть зм обозначает максимальное число формальных переменных с нижним индексом 1, упя«жнвния которые входят в один л-членный кортеж, содержащий аы. Пусть л л !ода, . 1=1!=! Рассмотрите изменение / по мере выполнения шагов вычисления, "*12.21.
Наложим следующее ограничение на вид шагов вычисления: в а -ЬОс операция Осостоитввыборе л/2 формальных переменных из циклического сдвига л-членного кортежа Ь ил/2 формальных переменных из дополнительных позиций в с. Найдите вычисление для множества л-членных кортежей из упр. 12.20, состоящее из 0(л !оя л) шагов. **12.22. Пусть 6 — ориентированный ациклическнй граф с л выделенными истоками (узлами, в которые не входят никакие ребра) и л выделенными выходами (узлами, из которых не выходят никакие ребра). Пусть Х и У вЂ” подмножества истоков и выходов соответственно, а 6(Х, У) — подграф, состоящий из всех ориентированных ребер, лежащих на путях из узлов множества Х в узлы множества У. Пропускной способностью графа 6(Х, )') называется наименьшее число узлов, удаление которых (вместе с входящими и выходящими ребрами) отделяет каждый узел из Х от каждого узла из У.
Допустим, что для любых Х и У' граф 6(Х, У) обладает пропускной способностью М1М (!(Х!(, (!)'!!). Покажите, что для каждого л существуег такой граф 6 с сл1ой л ребрами, где с — некоторая постоянная. ««12.23. Сдвигаюи!ей схемой называется такой ориентированный граф с л истоками, занумерованными числами от 0 до л — 1, и л выходами, занумерованными числами от 0 до л — 1, что для каждого з, 0(з~л — 1, найдется множество путей, непересекающихся по узлам, которое для каждого 1 содержит путь из истока ! в выход (!+з) по модулю л.
(а) Покажите, что для каждого л существует сдвигающая схема с 2л 1оя л ребрами. (б) Покажите, что для сдвигающей схемы асимптотически требуется л 1од л ребер. (в) Покажите, что с помощью сдвигающей схемы можно вычислить транспонированную матрицу. Определение. Пусть à — поле и х„..., х„— формальные переменные. Линейным вычислением называются последовательность шагов вида а ~ — ).,Ь+),с, где а — переменная, Ь и с — переменные или формальные переменные, а ), и 1., — элементы из Е (называемые постоянными), «*12.24. Пусть г" — поле комплексных чисел, А — матрица с элементами из г и х=(х,,..., х„Р. Покажите, что любое линейное вычисление для Ах требует!оя !йе1(А))/!оя(2с) шагов, где с — наи- гл.
цс нижниа оцннки числа лвифматичнских опврацип больший из модулей ') постоянных, входящих в шаги этого вычис- ления. *12.25. Покажите, что для преобразования Фурье вектора [х„... ..., ха] линейное вычисление с постоянными, по модулю не превосходящими 1, требует'/,п 1ой и шагов, Следующие б упражнений касаются минимального числа логических элементов с двумя входами, необходимых для реализации булевой функции. *12.26.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
