Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Teoria e ricerca di patterns in biosequenze

L'anteprima di questa tesi è scaricabile in PDF gratuitamente.
Per scaricare il file PDF è necessario essere iscritto a Tesionline.
L'iscrizione non comporta alcun costo. Mostra/Nascondi contenuto.

10 Algoritmo di Rabin-Karp In questo algoritmo il testo (che è la stringa di input) T viene precedentemente codificato in cifre in base d dove d=|Σ| e Σ è l’alfabeto dei caratteri del testo. Assumiamo inizialmente d=10 e vediamo poi come estendere l’algoritmo a d generico. Indichiamo con p il valore decimale della stringa P e con t s il valore decimale di T[s+1,…,s+m]. E’ chiaro che s è uno spostamento valido se e solo se t s =p. Mostriamo che tutte le sottostringhe di T di lunghezza m (cioè tutti i t s ) possono essere calcolate in tempo O(m); è ovvio che t 0 si calcola in tempo O(m), ma per i successivi t i si procede ricorsivamente usando la formula: t s+1 = 10(t s -10 m-1 T[s+1])+T[s+m+1] infatti la cifra t i+1 si calcola da t i rimuovendo la prima cifra con 10 m-1 T[i+1] (detta cifra maggiormente significativa) e aggiungendo la nuova cifra a destra con T[i+m+1] (detta cifra meno significativa). Ogni t i viene determinato in tempo costante, quindi il calcolo di tutti i restanti n-m t i costa O(n-m). Il costo totale dei t i è dunque O(n). Per p il discorso è analogo, lo si calcola da P con la regola di Horner: p =P[m]+10(P[m-1]+10(P[m-2]+…+10(P[2]+10P[1])…)) e quindi viene calcolato in un tempo O(m). Complessivamente la costruzione di p e degli t i è O(n+m). Una volta ottenute queste stringhe si eseguono i confronti di p con ciascuno dei t i ∀ i=0,…n-m, confronti che non vengono fatti cifra a cifra, ma che vengono fatti considerando il valore decimale di p e t i . Il costo totale della procedure è allora O(n+m), ma quando p e t i sono molto grandi sorgono dei problemi causati da cifre che potrebbero non essere conformi alla parola della macchina. In tali situazioni si assumono i numeri modulo q con q in modo tale che 10q sia rappresentabile dentro una parola della macchina. Possiamo allora generalizzare al caso non decimale assumendo un alfabeto {0,1,…d-1} e scegliendo q in modo tale che dq sia rappresentabile in una parola della macchina.

Anteprima della Tesi di Desir Franchin

Anteprima della tesi: Teoria e ricerca di patterns in biosequenze, Pagina 7

Tesi di Laurea

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Desir Franchin Contatta »

Composta da 92 pagine.

 

Questa tesi ha raggiunto 1018 click dal 27/04/2004.

 

Consultata integralmente una volta.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.