Home

Семинар 16 июня 2006 года

Пятница, 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, Лифшица и Матиясевича.