Алгоритмы - построение и анализ (1021735), страница 194
Текст из файла (страница 194)
30.5. Она начинается с поразрядной обратной перестановки исходных значений, затем следует 18 и этапов, на каждом из которых параллельно производится и/2 преобразований бабочки. Таким образом, глубина схемы составляет 6 (18 п). На рисунке каждое преобразование бабочки получает в качестве исходных значения, поступающие по двум проводам, вместе с поворачивающим множителем, и передает полученные значения на два выходящих провода. Различные этапы каскада преобразований бабочки нумеруются в соответствии с итерациями 'Интересные реаяизаиии реверса битов рассматриваются в разделе 7.1 книги Г.
Уоррен. Алгоритмические трюки для программистов. — Мл Издательский дом "Вильямс", 2003. — Прим. ред. Часть Ч11. Избранные темы 948 Рис. 30.5. Схема процедуры Рлвльш. РГТ, вычисляющей БПФ при и = 8. самого внешнего цикла процедуры 1тивлт~ув РРТ. Только верхний и нижний провода, проходя через "бабочку", участвуют в вычислениях; провода, проходящие через середину "бабочки", никак не взаимодействуют с ней, и их значения также не меняются данной бабочкой". Например, верхняя бабочка на этапе 2 ничего не делает с проводом 1 (которому соответствует переменная вывода, обозначенная уз); ее переменные ввода и вывода находятся на проводах 0 и 2 (обозначенных уо и уз, соответственно). Для вычисления БПФ для п переменных ввода требуется схема глубиной О (18 п), содержащая О (и 18 и) преобразований бабочки.
Левая часть схемы Рлклы.а. РРТ выполняет поразрядно обратную перестановку, а остальная часть представляет собой итеративную процедуру 1тннлт~че РРТ. Поскольку при каждом повторении внешнего цикла 1ог выполняется п/2 независимых преобразований бабочки, в данной схеме они выполняются параллельно. Значение з в каждой итерации 1тивлт~чи РРТ соответствует каскаду преобразований бабочки, показанному на рис. 30.5. В пределах этапа з = 1, 2,..., 18 и имеется и/2' групп преобразований бабочки (соответствующих различным значениям /с процедуры 1тякАт~че РРТ), в каждой группе выполняется 2' ~ операций (соответствующих различным значениям з процедуры 1тикАтюн РРТ). Преобразования бабочки, показанные на рис.
30.5, соответствуют преобразованиям во внутреннем цикле (строки 9-12 процедуры 1тияАт~чн РРТ). Заметим также, что используемые в "бабочках*' поворачивающие множители соответствуют Глава 30. Полиномы н быстрое преобразование Фурье 949 поворачивающим множителям, используемым в процедуре 1тнклт~че РРТ: на этапе з используются значения ~„„ь~,„,..., ю„,, где т = 2 . о 1 ш/2 — 1 д Упражнения 30.3-1. Покажите, как процедура 1тнклт1чн РРТ вычисляет ДПФ исходного вектора (0,2,3,-1,4,5,7,9).
30.3-2. Покажите, как реализовать алгоритм БПФ, в котором обратная перестановка битов выполняется в конце, а не в начале процесса вычислений. (Указание: рассмотрите обратное ДПФ.) 30.3-3. Сколько раз процедура 1тнкАт|чп РРТ вычисляет поворачивающие множители на каждом этапе? Перепишите процедуру 1тнкАт]чя РРТ так, чтобы поворачивающие множители на этапе з вычислялись только 2' 1 раз * 30.3-4. Предположим, что сумматоры в преобразованиях бабочки схемы БПФ иногда дают сбои, приводящие к нулевому результату независимо от подаваемых на вход значений. Предположим, что сбой произошел в точности в одном сумматоре, однако не известно, в каком именно. Опишите, как можно быстро выявить неисправный сумматор путем тестирования всей БПФ-схемы с помощью различных вводов и изучения выводов.
Насколько эффективен этот метод? Задачи 30-1. Умножение посредством декомпозиции а) Покажите, как умножить два линейных полинома ах + Ь и сх + + и', используя только три операции умножения. (Указание: одно из умножений (а+ Ь) (с+ с~).) б) Приведите два алгоритма декомпозиции для умножения полиномов степени не выше и, время выполнения которых О (и'кз). В первом алгоритме следует разделить коэффициенты исходного полинома на старшие и младшие, а во втором — на четные и нечетные. в) Покажите, что два и-битовых целых числа можно умножить за О (в~к~) шагов, где каждый шаг оперирует с однобнтовыми значениями, количество которых не превышает некую константу.
30-2. Матрицы Теплица Матрицей Теплица (Тоерйх шаспх) называется матрица А = (ач ) размером и х и, в которой а; = а; з ~ 1 для г, ( = 2, 3,..., и. Часть Ч11. Избранные темы 950 а) Всегда ли сумма двух матриц Теплица является матрицей Теплица? Что можно сказать об их произведении? б) Каким должно быть представление матриц Теплица, чтобы сложение двух матриц Теплица размером п х и можно было выполнить за время О (и)? в) Предложите алгоритм умножения матрицы Теплица размером и х х и на вектор длины п со временем работы 0(п1бп).
Воспользуйтесь представлением, полученным при решении предыдущего пункта данной задачи. г) Предложите эффективный алгоритм умножения двух матриц Теплица размером 11 х и и оцените время его выполнения. 30-3. Многомерное быстрое преобразование Фурье Можно обобщить одномерное дискретное преобразование Фурье, определенное уравнением 130.8), на д-мерный случай. Пусть на вход подается Ы-мерный массив А = (а1,;,; ), размерности п1, пз,..., пл которого удовлетворяют соотношению п1из па = п.
Определим д-мерное дискретное преобразование Фурье следующим образом: п1 — 1 па — 1 па — 1 1!ь1 321а... Зайа уь,,ь..,ь, = ~~ ~~ " ~~ а..,...„м„, ы., "ы 1,=О Ь=О За=О для 0 < )с1 < п1, 0 < йз < пз,..., 0 < йн < пн. а) Покажите, что можно вычислить и'-мерное дискретное преобразование Фурье путем поочередного вычисления одномерных ДПФ. Таким образом, сначала вычисляется п/п1 отдельных одномерных ДПФ вдоль первого измерения.
Затем, используя результат ДПФ вдоль первого измерения в качестве ввода, вычисляется и/пз одномерных ДПФ вдоль второго измерения. Используя этот результат в качестве ввода, вычисляется и/из отдельных ДПФ вдоль третьего измерения и т.д., до измерения д. б) Покажите, что порядок следования измерений не имеет значения, т.е.
можно вычислять И-мерное ДПФ путем вычисления одномерных ДПФ для каждого из и' измерений в произвольном порядке. в) Покажите, что если каждое одномерное ДПФ вычислять с помощью быстрого преобразования Фурье, то суммарное время вычисления и'-мерного ДПФ составляет О (и 1я п) независимо от 11. Глава 30. Полиномы и быстрое преобразование Фурье 951 30-4. Вычисление всех производных полинома в определенной точке Пусть задан полипом А(х) степени не выше п; г-я производная этого полинома определяется формулой А(х) если 8 = О, А(0(х) = 4~~А!' ~1(х) если 1 < 8 < п — 1, 0 если $ > и.
Пусть заданы коэффициентное представление (ао, аз,..., а„») полинома А (х) и некая точка хо. Требуется найти А!'! (хо) для т = О, 1,... п — 1. а) Пусть заданы коэффициенты Ьо, Ьм..., Ь„з, такие что »» — 1 А(х) = ,') 63(х-хо)' Покажите, как вычислить А!'1 (хо) для г = О, 1,... п — 1 за время 0 (п). б) Объясните, как найти Ьо, Ьы..., Ь„~ за время 0 (п1кп), если даны значениЯ А (хо + ь»иь) длЯ й = О, 1,...
п — 1. в) Докажите, что »»-1 ь„»»-1 А(,»- „") = 1 — ", т»(яд».-я), т=о 3=0 гдеУЦ)=от Я,а о хо ~/( — 1)! если — (п — 1) < 1 < О, 0 если 1 < 1 < (п — 1). г) Объясните, как вычислить А (хо+ ь»„") для /с = 0,1,...п — 1 за время 0 (п 1к п). Обоснуйте, что все нетривиальные производные полинома А (х) в точке хо можно вычислить за время 0 (п 1я п). 30-5.
Вычисление полинома в нескольких точках Как отмечалось, задачу вычисления полинома степени не выше п в единственной точке с помощью схемы Горнера можно решить за время 0 (п). Мы также показали, что с помощью БПФ такой полипом можно вычислить во всех п комплексных корнях единицы за время 0 (п 1я п). Теперь покажем, как вычислить полином степени не выше п в произвольных п точках за время 0 (п 1я~ п). Часть Чй.
Избранные темы 952 Для этого мы воспользуемся тем фактом, что при делении одного такого полинома на другой остаток можно вычислить за время 0 (и1яи) (этот результат мы принимаем без доказательства). Например, остаток при делении Зхз + хз — Зх + 1 на хз + х + 2 равен (Зх +х — Зх+ 1) пюс1 (х + х+ 2) = — ?х+ 5. Пусть заданы коэффициентное представление полинома А (х) = ,'>',~", о аьх" и п точек хо, хы..., х„п и нам необходимо вычислить п значений А (хо), А (х1),..., А (х„1). Для 0 < г < 1 < и — 1 определим полиномы РЗ (х) = 11ь,. (х — хь) и ь)1 = А (х) пзос1 Р; (х). Заметим, что при этом 6); (х) имеет степень не выше 1 — г. а) Докажите, что А (х) шод (х — г) = А(з) в любой точке ж б) Докажите, что (~ьь (х) = А (хь), а Яо,„~ (х) = А (х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
