Информатика. Построение и анализ алгоритмов

2007.Введение.
Архитектура вычислительных систем.
Основные компоненты ЭВМ.
Архитектура процессора.
Оперативная память.
Параллельные вычисления.
Классификация параллельных систем.
Параллельные алгоритмы.
Реализация вычислительных алгоритмов.
Влияние характеристик процессора на скорость вычислений.
Исследование возможностей процессора.
Другие приемы повышения производительности.
Реализация вычислительного алгоритма.
Алгоритмы компьютерной алгебры.
Анализ сложности алгоритмов.
Метод подстановки.
Метод итераций.
Операции над матрицами.
Умножение произвольных матриц.
Умножение двоичных матриц.
Алгоритмы работы с разреженными матрицами.
Операции над многочленами.
Билинейные формы.
Алгоритмы Карацубы и Тоома-Кука вычисления свертки.
Алгоритм Винограда.
Перенос алгоритмов на поля другой природы.
Гнездовые алгоритмы свертки.
Итеративные алгоритмы.
Деление многочленов.
Вычисление значений многочленов.
Интерполяция.
Реализация быстрого алгоритма свертки в виде линейной программы.
Реализация итерированного быстрого алгоритма свертки.
Распараллеливание быстрого алгоритма свертки.
Дискретное преобразование Фурье.
Преобразование Фурье в дискретном и непрерывном случаях.
Общие алгоритмы быстрого преобразования Фурье.
Алгоритмы БПФ в конечных полях.
Применение БПФ для вычисления свертки.
Алгоритм Шёнхаге-Штрассена.
Реализация алгоритма БПФ в виде линейной программы.
Реализация алгоритма БПФ большой размерности.
Реализация параллельного алгоритма БПФ большой размерности.
Операции над целыми числами.
Представление целых чисел в ЭВМ.
Сложение.
Умножение.
Деление.
Возведение в степень.
Основные результаты.
Упражнения.
Задания для курсовых работ.