Gilles Didier – Complexité moyenne d’algorithmes de pattern matching et optimalité Carte non disponible Date/heure Date(s) - 13 janvier 2016 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 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\geq |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, \ldots, n\$ vers $\alp$ telles que, pour tout $i<|w|$, si $f(i)$ est défini alors $f(i) = w_i$.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.[
Gilles DIDIER – Complexité moyenne d’algorithmes de pattern matching et optimalité Carte non disponible Date/heure Date(s) - 13 janvier 2016 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 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\geq |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, \ldots, n\$ vers $\alp$ telles que, pour tout $i<|w|$, si $f(i)$ est défini alors $f(i) = w_i$.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.[
