Задача о наибольшей общей подпоследовательности: суперклей из водорослей

Задача о наибольшей общей подпоследовательности: суперклей из водорослей

Speaker:

Александр Тискин

Date:

Friday, September 30, 2016 - 17:30

Abstract:

Вычисление наибольшей общей подпоследовательности (longest common subsequence, LCS) двух заданных строк - фундаментальная алгоритмическая задача, традиционно решаемая методом динамического программирования. Мы рассматриваем альтернативный метод решения типа divide-and-conquer, основанный на обобщении этой задачи, вычисляющем неявные матрицы полулокальных LCS. Решения на подзадачах "склеиваются" при помощи эффективного умножения в "моноиде водорослей", тесно связанном с классической группой кос. Предлагаемый метод позволяет получать эффективные алгоритмы для различных нетрадиционных вариантов задачи LCS - в частности, для LCS на динамических строках, сжатых строках, а также для параллельного вычисления LCS с минимальной коммуникацией и синхронизацией между процессорами.