Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 212
Текст из файла (страница 212)
Пусть на вход подается Н-мерный массив А = (а...,„) с РазмеРностЯми им из,..., пе, котоРые УДовлетвоРЯют соотношению п1из пв = п. Определим Н-мерное ДПФ следующим образом: 31 Ь1,ззьз... 3аьа "вя,,яз Ь„= ~ ~ . ~' анд,, о ы„, ',з у,=о у,=о для 0 < Ь1 < ип 0 < йз < пз,..., 0 < йв < ие.
а Покажите, что можно вычислить Н-мерное ДПФ путем поочередного вычисления одномерных ДПФ. Таким образом, сначала вычисляется и~из отдельных одномерных ДПФ вдоль первого измерения. Затем, используя результат ДПФ вдоль первого измерения в качестве входных данных, вычисляется и/из одномерных ДПФ вдоль второю измерения. Используя этот результат в качестве входных данных, вычисляется и/пз отдельных ДПФ вдоль третьего измерения, и так до последнего измерения а'.
б. Покажите, что порядок следования измерений не имеет значения, хе. что можно вычислять Н-мерное ДПФ путем вычисления одномерных ДПФ для каждого из б измерений в произвольном порядке. в. Покажите, что если каждое одномерное ДПФ вычислять с помощью быстрого преобразования Фурье, то суммарное время вычисления Ы-мерного ДПФ составляет 0(п 1я п) независимо от Н. Зб.4.
Вычисление всех производных нолннанв в точке Пусть задан полинам А(х) с границей степени и; 1-я производная этого поли- нома определяется формулой А(х), если г = О, АО)(х) — „~ АО П(х), если 1 < 1 < и — 1, О, если 1 > и. Пусть заданы представление в форме коэффициентов (ас, аы, а„1) полино- ма А(х) и некоторая точка хс. Требуется найти АОО(хс) для г = 0,1,...,и — 1. о.
Пусть заданы коэффициенты Ьс, Ь|,,.,,Ь„и такие, что А(х) = ~' Ь (х — хс)' Покажите, как вычислить АО>(хс) для г = О, 1,..., п — 1 за время 0(п). 9б5 Глава 50. Поланаыы а быстрое ареобразованае Фурье б. Поясните, как найти Ьс, Ьы..., Ь„1 за время 0(п 1к и) при заданных значениях А(хо+и„") для lс = 0,1,...,п — 1. е.
Докажите, что о — 1 ь о — 1 А(хо + а4) = ~~~ — ", ~ Я)д(г — у) =о у=о где Д5) = а 5), а (1) о т х ~/( — 1)!, если — (и — 1) <1 < О, О, если 1 < 1< и — 1. а Поясните, как вычислить А(хс+ыь) для /с = О, 1,..., и — 1 за время 0(п!ли). Сделайте вывод, что все нетривиальные производные А(х) в точке хс можно вычислить за время 0(п 1й и). Зд.5. Вычисление налнномн в нескольких иеочккх Как уже говорилось, задачу вычисления полинома с границей степени и в единственной точке можно решить с помощью схемы Горнера за время 0(п). Мы также показали, как с помощью БПФ такой полипом можно вычислить во всех и комплексных корнях единицы за время 0(п!кп). Теперь покажем, как вычислить полипом с границей степени и в произвольных и точках за время 0(п1йз и).
Для зтого будем считать, что остаток при делении одного такого полинома на другой можно вычислить за время О(п)кп) (зтот результат мы принимаем без доказательства). Например, остаток при делении Зхз + х — Зх + 1 на х + х + 2 равен (Зхз + х — Зх + 1) шос( (хз + х + 2) = — 7х + 5 . Пусть заданы представление полинома А(х) = 2 ь ' аьх" в форме козффициентов и и точек хс,хм.,.,х„1 и пусть необходимо вычислить п значений А(хс),А(хз),...,А(х„1). Для О < 1 < 5' < и — 1 определим полиномы Р, (х) = Пол з(х — хь) и Я, (х) = А(х) шос) Ру(х).
Заметим, что полинам Я,"(х) имеет степень не выше 5 — г. и. Докажите, что А(х) щи (х — з) = А(з) для любой точки е. б. Докажите, что Яьь(х) = А(хь) и что Яс „1(х) = А(х). в. Докажите, что для 1 < /с < 5 справедливы соотношения ь,чь(х) = Я; (х) шос( Рьь(х) и фу(х) = Я; (х) шос( Рь (х).
а Предложите алгоритм вычисления А(хс), А(х1),..., А(х„1) за время О(п!йзп). 966 Часть гтв Иэбранные тека 30.6. БПФ с использованием модульной арифметики Согласно определению при вычислении дискретного преобразования Фурье требуется использовать комплексные числа, что может привести к потере точности из-за ошибок округления.
Для некоторых задач известно, что ответы содержат только целые значения, поэтому желательно использовать вариант БПФ, основанный на модульной арифметике, чтобы гарантировать, что ответ вычисляется точно. Примером такой задачи является умножение двух полиномов с целыми коэффициентами. В упр. 30.2.6 предлагался подход, в котором используются модули длиной П(п) бит для вычисления ДПФ по и точкам. В данной задаче предлагается иной подход, в ютором используются модули более подходящей длины 0(18 п); для его понимания следует ознакомиться с материалом главы 31.
Предполагается, что и является степенью 2. а. Предположим, что требуется найти наименьшее значение (с, такое, что р = (сп + 1 является простым числом. Предложите простое эвристическое доказательство того, что lс примерно равно 18 и. (Значение )с может быть больше или меньше, но в среднем придется рассмотреть 0(18 и) возможных значений к.) Как ожидаемая длина р соотносится с длиной п7 Предположим, что д является генератором Щ, и пусть ю = дь шос) р. й.
Докажите, что ДПФ и обратное ДПФ являются вполне определенными обратными операциями по модулю р, если в качестве гс используется главное значение корня и-й степени из единицы. в. Покажите, как БПФ и обратное ему преобразование по модулю р могут выполняться за время 0(п 18 и), если при этом операции со словами длиной 0(18 и) бит выполняются за единичное время. (Значения р и ю считаются заданными.) г. Вычислите ДПФ по модулю р = 17 для вектора (0,5,3,7,7,2,1,0). Учтите, что генератором 317 является д = 3, Заключительные замечании Подробное рассмотрение БПФ можно найти в книге Ван Лона (Уап Боап) (341). В работах Пресса (Ргевв), Тукольски (Тец(со(вку), Веттерлинга (Чепегйпй) и Фланнери (Р(аппегу) [281,282) имеется хорошее описание БПФ и его приложений.
Прекрасное введение в обработку сигналов — область широкого применения БПФ вЂ” предлагается в работах Оппенгейма (Орреллепп) и Шафера (БсЬаГег) (264) и Оппенгейма и Уиллски (%11!яку) (265]. В книге Оппеигейма и Шафера также описана работа в ситуации, когда и ие является целой степенью 2. Анализ Фурье не ограничивается одномерными данными.
Он широко используется в обработке изображений для анализа данных в двух и более измерениях. Гаева ЗЦ Поаиноиы и быстрое нреобравование Фурье 9бу Многомерные преобразования Фурье и их применение в обработке изображений обсуждаются в книгах Гонзалеса (Оолха!ех) и Вудса (%оома) [145] и Пратта (Ргап) [279], а в книгах Толимьери (То!пшеп), Эн (Ап) и Лу (1ц) [336] и Ван Лона (Чап 1.оап) [341] обсуждаются математические аспекты многомерных БПФ.
Изобретение БПФ в середине 1960-х годов часто связывают с работой Кули (Соо1е1) и Таки (Тп3сеу) [75], На самом деле БПФ неоднократно изобреталось до этого, но важность его в полной мере не осознавалась до появления современных компьютеров. Хотя Пресс, Тукольски, Ветгерлинг и Фланнери приписывают открытие данного метода Рунге (Кппйе) и Кенигу (Коп)й) в 1924 году„Хейдеман (НеЫешап), Джонсон ()оЬпвоп) и Баррус (Вшпьз) [162] в своей статье утверждают, что БПФ открыл еще К.Ф.
Гаусс (С.Е Оапзз) в 1805 г. Фриго (Рпйо) и Джонсон (ЗоЬпяоп) [116] разработали быструю и гибкую реализацию БПФ, названную РРТ% (Тазгез1 Роцпег папвТопп |п йзе %езг — быстрейшее преобразование Фурье на Западе). РРТ% разработано для ситуаций, когда требуется многократное вычисление ДПФ для задач одного и того же размера.
Перед тем как приступить к фактическому вычислению ДПФ, РРТ% вызывает "планировщик", который путем ряда пробных запусков определяет, как наилучшим образом выполнить декомпозицию для данного размера задачи на конкретной машине. РРТ% адаптировано для эффективного использования аппаратного кеша„а когда подзадачи оказываются достаточно малы, РРТ% решает их с помощью оптимизированного линейного кода. Кроме того, РРТ% обладает необычным преимуществом — временем работы сЭ(п 1я и) для любого размера задачи и, даже когда и представляет собой большое простое число.
Хотя стандартное преобразование Фурье предполагает, что входные данные представляют собой равномерно распределенные по временнбй области точки, другие методики могут аппроксимировать БПФ на "неравноудаленных" данных. Обзор таких методов можно найти в статье Вэра (%аге) [346]. Глава 31. Теоретико-числовые алгоритмы Ранее теория чисел рассматривалась как элегантная, но почти бесполезная область чистой математики, но в наши дни теоретико-числовые алгоритмы нашли широкое применение, в большей степени благодаря изобретению криптографических схем, основанных на больших простых числах.
Применимость этих схем базируется на том, что можно легко находить большие простые числа, а их безопасность — на неизвестности эффективного способа разложения на множители произведения больших простых чисел (или решения других связанных задач, таких как вычисление дискретных логарифмов). В этой главе представлены некоторые вопросы теории чисел и связанные с ними алгоритмы, лежащие в основе таких приложений. В разделе 31.1 изложены базовые концепции теории чисел, такие как делимость, равенство по модулю и однозначность разложения на множители. В разделе 31.2 исследуется один из самых старых алгоритмов: алгоритм Евклида, предназначенный для вычисления наибольшего общего делителя двух целых чисел.
В разделе 31.3 представлен обзор концепций модульной арифметики. В разделе 31.4 изучается множество чисел, которые являются кратными заданного числа а по модулю п, н показано, как с помощью алгоритма Евклида найти все решения уравнения ак = Ь (щось и). В разделе 31.5 вы познакомитесь с китайской теоремой об остатках.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
