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

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

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
  • Программные системы: теория и приложения
    Просмотров:
    Эта страница:43
    Полный текст:13
    Литература:12

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