6
Elenco delle figure
1.1 Diagramma di transizione di un automa finito ……….…….… 18
1.2 Funzione di transizione dell’automa in fig. 1.1 ………. 19
2.1 Algoritmo che genera una stringa casuale appartenente all’insieme Ln(M) ………..34
2.2 Esempi di automi ………37
2.3 Confronto della dimensione di L(M2) e L(M1) usando due diverse misure ……….38
2.4 Esempi di automi ………41
3.1 Esempio di RE-TREE ………..48
3.2 Algoritmo per la ricerca nel RE-TREE ………...49
3.3 Algoritmo che propaga gli aggiornamenti durante una inserzione nel RE-TREE ………51
3.4 Algoritmo che esegue la suddivisione di un insieme di automi ………..55
7
3.6 Classificazione dei segmenti rispetto a xmid ………58
3.7 Posizionamento di qx rispetto a xmid ……….…...59
3.8 Esempio di Interval Tree ……….60
3.9 Algoritmo per la costruzione di un Interval Tree ………...61
3.10 Algoritmo per la ricerca di un query point qx ………62
4.1 Classificazione degli intervalli rispetto a xmid ………68
4.2 Posizionamento di qx rispetto a xmid ………68
4.3 Algoritmo per la ricerca di intervalli che contengono qx ………...70
4.4 Automa che accetta il linguaggio definito da r = (a | b)(c) ………75
4.5 Automa che accetta il linguaggio definito da r = (a)*(c) ………...78
5.1 Algoritmo per determinare la stringa massima e minima di L(r) ……...97
6.1 Algoritmo per la ricerca di sottosequenze di aminoacidi ……….113
6.2 Numero totale di intervalli ottenuti al variare di k ………...115
6.3 Valori del rapporto (2) relativi a Qsuccesso al variare di k …………116
6.4 Valori del rapporto (3) relativi a Qfallimento al variare di k ………..117
6.5 Valori del rapporto (2) relativi a Qsuccesso al variare di Dnum ……...119
6.6 Valori del rapporto (3) relativi a Qfallimento al variare di Dnum …….119
6.7 Valori del numero medio di intervalli in cui la query string in ingresso è contenuta, calcolati al variare del numero delle occorrenze ……….120
6.8 Valori del numero medio di intervalli (espresso in %) in cui la query string in ingresso è contenuta, calcolati al variare del numero delle occorrenze ……….121
