Sottosuccessione

Da Wikipedia, l'enciclopedia libera.

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 \{\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]

Definizione[modifica | modifica sorgente]

Se X è un insieme e (a_n)_{n \in \N} una successione in X, una sottosuccessione è un sottoinsieme infinito della successione. Una sottosuccessione di (a_n) è dunque una successione della forma  (a_{n_r})_{r \in \N} , dove (n_r)_{r \in \N} è una successione strettamente crescente, ovvero n_1 < n_2 < \ldots.

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

Proprietà[modifica | modifica sorgente]

Di particolare importanza sono i seguenti teoremi:

Esempi[modifica | modifica sorgente]

  • Siano:
X=\mathbb{R} \qquad x_n = (-1)^n \qquad  n_j = 2j
Allora:
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 X=\mathbb{C} e  x_n = i^n:
    • Se n_j = 4j allora  x_{n_j} = i^{4j}=1
    • Se n_j = 4j+1 allora  x_{n_j} = i
    • Se n_j = 4j+2 allora  x_{n_j} = -1
    • Se n_j = 4j+3 allora  x_{n_j} = -i
  • Si consideri:
 \langle B,C,D,G \rangle
Si tratta di una sottosequenza di:
 \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 X e Y, una sequenza G è una sottosequenza comune a X e a Y se è una sottosequenza sia di X che di Y. Per esempio, se:
 X = \langle A,C,B,D,E,G,C,E,D,B,G \rangle e:
 Y = \langle B,E,G,C,F,E,U,B,K \rangle
allora una sottosequenza comune a X e a Y potrebbe essere:
 G = \langle B,E,E \rangle
Questa però non è la massima sottosequenza comune, dato che G ha lunghezza 3, e la sottosequenza comune  \langle B,E,E,B \rangle ha lunghezza 4. La massima sottosequenza comune a X e a Y è  \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 :
ORG1 = ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
ORG2 = 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.

Note[modifica | modifica sorgente]

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

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

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