Succesiunea

În matematică , o subsecvență a unei secvențe , numită și subsecvență extrasă sau succesiune, este o secvență care se formează din secvența originală în care au fost eliminate unele elemente, fără a schimba poziția relativă a elementelor rămase. Uneori termenul „subsecvență” indică un subset finit al secvenței de pornire, din care dorim adesea să cunoaștem subsecvența comună maximă .

De exemplu, având în vedere succesiunea numerelor întregi $\{\dots ,-3,-2,-1,0,1,2,3,\dots \}$ ${\ displaystyle \ {\ dots, -3, -2, -1,0,1,2,3, \ dots \}}$ ${\ displaystyle \ {\ dots, -3, -2, -1,0,1,2,3, \ dots \}}$ , succesiunea numerelor pare este o subsecvență.

Importanța subsecvențelor constă în considerarea că unele rezultate, chiar fundamentale, ale limitei nu pot fi atinse pentru întreaga succesiune, ci doar pentru o subsecvență adecvată extrasă din aceasta. Vezi, de exemplu, teorema Ascoli-Arzelà , referindu-se la care se spune că o secvență converge la mai puțin decât subsecvențe.

În informatică, termenul șir este în general înțeles ca un sinonim pentru „secvență”, dar este important de reținut că șirul și subsecvența nu sunt sinonime. Un șir este format din părți consecutive ale unui șir, în timp ce o subsecvență nu este neapărat. Aceasta înseamnă că un șir de caractere al unui șir este în mod necesar o subsecvență a acestuia, dar o subsecvență a unui șir nu este neapărat un subșir al aceluiași. ^[1]

Definiție

De sine $X$ ${\ displaystyle X}$ $X$ este un set și $(a_{n})_{n\in \mathbb {N} }$ ${\ displaystyle (a_ {n}) _ {n \ in \ mathbb {N}}}$ $(a_ {n}) _ {{n \ in \ mathbb {N}}}$ o succesiune în $X$ ${\ displaystyle X}$ $X$ , o subsecvență a $(a_{n})$ ${\ displaystyle (a_ {n})}$ ${\ displaystyle (a_ {n})}$ este o succesiune de forme $(a_{n_{r}})_{r\in \mathbb {N} }$ ${\ displaystyle (a_ {n_ {r}}) _ {r \ in \ mathbb {N}}}$ ${\ displaystyle (a_ {n_ {r}}) _ {r \ in \ mathbb {N}}}$ , unde este $(n_{r})_{r\in \mathbb {N} }$ ${\ displaystyle (n_ {r}) _ {r \ in \ mathbb {N}}}$ ${\ displaystyle (n_ {r}) _ {r \ in \ mathbb {N}}}$ este o succesiune strict crescătoare, adică $n_{1}<n_{2}<\ldots$ ${\ displaystyle n_ {1} <n_ {2} <\ ldots}$ ${\ displaystyle n_ {1} <n_ {2} <\ ldots}$ .

Mai exact, fie $\phi :\mathbb {N} \to X$ ${\ displaystyle \ phi: \ mathbb {N} \ to X}$ ${\ displaystyle \ phi: \ mathbb {N} \ to X}$ o succesiune e $n:\mathbb {N} \to \mathbb {N}$ ${\ displaystyle n: \ mathbb {N} \ to \ mathbb {N}}$ ${\ displaystyle n: \ mathbb {N} \ to \ mathbb {N}}$ ( $n=n(i)$ ${\ displaystyle n = n (i)}$ ${\ displaystyle n = n (i)}$ ) o succesiune strict în creștere. Apoi este definit ca subsecvența lui $\phi$ ${\ displaystyle \ phi}$ $\ phi$ aplicația compusă $\phi (n_{i})$ ${\ displaystyle \ phi (n_ {i})}$ ${\ displaystyle \ phi (n_ {i})}$ .

Proprietate

O importanță deosebită sunt următoarele teoreme :

O succesiune are o limită $l\in \mathbb {R} ^{*}$ ${\ displaystyle l \ in \ mathbb {R} ^ {*}}$ ${\ displaystyle l \ in \ mathbb {R} ^ {*}}$ dacă și numai dacă fiecare dintre subsecvențele sale are limite $L$ ${\ displaystyle l}$ $L$ .
De sine $(u_{2n})_{n\in \mathbf {N} }$ ${\ displaystyle (u_ {2n}) _ {n \ in \ mathbf {N}}}$ ${\ displaystyle (u_ {2n}) _ {n \ in \ mathbf {N}}}$ Și $(u_{2n+1})_{n\in \mathbf {N} }$ ${\ displaystyle (u_ {2n + 1}) _ {n \ in \ mathbf {N}}}$ ${\ displaystyle (u_ {2n + 1}) _ {n \ in \ mathbf {N}}}$ converg la aceeași limită $L$ ${\ displaystyle l}$ $L$ , asa de $(u_{n})_{n\in \mathbf {N} }$ ${\ displaystyle (u_ {n}) _ {n \ in \ mathbf {N}}}$ ${\ displaystyle (u_ {n}) _ {n \ in \ mathbf {N}}}$ converge la $L$ ${\ displaystyle l}$ $L$ (această teoremă și precedenta se numesc teoreme de restricție pentru secvențe ).
Orice secvență limitată la valori în $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ $\ mathbb {R}$ admite cel puțin o subsecvență convergentă (din teorema Bolzano-Weierstrass ).
Fiecare secvență evaluată într-un spațiu metric compact are o subsecvență convergentă.
De sine $(u_{2n})_{n\in \mathbf {N} }$ ${\ displaystyle (u_ {2n}) _ {n \ in \ mathbf {N}}}$ ${\ displaystyle (u_ {2n}) _ {n \ in \ mathbf {N}}}$ , $(u_{2n+1})_{n\in \mathbf {N} }$ ${\ displaystyle (u_ {2n + 1}) _ {n \ in \ mathbf {N}}}$ ${\ displaystyle (u_ {2n + 1}) _ {n \ in \ mathbf {N}}}$ Și $(u_{3n})_{n\in \mathbf {N} }$ ${\ displaystyle (u_ {3n}) _ {n \ in \ mathbf {N}}}$ ${\ displaystyle (u_ {3n}) _ {n \ in \ mathbf {N}}}$ Atunci sunt din Cauchy $(u_{n})_{n\in \mathbf {N} }$ ${\ displaystyle (u_ {n}) _ {n \ in \ mathbf {N}}}$ ${\ displaystyle (u_ {n}) _ {n \ in \ mathbf {N}}}$ este o secvență Cauchy .
Dacă o secvență Cauchy are o subsecvență convergentă, atunci întreaga secvență converge.

Exemple

Sunt:

X=\mathbb {R} \qquad x_{n}=(-1)^{n}\qquad n_{j}=2j

{\ displaystyle X = \ mathbb {R} \ qquad x_ {n} = (- 1) ^ {n} \ qquad n_ {j} = 2j}

{\ displaystyle X = \ mathbb {R} \ qquad x_ {n} = (- 1) ^ {n} \ qquad n_ {j} = 2j}

Atunci:

x_{n_{j}}=(-1)^{2j}=1

{\ displaystyle x_ {n_ {j}} = (- 1) ^ {2j} = 1}

{\ displaystyle x_ {n_ {j}} = (- 1) ^ {2j} = 1}

Observăm că secvența originală nu este convergentă (oscilează), în timp ce subsecvența converge, și în acest caz este, de asemenea, constantă.

Lasa-i sa fie $X$ $=$ $C.$ {\ displaystyle X = \ mathbb {C}} ${\ displaystyle X = \ mathbb {C}}$ Și $X$ $n$ $=$ $the$ $n$ {\ displaystyle x_ {n} = i ^ {n}} ${\ displaystyle x_ {n} = i ^ {n}}$ :
- De sine $n_{j}=4j$ ${\ displaystyle n_ {j} = 4j}$ ${\ displaystyle n_ {j} = 4j}$ asa de $x_{n_{j}}=i^{4j}=1$ ${\ displaystyle x_ {n_ {j}} = i ^ {4j} = 1}$ ${\ displaystyle x_ {n_ {j}} = i ^ {4j} = 1}$
- De sine $n_{j}=4j+1$ ${\ displaystyle n_ {j} = 4j + 1}$ ${\ displaystyle n_ {j} = 4j + 1}$ asa de $x_{n_{j}}=i$ ${\ displaystyle x_ {n_ {j}} = i}$ ${\ displaystyle x_ {n_ {j}} = i}$
- De sine $n_{j}=4j+2$ ${\ displaystyle n_ {j} = 4j + 2}$ ${\ displaystyle n_ {j} = 4j + 2}$ asa de $x_{n_{j}}=-1$ ${\ displaystyle x_ {n_ {j}} = - 1}$ ${\ displaystyle x_ {n_ {j}} = - 1}$
- De sine $n_{j}=4j+3$ ${\ displaystyle n_ {j} = 4j + 3}$ ${\ displaystyle n_ {j} = 4j + 3}$ asa de $x_{n_{j}}=-i$ ${\ displaystyle x_ {n_ {j}} = - i}$ ${\ displaystyle x_ {n_ {j}} = - i}$

Considera:

\langle B,C,D,G\rangle

{\ displaystyle \ langle B, C, D, G \ rangle}

{\ displaystyle \ langle B, C, D, G \ rangle}

Este o subsecvență a:

\langle A,C,B,D,E,G,C,E,D,B,G\rangle

{\ displaystyle \ langle A, C, B, D, E, G, C, E, D, B, G \ rangle}

{\ displaystyle \ langle A, C, B, D, E, G, C, E, D, B, G \ rangle}

cu secvența corespunzătoare de indici <3, 7, 9, 11>.

Dă două secvențe $X$ ${\ displaystyle X}$ $X$ Și $Da$ ${\ displaystyle Y}$ $Da$ , o secvență $G.$ ${\ displaystyle G}$ $G.$ este o subsecvență comună a $X$ ${\ displaystyle X}$ $X$ este la $Da$ ${\ displaystyle Y}$ $Da$ dacă este o subsecvență ambele $X$ ${\ displaystyle X}$ $X$ cea a $Da$ ${\ displaystyle Y}$ $Da$ . De exemplu, dacă:

X=\langle A,C,B,D,E,G,C,E,D,B,G\rangle

{\ displaystyle X = \ langle A, C, B, D, E, G, C, E, D, B, G \ rangle}

{\ displaystyle X = \ langle A, C, B, D, E, G, C, E, D, B, G \ rangle}

Și:

Y=\langle B,E,G,C,F,E,U,B,K\rangle

{\ displaystyle Y = \ langle B, E, G, C, F, E, U, B, K \ rangle}

{\ displaystyle Y = \ langle B, E, G, C, F, E, U, B, K \ rangle}

apoi o subsecvență comună a

X

{\ displaystyle X}

X

este la

Da

{\ displaystyle Y}

Da

ar putea fi:

G=\langle B,E,E\rangle

{\ displaystyle G = \ langle B, E, E \ rangle}

{\ displaystyle G = \ langle B, E, E \ rangle}

Cu toate acestea, aceasta nu este cea mai mare subsecvență comună , având în vedere că

G.

{\ displaystyle G}

G.

are lungimea 3, iar subsecvența este comună

\langle B,E,E,B\rangle

{\ displaystyle \ langle B, E, E, B \ rangle}

{\ displaystyle \ langle B, E, E, B \ rangle}

are lungimea 4. Cea mai mare subsecvență comună a

X

{\ displaystyle X}

X

este la

Da

{\ displaystyle Y}

Da

Și

\langle B,E,G,C,E,B\rangle

{\ displaystyle \ langle B, E, G, C, E, B \ rangle}

{\ displaystyle \ langle B, E, G, C, E, B \ rangle}

.

Sottosequences își găsesc aplicația în informatică , în special în disciplina Bioinformaticii , unde computerele sunt folosite pentru a compara, analiza și stoca șiruri de ADN .

El a luat două șiruri de ADN, acestea sunt:

ORG ₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

ORG ₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Sottosequences sunt utilizate pentru a determina gradul de asemănare între două șiruri de ADN, utilizând bazele azotate : adenină , guanină , citozină și timină .

Notă

^ Dan Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology , SUA, Cambridge University Press, 1999 [1997] , p. 4, ISBN 0-521-58519-8 .

Elemente conexe

linkuri externe

( EN ) subsecvență , în PlanetMath .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Dan Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology , SUA, Cambridge University Press, 1999 [1997] , p. 4, ISBN 0-521-58519-8 .

[1]