Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Полулокальное сравнение строк (Александр Тискин, University of Warwick)
Computer Science семинар


Что: Лекция
Когда: Суббота, 20 октября 2012, 17:20–18:45
Где: ПОМИ РАН
Слайды: csseminar_lecture_201012.pdf

Описание

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

Видео

Материалы

Приложенные файлы