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:7804@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20160524T110000
DTEND;TZID=Europe/Paris:20160524T120000
DTSTAMP:20241120T204836Z
URL:https://www.i2m.univ-amu.fr/evenements/complexite-moyenne-dalgorithmes
 -de-pattern-matching-et-optimalite-gilles-didier/
SUMMARY:Gilles Didier (I2M\, CNRS\, Marseille): Complexité moyenne d’alg
 orithmes de pattern matching et optimalité
DESCRIPTION:Gilles Didier: Nous étudions la vitesse asymptotique d’algor
 ithmes de pattern matching cherchant un motif w dans un texte aléatoire B
 ernoulli. La vitesse asymptotique est définie comme la limite\, quand n t
 end 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’ét
 ude est limitée aux algorithmes qui\, à chaque itération et à partir d
 e la position courante\, lisent une position relative déterminée par leu
 r état interne et\, selon la lettre lue\, changent d’état interne\, in
 crémentent (ou pas) la position courante et\, le cas échéant\, signalen
 t 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 g
 rande position\, relativement à la position courante\, qu’il lit en che
 rchant 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 probabili
 tés de transition\, ce qui permet d’en calculer la vitesse asymptotique
 .\nNotre résultat principal est\, qu’étant donnés un motif w\, un ent
 ier k≤|w|-1 et un modèle Bernoulli\, il existe\, parmi les algorithmes 
 d’ordre k\, un algorithme de vitesse asymptotique maximale dont l’ense
 mble des états internes est en bijection avec un sous-ensemble des foncti
 ons partielles f de{0\, …\, n}vers l'alphabet telles que\, pour tout i&l
 t\;|w|\, si f(i) est défini alors f(i) = wᵢ.\nLe 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 or
 dre et un modèle Bernoulli donnés.\nAverage complexity of pattern matchi
 ng algorithms and optimality \nWe study the asymptotic speed of pattern ma
 tching algorithms looking for a pattern w in a Bernoulli random text. The 
 asymptotic speed is defined as the limit\, as n approaches infinity\, of t
 he expectation of the ratio of n by the number of read accesses made for a
  random text of size n. The study is limited to algorithms which\, at each
  iteration and from the current position\, read a relative position determ
 ined by their internal state and\, depending on the letter read\, change i
 nternal state\, increment (or not) the current position. and\, where appro
 priate\, signal a match (a priori all the usual algorithms can be coded in
  this form). Given w\, the order of an algorithm is the largest position\,
  relative to the current position\, that it reads while searching for w (u
 sually |w|-1 or |w|). We show that if a text is Bernoulli then the sequenc
 e of internal states of an algorithm is a Markov chain with hidden states 
 whose transition probabilities we know how to make explicit\, which makes 
 it possible to calculate its asymptotic speed.\nOur main result is\, that 
 given a pattern w\, an integer k≤ | w | -1 and a Bernoulli model\, there
  exists\, among the algorithms of order k\, a maximal asymptotic speed alg
 orithm whose set of states internal is in bijection with a subset of the p
 artial functions f from {0\,…\, n} to the alphabet such that\, for all i
 &lt\;|w|\, if f(i) is defined then f (i) = wᵢ .\nThe number of algorithm
 s verifying this property being finite\, it is possible to evaluate them a
 ll and thus to determine an optimal algorithm for a given pattern\, order 
 and Bernoulli model.\nhttps://arxiv.org/abs/1604.08437\n\n&nbsp\;
ATTACH;FMTTYPE=image/jpeg:https://www.i2m.univ-amu.fr/wp-content/uploads/2
 020/01/Gilles_Didier.jpg
CATEGORIES:Séminaire,Ernest
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