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

Т. О. Евдокимова
бакалавриат, семестр 7

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