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

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

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



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






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


Программные системы: теория и приложения, 2016, том 7, выпуск 4, страницы 347–358 (Mi ps229)  

Математические основы программирования

Приближение длины наибольшей общей подпоследовательности пары случайных строк

С. В. Знаменский

Институт программных систем им. А. К. Айламазяна РАН
Список литературы:
Аннотация: Математическое ожидание $E$ длины длиннейшей общей подпоследовательности букв двух случайных слов рассматривается как функция от длин $m$ и $n$ этих слов и мощности алфавита $\alpha=|A|$. При этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой позиции слова.
Указан вид приближённой формулы для $E (m,n,\alpha)$, позволяющий вычислять $E (m,n,\alpha)$ с погрешностью в $0.3$ процента для $64\leqslant m+n\leqslant 65536$ и $1<\alpha<129$. Коэффициенты подобраны вручную и могут быть уточнены. Ожидается, что формула справедлива для всех больших значений аргументов с той же относительной погрешностью.
Ключевые слова и фразы: сходство строк, выравнивание последовательностей, случайные общие подпоследовательности, LCS, метрика Левенштейна.
Поступила в редакцию: 24.11.2016
Подписана в печать : 28.12.2016
Тип публикации: Статья
УДК: 004.416
MSC: 68T37; 68P10, 68W32
Образец цитирования: С. В. Знаменский, “Приближение длины наибольшей общей подпоследовательности пары случайных строк”, Программные системы: теория и приложения, 7:4 (2016), 347–358
Цитирование в формате AMSBIB
\RBibitem{Zna16}
\by С.~В.~Знаменский
\paper Приближение длины наибольшей общей подпоследовательности пары случайных строк
\jour Программные системы: теория и приложения
\yr 2016
\vol 7
\issue 4
\pages 347--358
\mathnet{http://mi.mathnet.ru/ps229}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/ps229
  • https://www.mathnet.ru/rus/ps/v7/i4/p347
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Программные системы: теория и приложения
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024