Volume 16, No 4, 2009, P. 31-46

UDC 519.2+621.391
A. V. Kel'manov, L. V. Mikhaylova, S. A. Khamidullin
On one problem of searching for tuples of fragments in a numerical sequence

Abstract:
A discrete optimization problem is considered to which the problem of the noise-proof detection of the recurring tuple of fragments in a numerical sequence is reduced. A variant of the problem in which the fragments from the desired tuples coincide (in the noiseless case) with the elements of the given tuple of vectors is analyzed. A new exact polynomial algorithm for solving this special optimization problem is proved. This algorithm provides that the solution is optimal under the minimum sum-of-squared deviations criterion. If noise is additive and it is a Gaussian sequence of independent identically distributed variables, then the solution is optimal under the maximum likelihood criterion as well. The time complexity of our algorithm is proved to be less then the complexity of the previously known algorithm.
Bibl. 4.

Keywords: discrete optimization problem, numerical sequence, recurring tuple of fragments, off-line algorithm.

Kel’manov Alexander Vasilyevich ¹
Mikhaylova Lyudmila Viktorovna ¹
Khamidullin Sergey Asgadullovich ¹
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: kelm@math.nsc.ru, mikh@math.nsc.ru, kham@math.nsc.ru