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 , 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 wikitesto]

Se è un insieme e una successione in , una sottosuccessione è un sottoinsieme infinito della successione. Una sottosuccessione di è dunque una successione della forma , dove è una successione strettamente crescente, ovvero .

In modo più sintetico, sia una successione e una successione strettamente crescente. Allora si definisce sottosuccessione di l'applicazione composta .

Proprietà[modifica | modifica wikitesto]

Di particolare importanza sono i seguenti teoremi:

  • Una successione ha limite se e solo se ogni sua sottosuccessione ha limite .
  • Se e convergono allo stesso limite , allora converge a (questa teorema e il precedente sono detti teoremi delle restrizioni per le successioni).
  • Ogni successione limitata a valori in ammette almeno una sottosuccessione convergente (dal teorema di Bolzano-Weierstrass).
  • Ogni successione a valori in uno spazio metrico compatto ha una sottosuccessione convergente.
  • Se , e sono di Cauchy, allora è una successione di Cauchy.
  • Se una successione di Cauchy possiede una sottosuccessione convergente, allora converge l'intera successione.

Esempi[modifica | modifica wikitesto]

  • Siano:
Allora:
Si nota che la successione originaria non è convergente (oscilla), mentre la sottosuccessione converge, e in questo caso è anche costante.
  • Siano e :
    • Se allora
    • Se allora
    • Se allora
    • Se allora
  • Si consideri:
Si tratta di una sottosequenza di:
con la corrispondente sequenza di indici <3, 7, 9, 11>.
  • Date due sequenze e , una sequenza è una sottosequenza comune a e a se è una sottosequenza sia di che di . Per esempio, se:
e:
allora una sottosequenza comune a e a potrebbe essere:
Questa però non è la massima sottosequenza comune, dato che ha lunghezza 3, e la sottosequenza comune ha lunghezza 4. La massima sottosequenza comune a e a è .
  • 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 wikitesto]

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

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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