Пятница, 30 сентября, ауд. 203. Начало в 17:20.
Докладчик: Александр Тискин (University of Warwick).
Тема: Задача о наибольшей общей подпоследовательности: суперклей из водорослей.
Abstract
Вычисление наибольшей общей подпоследовательности (longest common subsequence, LCS) двух заданных строк - фундаментальная алгоритмическая задача, традиционно решаемая методом динамического программирования. Мы рассматриваем альтернативный метод решения типа divide-and-conquer, основанный на обобщении этой задачи, вычисляющем неявные матрицы полулокальных LCS. Решения на подзадачах "склеиваются" при помощи эффективного умножения в "моноиде водорослей", тесно связанном с классической группой кос. Предлагаемый метод позволяет получать эффективные алгоритмы для различных нетрадиционных вариантов задачи LCS - в частности, для LCS на динамических строках, сжатых строках, а также для параллельного вычисления LCS с минимальной коммуникацией и синхронизацией между процессорами.
