Приближение длины наибольшей общей подпоследовательности пары случайных строк
Автор: Знаменский Сергей Витальевич
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Математические основы программирования
Статья в выпуске: 4 (31) т.7, 2016 года.
Бесплатный доступ
Математическое ожидание длины длиннейшей общей подпоследовательности букв двух случайных слов рассматривается как функция от длин и этих слов и мощности алфавита = A. При этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой позиции слова. Указан вид приближённой формулы для 𝐸(𝑚, 𝑛, 𝛼), позволяющий вычислять 𝐸(𝑚, 𝑛, 𝛼) с погрешностью в 0.3 процента для 64 6 + 6 65536 и 1
ID: 14336100 Короткий адрес: https://sciup.org/14336100
Список литературы Приближение длины наибольшей общей подпоследовательности пары случайных строк
- V. Chv´atal, D. Sankoff. "Longest Common subsequences of two random sequences", J. Appl. Probability, V. 12. No. 2. 1975. P. 306-315.
- R. Bundschuh. "High precision simulations of the longest common subsequence problem", The European Physical Journal B-Condensed Matter and Complex Systems, V. 22. No. 4. 2001. P. 533-541.
- R. Baeza-Yates, G. Navarro, R. Gavald´ a, R. Schehing. "Bounding the expected length of the longest common subsequences and forests", Theory of Computing Systems, V. 32. No. 4. 1999. P. 435-452.
- J. Boutet de Monvel. "Extensive simulations for longest common subsequences", The European Physical Journal B -Condensed Matter and Complex Systems, V. 7. No. 2. 1999. P. 293-308.
- G. S. Lueker. "Improved bounds on the average length of longest common subsequences", Journal of the ACM, V. 56. No. 3. 2009. P. 17.
- M. A. Kiwi, M. Loebl, J. Matousek. "Expected length of the longest common subsequence for large alphabets", Advances in Mathematics, V. 197. No. 2. 2005. P. 480-498.
- J. D. Dixon. Longest common subsequences in binary sequences, 2013, arXiv: 1307.2796.
- C. В. Знаменский. Картина наибольшей длины общих подпоследовательностей пары случайных строк 4-буквенного алфавита//Программные системы: теория и приложения, Т. 7, №. 1(28). 2016. С. 201-208 (англ.).
- S. V. Znamenskij. "A Formula for the Mean Length of the Longest Common Subsequence", Journal of Siberian Federal University. Mathematics & Physics, V. 10. No. 1. 2017. P. 71-74.
- J. Lember, H. Matzinger, The Annals of Probability, V. 37. No. 3. 2009. P. 1192-1235.
Ред. заметка
