Список лекций по курсу «Вычислительные алгоритмы»

(2010 год)

Лекция 1. Алгоритмы и их сложности. Простейшая модель вычислений: детерминированная машина Тьюринга. Труднорешаемые задачи. Задача о коммивояжере. Экспоненциальное время и экспоненциальное пространство. Задача распознавания образов.

Лекция 2. Недетерминированная машина Тьюринга. Классы P и NP. Языки и задачи. NP полнота задачи выполнимости. Подходы к решению NP полных задач. Иерархия задач по сложности.

Лекция 3. Быстрые алгоритмы, основанные на стратегии дублирования. Умножение полиномов. Быстрые алгоритмы сортировки. Алгоритм Штрассена для умножения матриц.

Лекция 4. Дискретное преобразование Фурье (ДПФ) в коммутативных кольцах, его свойства. Связь ДПФ с полиномами. Теорема о свертке.

Лекция 5. Быстрые алгоритмы дискретного преобразования Фурье (БПФ): алгоритм Кули-Тьюки, алгоритм Гуда-Томаса.

Лекция 6. Алгоритм Шенхаге-Штрассена для умножения целых чисел.

Лекция 7. Задача на собственные значения. Метод прямых итераций. Метод обратных итераций со сдвигом.

Лекция 8. Матрицы вращений Гивенса. Умножение на матрицы Гивенса. Алгоритм Якоби поиска собственных значений. Стратегии перебора индексов.

Лекция 9. Преобразование матрицы к трехдиагональной форме. Рекуррентный метод поиска собственных значений трехдиагональных матриц.

Литература:

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов, Москва, Мир, 1979.
2. Блэйхут Р.  Быстрые алгоритмы цифровой обработки сигналов, Москва, Мир, 1989.
3. Голуб Дж., Ван Лоун Ч. Матричные вычисления, Москва, Мир, 1999.
4. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры.