ru en

Новости

02.11.2020
«Удивительная алгебра сравнения строк»

«Удивительная алгебра сравнения строк»

Александр Тискин (ФМКН)

Коллоквиум Факультета математики и компьютерных наук

Четверг 5 ноября 18:15 zoom ID 958-115-833

Аннотация

 

Доклад будет посвящен классической задаче вычисления наибольшей общей подпоследовательности (Longest Common Subsequence, LCS) для пары строк, также известной в мире биоинформатики как задача выравнивания последовательностей (Sequence Alignment). Решение из учебника основано на методе динамического программирования и кажется единственно возможным. Мы увидим, что это не так: предварительно обобщив задачу, ее можно эффективно решить при помощи рекурсии, где «склеивание» подзадач производится при помощи на первый взгляд совершенно посторонней структуры — моноида Гекке или «липких кос», определяемого через тропическое матричное умножение и очень похожего на классическую группу кос. Такое решение представляет не только теоретический интерес, но и позволяет получить эффективные алгоритмы для сравнения сжатых строк без их декомпрессии, параллельного сравнения строк, а также решения некоторых практических задач биоинформатики.

Приглашаются все желающие!