Приближение длины наибольшей общей подпоследовательности пары случайных строк
Автор: Знаменский Сергей Витальевич
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Математические основы программирования
Статья в выпуске: 4 (31) т.7, 2016 года.
Бесплатный доступ
Математическое ожидание длины длиннейшей общей подпоследовательности букв двух случайных слов рассматривается как функция от длин и этих слов и мощности алфавита = A. При этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой позиции слова. Указан вид приближённой формулы для 𝐸(𝑚, 𝑛, 𝛼), позволяющий вычислять 𝐸(𝑚, 𝑛, 𝛼) с погрешностью в 0.3 процента для 64 6 + 6 65536 и 1
ID: 14336100 Короткий адрес: https://sciup.org/14336100
Ред. заметка