Laboratory of Mathematical Logic

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

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

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

Abstract

Для двух заданных строк

длины

, длина их наибольшей общей подпоследовательности

может быть вычислена за время

методом динамического программирования. В 1980 г., Masek and Paterson показали, что длина

может быть вычислена за субквадратичное время. Мы покажем, как достичь еще большего: длины всех

, где B' является подстрокой B, также можно вычислить за субквадратичное время, получая на выходе эффективное неявное представление

выходных значений. Такое "полулокальное" сравнение строк может быть использовано в вычислительной биологии, а также позволяет получить улучшенный алгоритм для следующей хорошо известной задачи: задан круг с

хордами, требуется найти наибольшее подмножество попарно пересекающихся хорд. В 1973 г. Gavril представил первый полиномиальный алгоритм для этой задачи, а в 1983 г. Rotem and Urrutia опубликовали алгоритм сложности

. Мы покажем, как улучшить эту оценку до

.

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