Лекция, 20 октября 2012, 17:15

Полулокальное сравнение строк

бесплатно
Описание встречи

Вычисление наибольшей общей подпоследовательности двух строк — одна из классических алгоритмических задач. Во многих приложениях необходимо обобщение этой задачи, которое мы называем полулокальной LCS (semi-local LCS). В этом случае требуется вычислить LCS между строкой и всеми подстроками другой строки, и/или между всеми префиксами одной строки и всеми суффиксами другой. Помимо важной роли этой обобщенной задачи в строковых

алгоритмах, у нее открываются неожиданные связи с алгеброй полугрупп и

вычислительной геометрией, с сетями сравнений (comparison networks), а также практические приложения в вычислительной биологии.

В докладе будет представлено эффективное решение задачи полулокальной LCS и дан обзор основных сопутствующих результатов и приложений. В их числе динамическая поддержка LCS; быстрое вычисление клик в некоторых специальных графах; быстрое сравнение сжатых строк; параллельные вычисления на строках.

Посетили
Показать Всех
Смотрите также