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

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Программные системы: теория и приложения:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Программные системы: теория и приложения, 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

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. С. В. Знаменский, “Приближение длины наибольшей общей подпоследовательности пары случайных строк”, Программные системы: теория и приложения, 7:4 (2016), 347–358  mathnet
    2. Sergej V. Znamenskij, “A formula for the mean length of the longest common subsequence”, Журн. СФУ. Сер. Матем. и физ., 10:1 (2017), 71–74  mathnet  crossref
  • Программные системы: теория и приложения
    Просмотров:
    Эта страница:76
    Полный текст:18
    Литература:14

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019