Fondamenti di informatica - Laurea triennale Informatica/Sequenze e Stringhe

Sequenze

Una sequenza è una funzione il cui dominio è un sottoinsieme degli interi. Invece della normale notazione funzionale, si usa spesso la notazione s_n​, dove n è l’indice della sequenza. Una sequenza può essere finita se il dominio contiene un numero finito di interi, oppure infinita se continua senza limite.

Le sequenze possono essere rappresentate usando formule generali, per esempio una regola che permette di calcolare il termine n-esimo. Esistono anche sequenze non numeriche, come quella formata dalle lettere di una parola. Si sottolinea che il nome dell’indice può essere scelto liberamente, purché sia chiaro il suo ruolo.

Una sequenza è crescente se, aumentando l’indice, aumentano anche i valori; è decrescente se i valori diminuiscono. Le sequenze non decrescenti e non crescenti permettono invece anche l’uguaglianza tra termini successivi.

La sottosequenza è una sequenza ottenuta scegliendo alcuni termini di una sequenza originale, mantenendo però lo stesso ordine. Per esempio, scegliendo il quinto ed il sesto termine di una sequenza si ottiene una sottosequenza. Se l’ordine viene cambiato, non si parla più di sottosequenza.

La notazione di somma è ottenuta sommando gli elementi di una sequenza, mentre la notazione di prodotto si ottiene moltiplicandoli fra loro. La notazione sigma ∑ serve a indicare in modo compatto la somma di più termini di una sequenza, mentre la notazione prodotto ∏ indica il prodotto di più termini. E' possibile in questa notazione cambiare i limiti superiori ed inferiori della sequenza da considerare.

Stringa

Una stringa è definita come una sequenza finita di caratteri o, più in generale, di elementi appartenenti a un insieme finito. Le stringhe sono molto importanti in informatica perché rappresentano testi, dati e istruzioni. Per esempio, una stringa binaria è composta solo da 0 e 1.

La stringa nulla, indicata con λ, non contiene elementi; la lunghezza di una stringa è numero dei suoi elementi mentre concatenazione è l'operazione e che unisce due stringhe mettendole una dopo l’altra.

La sottostringa è una porzione consecutiva di una stringa. A differenza della sottosequenza, nella sottostringa gli elementi scelti devono essere consecutivi.

Quanto visto con le funzioni nel capitolo precedente si può applicare anche a sequenze e stringhe:

L'inversione delle stringhe è una funzione biettiva in quanto da uno specifico input si ottiene solo un output (iniettiva) e non esistono elementi dell'output non collegati ad un input (suriettiva).

La concatenazione di stringhe è invece solo suriettiva in quanto tutti gli elementi dell'input si ritrovano nell'output, ma rende impossibile capire dove sono i limiti delle due stringhe originali (per tale ragione questa funzione non è biettiva/iniettiva)