Complexité moyenne d’algorithmes de pattern matching et optimalité

Carte non disponible

Date/heure
Date(s) - 17/06/2016
11 h 00 min - 12 h 00 min

Catégories Pas de Catégories


Nous étudions la vitesse asymptotique d’algorithmes de pattern matching cherchant un motif w dans un texte aléatoire iid. La vitesse asymptotique est définie comme la limite, quand n tend vers l’infini, de l’espérance du rapport de n par le nombre d’accès en lecture effectués pour chercher un motif donné dans un texte aléatoire de taille n. L’étude est limitée aux algorithmes qui, à chaque itération et à partir de la position courante, lisent une position relative déterminée par leur état interne et, selon la lettre lue, changent d’état interne, incrémentent (ou pas) la position courante et, le cas échéant, signalent un match (tous les algorithmes usuels peuvent être “codés” sous cette forme). Étant donné un motif w, l’ordre d’un algorithme est la plus grande position, relativement à la position courante, qu’il lit en cherchant w (généralement |w|-1 ou |w| pour les algorithmes usuels, où |w| désigne la longueur du motif w). On montre que si un texte est iid alors la séquence des états internes d’un algorithme est une chaîne de Markov dont on sait expliciter les probabilités de transition, ce qui permet d’en calculer la vitesse asymptotique.
On montre ensuite, qu’étant donnés un motif w, un entier k>=|w|-1 et un modèle iid, il existe, parmi les algorithmes d’ordre k, un algorithme de vitesse asymptotique maximale dont l’ensemble des états internes est en bijection avec un sous-ensemble des fonctions partielles f de {0, …, k} vers l’alphabet qui sont telles que, pour tout i<|w|, si f(i) est défini alors f(i) = w_i (i.e. la ième lettre de w).
Le nombre d’algorithmes vérifiant cette propriété étant fini, il est possible de tous les évaluer et de déterminer ainsi un algorithme optimal pour un motif, un ordre et un modèle iid donnés. L’approche a été implémentée et appliquée à des textes réels (anglais et ADN).

Webpage“>Webpage

Olivier CHABROL
Posts created 14

Complexité moyenne d’algorithmes de pattern matching et optimalité

Carte non disponible

Date/heure
Date(s) - 24/05/2016
11 h 00 min - 12 h 00 min

Catégories


Nous étudions la vitesse asymptotique d’algorithmes de pattern matching cherchant un motif w dans un texte aléatoire Bernoulli. La vitesse asymptotique est définie comme la limite, quand n tend vers l’infini, de l’espérance du rapport de n par le nombre d’accès en lecture effectués pour un texte aléatoire de taille n. L’étude est limitée aux algorithmes qui, à chaque itération et à partir de la position courante, lisent une position relative déterminée par leur état interne et, selon la lettre lue, changent d’état interne, incrémentent (ou pas) la position courante et, le cas échéant, signalent un match (a priori tous les algorithmes usuels peuvent être codés sous cette forme). Étant donné w, l’ordre d’un algorithme est la plus grande position, relativement à la position courante, qu’il lit en cherchant w (généralement |w|-1 ou |w|). Nous montrons que si un texte est Bernoulli alors la séquence des états internes d’un algorithme est une chaîne de Markov à états cachés dont on sait expliciter les probabilités de transition, ce qui permet d’en calculer la vitesse asymptotique.
Notre résultat principal est, qu’étant donnés un motif w, un entier k≤|w|-1 et un modèle Bernoulli, il existe, parmi les algorithmes d’ordre k, un algorithme de vitesse asymptotique maximale dont l’ensemble des états internes est en bijection avec un sous-ensemble des fonctions partielles f de {0, …, n} vers l’alphabet telles que, pour tout i<|w|, si f(i) est défini alors f(i) = wᵢ.
Le nombre d’algorithmes vérifiant cette propriété étant fini, il est possible de tous les évaluer et de déterminer ainsi un algorithme optimal pour un motif, un ordre et un modèle Bernoulli donnés.

Webpage“>Webpage

Olivier CHABROL
Posts created 14

Articles similaires

Commencez à saisir votre recherche ci-dessus et pressez Entrée pour rechercher. ESC pour annuler.

Retour en haut
Secured By miniOrange