Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Петербургский семинар по теории представлений и динамическим системам
18 мая 2022 г. 16:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)
 


Проблема Хватала-Санкова: Осмысление сравнения случайных строк через стохастические процессы

А. В. Тискин

Количество просмотров:
Эта страница:114

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