Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 194
Текст из файла (страница 194)
30-2. Матрицы Теплица Матрицей Теплица (Тоерйх шаспх) называется матрица А = (ач ) размером и х и, в которой а; = а; з ~ 1 для г, ( = 2, 3,..., и. Часть Ч11. Избранные темы 950 а) Всегда ли сумма двух матриц Теплица является матрицей Теплица? Что можно сказать об их произведении? б) Каким должно быть представление матриц Теплица, чтобы сложение двух матриц Теплица размером п х и можно было выполнить за время О (и)? в) Предложите алгоритм умножения матрицы Теплица размером и х х и на вектор длины п со временем работы 0(п1бп).
Воспользуйтесь представлением, полученным при решении предыдущего пункта данной задачи. г) Предложите эффективный алгоритм умножения двух матриц Теплица размером 11 х и и оцените время его выполнения. 30-3. Многомерное быстрое преобразование Фурье Можно обобщить одномерное дискретное преобразование Фурье, определенное уравнением 130.8), на д-мерный случай. Пусть на вход подается Ы-мерный массив А = (а1,;,; ), размерности п1, пз,..., пл которого удовлетворяют соотношению п1из па = п.
Определим д-мерное дискретное преобразование Фурье следующим образом: п1 — 1 па — 1 для 0 < )с1 < п1, 0 < йз < пз,..., 0 < 1сн < пн. а) Покажите, что можно вычислить и'-мерное дискретное преобразование Фурье путем поочередного вычисления одномерных ДПФ. Таким образом, сначала вычисляется п/п1 отдельных одномерных ДПФ вдоль первого измерения. Затем, используя результат ДПФ вдоль первого измерения в качестве ввода, вычисляется и/пз одномерных ДПФ вдоль второго измерения.
Используя этот результат в качестве ввода, вычисляется и/из отдельных ДПФ вдоль третьего измерения и т.д., до измерения д. б) Покажите, что порядок следования измерений не имеет значения, т.е. можно вычислять И-мерное ДПФ путем вычисления одномерных ДПФ для каждого из и' измерений в произвольном порядке. в) Покажите, что если каждое одномерное ДПФ вычислять с помощью быстрого преобразования Фурье, то суммарное время вычисления и'-мерного ДПФ составляет О (и 1я п) независимо от 11. Глава 30.
Полиномы и быстрое преобразование Фурье 951 30-4. Вычисление всех производных полинома в определенной точке Пусть задан полипом А(х) степени не выше п; г-я производная этого полинома определяется формулой А(х) если 8 = О, А01(х) = 4~~АО ~1(х) если 1 < 8 < п — 1, 0 если $ > и. Пусть заданы коэффициентное представление (ао, аз,..., а„») полинома А (х) и некая точка хо.
Требуется найти А01 (хо) для т = О, 1,... п — 1. а) Пусть заданы коэффициенты Ьо, Ьм..., Ь„з, такие что »» — 1 А(х) = ,') 63(х-хо)' Покажите, как вычислить А01 (хо) для г = О, 1,... п — 1 за время 0 (п). б) Объясните, как найти Ьо, Ьы..., Ь„~ за время 0 (п1кп), если даны значениЯ А (хо + ь»иь) длЯ й = О, 1,... п — 1. в) Докажите, что »»-1 ь„»»-1 А(,»- „") = 1 — ", т»(яд».-я), т=о 3=0 гдеУЦ)=от Я,а о хо ~/( — 1)! если — (п — 1) < ! < О, 0 если 1 < 1 < (п — 1).
г) Объясните, как вычислить А (хо+ ь»„") для /с = 0,1,...п — 1 за время 0 (п !к п). Обоснуйте, что все нетривиальные производные полинома А (х) в точке хо можно вычислить за время 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 — г.
а) Докажите, что А (х) шод (х — г) = А(з) в любой точке ж б) Докажите, что (~ьь (х) = А (хь), а Яо,„~ (х) = А (х). в) Докажите, что для г < Й < 1 справедливы соотношения Я;ь (х) = = Щ (х) шод Рьь (х) и Яь (х) = Я; (х) гпос1 Рь (х). г) Предложите алгоритм вычисления А(хо), А(х1),..., А (х„1) со временем работы О (и 15~ и). 30-6. БПФ с использованием модульной арифметики Согласно определению, при вычислении дискретного преобразования Фурье требуется использовать комплексные числа, что может привести к потере точности из-за ошибок округления.
Для некоторых задач известно, что ответы содержат только целые значения, поэтому желательно использовать вариант БПФ, основанный на модульной арифметике, чтобы гарантировать, что ответ вычисляется точно. Примером такой задачи является умножение двух полиномов с целыми коэффициентами. В упражнении 30.2-6 предлагался подход, в котором используются модули длиной й (и) битов для вычисления ДПФ по п точкам. В данной задаче предлагается иной подход, в котором используются модули более подходящей длины 0(1яи); для его понимания следует ознакомиться с материалами главы 31. Предполагается, что и является степенью 2.
а) Пусть требуется найти наименьшее значение lс, такое что р = йп+ + 1 является простым числом. Предложите простое эвристическое доказательство того, что й примерно равно 1я п. (Значение 1с может быль больше или меньше, но в среднем нам придется рассмотреть 0 (1я п) возможных значений й.) Как ожидаемая длина р соотносится с длиной п? Предположим, что д является генератором Ер, и пусть ю = д" шой р.
Глава 30. Полиномы и быстрое преобразование Фурье 953 б) Докажите, что ДПФ и обратное ДПФ являются вполне определенными обратными операциями по модулю р, если в качестве в используется главное значение корня и-й степени из единицы. в) Докажите, что БПФ и обратное ему преобразование по модулю р могут выполняться за время О (п18п), если при этом операции со словами длиной О (18 и) выполняются за единичное время. (Значения р и тс считаются заданными.) г) Вычислите ДПФ по модулю р = 17 для вектора (0,5,3,7,7,2,1,6).
Учтите, что генератором Е;т является д = 3. Заключительные замечания Подробное рассмотрение быстрого преобразования Фурье содержится в книге Ван Лона (ЧапЬоап) [303]. В работах Пресса (Ргезз), Фланнери (Р1аппегу), Тукольски (Тецко1з1су) и Ветгерлинга (Чепегйпй) [248, 249] предлагается хорошее описание быстрого преобразования Фурье и его приложений. Прекрасное введение в обработку сигналов, область широкого применения БПФ, предлагается в работах Оппенгейма (ОррепЬепп) и Шафера (ЯсЬаГег) [232], а также Оппенгейма и Уиллски (М11з1су) [233]. В книге Оппенгейма и Шафера также описаны действия в случае, когда п не является целой степенью 2.
Анализ Фурье не ограничивается одномерными данными. Он широко используется в обработке изображений для анализа данных в двух и более измерениях. Многомерные преобразования Фурье и их применение в обработке изображений обсуждаются в книгах Гонзалеса (Попка!ех) и Вудса (%оооз) [127] и Пратта (Ргап) [246], а в книгах Толимьери (То!пшеп), Эн (Ап) и Лу (Ьп) [300] и Ван Лона (Чап Ьоап) [303] обсуждаются математические аспекты многомерных быстрых преобразований Фурье.
Изобретение БПФ в середине 1960-х часто связывают с работой Кули (Соо!е!) и Таки (Ти1сеу) [68]. На самом деле БПФ неоднократно изобреталось до этого, но важность его в полной мере не осознавалась до появления современных компьютеров. Хотя Пресс, Фланнери, Тукольски и Веттерлинг приписывают открытие данного метода Рунге (Кцпйе) и Кенигу (Кбшй) в 1924 году, Хейдеман (НеЫешап), Джонсон (1оЬпзоп) и Баррус (Вштиз) [141] в своей статье утверждают, что БПФ открыл еще Гаусс (Овика) в 1805 г.
ГЛАВА 31 Теоретико-числовые алгоритмы Раньше теория чисел рассматривалась как элегантная, но почти бесполезная область чистой математики. В наши дни теоретико-числовые алгоритмы нашли широкое применение. В определенной степени это произошло благодаря изобретению криптографических схем, основанных на больших простых числах.
Применимость этих схем базируется на том, что имеется возможность легко находить большие простые числа, а их безопасность — на отсутствии простой возможности разложения на множители произведения больших простых чисел. В этой главе изложены некоторые вопросы теории чисел и связанные с ними алгоритмы, на которых основаны важные приложения. В разделе 31.1 представлено введение в такие основные концепции теории чисел, как делимость, равенство по модулю и однозначность разложения на множители. В разделе 31.2 исследуется один из самых старых алгоритмов: алгоритм Евклида, предназначенный для вычисления наибольшего общего делителя двух целых чисел. В разделе 31.3 представлен обзор концепций модульной арифметики.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
