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

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

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, метрика Левенштейна.

Полный текст: PDF файл (1547 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 004.416
MSC: 68T37; 68P10, 68W32
Поступила в редакцию: 24.11.2016
Подписана в печать : 28.12.2016

Образец цитирования: С. В. Знаменский, “Приближение длины наибольшей общей подпоследовательности пары случайных строк”, Программные системы: теория и приложения, 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}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ps229
  • http://mi.mathnet.ru/rus/ps/v7/i4/p347

    ОТПРАВИТЬ: 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
  • Программные системы: теория и приложения
    Просмотров:
    Эта страница:51
    Полный текст:19
    Литература:11

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