Sottosuccessione

In matematica, una sottosuccessione di una successione, anche detta sottosequenza o successione estratta, è una successione che è formata dalla successione originale a cui sono stati tolti alcuni elementi, senza modificare la posizione relativa degli elementi rimanenti. Talvolta con "sottosequenza" si indica un sottoinsieme finito della successione di partenza, di cui spesso si vuole conoscere la massima sottosequenza comune.

Per esempio, data la successione dei numeri interi ${\displaystyle \{\dots ,-3,-2,-1,0,1,2,3,\dots \}}$, la successione dei numeri pari è una sottosuccessione.

L'importanza delle sottosuccessioni sta nella considerazione che alcuni risultati, anche fondamentali, di limite non si riescono a raggiungere per l'intera successione, ma solo per un'opportuna sottosuccessione estratta da questa. Si veda ad esempio il teorema di Ascoli-Arzelà, riferendosi al quale si dice che una successione converge a meno di sottosuccessioni.

In informatica, il termine stringa è generalmente inteso come un sinonimo di "sequenza", ma è importante notare che sottostringa e sottosequenza non sono sinonimi. Una sottostringa è formata da parti consecutive di una stringa, mentre una sottosequenza non lo è necessariamente. Questo vuol dire che una sottostringa di una stringa è necessariamente una sottosequenza della stessa, ma una sottosequenza di una stringa non è necessariamente una sottostringa della stessa.^[1]

Se ${\displaystyle X}$ è un insieme e ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ una successione in ${\displaystyle X}$, una sottosuccessione di ${\displaystyle (a_{n})}$ è una successione della forma ${\displaystyle (a_{n_{r}})_{r\in \mathbb {N} }}$, dove ${\displaystyle (n_{r})_{r\in \mathbb {N} }}$ è una successione strettamente crescente di numeri naturali, ovvero ${\displaystyle n_{1}<n_{2}<\ldots }$.

In modo più preciso, sia ${\displaystyle \phi :\mathbb {N} \to X}$ una successione e ${\displaystyle n:\mathbb {N} \to \mathbb {N} }$ (${\displaystyle n=n(i)}$) una successione strettamente crescente. Allora si definisce sottosuccessione di ${\displaystyle \phi }$ l'applicazione composta ${\displaystyle \phi (n_{i})}$.

Di particolare importanza sono i seguenti teoremi:

• Una successione ha limite ${\displaystyle l\in \mathbb {R} ^{*}}$ se e solo se ogni sua sottosuccessione ha limite ${\displaystyle l}$.
• Se ${\displaystyle (u_{2n})_{n\in \mathbf {N} }}$ e ${\displaystyle (u_{2n+1})_{n\in \mathbf {N} }}$ convergono allo stesso limite ${\displaystyle l}$, allora ${\displaystyle (u_{n})_{n\in \mathbf {N} }}$ converge a ${\displaystyle l}$ (questa teorema e il precedente sono detti teoremi delle restrizioni per le successioni).
• Ogni successione limitata a valori in ${\displaystyle \mathbb {R} }$ ammette almeno una sottosuccessione convergente (dal teorema di Bolzano-Weierstrass).
• Ogni successione a valori in uno spazio metrico compatto ha una sottosuccessione convergente.
• Se ${\displaystyle (u_{2n})_{n\in \mathbf {N} }}$, ${\displaystyle (u_{2n+1})_{n\in \mathbf {N} }}$ e ${\displaystyle (u_{3n})_{n\in \mathbf {N} }}$ sono di Cauchy, allora ${\displaystyle (u_{n})_{n\in \mathbf {N} }}$ è una successione di Cauchy.
• Se una successione di Cauchy possiede una sottosuccessione convergente, allora converge l'intera successione.

• Siano:

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

Allora:

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

Si nota che la successione originaria non è convergente (oscilla), mentre la sottosuccessione converge, e in questo caso è anche costante.

• Siano ${\displaystyle X=\mathbb {C} }$ e ${\displaystyle x_{n}=i^{n}}$:
  • Se ${\displaystyle n_{j}=4j}$ allora ${\displaystyle x_{n_{j}}=i^{4j}=1}$
  • Se ${\displaystyle n_{j}=4j+1}$ allora ${\displaystyle x_{n_{j}}=i}$
  • Se ${\displaystyle n_{j}=4j+2}$ allora ${\displaystyle x_{n_{j}}=-1}$
  • Se ${\displaystyle n_{j}=4j+3}$ allora ${\displaystyle x_{n_{j}}=-i}$

• Si consideri:

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

Si tratta di una sottosequenza di:

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

con la corrispondente sequenza di indici <3, 7, 9, 11>.

• Date due sequenze ${\displaystyle X}$ e ${\displaystyle Y}$, una sequenza ${\displaystyle G}$ è una sottosequenza comune a ${\displaystyle X}$ e a ${\displaystyle Y}$ se è una sottosequenza sia di ${\displaystyle X}$ che di ${\displaystyle Y}$. Per esempio, se:

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

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

allora una sottosequenza comune a ${\displaystyle X}$ e a ${\displaystyle Y}$ potrebbe essere:

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

Questa però non è la massima sottosequenza comune, dato che ${\displaystyle G}$ ha lunghezza 3, e la sottosequenza comune ${\displaystyle \langle B,E,E,B\rangle }$ ha lunghezza 4. La massima sottosequenza comune a ${\displaystyle X}$ e a ${\displaystyle Y}$ è ${\displaystyle \langle B,E,G,C,E,B\rangle }$.

• Le sottosequenze trovano applicazione in informatica, specialmente nella disciplina della Bioinformatica, dove i computer sono utilizzati per confrontare, analizzare, e memorizzare stringhe di DNA.

Prese due stringhe di DNA, siano :

ORG₁ = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA

ORG₂ = CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA

Le sottosequenze sono utilizzate per determinare il grado di similarità tra due stringhe di DNA, servendosi delle basi azotate: adenina, guanina, citosina e timina.

• Successione (matematica)
• Successione ricorsiva
• Classe limite
• Limite superiore

• (EN) subsequence, in PlanetMath.

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica