- Номер
- Журнал СФУ. Математика и физика. 2017 10 (1)
- Авторы
- Знаменский, Сергей В.
- Контактная информация
- Знаменский, Сергей В.: Институт программных систем РАН Петра Первого, 4, Переславльский район, Ярославская обл., 152021 Россия
- Ключевые слова
- longest common subsequence; expected value; LCS length; simulation; asymptotic formula; длиннейшая общая подпоследовательность; математическое ожидание; длина LCS; численное моделирование; асимптотическая формула
- Аннотация
Математическое ожидание E длиннейшей общей подпоследовательности букв двух случайных слов рассматривается как функция от мощности алфавита jAj и длин m и n этих слов. При этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой позиции слова. Предъявлено простое выражение для E( ; m; n) при фиксированных и m + n
- Страницы
- 71–74
- Статья в архиве электронных ресурсов СФУ
- https://elib.sfu-kras.ru/handle/2311/30296
Журнал СФУ. Математика и физика / Формула для средней длины длиннейшей общей подпоследовательности
Полный текст (.pdf)