Параллельные алгоритмы; алгоритмы на строках

Александр Тискин (University of Warwick) 20 октября в CS клубе прочитает две лекции на тему "Полулокальное сравнение строк". А также проведет мини-курс, 21 октября, посвященный теме "Эффективные параллельные алгоритмы: методика BSP". Аннотация "Полулокальное сравнение строк": Вычисление наибольшей общей подпоследовательности (longest common subsequence, LCS) двух строк - одна из классических алгоритмических задач. Во многих приложениях необходимо обобщение этой задачи, которое мы называем полулокальной LCS (semi-local LCS). В этом случае требуется вычислить LCS между строкой и всеми подстроками другой строки, и/или между всеми префиксами одной строки и всеми суффиксами другой. Помимо важной роли этой обобщенной задачи в строковых алгоритмах, у нее открываются неожиданные связи с алгеброй полугрупп и вычислительной геометрией, с сетями сравнений (comparison networks), а также практические приложения в вычислительной биологии. В докладе будет представлено эффективное решение задачи полулокальной LCS и дан обзор основных сопутствующих результатов и приложений. В их числе динамическая поддержка LCS; быстрое вычисление клик в некоторых специальных графах; быстрое сравнение сжатых строк; параллельные вычисления на строках. Веб-страница первой лекции: http://compsciclub.ru/node/2062 Аннотация "Эффективные параллельные алгоритмы: методика BSP": Параллельные вычисления стремительно входят в мейнстрим современной computer science. Новый уровень сложности, привносимый параллелизмом в вычислительный процесс, создает потребность в его теоретическом осмыслении. Одна из самых интересных идей, выдвинутых в этом направлении - модель блочно-синхронного параллелизма (bulk-synchronous parallelism, BSP), предложенная Лесли Вэлиантом (Leslie Valiant) в 1990 г. Наряду с временем, затраченным на собственно вычисления, модель BSP рассматривает в качестве ограниченных ресурсов также межпроцессорную коммуникацию и синхронизацию. Вычислительный процесс BSP представляет из себя последовательность блоков асинхронных локальных вычислений, чередующихся с блоками коммуникации и барьерной синхронизации. Вэлиант доказал, что такой ограниченный класс параллельных вычислений может быть эффективно реализован при помощи чрезвычайно простого вероятностного алгоритма маршрутизации. При этом данный класс достаточно широк, чтобы служить основой для разработки эффективных параллельных алгоритмов. Мы изучим основные принципы разработки BSP алгоритмов на примере нескольких классических задач: сортировка, быстрое преобразование Фурье, ранжирование списка, вычисления на решетке, умножение матриц, решение системы линейных уравнений, поиск кратчайших путей в графе. Для большинства этих задач возможно наивное распараллеливание вычислений, однако оптимальные решения (с учетом времени на коммуникацию и синхронизацию) зачастую нетривиальны и поучительны. Веб-страница мини-курса: http://compsciclub.ru/courses/parallelalgo