Реферат: Быстрые алгоритмы
Наименование дисциплины: Быстрые алгоритмы
Направление подготовки: 010200 Математика и компьютерные науки
Квалификация (степень) выпускника: бакалавр
Форма обучения: очная
Автор: к.ф.–м.н , доцент, доцент кафедры алгебры и математической логики С.И.Яблокова.
1. Целями освоения дисциплины "Быстрые алгоритмы" являются:
Овладение быстрыми алгоритмами цифровой обработки сигналов и математическим аппаратом, лежащим в основе разработки таких алгоритмов, формирование практических навыков оценки сложности алгоритмов.
2. Дисциплина входит в вариативную часть цикла Б3. профессиональных дисциплин. Для ее успешного изучения необходимы знания и умения и навыки, приобретенные в ходе освоения таких базовых курсов, как «Алгебра» и «Теория чисел».
В основе быстрых алгоритмов лежит специальная организация массивов данных в виде конечных алгебраических структур (групп, колец, полей), что позволяет применять структурные теоремы алгебры и теории чисел. Использование алгебраических структур позволяет строить алгоритмы, обеспечивающие работу цифровых процессоров в реальном масштабе времени для решения задач, возникающих в таких приложениях, как все виды связи, радиолокация, радиоастрономия, цифровая голография, медицинская электроника и т.д.
3. В результате освоения дисциплины обучающийся должен:
Знать:
основные понятия и определения теории конечных полей, конечных групп, а также основных методов обработки сигналов (линейная и циклическая свертка, дискретное преобразование Фурье и т.п.), формулировки утверждений, методы их доказательства, методы построения быстрых алгоритмов цифровой обработки сигналов. Эти знания необходимы при решении практических задач из разнообразных прикладных областей, таких как обработка и передача данных, создание интегральных схем и др.
Уметь:
решать задачи на построение быстрых алгоритмов вычисления линейной и циклической сверток малых длин, применяя алгоритмы Кука – Тома и Винограда, и дискретного преобразования Фурье; строить и анализировать быстрые алгоритмы дискретного преобразования Фурье с использованием алгоритмов Кули – Тьюки, Рейдера – Бреннера, Гуда – Томаса, Рейдера, Винограда; оценивать сложность полученного алгоритма.
Владеть:
математическим аппаратом, лежащим в основе построения быстрых алгоритмов цифровой обработки сигналов, методами построения таких алгоритмов и методами оценки сложности этих алгоритмов.
4. Общая трудоемкость дисциплины составляет 2 зачетные единицы, 72 часа.
5. Содержание дисциплины:
№ п/п
Раздел дисциплины
1
Введение в быстрые алгоритмы. Матричная запись алгоритма. Матрицы предсложений и постсложений. Цифровой фильтр. Задача фильтрации, Фильтры с конечным импульсным откликом (КИО-фильтры) и авторегрессионные фильтры. Определение линейной свертки и корреляции. Запись через многочлены.
2
Циклическая свертка и ее связь с линейной. Определение дискретного преобразования Фурье (ДПФ). Теорема о свертке. История развития быстрых алгоритмов обработки сигналов..
3
Группа. Кольцо. Поле. Кольцо целых чисел. Характеристика кольца. Кольца многочленов. Кольцо Кольцо с простой характеристикой. Поля Галуа. Расширения, подполя. Характеристика поля. Существование примитивного элемента.
Цикличность группы Китайская теорема об остатках для чисел. Китайская теорема об остатках для многочленов.
4
Вычисление циклической свертки с использованием теоремы о свертке и дискретного преобразования Фурье. Вещественное преобразование Фурье. Одновременное вычисление двух вещественных сверток. Алгоритм Кука – Тома вычисления линейной свертки. Иллюстрация на примере 2x2 – свертки. Матричная форма записи алгоритма. Модификация алгоритма.
5
Алгоритмы Винограда вычисления коротких сверток. Алгоритм Винограда как обобщение метода вычисления сверток с помощью преобразования Фурье. Иллюстрация на примере 3x2 – свертки. Матричная запись алгоритма. Обобщение алгоритма Винограда. Построение алгоритмов коротких линейных сверток: 3x3 – свертка. Сравнение разных алгоритмов вычисления 3x2 – свертки.
6
Вещественные и комплексные свертки. Сложность.
Вычисление произведения многочленов по модулю некоторого многочлена с помощью алгоритма свертки. Сравнение сложности разных алгоритмов.
Построение алгоритмов коротких циклических сверток. Иллюстрация на примере 4 –точечной циклической свертки. Матричная запись. Вычисление над полем вещественных и над полем комплексных чисел. Алгоритм Винограда как метод разложения матриц. Теплицевы матрицы. Теорема об обмене матриц.
7
Свертки в общих кольцах и полях. Сложность алгоритмов свертки. Формализация алгоритмов (к задаче вида ). Ранг матрицы по строкам. Теорема о ранге матрицы по строкам. Ранг матрицы по столбцам. Теорема о ранге по столбцам.
Оценка снизу количества умножений для вычисления линейной свертки. Теоремы об оценке числа умножений в задаче вычисления произведения двух многочленов по модулю третьего.
8
Алгоритм Кули – Тьюки быстрого преобразования Фурье. Оценка сложности алгоритма.
Алгоритмы Кули – Тьюки по малому основанию: БПФ – алгоритм Кули – Тьюки по основанию два с прореживанием по времени, БПФ – алгоритм Кули – Тьюки по основанию два с прореживанием по частоте. Иллюстрация на примере 8 – точечного преобразования. Оценка сложности этих алгоритмов.
Модификация БПФ Рейдера – Бреннера. БПФ – алгоритмы Кули – Тьюки по основанию четыре с прореживанием по времени и по частоте. Матричная запись и оценка сложности.
Алгоритм Гуда – Томаса быстрого преобразования Фурье. Сложность алгоритма.
9
Вычисление преобразования Фурье с помощью свертки. Два способа перехода от преобразования Фурье к свертке: чирп – алгоритм Блюстейна и алгоритм Рейдера для простых чисел. Иллюстрация алгоритма Рейдера в поле Построение 5 – точечного преобразования Фурье с помощью алгоритма Рейдера.
10
Алгоритм Рейдера в случае, когда длина преобразования равна степени нечетного простого числа. Случай, когда длина преобразования равна степени двойки. Иллюстрация на примере 16 – точечного преобразования Фурье.
Алгоритм Винограда для быстрого преобразования Фурье малой длины. Случаи, когда длина преобразования равна:
а) простому числу;
б) степени простого числа;
в) степени двойки.
6. Учебно-методическое и информационное обеспечение дисциплины:
а) основная литература:
1.Яблокова С.И. Введение в быстрые алгоритмы цифровой обработки сигналов: учебное пособие. – Ярославль, ЯрГу, 2009.
б) дополнительная литература:
1.Ван дер Варден Б.Л. Алгебра. – М.: Наука, 1976. – 648с.
2.Берлекэмп Э. Алгебраическая теория кодирования. – М.: Мир, 1971.
3.Макклеллан Дж. Х., Редер Ч.М. Применение теории чисел в цифровой обработке сигналов. – М.: Радио и связь, 1983.
еще рефераты
Еще работы по разное
Реферат по разное
Десятилетие, включающее года с 1960 по 1969
18 Сентября 2013
Реферат по разное
Неотъемлемой чертой повседневной жизни и своеобразным символом новой, постсоветской России стали беспризорные дети
18 Сентября 2013
Реферат по разное
Московской государственной юридической академии им. О. Е
18 Сентября 2013
Реферат по разное
Александр невский (1221?-1263), князь новгородский в 1236-51, великий князь владимирский с 1252. Сын князя Ярослава Всеволодовича
18 Сентября 2013