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