Быстрое преобразование Фурье и многочлены, Кульков А., 2017

Быстрое преобразование Фурье и многочлены, Кульков А., 2017.

Фрагмент из книги:
Метод Карацубы. Рассмотрим такую распространённую операцию как умножение двух чисел. Со школы все знают алгоритм, работающий за О(n2): умножение в столбик. Долгое время предполагалось, что ничего быстрее придумать нельзя. Первым эту гипотезу опроверг Карацуба, хотя считается, что преобразование Фурье в своих работах использовал ещё Гаусс.




Применения и вариации преобразования.
В обоих случаях мы предполагаем, что вне допустимых индексов последовательности равны нулям. Корреляцию можно интерпретировать двумя способами. С одной стороны, это коэффициент в произведении A(х) • В(х-1), т.е. сдвинутая свёртка первой последовательности и развёрнутой второй. С другой стороны, dk - в точности скалярное произведение последовательности аi и отрезка последовательности bj, начинающегося в позиции k. Именно свёртка и корреляция являются теми величинами, которые чаще всего нужно считать в задачах на преобразование Фурье.

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

Содержание.
1. Быстрое умножение.
Метод Карацубы.
Умножение многочленов.
Интерполяция.
Дискретное преобразование Фурье.
Схема Кули-Тьюки.
Обратное преобразование.
Интерлюдия.
2. Применения и вариации преобразования.
Свёртки и корреляции.
Преобразование в кольце по модулю.
Chirp Z-transform.
Одновременное преобразование вещественных многочленов.
Умножение но произвольному модулю.
Многомерное преобразование Фурье.
Преобразование Уолша-Адамара и другие свёртки.
Метод Ньютона для функций над многочленами.
Разделяй и властвуй.
Деление и интерполяция.
3. Упражнения.
Рюкзак.
Степенной ряд.
Общая схема Кули-Тьюки.
Арифметические прогрессии.
Расстояние между точками.
Сопоставление шаблонов.
Линейные рекурренты.
Степень многочлена.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Быстрое преобразование Фурье и многочлены, Кульков А., 2017 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск.




Теги: учебник по программированию :: программирование :: Кульков