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