sousséquences

Dans le domaine des suites, une sous-séquence est une suite obtenue en supprimant certains termes tout en conservant l'ordre des éléments. Si (a_n) est une suite dans un ensemble S, alors une sous-séquence est une suite (a_{n_k}) où n_1 < n_2 < ... et chaque n_k est un entier positif. La sous-séquence est infinie lorsque la suite d'indices est infinie; elle peut aussi être finie si l'on choisit un nombre fini d'indices.

Une sous-séquence peut être contiguë. Si les indices n_k sont consécutifs, alors la sous-séquence est appelée sous-séquence contiguë, ou segment, de la suite.

Principales propriétés. Toute suite possède de nombreuses sous-séquences. Si a_n → L, alors toute sous-séquence a_{n_k} → L. En analyse réelle, Bolzano-Weierstrass garantit que toute suite bornée admet une sous-séquence convergente. En combinatoire, Erdős–Szekeres affirme que toute suite de longueur (r−1)(s−1)+1 contient une sous-séquence croissante de longueur r ou une sous-séquence décroissante de longueur s. Le problème de la plus longue sous-séquence croissante (Longest Increasing Subsequence) est un enjeu algorithmique classique, résoluble en O(n log n).

Applications et usages. Les sous-séquences servent à étudier la convergence, la régularité, et elles apparaissent en informatique et en bioinformatique pour repérer des motifs non contigus dans des séquences.

Voir aussi: suite, sous-séquence, sous-séquence contiguë, suite monotone.