|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
A formula for the mean length of the longest common subsequence
[Формула для средней длины длиннейшей общей подпоследовательности]
Sergej V. Znamenskij Ailamazyan Program Systems Institute of RAS, Peter the First, 4, Veskovo village, Pereslavl area, Yaroslavl region, 152021,
Russia
Аннотация:
Математическое ожидание $E$ длиннейшей общей подпоследовательности букв двух случайных слов рассматривается как функция от мощности алфавита $|A|$ и длин $m$ и $n$ этих слов. При этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой позиции слова. Предъявлено простое выражение для $E(\alpha, m, n)$ при фиксированных $\alpha $ и $m+n$.
Ключевые слова:
длиннейшая общая подпоследовательность, математическое ожидание, длина LCS, численное моделирование, асимптотическая формула.
Получена: 10.10.2016 Исправленный вариант: 10.11.2016 Принята: 20.12.2016
Образец цитирования:
Sergej V. Znamenskij, “A formula for the mean length of the longest common subsequence”, Журн. СФУ. Сер. Матем. и физ., 10:1 (2017), 71–74
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/jsfu526 https://www.mathnet.ru/rus/jsfu/v10/i1/p71
|
|