Аннотация:
Доклад будет посвящен неожиданной тесной связи между тремя на первый взгляд не связанными структурами: во-первых, поведением наибольшей общей подпоследовательности строк при их конкатенации (мера их похожести, эквивалентная редакционному расстоянию); во-вторых, моноидом определенного класса целочисленных матриц при их тропическом умножении; в-третьих, моноидом Гекке, или "липких кос", то есть классической группы кос, где инверсия образующих заменена отношением идемпотентности. Три указанные структуры, несмотря на различный характер их определений, изоморфны между собой, то есть по сути дела являются разными точками зрения на одну и ту же структуру. Будет представлен эффективный алгоритм умножения в этой структуре и рассказано о его использовании для решения разнообразных задач сравнения строк. Также будет исследована связь этой структуры с сортирующими сетями и открытой проблемой вычисления константы Хватала-Санкова, то есть длины наибольшей общей подпоследовательности пары равномерно случайных строк над конечным алфавитом.
|
