"Записки научных семинаров ПОМИ"
Том 528, стр. 214-237
Проблема Хватала--Санкоффа как задача символической динамики
А. Тискин
Department of Mathematics
and Computer Science, St. Petersburg State University;
St.Petersburg Electrotechnical University ``LETI''
alextiskin@gmail.com
- Аннотация:
Пусть даны две равномерно случайные двоичные строки равной длины. Математическое
ожидание длины их наибольшей общей подпоследовательности (longest common subsequence,
LCS) асимптотически пропорционально длине строк. Естественным образом возникает
проблема нахождения коэффициента этой пропорциональности $\gamma$, то есть предела
нормализованной длины LCS двух случайных двоичных строк длины $n \to \infty$.
Эта проблема была впервые сформулирована Хваталом (Chv\'atal) и Санкоффом (Sankoff)
в 1975 г. и до сих пор не решена. Она имеет отношение к самым разнообразным областям
исследований: от комбинаторики и анализа алгоритмов до теории кодирования и вычислительной
биологии. В предыдущей статье мы использовали методы статистической механики,
а также известные результаты о комбинаторной структуре LCS, чтобы установить связь
между константой $\gamma$ и параметрами некоторого стохастического процесса взаимодействия
частиц. В данной статье, мы дополняем этот анализ формулировкой задачи на языке
символической динамики и клеточных автоматов, и приводим некоторые предварительные
результаты вычислительного эксперимента, выполненного с целью улучшить существующие
численные оценки для $\gamma$. Мы также указываем на ошибку в предыдущей статье,
которая отменяет некоторые заявленные в ней результаты относительно свойств
$\gamma$.
Библ. -- 57 назв.
- Ключевые слова: случайные строки, наибольшая общая подпоследовательность,
проблема Хватала--Санкоффа, процессы взаимодействия частиц, символическая динамика,
клеточные автоматы
[random strings, longest common subsequence, the Chv\'atal--Sankoff problem, particle processes,
symbolic dynamics, cellular automata]
Полный текст(.pdf)