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

Год выпуска: 2007.
Автор: Трифонов П. Ф.
Формат: PDF, DOC.

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