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

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

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

Proprietà modifica

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

  • 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

  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

Collegamenti esterni modifica

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