– Страница мероприятия
– 1 апреля, 19:00 – 21:00
– Мраморный зал, ПОМИ РАН, наб. реки Фонтанки, 27, Санкт-Петербург
– Пожалуйста, не забудьте зарегистрироваться — это необходимое условие посещения ПОМИ РАН.
⭐️ О лекторах
Александр Тискин
– DPhil (Oxford)
– доцент факультета МКН СПбГУ
– Научные интересы: алгоритмы на строках, параллельные алгоритмы, комбинаторная оптимизация
Борис Золотов
– Аспирант МКН СПбГУ, преподаватель
– Научные интересы: алгоритмы на строках, структуры данных, вычислительная геометрия
📢 Анонс
Доклад будет посвящен классической задаче вычисления наибольшей общей подпоследовательности (Longest Common Subsequence, LCS) для пары строк, также известной в мире биоинформатики как задача выравнивания последовательностей (Sequence Alignment). Решение из учебника основано на методе динамического программирования и кажется единственно возможным. Мы увидим, что это не так: предварительно обобщив задачу, ее можно эффективно решить при помощи рекурсии, где «склеивание» подзадач производится при помощи на первый взгляд совершенно посторонней структуры — моноида Гекке или «липких кос», определяемого через тропическое матричное умножение и очень похожего на классическую группу кос. Такое решение представляет не только теоретический интерес, но и позволяет получить эффективные алгоритмы для сравнения сжатых строк без их декомпрессии, параллельного сравнения строк, а также решения некоторых практических задач биоинформатики. В последние годы появляется все больше приложений этого метода: приближенный поиск по образцу в режиме малого редакционного расстояния; сравнение динамических строк; сравнение периодических строк; локальное сравнение строк при помощи оракула. Мы опишем основные идеи некоторых из них.