RUS  ENG
Полная версия
СЕМИНАРЫ

Петербургский семинар по теории представлений и динамическим системам
1 ноября 2023 г. 17:00, г. Санкт-Петербург, ПОМИ (наб. р. Фонтанки, 27), ауд. 311 + трансляция в zoom, см. http://www.pdmi.ras.ru/~rtheory/nextsem.html


Проблема Хватала-Санкова как задача символической динамики

А. В. Тискин

Санкт-Петербургский государственный университет

Аннотация: Пусть заданы две равномерно случайные бинарные строки равной длины. Математическое ожидание длины их наибольшей общей подпоследовательности (LCS) асимптотически пропорционально длине этих строк. Нахождение коэффициента $\gamma$ этой пропорциональности, то есть предела нормализованной длины LCS для пары случайных бинарных строк длины $n \to \infty$ - естественная проблема, впервые сформулированная Хваталом и Санковым в 1975 году и до сих пор не решенная. Данная проблема возникает в различных областях исследований, от комбинаторики и анализа алгоритмов до теории кодирования и вычислительной биологии. В докладе будут представлены результаты о комбинаторной структуре LCS, ранее полученные автором, а также рассказано о сведении проблемы Хватала-Санкова к задаче статистической механики, связывающем константу $\gamma$ с параметрами определенного стохастического процесса взаимодействия частиц. Исследование данного процесса методами символической динамики позволяет получить новые оценки для значения $\gamma$, а также реализовать качественно новый тип вычислительного эксперимента для его численного приближения.


© МИАН, 2024