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

Автор: Знаменский Сергей Витальевич

Журнал: Программные системы: теория и приложения @programmnye-sistemy

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

Статья в выпуске: 4 (31) т.7, 2016 года.

Бесплатный доступ

Математическое ожидание длины длиннейшей общей подпоследовательности букв двух случайных слов рассматривается как функция от длин и этих слов и мощности алфавита = A. При этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой позиции слова. Указан вид приближённой формулы для 𝐸(𝑚, 𝑛, 𝛼), позволяющий вычислять 𝐸(𝑚, 𝑛, 𝛼) с погрешностью в 0.3 процента для 64 6 + 6 65536 и 1

ID: 14336100 Короткий адрес: https://sciup.org/14336100

Ред. заметка