Распараллеливание вычислительных алгоритмов

Евдокимова Т.О.
бакалавриат, семестр 7
курс для специализации "Технология программирования"

В первой части курса обсуждаются некоторые базовые методы и парадигмы, которые признаны эффективными для решения широкого круга задач: нахождения префиксных сумм, параллельного префикса, построения выпуклой оболочки, слияния. Это метод перехода по указателю, построение сбалансированного двоичного дерева, метод “разделяй и властвуй”, метод разбиения и конвейерная обработка. Во второй части курса эти базовые методы используются для построения эффективных алгоритмов для некоторых задач на строках и деревьях, для задач поиска, слияния, выбора и сортировки, для задач на графах и задач вычислительной геометрии. Третья часть посвящена нескольким численным задачам: обращение треугольной матрицы, быстрое преобразование Фурье, умножение полиномов и сверка, вычисления с матрицами Теплица, деление полиномов, вычисление значений полиномов и интерполяция.