BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:7785@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20160617T110000
DTEND;TZID=Europe/Paris:20160617T120000
DTSTAMP:20241120T204830Z
URL:https://www.i2m.univ-amu.fr/evenements/complexite-moyenne-dalgorithmes
 -de-pattern-matching-et-optimalite-gilles-didier-2-3/
SUMMARY:Gilles Didier (I2M\, CNRS\, Marseille): Complexité moyenne d’alg
 orithmes de pattern matching et optimalité - Gilles Didier
DESCRIPTION:Gilles Didier: Nous étudions la vitesse asymptotique d’algor
 ithmes de pattern matching cherchant un motif w dans un texte aléatoire i
 id. La vitesse asymptotique est définie comme la limite\, quand n tend ve
 rs 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éato
 ire de taille n. L’étude est limitée aux algorithmes qui\, à chaque i
 tération et à partir de la position courante\, lisent une position relat
 ive déterminée par leur état interne et\, selon la lettre lue\, changen
 t 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’u
 n algorithme est la plus grande position\, relativement à la position cou
 rante\, qu’il lit en cherchant w (généralement |w|-1 ou |w| pour les a
 lgorithmes usuels\, où |w| désigne la longueur du motif w). On montre qu
 e si un texte est iid alors la séquence des états internes d’un algori
 thme est une chaîne de Markov dont on sait expliciter les probabilités d
 e transition\, ce qui permet d’en calculer la vitesse asymptotique.\nOn 
 montre ensuite\, qu’étant donnés un motif w\, un entier k&gt\;=|w|-1 e
 t un modèle iid\, il existe\, parmi les algorithmes d’ordre k\, un algo
 rithme de vitesse asymptotique maximale dont l’ensemble des états inter
 nes est en bijection avec un sous-ensemble des fonctions partielles f de {
 0\, ...\, k} vers l'alphabet qui sont telles que\, pour tout i&lt\;|w|\, s
 i f(i) est défini alors f(i) = w_i (i.e. la ième lettre de w).\nLe nombr
 e d’algorithmes vérifiant cette propriété étant fini\, il est possib
 le 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ém
 entée et appliquée à des textes réels (anglais et ADN).\n\n\n
ATTACH;FMTTYPE=image/jpeg:https://www.i2m.univ-amu.fr/wp-content/uploads/2
 020/01/Gilles_Didier.jpg
CATEGORIES:Séminaire,Probabilités
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20160327T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR