|
Программные системы: теория и приложения, 2016, том 7, выпуск 1, страницы 201–208
(Mi ps207)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Математические основы программирования
A picture of common subsequence length for two random strings over an alphabet of 4 symbols
[Картина наибольшей длины общих подпоследовательностей пары случайных строк 4-буквенного алфавита]
S. V. Znamenskij Ailamazyan Program System Institute of RAS
Аннотация:
Наибольшая длина (LCS) общей подпоследовательности пары случайных конечных последовательностей из 4 букв рассмотрена как случайная функция от длин $m$ и $n$ этих двух последовательностей.
Представлены таблицы точных значений вероятностей для всех пар конкретных длин в диапазоне $2<m+n<19$.
Графики зависимости математического ожидания и дисперсии показаны в линейной перспективе, позволяющей просматривать на горизонте поведение при растущих длинах.
Для иллюстрации поведения при больших значениях длин на этих же графиках показаны результаты численного экcперимента для больших значений $m+n=32$, 512, 8192 и 131072.
Представленный график зависимости математического ожидания от $m$ и $n$ выглядит имеющим асимптотический прямой круговой конус.
Дисперсия выглядит растущей как $(n+m)^{\frac34}$.
Ключевые слова и фразы:
сходство строк, выравнивание последовательностей, случайные общие подпоследовательности, LCS, метрика Левенштейна.
Полный текст:
PDF файл (1200 kB)
Список литературы:
PDF файл
HTML файл
Тип публикации:
Статья
УДК:
004.416 Поступила в редакцию: 25.12.2015 Подписана в печать : 28.03.2016
Язык публикации: английский
Образец цитирования:
S. V. Znamenskij, “A picture of common subsequence length for two random strings over an alphabet of 4 symbols”, Программные системы: теория и приложения, 7:1 (2016), 201–208
Цитирование в формате AMSBIB
\RBibitem{Zna16}
\by S.~V.~Znamenskij
\paper A picture of common subsequence length for two random strings over an alphabet of 4 symbols
\jour Программные системы: теория и приложения
\yr 2016
\vol 7
\issue 1
\pages 201--208
\mathnet{http://mi.mathnet.ru/ps207}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/ps207 http://mi.mathnet.ru/rus/ps/v7/i1/p201
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
С. В. Знаменский, “Приближение длины наибольшей общей подпоследовательности пары случайных строк”, Программные системы: теория и приложения, 7:4 (2016), 347–358
-
Sergej V. Znamenskij, “A formula for the mean length of the longest common subsequence”, Журн. СФУ. Сер. Матем. и физ., 10:1 (2017), 71–74
|
Просмотров: |
Эта страница: | 95 | Полный текст: | 24 | Литература: | 16 |
|