Today: Wednesday 28 July 2021 , 1:14 am


advertisment
search




Plus longue sous-suite strictement croissante

Dernière mise à jour 25 Jour , 1 heure 76 Vues

Advertisement
In this page talks about ( Plus longue sous-suite strictement croissante ) It was sent to us on 02/07/2021 and was presented on 02/07/2021 and the last update on this page on 02/07/2021

Votre commentaire


Entrez le code
  La recherche d'une plus longue sous-suite strictement croissante dans une suite finie est un problème classique en algorithmique. Ce problème peut être résolu en temps O(n log n) en la longueur de la suite.

Description

L'entrée du problème est une suite finie x , ..., x . De façon formelle, l'objectif est de trouver une sous-suite strictement croissante (x_{\varphi(i))_{i \leq L de la suite (x_i)_{i \leq n, \varphi étant une fonction strictement croissante ⟦1, L⟧ → ⟦1, n⟧, pour la plus grande longueur L possible ..
Par exemple, la suite (6, 1, 4, 9, 5, 11) possède des sous-suites strictement croissantes de longueur 4, mais aucune de longueur 5. Une plus longue sous-suite strictement croissante est (1, 4, 9, 11), obtenue en prenant les éléments en position 2, 3, 4 et 6 de la suite initiale. En général, la solution n'est pas unique. Ici, une autre solution est (1, 4, 5, 11).
Ce problème est parfois désigné par l'acronyme LIS, pour .

Algorithme

L'algorithme de programmation dynamique suivant résout le problème de la plus longue sous-suite croissante en temps quasi-linéaire O(n log n). Il utilise seulement des tableaux et une fonction de recherche dichotomique. Il traite les éléments de la suite dans l'ordre, en gardant en mémoire la plus longue sous-suite strictement croissante trouvée jusqu'à présent et d'autres sous-suites plus courtes mais dont le dernier élément est plus petit (donc potentiellement plus faciles à compléter avec les éléments suivants). Les éléments de la suite sont notés X1, X2, ..., XN. Après avoir traité Xi, les invariants suivants sont vérifiés :
  • Mj contient une position k telle que Xk soit la plus petite valeur possible du dernier élément d'une sous-suite strictement croissante de X1, ..., Xi ayant exactement j éléments.
  • Pk contient l'indice du prédécesseur de Xk dans une plus longue sous-suite strictement croissante se terminant en position k.
L'algorithme conserve dans une variable L la longueur de la plus longue sous-suite strictement croissante trouvée.
À tout moment, la suite XM1, XM2, ..., XML est croissante. En effet, s'il existe une sous-suite strictement croissante de longueur i>1 se terminant en position Mi, alors il existe une sous-suite strictement croissante de longueur i-1 se terminant par une valeur inférieure. Comme la suite est croissante, il est possible de faire une recherche dichotomique dans cette suite. Attention : en général, la suite d'indices M1, M2, ..., ML n'est pas croissante, donc XM1, XM2, ..., XML n'est pas une sous-suite de X1, ..., XL (donc pas une solution du problème).
Description de l'algorithme :
Entrée : X, un tableau indicé de 1 à n.
Sortie : L, longueur de la plus longue sous-suite strictement croissante de X.
P, tableau de prédécesseurs permettant de reconstruire explicitement la suite.
P = tableau indicé de 1 à n
M = tableau indicé de 0 à n
L = 0
M0 = 0
pour i = 1, 2, ..., n :
par recherche dichotomique, trouver le plus grand entier j tel que 1 ≤ j ≤ L
et XMj < Xi ou définir j = 0 s'il n'en existe aucun.
Pi = Mj
si j == L ou Xi < XMj + 1 :
Mj + 1 = i
L = max(L, j + 1)
Les éléments de la sous-suite peuvent être calculés en partant du dernier élément XML, puis en remontant dans le tableau P des prédécesseurs : l'avant-dernier élément est XPML, l'antépénultième est XPPML, etc.
À chaque tour de boucle, l'opération la plus coûteuse est la recherche dichotomique, de complexité O(log n). Le temps total d'exécution de l'algorithme est donc O(n log n).

Liens avec la plus longue sous-séquence commune

Le problème de la plus longue sous-suite croissante est lié à celui de la plus longue sous-suite commune à deux suites, pour lequel il existe un algorithme de résolution par programmation dynamique de complexité quadratique : pourvu que l'alphabet sur lequel sont définies les chaînes soit muni d'une relation d'ordre, la plus longue sous-suite croissante d'une suite S est la plus longue sous-suite commune à S et T, où T est obtenue en triant S.
Inversement, le problème de la plus longue sous-suite commune à deux suites (S , ..., S ) et (T , ..., T ) peut être réduit au problème de la plus longue sous-suite croissante. Pour cela, on note Ax la liste des indices des éléments de S valant x par ordre décroissant. la plus longue sous-suite strictement croissante de la suite obtenue en concaténant AT , ..., AT est égale à la longueur de la plus longue sous-suite commune à S et T. La taille de la suite obtenue par concaténation est au plus nm, mais seulement m si la première suite ne contient pas d'élément en double. Ainsi, la réduction donne une méthode de résolution du problème de la plus longue sous-suite commune relativement efficace dans des cas particuliers courants ..

Plus longue sous-suite strictement croissante d'une permutation


Définition

On note par \mathfrak{S_n le groupe symétrique de permutations de ⟦1, n⟧. Soit \sigma \in \mathfrak{S_n une permutation, on identifie la plus longue suite croissante de la permutation avec la plus longue sous suite croissante de (\sigma(i))_{1\leq i \leq n et soit \ell(\sigma) sa longueur. \ell(\sigma) présente également le nombre de piles dans le Patience sorting .

Théorème de Baik-Deift-Johansson


Soit n un entier non nul et \mathbb{P_n la mesure de Haar (probabilité uniforme) sur \mathfrak{S_n alors pour tout réel s
\lim_{n\to \infty \mathbb{P_n\left(\frac{\ell(\sigma)-2\sqrt{n{n^\frac 16
 
commentaires

Il n'y a pas encore de commentaires

vu pour la dernière fois
Most vists