Laboratory of Mathematical Logic at PDMI

Пятница, 16 июня, комната 106. Начало в 17:30.

Докладчик: А. Тискин.

Тема: Полулокальное сравнение строк.

Abstract

Для двух заданных строк $A, B$ длины $n$, длина их наибольшей общей подпоследовательности $LCS(A, B)$ может быть вычислена за время $O(n^2)$ методом динамического программирования. В 1980 г., Masek and Paterson показали, что длина $LCS$ может быть вычислена за субквадратичное время. Мы покажем, как достичь еще большего: длины всех $LCS(A, B')$, где B' является подстрокой B, также можно вычислить за субквадратичное время, получая на выходе эффективное неявное представление $Theta(n^2)$ выходных значений. Такое "полулокальное" сравнение строк может быть использовано в вычислительной биологии, а также позволяет получить улучшенный алгоритм для следующей хорошо известной задачи: задан круг с $n$ хордами, требуется найти наибольшее подмножество попарно пересекающихся хорд. В 1973 г. Gavril представил первый полиномиальный алгоритм для этой задачи, а в 1983 г. Rotem and Urrutia опубликовали алгоритм сложности $O(n^2)$. Мы покажем, как улучшить эту оценку до $O(n^1.5)$.

Доклад будет являться расширенным вариантом доклада автора на CSR 2006. Также будет продемонстрирована связь с результатами, представленными на CSR 2006 в статье Cegielski, Guessarian, Лифшица и Матиясевича.